Yang lebih cepat: Alokasi tumpukan atau Alokasi tumpukan

Pertanyaan ini mungkin terdengar sangat mendasar, tetapi ini adalah perdebatan yang saya miliki dengan pengembang lain yang bekerja dengan saya.

Saya berhati-hati untuk menumpuk mengalokasikan hal-hal di mana saya bisa, bukannya menumpuk mengalokasikannya. Dia berbicara kepada saya dan mengawasi dari balik pundak saya dan berkomentar bahwa itu tidak perlu karena mereka memiliki kinerja yang sama bijaksana.

Saya selalu mendapat kesan bahwa menumbuhkan tumpukan adalah waktu yang konstan, dan kinerja alokasi tumpukan bergantung pada kerumitan tumpukan saat ini untuk kedua alokasi (menemukan lubang dengan ukuran yang tepat) dan de-alokasi (lubang runtuh untuk mengurangi fragmentasi, seperti banyak implementasi pustaka standar membutuhkan waktu untuk melakukan ini selama penghapusan jika saya tidak salah).

Ini menurut saya sebagai sesuatu yang mungkin akan sangat bergantung pada kompiler. Untuk proyek ini khususnya saya menggunakan kompiler Metrowerks untuk arsitektur PPC . Wawasan tentang kombinasi ini akan sangat membantu, tetapi secara umum, untuk GCC, dan MSVC ++, apa masalahnya? Apakah alokasi tumpukan tidak berkinerja tinggi seperti alokasi tumpukan? Apakah tidak ada perbedaan? Atau perbedaan begitu menit itu menjadi optimasi mikro sia-sia.

Alokasi tumpukan jauh lebih cepat karena yang dilakukannya hanyalah memindahkan penunjuk tumpukan. Menggunakan kumpulan memori, Anda bisa mendapatkan kinerja yang sebanding dari alokasi tumpukan, tetapi itu datang dengan sedikit kompleksitas tambahan dan sakit kepala sendiri.

Juga, tumpukan vs tumpukan tidak hanya pertimbangan kinerja; itu juga memberi tahu Anda banyak tentang umur objek yang diharapkan.

Stack jauh lebih cepat. Secara harfiah hanya menggunakan satu instruksi pada sebagian besar arsitektur, dalam banyak kasus, misalnya pada x86:

sub esp, 0x10

(Itu menggerakkan penunjuk tumpukan turun 0x10 byte dan dengan demikian "mengalokasikan" byte tersebut untuk digunakan oleh variabel.)

Tentu saja, ukuran tumpukan sangat, sangat terbatas, karena Anda akan segera mengetahui apakah Anda terlalu banyak menggunakan alokasi tumpukan atau mencoba melakukan rekursi :-)

Juga, ada sedikit alasan untuk mengoptimalkan kinerja kode yang tidak benar-benar membutuhkannya, seperti ditunjukkan oleh profil. "Optimasi prematur" seringkali menyebabkan lebih banyak masalah daripada nilainya.

Aturan praktis saya: jika saya tahu saya akan memerlukan beberapa data pada waktu kompilasi , dan ukurannya di bawah beberapa ratus byte, saya menumpuk-mengalokasikannya. Kalau tidak, saya menumpuk-mengalokasikannya.

Jujur saja, menulis program untuk membandingkan kinerjanya sepele:

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

Dikatakan bahwa konsistensi bodoh adalah hobgoblin pikiran kecil . Kompiler pengoptimal yang kelihatannya optimal adalah hobgoblin dari pikiran banyak programmer. Diskusi ini dulu ada di bagian bawah jawaban, tetapi orang-orang tampaknya tidak mau repot untuk membaca sejauh itu, jadi saya pindah ke sini untuk menghindari mendapatkan pertanyaan yang sudah saya jawab.

Kompiler pengoptimal mungkin memperhatikan bahwa kode ini tidak melakukan apa-apa, dan dapat mengoptimalkannya semua. Adalah tugas pengoptimal untuk melakukan hal-hal seperti itu, dan melawan pengoptimal adalah tugas orang bodoh.

Saya akan merekomendasikan kompilasi kode ini dengan optimisasi dimatikan karena tidak ada cara yang baik untuk menipu setiap pengoptimal yang sedang digunakan atau yang akan digunakan di masa depan.

Siapa pun yang mengaktifkan pengoptimal dan kemudian mengeluh tentang melawannya harus menjadi bahan ejekan publik.

Jika saya peduli tentang presisi nanodetik, saya tidak akan menggunakannya std::clock(). Jika saya ingin mempublikasikan hasilnya sebagai tesis doktoral, saya akan membuat kesepakatan yang lebih besar tentang ini, dan saya mungkin akan membandingkan GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC dan kompiler lainnya. Karena itu, alokasi tumpukan membutuhkan waktu ratusan kali lebih lama dari alokasi tumpukan, dan saya tidak melihat ada gunanya menyelidiki pertanyaan lebih lanjut.

Pengoptimal memiliki misi untuk menyingkirkan kode yang saya uji. Saya tidak melihat alasan untuk memberitahu pengoptimal untuk menjalankan dan kemudian mencoba menipu pengoptimal agar tidak benar-benar mengoptimalkan. Tetapi jika saya melihat nilai dalam melakukan itu, saya akan melakukan satu atau lebih hal berikut ini:

1. Tambahkan anggota data ke empty, dan akses anggota data itu dalam loop; tetapi jika saya hanya pernah membaca dari anggota data optimizer dapat melakukan pelipatan konstan dan menghapus loop; jika saya hanya pernah menulis ke anggota data, pengoptimal dapat melewati semua tapi iterasi terakhir dari loop. Selain itu, pertanyaannya bukanlah "alokasi tumpukan dan akses data vs. alokasi tumpukan dan akses data."

2. Nyatakan e volatile, tetapi volatilesering kali dikompilasi secara salah (PDF).

3. Ambil alamat edi dalam loop (dan mungkin tetapkan ke variabel yang dideklarasikan externdan didefinisikan dalam file lain). Tetapi bahkan dalam kasus ini, kompiler mungkin memperhatikan bahwa - setidaknya pada stack - eakan selalu dialokasikan pada alamat memori yang sama, dan kemudian melakukan pelipatan konstan seperti pada (1) di atas. Saya mendapatkan semua iterasi loop, tetapi objek tidak pernah benar-benar dialokasikan.

Di luar yang jelas, tes ini cacat karena mengukur baik alokasi dan deallokasi, dan pertanyaan awal tidak bertanya tentang deallokasi. Tentu saja variabel yang dialokasikan pada stack secara otomatis dialokasikan pada akhir ruang lingkup mereka, jadi tidak memanggil deleteakan (1) membelokkan angka-angka (stack deallocation termasuk dalam angka-angka tentang alokasi stack, jadi itu hanya adil untuk mengukur heap deallocation) dan ( 2) menyebabkan kebocoran memori yang sangat buruk, kecuali kita menyimpan referensi ke pointer baru dan memanggil deletesetelah kita mendapatkan pengukuran waktu kita.

Di mesin saya, menggunakan g ++ 3.4.4 di Windows, saya mendapatkan "0 tick ticks" untuk alokasi stack dan heap untuk alokasi kurang dari 100000, dan bahkan kemudian saya mendapatkan "tick tick 0" untuk alokasi stack dan "tick tick 15 clock "untuk alokasi tumpukan. Ketika saya mengukur alokasi 10.000.000, alokasi tumpukan mengambil 31 kutu jam dan alokasi tumpukan mengambil 1.562 kutu jam.

Ya, kompiler pengoptimal mungkin dapat menghilangkan pembuatan objek kosong. Jika saya mengerti dengan benar, itu bahkan dapat menghilangkan seluruh loop pertama. Ketika saya meningkatkan iterasi hingga 10.000.000 alokasi stack, mengambil 31 tick ticks dan heap alokasi mengambil 1562 tick ticks. Saya pikir aman untuk mengatakan bahwa tanpa memberitahu g ++ untuk mengoptimalkan executable, g ++ tidak menghilangkan konstruktor.

Pada tahun-tahun sejak saya menulis ini, preferensi pada Stack Overflow adalah mengirim kinerja dari build yang dioptimalkan. Secara umum, saya pikir ini benar. Namun, saya masih berpikir itu konyol untuk meminta kompiler untuk mengoptimalkan kode ketika Anda sebenarnya tidak ingin kode itu dioptimalkan. Menurut saya itu sangat mirip dengan membayar ekstra untuk parkir valet, tetapi menolak untuk menyerahkan kunci. Dalam kasus khusus ini, saya tidak ingin pengoptimal berjalan.

Menggunakan versi tolok ukur yang sedikit dimodifikasi (untuk mengatasi titik yang valid bahwa program asli tidak mengalokasikan sesuatu pada tumpukan setiap kali melalui loop) dan mengkompilasi tanpa optimisasi tetapi menautkan untuk melepaskan pustaka (untuk mengatasi titik valid yang kami tidak tidak ingin menyertakan perlambatan yang disebabkan oleh tautan ke perpustakaan debug):

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

menampilkan:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

pada sistem saya ketika dikompilasi dengan baris perintah cl foo.cc /Od /MT /EHsc.

Anda mungkin tidak setuju dengan pendekatan saya untuk mendapatkan bangunan yang tidak dioptimalkan. Tidak apa-apa: silakan memodifikasi tolok ukur sebanyak yang Anda inginkan. Ketika saya mengaktifkan optimasi, saya mendapatkan:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Bukan karena alokasi tumpukan sebenarnya instan tetapi karena setiap kompiler yang setengah layak dapat melihat bahwa on_stacktidak melakukan apa pun yang berguna dan dapat dioptimalkan. GCC di laptop Linux saya juga pemberitahuan yang on_heaptidak melakukan apa pun yang berguna, dan juga mengoptimalkannya:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Suatu hal yang menarik yang saya pelajari tentang Stack vs. Heap Allocation pada prosesor Xbox 360 Xenon, yang mungkin juga berlaku untuk sistem multicore lainnya, adalah bahwa mengalokasikan pada Heap menyebabkan Bagian Kritis dimasukkan untuk menghentikan semua core lain sehingga alokasi tidak konflik. Dengan demikian, dalam loop ketat, Alokasi Tumpukan adalah cara untuk pergi untuk array berukuran tetap karena mencegah warung.

Ini mungkin merupakan percepatan lain untuk dipertimbangkan jika Anda mengkode multicore / multiproc, karena alokasi tumpukan Anda hanya akan dapat dilihat oleh inti yang menjalankan fungsi cakupan Anda, dan itu tidak akan memengaruhi core / CPU lainnya.

Anda dapat menulis pengalokasian tumpukan khusus untuk ukuran objek tertentu yang sangat performan. Namun, pengalokasian tumpukan umum tidak secara khusus berkinerja.

Juga saya setuju dengan Torbjörn Gyllebring tentang umur objek yang diharapkan. Poin bagus!

Saya tidak berpikir alokasi tumpukan dan alokasi tumpukan umumnya dipertukarkan. Saya juga berharap bahwa kinerja keduanya cukup untuk penggunaan umum.

Saya akan sangat menyarankan untuk barang-barang kecil, mana yang lebih cocok dengan ruang lingkup alokasi. Untuk item besar, heap mungkin diperlukan.

Pada sistem operasi 32-bit yang memiliki banyak utas, tumpukan seringkali agak terbatas (walaupun biasanya setidaknya beberapa mb), karena ruang alamat perlu dipahat dan cepat atau lambat satu tumpukan tumpukan akan menumpuk ke yang lain. Pada sistem single threaded (Linux glibc single threaded sih) batasannya jauh lebih sedikit karena stack hanya bisa tumbuh dan tumbuh.

Pada sistem operasi 64-bit ada ruang alamat yang cukup untuk membuat tumpukan benang cukup besar.

Biasanya alokasi stack hanya terdiri dari pengurangan dari register stack pointer. Ini lebih cepat daripada mencari tumpukan.

Terkadang alokasi tumpukan membutuhkan penambahan satu halaman dari memori virtual. Menambahkan halaman baru dari memori nol tidak perlu membaca halaman dari disk, jadi biasanya ini masih akan menjadi lebih cepat daripada mencari heap (terutama jika bagian dari heap juga diketengahkan). Dalam situasi yang jarang terjadi, dan Anda dapat membuat contoh seperti itu, cukup ruang yang tersedia di bagian tumpukan yang sudah ada dalam RAM, tetapi mengalokasikan halaman baru untuk tumpukan harus menunggu beberapa halaman lain untuk dituliskan ke disk. Dalam situasi langka itu, tumpukan lebih cepat.

Selain dari keunggulan kinerja pesanan-besarnya dibandingkan alokasi tumpukan, alokasi tumpukan lebih disukai untuk aplikasi server yang berjalan lama. Bahkan tumpukan terbaik yang dikelola akhirnya menjadi sangat terfragmentasi sehingga kinerja aplikasi menurun.

Tumpukan memiliki kapasitas terbatas, sedangkan tumpukan tidak. Tumpukan khas untuk suatu proses atau utas adalah sekitar 8K. Anda tidak dapat mengubah ukuran setelah dialokasikan.

Variabel stack mengikuti aturan pelingkupan, sementara variabel tumpukan tidak. Jika penunjuk instruksi Anda melampaui fungsi, semua variabel baru yang terkait dengan fungsi akan hilang.

Yang terpenting dari semuanya, Anda tidak dapat memprediksi rantai panggilan fungsi secara keseluruhan sebelumnya. Jadi alokasi 200 byte hanya pada bagian Anda dapat meningkatkan stack overflow. Ini sangat penting jika Anda sedang menulis perpustakaan, bukan aplikasi.

Saya pikir seumur hidup sangat penting, dan apakah hal yang dialokasikan harus dibangun dengan cara yang kompleks. Misalnya, dalam pemodelan berbasis transaksi, Anda biasanya harus mengisi dan meneruskan struktur transaksi dengan sekelompok bidang ke fungsi operasi. Lihatlah standar OSCI SystemC TLM-2.0 untuk contoh.

Mengalokasikan ini pada tumpukan dekat dengan panggilan ke operasi cenderung menyebabkan overhead yang sangat besar, karena konstruksinya mahal. Cara yang baik untuk mengalokasikan pada heap dan menggunakan kembali objek transaksi baik dengan penyatuan atau kebijakan sederhana seperti "modul ini hanya membutuhkan satu objek transaksi yang pernah".

Ini jauh lebih cepat daripada mengalokasikan objek pada setiap panggilan operasi.

Alasannya sederhana bahwa objek memiliki konstruksi yang mahal dan masa manfaat yang cukup lama.

Saya akan mengatakan: coba keduanya dan lihat mana yang paling baik dalam kasus Anda, karena itu benar-benar dapat bergantung pada perilaku kode Anda.

Mungkin masalah terbesar dari alokasi tumpukan versus alokasi tumpukan, adalah bahwa alokasi tumpukan dalam kasus umum adalah operasi yang tidak terikat, dan dengan demikian Anda tidak dapat menggunakannya di mana waktu adalah masalah.

Untuk aplikasi lain di mana pengaturan waktu tidak menjadi masalah, mungkin tidak terlalu penting, tetapi jika Anda banyak mengalokasikan, ini akan mempengaruhi kecepatan eksekusi. Selalu coba gunakan tumpukan untuk waktu yang singkat dan sering dialokasikan memori (misalnya dalam loop), dan selama mungkin - lakukan alokasi tumpukan selama startup aplikasi.

Bukan hanya alokasi stack yang lebih cepat. Anda juga menang banyak dalam menggunakan variabel stack. Mereka memiliki lokalitas referensi yang lebih baik. Dan akhirnya, deokasi juga jauh lebih murah.

Alokasi tumpukan adalah beberapa instruksi sedangkan pengalokasian tumpukan rtos tercepat yang saya kenal (TLSF) menggunakan rata-rata pada urutan 150 instruksi. Juga alokasi stack tidak memerlukan kunci karena mereka menggunakan penyimpanan lokal thread yang merupakan kemenangan besar lainnya. Jadi alokasi tumpukan bisa 2-3 kali lipat lebih cepat tergantung pada seberapa banyak multithread lingkungan Anda.

Secara umum alokasi heap adalah pilihan terakhir Anda jika Anda peduli dengan kinerja. Opsi di antara yang layak dapat berupa pengalokasian kumpulan tetap yang juga hanya merupakan beberapa instruksi dan memiliki sedikit overhead per alokasi sehingga sangat bagus untuk objek berukuran kecil. Pada sisi negatifnya itu hanya bekerja dengan objek ukuran tetap, tidak inheren thread aman dan memiliki masalah fragmentasi blok.

Masalah Khusus untuk Bahasa C ++

Pertama-tama, tidak ada yang disebut alokasi "tumpukan" atau "tumpukan" yang diamanatkan oleh C ++ . Jika Anda berbicara tentang objek otomatis dalam lingkup blok, mereka bahkan tidak "dialokasikan". (BTW, durasi penyimpanan otomatis dalam C jelas TIDAK sama dengan "dialokasikan"; yang terakhir adalah "dinamis" dalam bahasa C ++.) Memori yang dialokasikan secara dinamis ada di toko bebas , tidak harus pada "tumpukan", meskipun yang terakhir sering kali merupakan implementasi (default) .

Meskipun sesuai aturan semantik mesin abstrak , objek otomatis masih menempati memori, implementasi C ++ yang sesuai diizinkan untuk mengabaikan fakta ini ketika dapat membuktikan bahwa ini tidak masalah (ketika itu tidak mengubah perilaku yang dapat diamati dari program). Izin ini diberikan oleh aturan seolah-olah dalam ISO C ++, yang juga merupakan klausa umum yang memungkinkan optimasi yang biasa (dan ada juga aturan yang hampir sama dalam ISO C). Selain aturan as-if, ISO C ++ juga memiliki aturan penyalinan salinan untuk memungkinkan penghilangan ciptaan objek tertentu. Karena itu panggilan konstruktor dan destruktor yang terlibat dihilangkan. Akibatnya, objek otomatis (jika ada) dalam konstruktor dan destruktor ini juga dihilangkan, dibandingkan dengan semantik abstrak naif yang tersirat oleh kode sumber.

Di sisi lain, alokasi toko gratis pasti "alokasi" oleh desain. Di bawah aturan ISO C ++, alokasi semacam itu dapat dicapai dengan panggilan fungsi alokasi . Namun, sejak ISO C ++ 14, ada aturan baru (non-as-if) untuk memungkinkan penggabungan fungsi alokasi global (yaitu ::operator new) panggilan dalam kasus tertentu. Jadi bagian-bagian dari operasi alokasi dinamis juga dapat menjadi tidak-suka seperti halnya objek otomatis.

Fungsi alokasi mengalokasikan sumber daya memori. Objek dapat selanjutnya dialokasikan berdasarkan alokasi menggunakan pengalokasi. Untuk objek otomatis, mereka disajikan langsung - meskipun memori yang mendasarinya dapat diakses dan digunakan untuk memberikan memori ke objek lain (dengan penempatannew ), tetapi ini tidak masuk akal seperti toko bebas, karena tidak ada cara untuk memindahkan sumber daya di tempat lain.

Semua masalah lain berada di luar cakupan C ++. Meskipun demikian, mereka masih signifikan.

Tentang Implementasi C ++

C ++ tidak memaparkan catatan aktivasi yang direvisi atau semacam kelanjutan kelas satu (misalnya oleh yang terkenal call/cc ), tidak ada cara untuk secara langsung memanipulasi frame rekaman aktivasi - di mana implementasi perlu menempatkan objek otomatis. Setelah tidak ada interoperasi (non-portabel) dengan implementasi yang mendasari ("asli" kode non-portabel, seperti kode assembly inline), penghilangan alokasi yang mendasari frame bisa sangat sepele. Sebagai contoh, ketika fungsi yang dipanggil digarisbawahi, frame dapat secara efektif digabung menjadi yang lain, sehingga tidak ada cara untuk menunjukkan apa itu "alokasi".

Namun, begitu interops dihormati, segalanya menjadi kompleks. Implementasi khas C ++ akan mengekspos kemampuan interop pada ISA (arsitektur set-instruksi) dengan beberapa konvensi pemanggilan sebagai batas biner yang dibagikan dengan kode asli (mesin level ISA). Ini akan secara eksplisit mahal, terutama, ketika mempertahankan penunjuk tumpukan , yang sering dipegang langsung oleh register tingkat ISA (dengan instruksi mesin yang mungkin khusus untuk diakses). Penunjuk tumpukan menunjukkan batas bingkai atas panggilan fungsi (saat ini aktif). Ketika panggilan fungsi dimasukkan, bingkai baru diperlukan dan penunjuk tumpukan ditambahkan atau dikurangi (tergantung pada konvensi ISA) dengan nilai tidak kurang dari ukuran bingkai yang diperlukan. Bingkai ini kemudian dikatakan dialokasikanketika stack pointer setelah operasi. Parameter fungsi dapat diteruskan ke bingkai tumpukan juga, tergantung pada konvensi pemanggilan yang digunakan untuk panggilan. Bingkai dapat menampung memori objek otomatis (mungkin termasuk parameter) yang ditentukan oleh kode sumber C ++. Dalam arti implementasi seperti itu, objek-objek ini "dialokasikan". Ketika kontrol keluar dari panggilan fungsi, bingkai tidak lagi diperlukan, biasanya dilepaskan dengan mengembalikan penunjuk tumpukan kembali ke keadaan sebelum panggilan (disimpan sebelumnya sesuai dengan konvensi pemanggilan). Ini dapat dilihat sebagai "deallokasi". Operasi-operasi ini membuat catatan aktivasi secara efektif struktur data LIFO, sehingga sering disebut " tumpukan (panggilan) ".

Karena sebagian besar implementasi C ++ (terutama yang menargetkan kode asli tingkat ISA dan menggunakan bahasa rakitan sebagai output langsungnya) menggunakan strategi serupa seperti ini, skema "alokasi" yang membingungkan sangat populer. Alokasi seperti itu (juga deallocations) menghabiskan siklus alat berat, dan itu bisa mahal ketika panggilan (yang tidak dioptimalkan) sering terjadi, meskipun arsitektur mikro CPU modern dapat memiliki optimasi yang kompleks diimplementasikan oleh perangkat keras untuk pola kode umum (seperti menggunakan stack engine dalam mengimplementasikan PUSH/ POPinstruksi).

Tapi bagaimanapun, secara umum, memang benar bahwa biaya alokasi bingkai tumpukan secara signifikan lebih kecil daripada panggilan ke fungsi alokasi yang mengoperasikan toko gratis (kecuali itu benar-benar dioptimalkan jauh) , yang itu sendiri dapat memiliki ratusan (jika tidak jutaan :-) operasi untuk mempertahankan stack pointer dan status lainnya. Fungsi alokasi biasanya didasarkan pada API yang disediakan oleh lingkungan yang dihosting (misalnya runtime yang disediakan oleh OS). Berbeda dengan tujuan memegang objek otomatis untuk panggilan fungsi, alokasi tersebut bertujuan umum, sehingga mereka tidak akan memiliki struktur bingkai seperti tumpukan. Secara tradisional, mereka mengalokasikan ruang dari penyimpanan kolam yang disebut heap (atau beberapa heaps). Berbeda dari "tumpukan", konsep "tumpukan" di sini tidak menunjukkan struktur data yang digunakan;ini berasal dari implementasi bahasa awal beberapa dekade yang lalu . (BTW, tumpukan panggilan biasanya dialokasikan dengan ukuran tetap atau yang ditentukan pengguna dari tumpukan oleh lingkungan dalam program atau utas startup.) Sifat kasus penggunaan membuat alokasi dan deallokasi dari tumpukan jauh lebih rumit (daripada push atau pop of tumpukan frame), dan hampir tidak mungkin dioptimalkan secara langsung oleh perangkat keras.

Efek pada Akses Memori

Alokasi tumpukan yang biasa selalu menempatkan frame baru di atas, sehingga memiliki lokalitas yang cukup baik. Ini cocok untuk cache. OTOH, memori yang dialokasikan secara acak di toko gratis tidak memiliki properti seperti itu. Sejak ISO C ++ 17, ada templat sumber daya kumpulan yang disediakan oleh <memory>. Tujuan langsung dari antarmuka tersebut adalah untuk memungkinkan hasil alokasi berturut-turut berdekatan dalam memori. Ini mengakui fakta bahwa strategi ini umumnya baik untuk kinerja dengan implementasi kontemporer, misalnya ramah terhadap cache dalam arsitektur modern. Ini tentang kinerja akses daripada alokasi .

Konkurensi

Harapan akses bersamaan ke memori dapat memiliki efek yang berbeda antara tumpukan dan tumpukan. Tumpukan panggilan biasanya secara eksklusif dimiliki oleh satu utas eksekusi dalam implementasi C ++. OTOH, tumpukan sering dibagi di antara utas dalam suatu proses. Untuk tumpukan seperti itu, fungsi alokasi dan deallokasi harus melindungi struktur data administrasi internal bersama dari ras data. Akibatnya, alokasi tumpukan dan deokasiasi mungkin memiliki overhead tambahan karena operasi sinkronisasi internal.

Efisiensi Ruang

Karena sifat kasus penggunaan dan struktur data internal, tumpukan mungkin menderita fragmentasi memori internal , sedangkan tumpukan tidak. Ini tidak memiliki dampak langsung pada kinerja alokasi memori, tetapi dalam sistem dengan memori virtual , efisiensi ruang yang rendah dapat menurunkan kinerja keseluruhan dari akses memori. Ini sangat mengerikan ketika HDD digunakan sebagai pertukaran memori fisik. Ini dapat menyebabkan latensi yang cukup lama - terkadang milyaran siklus.

Keterbatasan Alokasi Tumpukan

Meskipun alokasi tumpukan sering unggul dalam kinerja daripada alokasi tumpukan pada kenyataannya, itu tentu saja tidak berarti alokasi tumpukan selalu dapat menggantikan alokasi tumpukan.

Pertama, tidak ada cara untuk mengalokasikan ruang pada stack dengan ukuran yang ditentukan saat runtime dengan cara portabel dengan ISO C ++. Ada ekstensi yang disediakan oleh implementasi seperti allocadan VLA G ++ (array variabel-panjang), tetapi ada alasan untuk menghindarinya. (IIRC, sumber Linux menghapus penggunaan VLA baru-baru ini.) (Juga perhatikan ISO C99 memang telah mengamanatkan VLA, tetapi ISO C11 mengubah dukungan opsional.)

Kedua, tidak ada cara yang andal dan portabel untuk mendeteksi kelelahan ruang stack. Ini sering disebut stack overflow _{(hmm, etimologi situs ini)} , tetapi mungkin lebih akurat, stack overrun . Pada kenyataannya, ini sering menyebabkan akses memori tidak valid, dan keadaan program kemudian rusak (... atau mungkin lebih buruk, lubang keamanan). Faktanya, ISO C ++ tidak memiliki konsep "stack" dan membuatnya tidak terdefinisi ketika sumber dayanya habis . Berhati-hatilah dengan berapa banyak ruang yang tersisa untuk objek otomatis.

Jika ruang stack habis, ada terlalu banyak objek yang dialokasikan dalam stack, yang dapat disebabkan oleh terlalu banyak panggilan fungsi atau penggunaan objek otomatis yang tidak tepat. Kasus-kasus seperti itu mungkin menunjukkan adanya bug, misalnya panggilan fungsi rekursif tanpa kondisi keluar yang benar.

Namun demikian, panggilan rekursif yang mendalam kadang-kadang diinginkan. Dalam implementasi bahasa yang membutuhkan dukungan panggilan aktif tidak terikat (di mana kedalaman panggilan hanya dibatasi oleh total memori), tidak mungkin untuk menggunakan tumpukan panggilan asli (kontemporer) secara langsung sebagai catatan aktivasi bahasa target seperti implementasi C ++ yang khas. Untuk mengatasi masalah tersebut, diperlukan cara alternatif untuk membangun catatan aktivasi. Sebagai contoh, SML / NJ secara eksplisit mengalokasikan frame pada heap dan menggunakan tumpukan kaktus . Alokasi rumit dari bingkai catatan aktivasi semacam itu biasanya tidak secepat bingkai tumpukan panggilan. Namun, jika bahasa tersebut diimplementasikan lebih lanjut dengan jaminan rekursi ekor yang tepat, alokasi tumpukan langsung dalam bahasa objek (yaitu, "objek" dalam bahasa tidak disimpan sebagai referensi, tetapi nilai primitif asli yang dapat dipetakan satu-ke-satu ke objek C ++ yang dibagikan) bahkan lebih rumit dengan lebih banyak penalti kinerja secara umum. Saat menggunakan C ++ untuk mengimplementasikan bahasa seperti itu, sulit untuk memperkirakan dampak kinerja.

Ada poin umum yang bisa dibuat tentang optimasi tersebut.

Optimasi yang Anda dapatkan sebanding dengan jumlah waktu penghitung program sebenarnya dalam kode itu.

Jika Anda mencicipi penghitung program, Anda akan menemukan di mana ia menghabiskan waktu, dan itu biasanya di bagian kecil dari kode, dan seringkali dalam rutinitas perpustakaan Anda tidak memiliki kendali atas.

Hanya jika Anda menemukannya menghabiskan banyak waktu dalam alokasi tumpukan objek Anda akan terasa lebih cepat untuk menumpuk-mengalokasikannya.

Alokasi tumpukan hampir selalu lebih cepat atau lebih cepat daripada alokasi tumpukan, meskipun tentu saja mungkin bagi seorang pengalokasi tumpukan untuk hanya menggunakan teknik alokasi berbasis tumpukan.

Namun, ada masalah yang lebih besar ketika berhadapan dengan kinerja keseluruhan alokasi berbasis tumpukan vs tumpukan (atau dalam istilah yang sedikit lebih baik, alokasi lokal vs eksternal). Biasanya, alokasi heap (eksternal) lambat karena berurusan dengan berbagai jenis alokasi dan pola alokasi. Mengurangi ruang lingkup pengalokasi yang Anda gunakan (menjadikannya lokal untuk algoritme / kode) akan cenderung meningkatkan kinerja tanpa perubahan besar. Menambahkan struktur yang lebih baik ke pola alokasi Anda, misalnya, memaksa pemesanan LIFO pada pasangan alokasi dan deallokasi juga dapat meningkatkan kinerja pengalokasi Anda dengan menggunakan pengalokasi dengan cara yang lebih sederhana dan lebih terstruktur. Atau, Anda dapat menggunakan atau menulis pengalokasi yang disetel untuk pola alokasi khusus Anda; sebagian besar program sering mengalokasikan beberapa ukuran diskrit, jadi tumpukan yang didasarkan pada buffer lookaside dari beberapa ukuran tetap (lebih disukai dikenal) akan bekerja dengan sangat baik. Windows menggunakan tumpukan rendah-fragmentasi untuk alasan ini.

Di sisi lain, alokasi berbasis tumpukan pada rentang memori 32-bit juga penuh bahaya jika Anda memiliki terlalu banyak utas. Tumpukan membutuhkan rentang memori yang berdekatan, sehingga semakin banyak utas yang Anda miliki, semakin banyak ruang alamat virtual yang Anda perlukan untuk menjalankannya tanpa stack overflow. Ini tidak akan menjadi masalah (untuk saat ini) dengan 64-bit, tetapi tentu saja dapat mendatangkan malapetaka dalam program yang berjalan lama dengan banyak utas. Kehabisan ruang alamat virtual karena fragmentasi selalu menyebalkan.

Seperti yang dikatakan orang lain, alokasi tumpukan umumnya jauh lebih cepat.

Namun, jika objek Anda mahal untuk disalin, mengalokasikan pada tumpukan dapat menyebabkan kinerja yang sangat besar nanti ketika Anda menggunakan objek jika Anda tidak hati-hati.

Misalnya, jika Anda mengalokasikan sesuatu pada tumpukan, dan kemudian memasukkannya ke dalam wadah, akan lebih baik untuk mengalokasikan di tumpukan dan menyimpan pointer di wadah (misalnya dengan std :: shared_ptr <>). Hal yang sama berlaku jika Anda melewati atau mengembalikan objek dengan nilai, dan skenario serupa lainnya.

Intinya adalah bahwa meskipun alokasi tumpukan biasanya lebih baik daripada alokasi tumpukan dalam banyak kasus, kadang-kadang jika Anda keluar dari cara Anda untuk menumpuk alokasi ketika itu tidak paling cocok dengan model perhitungan, itu dapat menyebabkan lebih banyak masalah daripada memecahkannya.

class Foo {
public:
    Foo(int a) {

    }
}
int func() {
    int a1, a2;
    std::cin >> a1;
    std::cin >> a2;

    Foo f1(a1);
    __asm push a1;
    __asm lea ecx, [this];
    __asm call Foo::Foo(int);

    Foo* f2 = new Foo(a2);
    __asm push sizeof(Foo);
    __asm call operator new;//there's a lot instruction here(depends on system)
    __asm push a2;
    __asm call Foo::Foo(int);

    delete f2;
}

Akan seperti ini di ASM. Ketika Anda berada di func, f1pointer dan f2telah dialokasikan pada tumpukan (penyimpanan otomatis). Dan omong-omong, Foo f1(a1)tidak memiliki efek instruksi pada stack pointer ( esp), itu telah dialokasikan, jika funckeinginan mendapatkan anggota yang f1, instruksi itu adalah sesuatu seperti ini: lea ecx [ebp+f1], call Foo::SomeFunc(). Hal lain yang dialokasikan stack dapat membuat seseorang berpikir memori itu sepertiFIFO , yang FIFObaru saja terjadi ketika Anda masuk ke suatu fungsi, jika Anda berada dalam fungsi dan mengalokasikan sesuatu seperti int i = 0, tidak ada dorongan yang terjadi.

Telah disebutkan sebelumnya bahwa alokasi stack hanya memindahkan pointer stack, yaitu, satu instruksi pada sebagian besar arsitektur. Bandingkan dengan apa yang umumnya terjadi dalam hal alokasi heap.

Sistem operasi mempertahankan bagian memori bebas sebagai daftar yang ditautkan dengan data payload yang terdiri dari pointer ke alamat awal bagian bebas dan ukuran bagian bebas. Untuk mengalokasikan memori X byte, daftar tautan dilintasi dan setiap catatan dikunjungi secara berurutan, memeriksa untuk melihat apakah ukurannya setidaknya X. Ketika bagian dengan ukuran P> = X ditemukan, P dibagi menjadi dua bagian dengan ukuran X dan PX. Daftar tertaut diperbarui dan penunjuk ke bagian pertama dikembalikan.

Seperti yang Anda lihat, alokasi tumpukan tergantung pada faktor-faktor seperti berapa banyak memori yang Anda minta, seberapa terfragmentasi memori itu dan sebagainya.

Secara umum, alokasi tumpukan lebih cepat daripada alokasi tumpukan seperti yang disebutkan oleh hampir setiap jawaban di atas. Tumpukan push atau pop adalah O (1), sedangkan mengalokasikan atau membebaskan dari heap bisa memerlukan langkah alokasi sebelumnya. Namun Anda biasanya tidak harus mengalokasikan dalam loop ketat, kinerja-intensif, sehingga pilihan biasanya akan turun ke faktor lain.

Mungkin lebih baik untuk membuat perbedaan ini: Anda dapat menggunakan "tumpukan pengalokasi" di heap. Sebenarnya, saya mengambil alokasi tumpukan berarti metode alokasi sebenarnya daripada lokasi alokasi. Jika Anda mengalokasikan banyak hal pada tumpukan program yang sebenarnya, itu bisa berakibat buruk karena berbagai alasan. Di sisi lain, menggunakan metode tumpukan untuk mengalokasikan di heap bila memungkinkan adalah pilihan terbaik yang dapat Anda buat untuk metode alokasi.

Karena Anda menyebutkan Metrowerks dan PPC, saya kira maksud Anda Wii. Dalam hal ini, memori berada pada tingkat premium, dan menggunakan metode alokasi tumpukan sedapat mungkin menjamin bahwa Anda tidak membuang-buang memori pada fragmen. Tentu saja, melakukan ini membutuhkan lebih banyak perhatian daripada metode alokasi tumpukan "normal". Adalah bijaksana untuk mengevaluasi pengorbanan untuk setiap situasi.

Perhatikan bahwa pertimbangannya biasanya bukan tentang kecepatan dan kinerja ketika memilih tumpukan versus alokasi tumpukan. Tumpukan bertindak seperti tumpukan, yang artinya cocok untuk mendorong blok dan muncul lagi, lalu masuk, keluar pertama. Eksekusi prosedur juga seperti stack, prosedur terakhir yang dimasukkan pertama kali harus keluar. Dalam sebagian besar bahasa pemrograman, semua variabel yang diperlukan dalam prosedur hanya akan terlihat selama eksekusi prosedur, sehingga mereka didorong saat memasuki prosedur dan muncul dari tumpukan saat keluar atau kembali.

Sekarang untuk contoh di mana tumpukan tidak dapat digunakan:

Proc P
{
  pointer x;
  Proc S
  {
    pointer y;
    y = allocate_some_data();
    x = y;
  }
}

Jika Anda mengalokasikan sebagian memori dalam prosedur S dan meletakkannya di tumpukan dan kemudian keluar S, data yang dialokasikan akan muncul dari tumpukan. Tetapi variabel x dalam P juga menunjuk ke data itu, jadi x sekarang menunjuk ke suatu tempat di bawah penunjuk tumpukan (asumsikan tumpukan tumbuh ke bawah) dengan konten yang tidak diketahui. Konten mungkin masih ada jika penunjuk tumpukan baru saja dipindahkan tanpa membersihkan data di bawahnya, tetapi jika Anda mulai mengalokasikan data baru pada tumpukan, penunjuk x mungkin sebenarnya menunjuk ke data baru itu sebagai gantinya.

Jangan pernah melakukan asumsi prematur karena kode aplikasi dan penggunaan lainnya dapat memengaruhi fungsi Anda. Jadi melihat fungsinya adalah isolasi tidak ada gunanya.

Jika Anda serius dengan aplikasi maka VTune atau gunakan alat profiling serupa dan lihat hotspot.

Ketan

Saya ingin mengatakan sebenarnya menghasilkan kode oleh GCC (saya ingat VS juga) tidak memiliki overhead untuk melakukan alokasi stack .

Katakan untuk fungsi berikut:

  int f(int i)
  {
      if (i > 0)
      {   
          int array[1000];
      }   
  }

Berikut ini adalah kode yang dihasilkan:

  __Z1fi:
  Leh_func_begin1:
      pushq   %rbp
  Ltmp0:
      movq    %rsp, %rbp
  Ltmp1:
      subq    $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited.
  Ltmp2:
      movl    %edi, -4(%rbp)
      movl    -8(%rbp), %eax
      addq    $3880, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

Jadi, berapa banyak variabel lokal yang Anda miliki (bahkan di dalam atau beralih), hanya 3880 yang akan berubah ke nilai lain. Kecuali Anda tidak memiliki variabel lokal, instruksi ini hanya perlu dijalankan. Jadi mengalokasikan variabel lokal tidak memiliki overhead.