Pertanyaan ini mendapat agak dingin di SO, jadi saya memutuskan untuk menghapusnya di sana dan coba di sini. Jika menurut Anda tidak cocok di sini, setidaknya tinggalkan komentar tentang saran bagaimana menemukan contoh yang saya cari ...
Bisakah Anda memberikan contoh , di mana menggunakan C99 VLA menawarkan keuntungan nyata dibandingkan dengan sesuatu seperti mekanisme CAIA RAPB-tumpukan standar saat ini?
Contoh yang saya cari harus:
- Dapatkan keunggulan kinerja yang mudah diukur (10% mungkin) dibandingkan menggunakan heap.
- Tidak memiliki solusi yang baik, yang tidak perlu seluruh array sama sekali.
- Sebenarnya mendapat manfaat dari menggunakan ukuran dinamis, bukan ukuran maksimum tetap.
- Tidak mungkin menyebabkan stack overflow dalam skenario penggunaan normal.
- Cukup kuat untuk menggoda pengembang yang membutuhkan kinerja untuk memasukkan file sumber C99 dalam proyek C ++.
Menambahkan beberapa klarifikasi pada konteks: Maksud saya VLA sebagaimana dimaksud oleh C99 dan tidak termasuk dalam standar C ++: di int array[n]
mana n
adalah variabel. Dan saya mencari contoh use case yang mengalahkan alternatif yang ditawarkan oleh standar lain (C90, C ++ 11):
int array[MAXSIZE]; // C stack array with compile time constant size
int *array = calloc(n, sizeof int); // C heap array with manual free
int *array = new int[n]; // C++ heap array with manual delete
std::unique_ptr<int[]> array(new int[n]); // C++ heap array with RAII
std::vector<int> array(n); // STL container with preallocated size
Beberapa ide:
- Fungsi mengambil varargs, yang secara alami membatasi jumlah barang untuk sesuatu yang masuk akal, namun tanpa batas atas tingkat API yang berguna.
- Fungsi rekursif, di mana tumpukan sia-sia tidak diinginkan
- Banyak alokasi dan rilis kecil, di mana tumpukan overhead akan buruk.
- Menangani array multi-dimensi (seperti matriks ukuran sewenang-wenang), di mana kinerjanya sangat penting, dan fungsi-fungsi kecil diharapkan banyak mendapat inline.
- Dari komentar: algoritma bersamaan, di mana alokasi tumpukan memiliki overhead sinkronisasi .
Wikipedia memiliki contoh yang tidak memenuhi kriteria saya , karena perbedaan praktis untuk menggunakan tumpukan tampaknya tidak relevan setidaknya tanpa konteks. Ini juga tidak ideal, karena tanpa lebih banyak konteks, tampaknya jumlah barang dapat menyebabkan stack overflow.
Catatan: Saya secara khusus mencari kode contoh, atau saran algoritma yang akan mendapat manfaat dari ini, bagi saya untuk mengimplementasikan contoh itu sendiri.
alloca()
benar-benar akan lebih cemerlangmalloc()
dalam lingkungan multithreaded karena pertikaian kunci dalam paku yang terakhir . Tetapi ini adalah peregangan nyata karena array kecil hanya harus menggunakan ukuran tetap, dan array besar mungkin akan membutuhkan heap.alloca
, yang saya pikir pada dasarnya adalah hal yang sama). Tetapi hal multithreaded itu baik, mengedit pertanyaan untuk memasukkannya!malloc
perilaku Linux sesuai dengan standar C.Jawaban:
Saya baru saja meretas sebuah program kecil yang menghasilkan satu set angka acak memulai kembali pada seed yang sama setiap kali, untuk memastikan bahwa itu "adil" dan "sebanding". Seiring berjalannya waktu, ia mencari min dan max dari nilai-nilai ini. Dan ketika telah menghasilkan himpunan angka, itu menghitung berapa banyak yang di atas rata-rata
min
danmax
.Untuk array SANGAT kecil, ini menunjukkan manfaat yang jelas dengan berakhirnya VLA
std::vector<>
.Ini bukan masalah nyata, tetapi kita dapat dengan mudah membayangkan sesuatu di mana kita akan membaca nilai-nilai dari file kecil daripada menggunakan angka acak, dan melakukan beberapa perhitungan penghitungan / min / maks lainnya yang lebih bermakna dengan jenis kode yang sama .
Untuk nilai SANGAT kecil dari "jumlah angka acak" (x) dalam fungsi yang relevan,
vla
solusi menang dengan margin yang sangat besar. Ketika ukurannya semakin besar, "win" semakin kecil, dan diberi ukuran yang cukup, solusi vektor tampaknya LEBIH efisien - tidak mempelajari varian terlalu banyak, seperti ketika kita mulai memiliki ribuan elemen dalam VLA, itu bukan sungguh apa yang seharusnya mereka lakukan ...Dan saya yakin seseorang akan memberi tahu saya bahwa ada beberapa cara untuk menulis semua kode ini dengan banyak templat dan menyelesaikannya tanpa menjalankan lebih dari RDTSC dan
cout
bit saat runtime ... Tapi saya tidak berpikir itu benar-benar inti nya.Saat menjalankan varian khusus ini, saya mendapatkan sekitar 10% perbedaan antara
func1
(VLA) danfunc2
(std :: vector).Ini dikompilasi dengan:
g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp
Berikut kodenya:
sumber
std::vector
.func3
yang menggunakanv.push_back(rand())
alih-alihv[i] = rand();
dan menghilangkan kebutuhanresize()
. Dibutuhkan sekitar 10% lebih lama dibandingkan dengan yang menggunakanresize()
. [Tentu saja, dalam prosesnya, saya menemukan bahwa penggunaanv[i]
adalah kontributor utama pada waktu fungsi - saya sedikit terkejut tentang itu].std::vector
implementasi aktual yang akan menggunakan VLA /alloca
, atau hanya spekulasi?vector
implementasi.Mengenai VLA versus Vektor
Apakah Anda menganggap bahwa suatu Vektor dapat memanfaatkan VLA itu sendiri. Tanpa VLA, Vector harus menentukan "skala" array misalnya 10, 100, 10000 untuk penyimpanan sehingga Anda akhirnya mengalokasikan 10.000 item array untuk menampung 101 item. Dengan VLA, jika Anda mengubah ukuran menjadi 200, algoritme mungkin mengasumsikan bahwa Anda hanya perlu 200 dan dapat mengalokasikan 200 item array. Atau dapat mengalokasikan buffer dari say n * 1.5.
Ngomong-ngomong, saya berpendapat bahwa jika Anda tahu berapa banyak item yang akan Anda butuhkan saat runtime, VLA lebih performan (seperti yang ditunjukkan oleh benchmark Mats '). Apa yang dia tunjukkan adalah iterasi dua pass sederhana. Pikirkan simulasi monte carlo di mana sampel acak diambil berulang kali, atau manipulasi gambar (seperti filter Photoshop) di mana perhitungan dilakukan pada setiap elemen beberapa kali dan sangat mungkin setiap perhitungan pada setiap elemen melibatkan melihat tetangga.
Penunjuk ekstra itu melompat dari vektor ke susunan internalnya bertambah.
Menjawab pertanyaan utama
Tetapi ketika Anda berbicara tentang menggunakan struktur yang dialokasikan secara dinamis seperti LinkedList, tidak ada perbandingan. Array menyediakan akses langsung menggunakan pointer aritmatika ke elemen-elemennya. Menggunakan daftar tertaut, Anda harus berjalan di titik untuk mendapatkan elemen tertentu. Jadi VLA menang telak dalam skenario ini.Menurut jawaban ini , secara arsitektur tergantung, tetapi dalam beberapa kasus akses memori pada stack akan lebih cepat karena stack tersedia pada cache. Dengan sejumlah besar elemen ini dapat dinegasikan (berpotensi menjadi penyebab berkurangnya pengembalian yang dilihat Mats dalam tolok ukurnya). Namun, perlu dicatat bahwa ukuran Cache tumbuh secara signifikan dan Anda akan berpotensi melihat lebih banyak dari itu.
sumber
std::vector
skala kebutuhan array? Mengapa perlu ruang untuk elemen 10K ketika hanya membutuhkan 101? Selain itu, pertanyaannya tidak pernah menyebutkan daftar tertaut, jadi saya tidak yakin dari mana Anda mendapatkannya. Akhirnya, VLA di C99 dialokasikan stack; mereka adalah bentuk standaralloca()
. Apa pun yang membutuhkan penyimpanan tumpukan (itu hidup sekitar setelah fungsi kembali) ataurealloc()
(array mengubah ukurannya sendiri) akan melarang VLA.Alasan untuk menggunakan VLA terutama karena kinerja. Merupakan kesalahan untuk mengabaikan contoh wiki karena hanya memiliki perbedaan "tidak relevan". Saya dapat dengan mudah melihat kasus-kasus di mana tepatnya kode itu dapat memiliki perbedaan besar, misalnya, jika fungsi itu disebut dalam loop ketat, di mana
read_val
ada fungsi IO yang kembali sangat cepat pada semacam sistem di mana kecepatan sangat penting.Bahkan, di sebagian besar tempat di mana VLA digunakan dengan cara ini, mereka tidak mengganti panggilan tumpukan tetapi malah mengganti sesuatu seperti:
Hal tentang deklarasi lokal adalah bahwa itu sangat cepat. Garis
float vals[n]
umumnya hanya memerlukan beberapa instruksi prosesor (mungkin hanya satu.) Itu hanya menambah nilain
ke stack pointer.Di sisi lain, alokasi tumpukan memerlukan berjalan struktur data untuk menemukan area bebas. Waktu mungkin urutan besarnya lebih lama bahkan dalam kasus paling beruntung. (Yaitu hanya tindakan menempatkan
n
di tumpukan dan meneleponmalloc
mungkin 5-10 instruksi.) Mungkin jauh lebih buruk jika ada jumlah data yang wajar di heap. Sama sekali tidak mengejutkan saya untuk melihat kasus di manamalloc
100x hingga 1000x lebih lambat dalam program nyata.Tentu saja, maka Anda juga memiliki beberapa dampak kinerja dengan pencocokan
free
, mungkin sama besarnya denganmalloc
panggilan.Selain itu, ada masalah fragmentasi memori. Banyak alokasi kecil cenderung memecah tumpukan. Tumpukan yang terfragmentasi membuang-buang memori dan menambah waktu yang dibutuhkan untuk mengalokasikan memori.
sumber
int vla[n]; if(test()) { struct LargeStruct s; int i; }
:: tumpukan offsets
tidak akan diketahui pada waktu kompilasi, dan juga diragukan apakah kompiler akan memindahkan penyimpanani
keluar dari ruang lingkup dalam untuk memperbaiki tumpukan offset. Jadi kode mesin tambahan diperlukan karena tipuan, dan ini juga dapat memakan register, penting pada perangkat keras PC. Jika Anda ingin kode contoh dengan output perakitan kompiler disertakan, silakan ajukan pertanyaan terpisah;)s
dani
ketika fungsi dimasukkan, sebelumtest
dipanggil atauvla
dialokasikan, sebagai alokasi untuks
dani
tidak memiliki efek samping. (Dan, pada kenyataannya,i
bahkan mungkin ditempatkan dalam register, artinya tidak ada "alokasi" sama sekali.) Tidak ada jaminan kompiler untuk urutan alokasi pada stack, atau bahkan bahwa stack digunakan.