buddy allocator workshop
1.0.0
Repositori ini berisi beberapa contoh kecil implementasi alokasi Buddy. Mereka dirancang untuk mengalokasikan memori fisik, meskipun dapat digunakan untuk jenis alokasi lain, seperti tumpukan. Akhirnya, yang terbaik akan digabungkan menjadi bunga.
Pertama, klon repo. Kemudian, cd ke dalamnya dan lakukan cargo +nightly run untuk menjalankan semua pengalokasi demo. Secara default, ukuran blok adalah 4kib dan jumlah blok adalah 100.000, jadi ini mungkin perlu beberapa saat untuk contoh daftar tertaut. Jangan khawatir, itu tidak akan benar -benar mengalokasikan apa pun - hanya blok memori tiruan. Lulus -h atau --help untuk mendapatkan bantuan dan melihat penggunaannya. Anda dapat mengedit kode sumber untuk mengubah ukuran blok min/max, dll. Untuk menjalankan tes unit, menjalankan cargo test . Sayangnya belum ada tolok ukur kargo, tetapi saya telah membandingkannya dengan agak tidak ilmiah pada mesin windows saya.
Saya menguji algoritma dengan mengatur waktu berbagai implementasi menggunakan pelaporan builtin, mengalokasikan gibibyte dalam blok 4Kib (dengan pencetakan) pada mesin windows saya. Jika Anda memiliki tolok ukur lain untuk ditambahkan, silakan lihat berkontribusi.
(MSI CX61-2QF)
| Pelaksanaan | Waktu | Throughput |
|---|---|---|
| Daftar - Vektor | 2 menit | ~ 8.33E-3 GIB/s |
| Daftar - Daftar Tertaut Ganda | 25 menit | ~ 6.66E-4 GIB/s |
| Pohon RB - Vektor | ~ 0,3S | ~ 3.33 Gib/s |
| Pohon RB - Daftar Tertaut Singly | ~ 0,5S | ~ 2 gib/s |
| Pohon bitmap | ~ 0,07 | ~ 14.28 Gib/s |
Catatan: Throughput diekstrapolasi dari waktu yang dibutuhkan untuk mengalokasikan 1 GIB di blok 4KIB. Untuk implementasi yang memiliki kompleksitas> o (log n) (seperti implementasi berbasis daftar naif), ini tidak akan akurat - throughput akan melambat karena lebih banyak blok dialokasikan. Ini harus akurat untuk orang -orang yang memiliki kompleksitas O (log n) atau kurang.
Implementasi ini menyimpan daftar per urutan blok. Ini generik di atas jenis daftar yang digunakan. Saya memutuskan untuk menggunakan dua jenis daftar: vektor ( Vec dari std ), dan daftar ditautkan ganda ( LinkedList , juga dari std ). Daftar terkait sering dihargai karena waktu push yang dapat diprediksi (tidak ada realokasi yang diperlukan untuk mendorong), sementara vektor memiliki lokalitas cache yang lebih baik karena elemen dialokasikan dalam blok memori yang berdekatan. Saya menggunakan daftar yang terhubung ganda karena lebih cepat untuk pengindeksan daripada daftar yang terhubung secara tunggal, karena mereka dapat mengulangi dari belakang atau depan tergantung pada apakah indeks lebih dekat ke awal atau akhir daftar. Saya memutuskan untuk menguji keduanya untuk melihat mana yang akan berkinerja lebih baik secara keseluruhan.
Implementasinya rekursif. Untuk mengalokasikan blok pesanan K gratis, pertama -tama mencari blok gratis dalam daftar blok pesanan K. Itu tidak menyimpan daftar gratis. Jika tidak ada yang ditemukan, ia berulang dengan mencoba mengalokasikan blok pesanan K + 1. Akhirnya, jika tidak ada blok gratis yang ditemukannya menyerah dan panik. Segera setelah satu itu membagi menjadi dua, menghapus blok asli dari daftar pesanannya dan mendorong bagian ke daftar pesanan segera lebih rendah. Kemudian mengembalikan pesanan dan indeks blok pertama dalam daftar pesanannya. Anda dapat menemukan algoritma ini di find_or_split .
Tolok ukur cepat, tidak ilmiah pada mesin Windows saya mengatakan bahwa butuh sekitar dua menit untuk mengalokasikan gibibyte penuh (1024^3 byte). Saya memang melihat split detik berhenti sesekali ketika harus merealokasi seluruh vektor untuk mendorong suatu elemen.
stdBenchmark serupa mengatakan bahwa butuh dua puluh lima menit untuk mengalokasikan gibibyte penuh. Ini lebih dari dua belas kali lebih lambat dari implementasi yang sama dengan vektor. Namun, implementasi ini tidak dioptimalkan untuk daftar yang ditautkan, sehingga sedikit tidak adil. Berbeda dengan implementasi dengan vektor, saya tidak melihat ada jeda, tetapi alokasi secara bertahap menjadi lebih lambat dan lebih lambat.
Kita dapat menyimpulkan bahwa meskipun daftar yang terhubung ganda secara teori lebih cepat dalam mendorong daripada vektor, mereka masih 12 kali lebih lambat dari vektor. Ini bisa jadi karena implementasinya sedikit mendukung vektor (banyak pengindeksan), atau karena vektor memiliki lokalitas cache yang lebih tinggi dan oleh karena itu mengalami lebih sedikit kesalahan cache, sementara daftar tertaut mengalami gangguan cache tinggi karena mereka memiliki elemen yang dialokasikan secara individual.
Implementasi ini menyimpan satu pohon merah-hitam (dari intrusive_collections ) untuk semua blok dan daftar gratis untuk setiap pesanan. Daftar gratis diimplementasikan untuk SinglyLinkedList Vec dan intrusive_collections . Saya memilih daftar yang terhubung secara tunggal karena tidak akan ada manfaat nyata untuk menghubungkan ganda - satu -satunya metode yang akan diuntungkan (dapat diabaikan begitu) adalah FreeList::remove , tetapi ini selalu disebut paling banyak pada elemen kedua dalam daftar bebas ini, jadi tidak ada poin nyata dalam mengoptimalkan ini. Pohon merah-hitam secara individual menumpuk mengalokasikan setiap node, yang membuat efisiensi cache lebih buruk, tetapi tidak seperti BTreeSet / BTreeMap std pencariannya adalah O(log n) , sementara std menggunakan pencarian linier, yang bukan O(log n) (Anda dapat membaca tentang ini di sini). Namun, pohon std tidak secara individual menumpuk node, jadi cache lokalitas lebih baik. Saya memutuskan bahwa meskipun ini benar, karena alokasi teman harus berurusan dengan sejumlah besar blok, lebih penting untuk memiliki algoritma pencarian yang lebih efisien.
Implementasinya rekursif. Untuk mengalokasikan blok pesanan K gratis, pertama -tama mencari blok gratis dalam daftar gratis daftar blok K orde. Jika tidak ada yang ditemukan, ia berulang dengan mencoba mengalokasikan blok pesanan K + 1. Akhirnya, jika tidak ada blok gratis yang ditemukannya menyerah dan panik. Segera setelah satu itu membagi menjadi dua, menghapus blok asli dari pohon dan memasukkan bagian, mendorong alamat mereka ke daftar gratis yang relevan. Kemudian mengembalikan kursor yang menunjuk ke blok pertama. Anda dapat menemukan algoritma ini di find_or_split . Pada lapisan luar rekursi (fungsi yang benar -benar menyebut fungsi find_or_split rekursif), blok yang dikembalikan ditandai seperti yang digunakan dan dihapus dari daftar bebas.
Menggunakan vektor sebagai daftar gratis memakan waktu ~ 0,3 untuk mengalokasikan Gib penuh. Ini ~ 0,2 lebih cepat dari daftar yang ditautkan sebagai versi daftar gratis. Ini mungkin karena vektor memiliki lokalitas cache yang lebih baik.
Menggunakan daftar tertaut sebagai daftar gratis memakan waktu ~ 0,5 untuk mengalokasikan GIB penuh. Lihat bagian vektor sebagai daftar gratis di atas.
Implementasi ini 400x lebih cepat daripada implementasi berbasis daftar naif (paling tidak, menggunakan vektor sebagai daftar gratis). Ini mungkin karena pohon merah-hitam yang memiliki operasi O(log n) di seluruh papan, lebih cepat dari pencarian, sisipan, dan penghapusan vektor atau daftar tertaut.
Implementasi ini tidak sepenuhnya bitmap, per se, tetapi merupakan modifikasi dari sistem bitmap. Pada dasarnya, setiap blok di pohon menyimpan urutan terbesar (sepenuhnya digabungkan) di suatu tempat di bawahnya. Misalnya, pohon yang semuanya gratis dengan 4 pesanan terlihat seperti ini:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
Jika kita mengalokasikan satu blok 0 pesanan, sepertinya ini (t adalah t aken):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
Itu diimplementasikan sebagai array yang rata, di mana untuk pohon seperti
1
2 3
Representasinya adalah 1; 2; 3 . Ini memiliki properti bagus yang jika kita menggunakan indeks yang dimulai pada 1 (yaitu indeks dan bukan offset), maka indeks anak kiri dari indeks yang diberikan adalah 2 * index , dan anak yang tepat hanya 2 * index + 1 . Induknya adalah floor(index / 2) . Karena semua operasi ini berfungsi dengan 2S, kita dapat menggunakan bitshifting yang efisien untuk menjalankannya ( index << 1 , (index << 1) | 1 , dan index >> 1 ).
Kita dapat melakukan pencarian biner untuk menemukan blok A yang bebas dari urutan yang diinginkan. Pertama, kami memeriksa apakah ada blok dari pesanan yang diinginkan gratis dengan memeriksa blok root. Jika ada, kami memeriksa apakah anak kiri memiliki cukup gratis. Jika ya, maka kami lagi memeriksa anak itu, dll. Jika anak kiri blok tidak memiliki cukup blok gratis, kami hanya menggunakan anak yang tepat. Kita tahu bahwa anak yang tepat harus memiliki cukup gratis, atau blok root tidak valid.
Implementasi ini sangat cepat. Di komputer saya, hanya butuh ~ 0,07 untuk mengalokasikan 1Gib. Saya telah melihatnya melakukan hingga 0,04 di komputer saya, meskipun - kinerja memang sedikit berfluktuasi. Saya berasumsi bahwa ini berkaitan dengan beban CPU.
Implementasi ini tidak memiliki lokalitas cache yang sangat baik, karena level disimpan jauh dari satu sama lain, sehingga blok induk bisa sangat jauh dari anaknya. Namun, yang lainnya masih sangat cepat, jadi dibuat untuk. Ini juga o (log n), tetapi praktis sangat cepat sehingga ini tidak terlalu penting. Untuk referensi: Mengalokasikan 8Gib membutuhkan 0,6 untuk saya, tetapi saya telah melihatnya berkinerja lebih baik di> 150ms di laptop @Gegy1000.
Jika Anda memiliki sesuatu untuk ditambahkan (seperti edit ke readme atau implementasi atau tolok ukur lainnya) jangan ragu untuk mengirimkan permintaan tarik! Anda juga dapat membuat masalah. Jika Anda hanya ingin mengobrol, jangan ragu untuk melakukan ping saya di Rust Perselisihan (restioson#8323).
