Setiap programmer akan mendapat manfaat dari pemahaman tentang berbagai
struktur data dan cara menganalisis kinerjanya. Namun dalam praktiknya, saya tidak pernah berguna untuk
pohon AVL ,
pohon merah-hitam ,
pohon awalan ,
lewati daftar , dll. Saya menggunakan beberapa struktur data hanya untuk satu algoritma spesifik dan tidak lebih (misalnya,
tumpukan untuk mengimplementasikan
antrian prioritas dalam
algoritma pencarian jalur A * ).
Dalam pekerjaan sehari-hari, saya biasanya melakukan dengan struktur data yang sangat sedikit. Paling sering, mereka berguna bagi saya:
- Array data bersama (Data massal) - cara untuk secara efektif menyimpan sejumlah besar objek.
- Referensi yang lemah (atau pegangan ) - cara untuk mengakses objek dalam data massal tanpa crash program jika objek dihapus.
- Indeks adalah cara untuk dengan cepat mengakses subset individu dalam data massal.
- Array array adalah cara menyimpan objek data massal dengan ukuran dinamis.
Saya akan mencurahkan beberapa artikel untuk bagaimana saya biasanya menerapkan semua struktur ini. Mari kita mulai dengan data massal yang paling sederhana dan paling berguna.
Data massal
Tidak ada istilah umum untuk konsep ini (atau saya tidak tahu tentang itu). Saya menyebut "
data massal " kumpulan besar benda-benda serupa. Misalnya, bisa jadi:
- Semua peluru di dalam game.
- Semua pohon dalam game.
- Semua koin dalam game.
Atau, jika Anda menulis kode pada level abstraksi yang lebih tinggi, bisa jadi:
- Semua entitas dalam game.
- Semua jerat dalam game.
- Semua suara dalam game.
Biasanya, setiap sistem (render, suara, animasi, fisika, dll.) Dalam permainan memiliki beberapa jenis objek yang perlu dilacak. Misalnya, untuk sistem suara, dapat berupa:
- Semua sumber suara yang bisa dimainkan.
- Semua suara sedang diputar.
- Semua efek (redaman, perubahan nada, dll.) Diterapkan pada suara.
Dalam hal data massal, saya akan menganggap sebagai berikut:
Tentu saja, Anda dapat menemukan situasi di mana urutan itu
penting . Misalnya, jika objek menunjukkan elemen untuk rendering, maka sebelum rendering kita mungkin perlu mengurutkannya dari depan ke belakang untuk mengurangi jumlah gambar
ulang .
Namun, saya percaya bahwa dalam kebanyakan kasus, lebih baik menyortir data dengan
cara yang digunakan , daripada menyimpan data dalam wadah yang disortir, seperti
pohon merah-hitam atau
pohon-B . Misalnya, kita bisa mengurutkan objek yang dirender dari depan ke belakang sebelum meneruskannya ke renderer, atau mengurutkan file secara alfabet sebelum menampilkannya di layar sebagai daftar. Menyortir data dalam setiap frame mungkin tampak mahal, tetapi dalam banyak kasus itu dilakukan dalam
O (n) menggunakan
radix sort .
Karena saya hanya menggunakan struktur data sederhana, saya lebih suka objek C ++ daripada objek C ++, karena lebih mudah untuk memahami apa yang terjadi dalam memori dan mengevaluasi kinerjanya. Namun, ada beberapa situasi ketika Anda perlu menyimpan data dalam jumlah besar sesuatu yang tidak memiliki ukuran tetap. misalnya, nama atau daftar objek anak. Saya akan berbicara tentang kasus-kasus ini di pos terpisah, di mana kita melihat "array array". Untuk sekarang, mari kita asumsikan bahwa semua objek sederhana, struktur data ukuran tetap.
Misalnya, berikut ini struktur struktur data massal untuk sistem suara hipotetis kami:
typedef struct { resource_t *resource;
Saat mempertimbangkan cara untuk menyimpan data massal, kami perlu mempertimbangkan beberapa tujuan:
- Menambah dan menghapus objek harus cepat.
- Data harus ditempatkan dalam bentuk yang nyaman untuk caching , sehingga Anda dapat dengan cepat beralih di atasnya untuk memperbarui sistem.
- Ini harus mendukung mekanisme tautan - harus ada cara untuk mengirimkan informasi tentang objek tertentu dalam data massal. Pada contoh di atas, fade harus dapat menentukan suara mana yang dilemahkan. Dalam contoh, saya menulis tautan sebagai pointer, tetapi implementasinya tergantung pada bagaimana data massal diatur.
- Data harus ramah alokasi - harus menggunakan beberapa alokasi memori besar, dan tidak mengalokasikan objek individual di heap.
Dua cara termudah untuk merepresentasikan data massal adalah array statis atau vektor C ++:
Bekerja dengan sebuah array sangat sederhana, dan dapat bekerja dengan baik untuk Anda jika Anda tahu persis berapa banyak objek yang dibutuhkan dalam aplikasi. Jika Anda
tidak tahu ini , maka buang memori Anda atau Anda akan kehabisan objek.
Vektor
std::vector juga merupakan solusi yang sangat layak dan sederhana, tetapi di sini Anda perlu mempertimbangkan beberapa aspek:
- Implementasi standar
std::vector dari Visual Studio lambat dalam mode Debug karena debugging iterators. Itu harus ditetapkan ke _ITERATOR_DEBUG_LEVEL = 0 . - Untuk membuat dan menghancurkan objek,
std::vector menggunakan konstruktor dan destruktor, dan dalam beberapa kasus mereka bisa jauh lebih lambat daripada memcpy() . std::vector jauh lebih sulit diurai daripada mengimplementasikan "stretchy buffer" yang sederhana .
Selain itu, tanpa tindakan tambahan, baik array reguler maupun vektor tidak mendukung referensi ke objek individual. Mari kita lihat topik ini, serta keputusan desain penting lainnya yang terlibat dalam menciptakan sistem data massal.
Strategi penghapusan
Keputusan penting pertama: apa yang harus dilakukan ketika menghapus objek
a[i] . Berikut adalah tiga opsi utama:
- Anda dapat menggeser semua elemen berikutnya
a[i+1] → a[i] , a[i+2] → a[i+1] , dll., Untuk menutup slot kosong. - Anda dapat memindahkan elemen terakhir array ke slot kosong:
a[i] = a[n-1] . - Atau Anda dapat membiarkan slot kosong dengan membuat lubang di array. Lubang ini nantinya bisa digunakan untuk menempatkan objek baru.
Opsi pertama mengerikan -
O (n) dihabiskan untuk pergerakan semua elemen ini. Satu-satunya manfaat dari metode pertama adalah jika array diurutkan, maka urutan di dalamnya dipertahankan. Namun seperti yang disebutkan di atas, urutannya tidak mengganggu kita. Perhatikan bahwa jika Anda menggunakan
a.erase() untuk menghapus elemen
std::vector , inilah yang akan terjadi!
Opsi kedua sering disebut "swap-and-pop". Mengapa Karena jika Anda menggunakan vektor C ++, opsi ini biasanya diterapkan dengan menukar elemen yang ingin Anda hapus dengan yang terakhir, diikuti dengan menghapus atau membuka elemen terakhir:
std::swap(a[i], a[a.size() - 1]); a.pop_back();
Mengapa semua ini perlu? Dalam C ++, jika kita
menetapkan a[i] = a[n-1] , pertama-tama kita harus menghapus
a[i] dengan memanggil destruktornya, dan kemudian memanggil copy constructor untuk membuat salinan
a[n-1] pada posisi
i dan akhirnya, kita menyebut destructor
a[n-1] saat menggeser vektor. Jika konstruktor salin mengalokasikan memori dan menyalin data, maka ini bisa sangat buruk. Jika kita menggunakan
std::swap alih-alih penugasan, maka kita hanya dapat melakukannya dengan pemindahan konstruktor dan tidak seharusnya mengalokasikan memori.
Sekali lagi, itu sebabnya C ++ saya lebih suka struktur data sederhana dan operasi C. C ++ memiliki banyak jebakan kinerja yang dapat Anda jatuhkan jika Anda tidak tahu apa yang sedang terjadi di dalam. Dalam C, operasi swap-erase akan sangat sederhana:
a.data[i] = a.data[--an];
Saat menggunakan swap-and-pop, objek tetap padat. Untuk menempatkan objek baru, cukup lekatkan ke ujung array.
Jika kita menggunakan opsi “with hole” I, maka ketika menempatkan objek baru pertama-tama kita perlu memeriksa apakah ada “hole” gratis yang bisa digunakan. Layak meningkatkan ukuran array hanya ketika tidak ada "lubang" gratis. Kalau tidak, dalam proses menghapus dan membuat objek, itu akan tumbuh tanpa batas.
Anda dapat menggunakan
std::vector<uint32_t> untuk melacak posisi lubang, tetapi ada solusi yang lebih baik yang tidak memerlukan memori tambahan.
Karena data objek di "lubang" tidak digunakan untuk apa pun, Anda dapat menggunakannya untuk menyimpan pointer ke lubang bebas berikutnya. Dengan demikian, semua lubang dalam array membentuk
daftar yang terhubung sederhana , dan jika perlu, kita dapat menambah dan menghapus elemen dari daftar tersebut.
Jenis struktur data ini, di mana memori yang tidak digunakan digunakan untuk mengikat elemen-elemen bebas, biasanya disebut
daftar bebas .
Dalam daftar tertaut tradisional,
elemen header daftar khusus menunjuk ke simpul pertama dalam daftar, dan elemen daftar terakhir menunjuk ke NULL, yang berarti akhir daftar. Sebagai gantinya, saya lebih suka menggunakan
daftar tertaut melingkar , di mana tajuk hanya item daftar khusus, dan item daftar terakhir menunjuk ke elemen tajuk:
Daftar tradisional dan ditautkan cincin.Keuntungan dari pendekatan ini adalah bahwa kode menjadi lebih sederhana dengan mengurangi jumlah kasus khusus di awal dan akhir daftar.
Perhatikan bahwa jika Anda menggunakan
std::vector untuk menyimpan objek, maka pointer ke objek akan berubah dengan setiap redistribusi vektor. Ini berarti bahwa kita tidak dapat menggunakan pointer reguler ke daftar tertaut, karena pointer terus berubah. Untuk mengatasi masalah ini, Anda dapat menggunakan indeks sebagai "pointer" ke daftar tertaut, karena indeks terus-menerus menunjuk ke slot tertentu bahkan ketika mendistribusikan ulang array. Kami akan berbicara lebih banyak tentang realokasi di bagian selanjutnya.
Anda dapat mengalokasikan ruang untuk elemen khusus dari judul daftar dengan selalu menyimpannya dalam slot array 0.
Kode akan terlihat seperti ini:
Apa strategi penghapusan terbaik? Memindahkan elemen terakhir ke slot kosong, memastikan pengemasan array yang ketat atau menjaga semua elemen di tempatnya dengan penciptaan "lubang" di array di tempat elemen yang dihapus?
Saat membuat keputusan, dua aspek harus diperhitungkan:
- Iterasi lebih dari array padat lebih cepat karena kita memotong lebih sedikit memori dan kita tidak perlu menghabiskan terlalu banyak waktu melewatkan slot kosong.
- Jika kita menggunakan array yang sangat padat, elemen akan bergerak. Ini berarti bahwa kita tidak dapat menggunakan indeks suatu elemen sebagai pengidentifikasi konstan untuk referensi eksternal ke elemen. Kami harus menetapkan pengidentifikasi yang berbeda untuk setiap elemen dan menggunakan tabel pencarian untuk mencocokkan ID konstan ini dengan indeks objek saat ini. Tabel pencarian ini bisa berupa tabel hash atau
std::vector berlubang, seperti dijelaskan di atas (opsi kedua lebih cepat). Tapi bagaimanapun, kita akan membutuhkan memori tambahan untuk tabel ini dan langkah tambahan tidak langsung untuk pengidentifikasi.
Memilih opsi terbaik tergantung pada proyek Anda.
Anda dapat mengatakan bahwa menyimpan array yang padat lebih baik, karena iterasi atas semua elemen (untuk memperbarui sistem) terjadi lebih sering daripada mencocokkan tautan eksternal. Di sisi lain, kita dapat mengatakan bahwa kinerja "array dengan lubang" lebih buruk hanya dalam kasus sejumlah besar lubang, dan dalam pengembangan game kita biasanya peduli dengan kinerja dalam
kasus terburuk (kami ingin memiliki frame rate 60 Hz, bahkan ketika operasi maksimum dilakukan dalam permainan) . Dalam kasus terburuk, kami memiliki jumlah maksimum objek nyata, dan dalam hal ini
tidak akan ada lubang dalam array. Lubang terjadi hanya ketika jumlah objek berkurang, ketika kita menghapus beberapa objek ini.
Ada juga strategi yang dapat digunakan untuk mempercepat pemrosesan array dengan banyak lubang. Misalnya, kita dapat melacak panjang urutan lubang yang berkelanjutan untuk melewati seluruh urutan lubang pada suatu waktu, daripada elemen demi elemen. Karena data ini hanya diperlukan untuk "lubang", dan bukan untuk elemen biasa, Anda dapat menyimpannya bersama dengan penunjuk daftar rilis dalam memori objek yang tidak teralokasi dan tidak membuang memori tambahan.
Menurut pendapat saya, jika Anda tidak perlu mengoptimalkan kode untuk iterasi cepat, maka mungkin lebih baik menggunakan opsi "array with hole". Ini lebih sederhana, tidak memerlukan struktur pencarian tambahan, dan Anda dapat menggunakan indeks objek sebagai ID-nya, yang sangat nyaman. Selain itu, kurangnya objek bergerak menghilangkan kemungkinan bug.
Strategi penghapusan data massal.Pointer yang lemah
Sebagai catatan, saya akan mengatakan bahwa mudah untuk mengimplementasikan dukungan untuk "pointer lemah" atau "deskriptor" untuk objek data massal.
Pointer yang lemah adalah referensi ke objek yang dalam beberapa cara menentukan bahwa objek yang dirujuk telah dihapus. Nyaman dalam petunjuk lemah adalah bahwa mereka memungkinkan Anda untuk menghapus objek tanpa khawatir tentang siapa yang dapat mereferensikannya. Tanpa petunjuk lemah untuk menghapus suatu objek, kita perlu mencari setiap tautan individual dan menyatakannya tidak valid. Ini bisa sangat sulit jika tautan disimpan dalam kode skrip, di komputer lain di jaringan, dll.
Ingatlah bahwa kita sudah memiliki ID yang secara unik mengidentifikasi objek yang
ada . Dalam opsi "dengan lubang", ID ini hanyalah indeks elemen (karena elemen tidak pernah bergerak). Dalam kasus array padat, indeks objek ini adalah catatan dalam
array pencarian .
ID itu sendiri tidak dapat digunakan sebagai penunjuk yang lemah, karena ID dapat digunakan kembali. Jika sebuah elemen dihapus dan elemen baru dibuat di slot yang sama, maka kami tidak akan dapat mengetahuinya hanya dengan ID. Untuk mendapatkan pointer yang lemah, Anda harus menggabungkan ID dengan bidang
generation :
typedef struct { uint32_t id; uint32_t generation; } weak_pointer_t;
Bidang
generation adalah bidang dalam struct objek yang melacak berapa kali slot dalam array data massal telah digunakan kembali. (Dalam hal pengemasan ketat, ini melacak berapa kali slot telah digunakan kembali dalam array
pencarian .)
Saat Anda menghapus item, kami menambah nomor pembuatan di slotnya. Untuk memeriksa apakah penunjuk lemah masih valid, kami memeriksa apakah
generation dalam struct penunjuk lemah cocok dengan pembuatan slot yang ditunjukkan oleh
id . Jika cocok, maka objek sumber yang kami referensi masih ada. Jika tidak, itu berarti itu dihapus, dan slotnya ada di daftar rilis, atau telah digunakan kembali.
Perlu diingat bahwa karena bidang
generation diperlukan untuk lubang dan benda yang ada, Anda harus menyimpannya di luar serikat:
typedef struct { uint32_t generation; union { object_t; freelist_item_t; }; } item_t;
Strategi distribusi
Jika Anda menggunakan
std::vector untuk menyimpan data elemen, maka ketika array sudah penuh dan perlu ditingkatkan, seluruh array elemen akan didistribusikan kembali. Item yang ada disalin ke array baru.
std::vector tumbuh secara
geometris . Ini berarti bahwa setiap kali vektor perlu meningkat, jumlah elemen terdistribusi dikalikan dengan beberapa faktor (biasanya dengan × 2). Pertumbuhan geometris (eksponensial) penting karena menjaga biaya untuk meningkatkan konstanta array.
Saat mendistribusikan ulang array, kita perlu memindahkan semua elemen, yang membutuhkan
O (n) . Namun, ketika array bertambah, kami menambahkan ruang untuk elemen
n lainnya, karena kami menggandakan ukurannya. Ini berarti bahwa kita tidak perlu menambah array lagi sampai kita menambahkan
n lebih banyak elemen ke dalamnya. Artinya, kenaikan biaya sama dengan
O (n) , tetapi kami hanya mengeksekusi mereka * O (n) * untuk waktu ke-n penulisan ke array, yaitu, rata-rata, biaya penulisan satu elemen adalah
O (n) / O (n) = O (1) .
Biaya pencatatan suatu item disebut
konstanta diamortisasi , karena jika Anda rata-rata semua catatan yang sedang dieksekusi, biaya akan tetap. Namun, kita tidak boleh lupa bahwa sebelum kita rata-rata, biayanya menjadi sangat spasmodik. Setelah setiap
O (n) mencatat, kita mendapatkan puncak ketinggian
O (n) :
Biaya penulisan ke std::vector .Mari kita lihat apa yang terjadi jika kita tidak menggunakan pertumbuhan geometris. Misalkan, alih-alih menggandakan memori selama pertumbuhan, kami hanya akan menambahkan 128 slot. Memindahkan data lama masih membebani kita
O (n) , tetapi sekarang kita perlu melakukannya setiap 128 item yang kita tambahkan, yaitu, biaya rata-rata sekarang adalah
O (n) / O (128) = O (n) . Biaya penulisan elemen ke array sebanding dengan ukuran array, jadi ketika array menjadi besar, ia mulai bekerja dengan kecepatan kura-kura. Ups!
Strategi distribusi
std::vector adalah opsi standar yang baik, bekerja dengan baik dalam banyak kasus, tetapi memiliki beberapa masalah:
- Constant Amortized tidak cocok untuk perangkat lunak waktu nyata. Jika Anda memiliki array yang sangat besar, katakanlah, ratusan juta elemen, maka meningkatkan array ini dan memindahkan semua elemen dapat menyebabkan perlambatan yang terlihat dari frame rate. Ini bermasalah karena alasan yang sama pengumpulan sampah bermasalah dalam game. Tidak masalah seberapa rendah biaya rata-rata, jika dalam beberapa bingkai biaya dapat melonjak, menyebabkan gangguan permainan.
- Demikian pula, strategi alokasi ini dalam kasus array besar dapat menghabiskan banyak memori. Katakanlah kita memiliki array 16 juta elemen dan kita perlu menulis satu lagi ke dalamnya. Ini akan membuat array bertambah menjadi 32 juta. Sekarang kita memiliki 16 juta elemen dalam array yang tidak kita gunakan. Untuk platform dengan memori rendah, ini banyak.
- Akhirnya, realokasi memindahkan objek dalam memori, membatalkan semua pointer ke objek. Ini bisa menjadi sumber bug yang sulit dilacak.
Kode di bawah ini adalah contoh bug yang dapat terjadi ketika memindahkan objek:
Masalahnya di sini adalah bahwa
item_2 allocate_slot() mungkin perlu mendistribusikan kembali array untuk membuat ruang untuk
item_2 . Dalam hal ini,
item_1 akan dipindahkan ke memori dan penunjuk ke
item_1 akan berhenti berlaku. Dalam kasus khusus ini, kami dapat menghilangkan kesalahan dengan memindahkan
item_1 penugasan_1, tetapi bug serupa dapat muncul lebih jelas. Secara pribadi, mereka telah menggigit saya berkali-kali.
Situasi seperti itu berbahaya oleh fakta bahwa bug hanya akan keluar ketika array didistribusikan kembali tepat pada saat
slot_2 . Program dapat bekerja dengan benar untuk waktu yang lama sampai sesuatu mengubah pola distribusi, setelah itu bug akan bekerja.
Semua masalah ini dapat diselesaikan dengan menggunakan strategi distribusi yang berbeda. Berikut ini beberapa opsi:
- : 16, 32, 64, …, . , 16 , 32 , .… ,
std::vector . - , . , . . , O(n)
push() , . - , , , , .
, . , - , , . , , .
, — ? , . , 16 , 16 , . , , 50 %. .
,
, , . *16 K * n*,
n — bulk data , , ( ).
. -, ,
blocks\[i / elements_per_block\][i % elements_per_block] . -, , (heap allocator), .
, « », -
std::vector , , . , , .
, , ID . , , . , 64 , 32 (4 — ).
(Array of Structures, AoS)
(Structure of Arrays, SoA). . , , , , :
typedef struct { float t; vec3_t pos; vec3_t vel; vec3_t col; } particle_t;
struct . « ». :
uint32_t num_particles; particle_t *particles;
, .
(SoA) struct:
uint32_t num_particles; typedef struct { float *t; vec3_t *pos; vec3_t *vel; vec3_t *col; } particles;
, ,
vec3_t struct:
uint32_t num_particles; typedef struct { float *t; float *pos_x; float *pos_y; float *pos_z; float *vel_x; float *vel_y; float *vel_z; float *col_r; float *col_g; float *col_b; } particles;
, AoS, ? :
- . ,
tick() t . simulate_physics() pos vel . SoA struct. ( ), . , tick() 1/10 , , 10 . - SoA SIMD . , FPU . AVX float , 8 .
,
tick() 80 ? Tidak. 10 , , , SIMD .
SoA:
- .
- , .
particle_t * , . .- ,
- ( ), . , .
, , struct , VM ( ). - 10 struct . 8- -, , . !
— SIMD. :
uint32_t num_particles; typedef struct { float t[8]; float position_x[8]; float position_y[8]; float position_z[8]; float velocity_x[8]; float velocity_y[8]; float velocity_z[8]; float color_r[8]; float color_g[8]; float color_b[8]; } eight_particles_t; eight_particles_t *particles;
- SIMD- , -, . , .
tick() 32 , 288 , 32 .. , 10- ,
t . -, - 64 , , , 5 . , , -, 100% .
, . ,
[16] , float - . , , , :
AoS SoA., SoA — « », SIMD , ( «»).
SIMD- «» , , , «» . , ,
, .
next , SIMD- . struct.
, , , struct . , , .
AoS SoA, , . «» AoS SoA , SIMD-, , . .
— AoS SoA - . , AoS SoA, , AoS ( ). , , .
, « ». 16- , SoA, . scratch buffer 16 .
Kesimpulan
, « » bulk data :
«» , VM ( ), ( 16 , ).
, :
, 8 SIMD VM .
.