Alokasi Memori Dinamis dan Manajemen Memori

Dalam game rata-rata, ada ratusan atau mungkin ribuan objek dalam adegan. Apakah sepenuhnya benar untuk mengalokasikan memori untuk semua objek, termasuk tembakan senjata (peluru), secara dinamis melalui default baru () ?

Haruskah saya membuat kumpulan memori untuk alokasi dinamis , atau apakah tidak perlu repot dengan ini? Bagaimana jika platform targetnya adalah perangkat seluler?

Apakah ada kebutuhan untuk manajer memori dalam gim seluler? Terima kasih.

Bahasa yang Digunakan: C ++; Saat ini dikembangkan di bawah Windows, tetapi direncanakan akan porting nanti.

Dalam permainan rata-rata, ada ratusan atau mungkin ribuan obsesi di tempat kejadian. Apakah benar untuk mengalokasikan memori untuk semua objek, termasuk tembakan senjata (peluru), secara dinamis melalui default baru ()?

Itu benar-benar tergantung apa yang Anda maksud dengan "benar." Jika Anda menggunakan istilah ini secara harfiah (dan mengabaikan konsep ketepatan dari desain yang tersirat) maka ya, itu bisa diterima. Program Anda akan mengkompilasi dan berjalan dengan baik.

Ini mungkin melakukan sub-optimal, tetapi masih juga bisa tampil cukup baik untuk menjadi game yang dapat dikirim dan menyenangkan.

Haruskah saya membuat kumpulan memori untuk alokasi dinamis, atau apakah tidak perlu repot dengan ini? Bagaimana jika platform target adalah perangkat seluler?

Profil dan lihat. Dalam C ++, misalnya, alokasi dinamis pada heap biasanya merupakan operasi "lambat" (dalam hal itu melibatkan berjalan melalui heap mencari blok ukuran yang sesuai). Dalam C #, ini biasanya operasi yang sangat cepat karena hanya melibatkan sedikit peningkatan. Implementasi bahasa yang berbeda memiliki karakteristik kinerja yang berbeda sehubungan dengan alokasi memori, fragmentasi pada rilis, dan sebagainya.

Menerapkan sistem penyatuan memori tentu saja dapat menghasilkan peningkatan kinerja - dan karena sistem seluler biasanya kurang bertenaga dibandingkan dengan sistem desktop, Anda mungkin melihat lebih banyak keuntungan di platform seluler tertentu daripada di desktop. Tetapi sekali lagi, Anda harus profil dan melihat - jika, saat ini, permainan Anda lambat tetapi alokasi / rilis memori tidak muncul di profiler sebagai hot spot, mengimplementasikan infrastruktur untuk mengoptimalkan alokasi memori dan akses mungkin menang ' t membuat Anda banyak bang for your buck.

Apakah ada kebutuhan untuk manajer memori dalam gim seluler? Terima kasih.

Sekali lagi, profil dan lihat. Apakah game Anda berjalan dengan baik sekarang? Maka Anda mungkin tidak perlu khawatir.

Semua itu adalah peringatan-berbicara di samping, menggunakan alokasi dinamis untuk semuanya tidak sepenuhnya berbicara diperlukan dan sehingga dapat menguntungkan untuk menghindarinya - baik karena potensi peningkatan kinerja, dan karena mengalokasikan memori yang Anda perlu lacak dan akhirnya lepaskan berarti Anda harus melacak dan akhirnya merilisnya, mungkin menyulitkan kode Anda.

Khususnya, dalam contoh asli Anda, Anda mengutip "peluru," yang cenderung menjadi sesuatu yang sering dibuat dan dihancurkan - karena banyak permainan melibatkan banyak peluru, dan peluru bergerak cepat dan dengan demikian mencapai akhir masa hidup mereka dengan cepat (dan sering kali hebat!). Jadi menerapkan pengalokasi kumpulan untuk mereka dan benda-benda seperti mereka (seperti partikel dalam sistem partikel) biasanya dapat menghasilkan keuntungan efisiensi dan kemungkinan akan menjadi tempat pertama untuk mulai melihat menggunakan alokasi kolam.

Saya tidak jelas apakah Anda mempertimbangkan implementasi memory pool berbeda dari "memory manager" - memory pool adalah konsep yang relatif baik, jadi saya dapat mengatakan dengan pasti bahwa mereka dapat bermanfaat jika Anda mengimplementasikannya . "Manajer memori" sedikit lebih kabur dalam hal tanggung jawabnya, jadi saya harus mengatakan apakah diperlukan atau tidak tergantung pada apa yang Anda pikir "manajer memori" akan lakukan.

Misalnya jika Anda menganggap manajer memori sebagai sesuatu yang hanya memotong panggilan ke baru / menghapus / bebas / malloc / apa pun dan menyediakan diagnostik pada berapa banyak memori yang Anda alokasikan, apa yang Anda bocorkan, dan lain-lain - maka itu dapat bermanfaat alat untuk permainan saat sedang dikembangkan untuk membantu Anda men-debug kebocoran dan menyesuaikan ukuran memori optimal Anda, dan sebagainya.

Saya tidak punya banyak hal untuk ditambahkan ke jawaban Josh yang luar biasa, tetapi saya akan mengomentari ini:

Haruskah saya membuat kumpulan memori untuk alokasi dinamis, atau apakah tidak perlu repot dengan ini?

Ada jalan tengah antara kumpulan memori dan memanggil newsetiap alokasi. Misalnya, Anda dapat mengalokasikan sejumlah objek dalam array, lalu menetapkan flag pada objek tersebut untuk 'menghancurkannya nanti. Saat Anda perlu mengalokasikan lebih banyak, Anda dapat menimpa yang dengan kumpulan bendera yang dihancurkan. Hal semacam ini hanya sedikit lebih kompleks untuk digunakan daripada yang baru / hapus (karena Anda akan memiliki 2 fungsi baru untuk tujuan itu) tetapi sederhana untuk ditulis dan dapat memberi Anda keuntungan besar.

Apakah sepenuhnya benar untuk mengalokasikan memori untuk semua objek, termasuk tembakan senjata (peluru), secara dinamis melalui default baru ()?

Tidak, tentu saja tidak. Tidak ada alokasi memori yang benar untuk semua objek. operator new () adalah untuk alokasi dinamis , yaitu, hanya sesuai jika Anda membutuhkan alokasi untuk menjadi dinamis, baik karena masa hidup objek itu dinamis atau karena jenis objek itu dinamis. Jika jenis dan masa pakai objek diketahui secara statis, Anda harus mengalokasikannya secara statis.

Tentu saja, semakin banyak informasi yang Anda miliki tentang pola alokasi Anda, semakin cepat alokasi ini dapat dilakukan melalui pengalokasi spesialis, seperti kumpulan objek. Tapi, ini adalah optimasi dan Anda hanya harus membuatnya jika mereka perlu.

Semacam menggemakan saran Kylotan tetapi saya akan merekomendasikan untuk menyelesaikan ini di tingkat struktur data bila memungkinkan, bukan pada tingkat pengalokasi yang lebih rendah jika Anda dapat membantu.

Berikut adalah contoh sederhana tentang bagaimana Anda dapat menghindari mengalokasikan dan membebaskan Foosberulang kali menggunakan array dengan lubang dengan elemen yang terhubung bersama (menyelesaikan ini di tingkat "wadah" alih-alih tingkat "pengalokasi"):

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

Sesuatu untuk efek ini: daftar indeks yang terhubung sendiri dengan daftar gratis. Tautan indeks memungkinkan Anda untuk melewati elemen yang dihapus, menghapus elemen dalam waktu konstan, dan juga mendapatkan kembali / menggunakan kembali / menimpa elemen gratis dengan penyisipan waktu konstan. Untuk beralih melalui struktur, Anda melakukan sesuatu seperti ini:

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

Dan Anda dapat menggeneralisasi jenis "array array lubang" di atas dengan menggunakan template, penempatan permintaan dokumen baru dan manual untuk menghindari persyaratan penugasan salinan, membuatnya memohon destruktor ketika elemen dihapus, berikan iterator maju, dll. Saya memilih untuk menyimpan contoh sangat C-suka untuk lebih menggambarkan konsep dan juga karena saya sangat malas.

Yang mengatakan, struktur ini cenderung menurun di lokasi spasial setelah Anda menghapus dan memasukkan banyak hal ke / dari tengah. Pada titik itu, nexttautan bisa membuat Anda berjalan bolak-balik di sepanjang vektor, memuat ulang data yang sebelumnya diusir dari garis cache dalam lintasan sekuensial yang sama (ini tidak bisa dihindari dengan struktur data atau pengalokasi yang memungkinkan penghapusan waktu-konstan tanpa mengocok elemen saat mengklaim kembali spasi dari tengah dengan penyisipan waktu-konstan dan tanpa menggunakan sesuatu seperti bitset paralel atau removedbendera). Untuk memulihkan keramahan cache, Anda dapat menerapkan metode copy ctor dan swap seperti ini:

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

Sekarang versi baru ini ramah cache lagi untuk dilintasi. Metode lain adalah menyimpan daftar indeks yang terpisah ke dalam struktur dan mengurutkannya secara berkala. Cara lain adalah menggunakan bitet untuk menunjukkan indeks apa yang digunakan. Itu akan selalu membuat Anda melintasi bitset secara berurutan (untuk melakukan ini secara efisien, periksa 64-bit pada suatu waktu misalnya menggunakan FFS / FFZ). Bitet adalah yang paling efisien dan tidak mengganggu, hanya membutuhkan bit paralel per elemen untuk menunjukkan mana yang digunakan dan mana yang dihapus alih-alih membutuhkan 32-bitnext indeks , tetapi yang paling memakan waktu untuk menulis dengan baik (itu tidak akan cepat untuk traversal jika Anda mengecek satu bit pada satu waktu - Anda perlu FFS / FFZ untuk menemukan set atau unset bit segera di antara 32+ bit sekaligus untuk secara cepat menentukan rentang indeks yang ditempati).

Solusi tertaut ini umumnya paling mudah diterapkan dan tidak mengganggu (tidak perlu dimodifikasi Foo untuk menyimpan beberapa removedflag) yang bermanfaat jika Anda ingin menggeneralisasi wadah ini untuk bekerja dengan tipe data apa pun jika Anda tidak keberatan 32-bit overhead per elemen.

Haruskah saya membuat kumpulan memori untuk alokasi dinamis, atau apakah tidak perlu repot dengan ini? Bagaimana jika platform target adalah perangkat seluler?

perlu adalah kata yang kuat dan saya bias bekerja di area yang sangat kritis terhadap kinerja seperti raytracing, pemrosesan gambar, simulasi partikel, dan pemrosesan mesh, tetapi relatif sangat mahal untuk mengalokasikan dan membebaskan objek kecil yang digunakan untuk pemrosesan yang sangat ringan seperti peluru dan partikel-partikel secara terpisah melawan pengalokasi memori berukuran besar yang bertujuan umum. Mengingat bahwa Anda harus dapat menggeneralisasi struktur data di atas dalam satu atau dua hari untuk menyimpan apa pun yang Anda inginkan, saya pikir itu akan menjadi pertukaran yang bermanfaat untuk menghilangkan biaya tumpukan / alokasi yang begitu saja dari pembayaran untuk setiap hal kecil. Selain mengurangi biaya alokasi / deallokasi, Anda mendapatkan lokalitas referensi yang lebih baik melintasi hasil (cache lebih sedikit dan kesalahan halaman, yaitu).

Adapun apa yang Josh sebutkan tentang GC, saya belum mempelajari implementasi GC C sedekat Jawa, tetapi pengalokasi GC sering memiliki alokasi awalitu sangat cepat karena itu menggunakan pengalokasi berurutan yang tidak dapat membebaskan memori dari tengah (hampir seperti tumpukan, Anda tidak dapat menghapus hal-hal dari tengah). Kemudian membayar biaya mahal untuk benar-benar memungkinkan menghapus objek individu di utas terpisah dengan menyalin memori dan membersihkan memori yang sebelumnya dialokasikan sebagai keseluruhan (seperti menghancurkan seluruh tumpukan sekaligus sekaligus menyalin data ke sesuatu yang lebih seperti struktur yang terhubung), tetapi karena dilakukan di utas terpisah, itu tidak selalu menghambat utas aplikasi Anda. Namun, itu membawa biaya tersembunyi yang sangat signifikan dari tingkat tipuan tambahan dan kerugian umum LOR setelah siklus GC awal. Ini adalah strategi lain untuk mempercepat alokasi - membuatnya lebih murah di utas panggilan dan kemudian melakukan pekerjaan mahal di yang lain. Untuk itu Anda perlu dua tingkat tipuan untuk referensi objek Anda, bukan satu karena mereka akhirnya akan terseret dalam memori antara waktu Anda awalnya mengalokasikan dan setelah siklus pertama.

Strategi lain dalam nada yang serupa yang sedikit lebih mudah diterapkan di C ++ hanya tidak perlu repot untuk membebaskan objek Anda di utas utama Anda. Terus menambahkan dan menambahkan dan menambahkan ke ujung struktur data yang tidak memungkinkan menghapus hal-hal dari tengah. Namun, tandai hal-hal yang perlu dihapus. Kemudian utas terpisah dapat menangani pekerjaan mahal untuk membuat struktur data baru tanpa elemen yang dihapus dan kemudian secara atomis menukar yang baru dengan yang lama, mis. Sebagian besar biaya elemen pengalokasian dan pembebasan dapat diteruskan ke suatu pisahkan utas jika Anda dapat membuat asumsi bahwa meminta untuk menghapus suatu elemen tidak harus segera dipenuhi. Itu tidak hanya membuat membebaskan lebih murah sejauh utas Anda terkait tetapi membuat alokasi lebih murah, karena Anda dapat menggunakan struktur data yang jauh lebih sederhana dan bodoh yang tidak pernah harus menangani kasus penghapusan dari tengah. Ini seperti sebuah wadah yang hanya membutuhkan apush_backfungsi untuk penyisipan, clearfungsi untuk menghapus semua elemen, dan swapuntuk menukar konten dengan wadah baru yang ringkas tidak termasuk elemen yang dihapus; itu saja sejauh bermutasi.