Contoh Array Panjang Variabel C yang bagus [ditutup]

9

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:

  1. Dapatkan keunggulan kinerja yang mudah diukur (10% mungkin) dibandingkan menggunakan heap.
  2. Tidak memiliki solusi yang baik, yang tidak perlu seluruh array sama sekali.
  3. Sebenarnya mendapat manfaat dari menggunakan ukuran dinamis, bukan ukuran maksimum tetap.
  4. Tidak mungkin menyebabkan stack overflow dalam skenario penggunaan normal.
  5. 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 nadalah 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.

Hyde
sumber
1
Agak spekulatif (karena ini adalah palu yang mencari paku), tetapi mungkin alloca()benar-benar akan lebih cemerlang malloc()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.
chrisaycock
1
@ chrisaycock Ya, sangat banyak palu mencari paku, tetapi palu yang benar-benar ada (baik itu C99 VLA atau yang tidak benar-benar-dalam-standar apa pun alloca, yang saya pikir pada dasarnya adalah hal yang sama). Tetapi hal multithreaded itu baik, mengedit pertanyaan untuk memasukkannya!
hyde
Salah satu kelemahan VLA adalah tidak ada mekanisme untuk mendeteksi kegagalan alokasi; jika tidak ada cukup memori, perilaku tidak terdefinisi. (Hal yang sama berlaku untuk array ukuran tetap - dan untuk alokasi ().)
Keith Thompson
@KeithThompson Yah, tidak ada jaminan bahwa malloc / baru mendeteksi kegagalan alokasi, misalnya, lihat Catatan untuk halaman manual malloc Linux ( linux.die.net/man/3/malloc ).
hyde
@ Hyde: Dan masih bisa diperdebatkan apakah mallocperilaku Linux sesuai dengan standar C.
Keith Thompson

Jawaban:

9

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 mindan max.

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, vlasolusi 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 coutbit saat runtime ... Tapi saya tidak berpikir itu benar-benar inti nya.

Saat menjalankan varian khusus ini, saya mendapatkan sekitar 10% perbedaan antara func1(VLA) dan func2(std :: vector).

count = 9884
func1 time in clocks per iteration 7048685
count = 9884
func2 time in clocks per iteration 7661067
count = 9884
func3 time in clocks per iteration 8971878

Ini dikompilasi dengan: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Berikut kodenya:

#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>

using namespace std;

const int SIZE = 1000000;

uint64_t g_val[SIZE];


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


int func1(int x)
{
    int v[x];

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}

int func2(int x)
{
    vector<int> v;
    v.resize(x); 

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

int func3(int x)
{
    vector<int> v;

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v.push_back(rand() % x);
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

void runbench(int (*f)(int), const char *name)
{
    srand(41711211);
    uint64_t long t = rdtsc();
    int count = 0;
    for(int i = 20; i < 200; i++)
    {
        count += f(i);
    }
    t = rdtsc() - t;
    cout << "count = " << count << endl;
    cout << name << " time in clocks per iteration " << dec << t << endl;
}

struct function
{
    int (*func)(int);
    const char *name;
};


#define FUNC(f) { f, #f }

function funcs[] = 
{
    FUNC(func1),
    FUNC(func2),
    FUNC(func3),
}; 


int main()
{
    for(size_t i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
    {
        runbench(funcs[i].func, funcs[i].name);
    }
}
Mats Petersson
sumber
Wow, sistem saya menunjukkan peningkatan 30% pada versi VLA std::vector.
chrisaycock
1
Nah, coba dengan kisaran ukuran sekitar 5-15 bukan 20-200, dan Anda mungkin akan memiliki peningkatan 1000% atau lebih. [Juga tergantung pada pilihan compiler - Saya akan mengedit kode di atas untuk menampilkan opsi compiler saya di gcc]
Mats Petersson
Saya baru saja menambahkan func3yang menggunakan v.push_back(rand())alih-alih v[i] = rand();dan menghilangkan kebutuhan resize(). Dibutuhkan sekitar 10% lebih lama dibandingkan dengan yang menggunakan resize(). [Tentu saja, dalam prosesnya, saya menemukan bahwa penggunaan v[i]adalah kontributor utama pada waktu fungsi - saya sedikit terkejut tentang itu].
Mats Petersson
1
@ MikeBrown Apakah Anda tahu std::vectorimplementasi aktual yang akan menggunakan VLA / alloca, atau hanya spekulasi?
hyde
3
Vektor memang menggunakan array secara internal, tetapi sejauh yang saya mengerti, tidak memiliki cara untuk menggunakan VLA. Saya percaya contoh saya menunjukkan bahwa VLA berguna dalam beberapa (bahkan mungkin banyak) kasus di mana jumlah datanya kecil. Bahkan jika vektor menggunakan VLA, itu akan menjadi setelah upaya tambahan dalam vectorimplementasi.
Mats Petersson
0

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.

Michael Brown
sumber
Saya tidak yakin saya memahami referensi Anda ke daftar tertaut, jadi saya menambahkan bagian ke pertanyaan, menjelaskan konteksnya sedikit lebih banyak dan menambahkan contoh alternatif yang saya pikirkan.
hyde
Mengapa std::vectorskala 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 standar alloca(). Apa pun yang membutuhkan penyimpanan tumpukan (itu hidup sekitar setelah fungsi kembali) atau realloc()(array mengubah ukurannya sendiri) akan melarang VLA.
chrisaycock
@chrisaycock C ++ tidak memiliki fungsi realloc () karena beberapa alasan, dengan asumsi memori dialokasikan dengan [] baru. Bukankah itu alasan utama mengapa std :: vector harus menggunakan skala?
@Lundin Apakah C ++ skala vektor dengan kekuatan sepuluh? Saya baru saja mendapat kesan bahwa Mike Brown benar-benar bingung dengan pertanyaan itu, mengingat referensi daftar tertaut. (Dia juga membuat pernyataan sebelumnya yang menyiratkan C99 VLA hidup di heap.)
chrisaycock
@ Ya ampun, aku tidak menyadari itu yang kamu bicarakan. Saya pikir Anda maksud struktur data berbasis tumpukan lainnya. Menarik sekarang karena Anda telah menambahkan klarifikasi ini. Saya tidak cukup ahli C ++ untuk memberi tahu Anda perbedaan di antara mereka.
Michael Brown
0

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_valada 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:

float vals[256]; /* I hope we never get more! */

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 nilai nke 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 ndi tumpukan dan menelepon mallocmungkin 5-10 instruksi.) Mungkin jauh lebih buruk jika ada jumlah data yang wajar di heap. Sama sekali tidak mengejutkan saya untuk melihat kasus di mana malloc100x hingga 1000x lebih lambat dalam program nyata.

Tentu saja, maka Anda juga memiliki beberapa dampak kinerja dengan pencocokan free, mungkin sama besarnya dengan mallocpanggilan.

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.

Gort the Robot
sumber
Tentang contoh Wikipedia: ini bisa menjadi bagian dari contoh yang baik, tetapi tanpa konteks, lebih banyak kode di sekitarnya, itu tidak benar-benar menunjukkan salah satu dari 5 hal yang disebutkan dalam pertanyaan saya. Kalau tidak ya, saya setuju dengan penjelasan Anda. Meskipun satu hal yang perlu diingat: menggunakan VLA dapat memiliki biaya untuk mengakses variabel lokal, dengan mereka offset semua variabel lokal tidak perlu diketahui pada waktu kompilasi, jadi harus berhati-hati untuk tidak mengganti satu kali heap cost dengan penalti loop batin untuk setiap iterasi.
hyde
Um ... tidak yakin apa yang Anda maksud. Deklarasi variabel lokal adalah operasi tunggal dan setiap kompiler yang sedikit dioptimalkan akan menarik alokasi keluar dari loop dalam. Tidak ada "biaya" khusus dalam mengakses variabel lokal, tentu saja tidak ada yang meningkatkan VLA.
Gort the Robot
Contoh konkret int vla[n]; if(test()) { struct LargeStruct s; int i; }:: tumpukan offset stidak akan diketahui pada waktu kompilasi, dan juga diragukan apakah kompiler akan memindahkan penyimpanan ikeluar 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;)
hyde
Kompiler tidak harus mengalokasikan dalam urutan yang ditemui dalam kode, dan tidak masalah jika ruang dialokasikan dan tidak digunakan. Pengoptimal yang pintar akan mengalokasikan ruang untuk sdan iketika fungsi dimasukkan, sebelum testdipanggil atau vladialokasikan, sebagai alokasi untuk sdan itidak memiliki efek samping. (Dan, pada kenyataannya, ibahkan mungkin ditempatkan dalam register, artinya tidak ada "alokasi" sama sekali.) Tidak ada jaminan kompiler untuk urutan alokasi pada stack, atau bahkan bahwa stack digunakan.
Gort the Robot
(menghapus komentar yang salah karena kesalahan bodoh)
hyde