Apakah bermanfaat menggunakan kolam partikel dalam bahasa yang dikelola?

10

Saya akan mengimplementasikan kumpulan objek untuk sistem partikel saya di Jawa, kemudian saya menemukan ini di Wikipedia. Singkatnya, dikatakan bahwa kumpulan objek tidak layak digunakan dalam bahasa yang dikelola seperti Java dan C #, karena alokasi hanya membutuhkan puluhan operasi dibandingkan dengan ratusan dalam bahasa yang tidak dikelola seperti C ++.

Tapi seperti yang kita semua tahu, setiap instruksi dapat merusak kinerja game. Misalnya, kumpulan klien dalam MMO: klien tidak akan masuk dan keluar dari pool terlalu cepat. Tetapi partikel bisa diperbarui puluhan kali dalam sedetik.

Pertanyaannya adalah: apakah layak menggunakan kumpulan objek untuk partikel (khususnya, yang mati dan dibuat ulang dengan cepat) dalam bahasa yang dikelola?

Gustavo Maciel
sumber

Jawaban:

14

Ya itu.

Waktu alokasi bukan satu-satunya faktor. Alokasi dapat memiliki efek samping, seperti menginduksi izin pengumpulan sampah, yang tidak hanya berdampak negatif pada kinerja, tetapi juga berdampak pada kinerja yang tidak terduga. Spesifikasi ini akan tergantung pada pilihan bahasa dan platform Anda.

Pooling secara umum juga meningkatkan lokalitas referensi untuk objek di pool, misalnya dengan menjaga mereka semua dalam array yang berdekatan. Ini dapat meningkatkan kinerja sambil mengulangi isi kumpulan (atau setidaknya bagian langsungnya) karena objek berikutnya dalam iterasi akan cenderung sudah ada dalam cache data.

Kebijaksanaan konvensional untuk mencoba menghindari alokasi apa pun di loop permainan terdalam Anda masih berlaku bahkan dalam bahasa yang dikelola (terutama pada, misalnya, 360 ketika menggunakan XNA). Alasannya hanya berbeda sedikit.


sumber
+1 Tapi, Anda tidak menyentuh apakah itu berharga saat menggunakan struct: pada dasarnya itu bukan (mengumpulkan nilai jenis tidak mencapai apa-apa) - sebaliknya Anda harus memiliki satu (atau mungkin satu set) array untuk mengelolanya.
Jonathan Dickinson
2
Saya tidak menyentuh pada hal struct karena OP disebutkan menggunakan Java dan saya tidak begitu akrab dengan bagaimana tipe nilai / struktur beroperasi dalam bahasa itu.
Tidak ada struct di Jawa, hanya kelas (selalu ada di heap).
Brendan Long
1

Untuk Java tidak begitu membantu untuk menyatukan objek * karena siklus GC pertama untuk objek yang masih ada akan mengubah mereka dalam memori, memindahkannya keluar dari ruang "Eden" dan berpotensi kehilangan lokalitas spasial dalam proses tersebut.

  • Itu selalu berguna dalam bahasa apa pun untuk menyatukan sumber daya kompleks yang sangat mahal untuk dihancurkan dan dibuat seperti utas. Itu bisa bernilai penyatuan karena biaya menciptakan dan menghancurkan mereka hampir tidak ada hubungannya dengan memori yang terkait dengan objek yang menangani sumber daya. Namun, partikel tidak sesuai dengan kategori ini.

Java menawarkan alokasi burst cepat menggunakan pengalokasi sekuensial ketika Anda dengan cepat mengalokasikan objek ke ruang Eden. Strategi alokasi sekuensial itu super cepat, lebih cepat daripada mallocdi C karena hanya pooling memory yang sudah dialokasikan secara berurutan lurus, tetapi ia datang dengan sisi negatifnya bahwa Anda tidak dapat membebaskan potongan memori individual. Ini juga merupakan trik yang berguna dalam C jika Anda hanya ingin mengalokasikan hal-hal yang super cepat untuk, katakanlah, struktur data di mana Anda tidak perlu menghapus apa pun darinya, cukup tambahkan semuanya lalu gunakan dan buang semuanya nanti.

Karena kelemahan ini karena tidak dapat membebaskan objek individual, Java GC, setelah siklus pertama, akan menyalin semua memori yang dialokasikan dari ruang Eden ke wilayah memori baru menggunakan pengalokasi memori yang lebih lambat dan lebih bertujuan umum yang memungkinkan memori untuk dibebaskan dalam potongan individu di utas yang berbeda. Kemudian ia dapat membuang memori yang dialokasikan di ruang Eden secara keseluruhan tanpa repot dengan objek individual yang sekarang telah disalin dan tinggal di tempat lain dalam memori. Setelah siklus GC pertama itu, objek Anda bisa menjadi terfragmentasi dalam memori.

Karena objek dapat berakhir terfragmentasi setelah siklus GC pertama, manfaat dari pengumpulan objek ketika itu terutama untuk meningkatkan pola akses memori (lokalitas referensi) dan mengurangi alokasi / deallokasi overhead sebagian besar hilang ... begitu banyak bahwa Anda akan mendapatkan referensi lokal yang lebih baik biasanya dengan hanya mengalokasikan partikel baru setiap saat dan menggunakannya saat mereka masih segar di ruang Eden dan sebelum mereka menjadi "tua" dan berpotensi tersebar di memori. Namun, apa yang bisa sangat membantu (seperti mendapatkan kinerja menyaingi C di Jawa) adalah untuk menghindari menggunakan objek untuk partikel Anda dan mengumpulkan data primitif lama polos. Sebagai contoh sederhana, alih-alih:

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Lakukan sesuatu seperti:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Sekarang untuk menggunakan kembali memori untuk partikel yang ada, Anda dapat melakukan ini:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Sekarang ketika nthpartikel mati, untuk memungkinkannya untuk digunakan kembali, dorong ke daftar gratis seperti:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

Saat menambahkan partikel baru, lihat apakah Anda dapat mengeluarkan indeks dari daftar gratis:

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

Ini bukan kode yang paling menyenangkan untuk dikerjakan, tetapi dengan ini Anda harus bisa mendapatkan beberapa simulasi partikel yang sangat cepat dengan pemrosesan partikel sekuensial yang selalu sangat ramah terhadap cache karena semua data partikel akan selalu disimpan secara bersebelahan. Jenis rep SoA ini juga mengurangi penggunaan memori karena kita tidak perlu khawatir tentang padding, metadata objek untuk refleksi / pengiriman dinamis, dan itu memecah bidang panas dari bidang dingin (misalnya, kita tidak perlu khawatir dengan data bidang seperti warna partikel selama lulus fisika sehingga akan sia-sia untuk memuatnya ke dalam garis cache hanya untuk tidak menggunakannya dan mengusirnya).

Untuk membuat kode lebih mudah untuk dikerjakan, mungkin ada baiknya menulis kontainer resizable dasar Anda sendiri yang menyimpan array float, array integer, dan array boolean. Sekali lagi Anda tidak dapat menggunakan obat generik dan di ArrayListsini (setidaknya sejak terakhir kali saya memeriksa) karena itu memerlukan objek yang dikelola GC, bukan data primitif yang berdekatan. Kami ingin menggunakan array yang berdekatan int, misalnya, bukan array yang dikelola GC Integeryang tidak harus berdekatan setelah meninggalkan ruang Eden.

Dengan array tipe primitif, mereka selalu dijamin bersebelahan, sehingga Anda mendapatkan lokalitas referensi yang sangat diinginkan (untuk pemrosesan partikel berurutan itu membuat perbedaan dunia) dan semua manfaat yang ingin disediakan oleh kumpulan objek. Dengan berbagai objek, itu agak analog dengan array pointer yang mulai menunjuk ke objek dengan cara yang berdekatan dengan asumsi Anda mengalokasikan semuanya sekaligus ke ruang Eden, tetapi setelah siklus GC, dapat menunjuk seluruh tempatkan di memori.


sumber
1
Ini adalah artikel yang bagus untuk masalah ini, dan setelah 5 tahun coding java saya bisa melihatnya dengan jelas; Java GC tentu saja tidak bodoh, juga tidak dibuat untuk pemrograman game (karena tidak terlalu peduli dengan lokalitas data dan lain-lain), jadi kita lebih baik bermain sesuka hati: P
Gustavo Maciel