Reset C int array ke nol: cara tercepat?

102

Dengan asumsi bahwa kita memiliki T myarray[100]dengan T = int, unsigned int, long long int atau unsigned long long int, apa cara tercepat untuk mengatur ulang semua kontennya menjadi nol (tidak hanya untuk inisialisasi tetapi untuk mengatur ulang konten beberapa kali dalam program saya) ? Mungkin dengan memset?

Pertanyaan yang sama untuk array dinamis seperti T *myarray = new T[100].

Vincent
sumber
16
@BoPersson: ya, new adalah C ++ ...
Matteo Italia
@ Matteo - yah, ya. Tidak banyak mempengaruhi jawaban (sampai sekarang :-).
Bo Persson
3
@BoPersson: Saya merasa tidak enak berbicara hanya tentang memsetketika C ++ entah bagaimana terlibat ... :)
Matteo Italia
2
Pada kompiler modern, Anda tidak bisa mengalahkan forloop sederhana . Namun, yang mengejutkan, Anda dapat melakukan jauh lebih buruk dengan mencoba menjadi pintar.
David Schwartz
Gunakan struct dan tempelkan array di dalamnya. Buat instance yang semuanya nol. Gunakan itu untuk menghilangkan orang lain yang Anda buat. Ini bekerja dengan baik. Tidak termasuk, tidak ada fungsi, cukup cepat.
Xofo

Jawaban:

170

memset(dari <string.h>) mungkin adalah cara standar tercepat, karena biasanya ini adalah rutinitas yang ditulis langsung dalam rakitan dan dioptimalkan dengan tangan.

memset(myarray, 0, sizeof(myarray)); // for automatically-allocated arrays
memset(myarray, 0, N*sizeof(*myarray)); // for heap-allocated arrays, where N is the number of elements

Ngomong-ngomong, di C ++ cara idiomatiknya adalah menggunakan std::fill(dari <algorithm>):

std::fill(myarray, myarray+N, 0);

yang dapat dioptimalkan secara otomatis menjadi memset; Aku cukup yakin bahwa itu akan bekerja secepat memsetuntuk ints, sementara itu mungkin melakukan sedikit lebih buruk untuk jenis yang lebih kecil jika optimizer tidak cukup pintar. Namun, jika ragu, profil.

Matteo Italia
sumber
10
Pada standar ISO C 1999, sebenarnya tidak ada jaminan yang memsetakan menetapkan integer ke 0; tidak ada pernyataan khusus bahwa semua-bit-nol adalah representasi dari 0. Sebuah Korrigendum Teknis menambahkan jaminan seperti itu, yang termasuk dalam standar ISO C 2011. Saya percaya bahwa all-bits-zero adalah representasi yang valid 0untuk semua tipe integer di semua implementasi C dan C ++ yang ada, itulah sebabnya panitia dapat menambahkan persyaratan itu. (Tidak ada jaminan serupa untuk tipe floating-point atau pointer.)
Keith Thompson
3
Menambah komentar @ KeithThompson: jaminan ini ditambahkan ke 6.2.6.2/5 dalam teks biasa di TC2 (2004); namun jika tidak ada bit padding maka 6.2.6.2/1 dan / 2 sudah menjamin bahwa all-bits-zero adalah 0. (Dengan bit padding, kemungkinan ada bahwa semua-bit-nol bisa menjadi representasi perangkap). Tetapi bagaimanapun juga, TC seharusnya mengakui dan mengganti teks yang rusak, jadi mulai tahun 2004 kami harus bertindak seolah-olah C99 selalu berisi teks ini.
MM
Di C, jika Anda mengalokasikan larik dinamis dengan benar , maka tidak akan ada perbedaan antara kedua memset. Alokasi dinamis yang benar akan menjadi int (*myarray)[N] = malloc(sizeof(*myarray));.
Lundin
@ Lundin: tentu saja - jika Anda tahu pada waktu kompilasi seberapa besar N, tetapi dalam sebagian besar kasus jika Anda menggunakan, mallocAnda hanya tahu pada waktu proses.
Matteo Italia
@MatteoItalia Kami telah memiliki VLA sejak tahun 1999.
Lundin
20

Pertanyaan ini, meskipun agak tua, membutuhkan beberapa tolok ukur, karena menanyakan cara yang tidak paling idiomatis, atau cara yang dapat ditulis dalam jumlah baris paling sedikit, tetapi cara tercepat . Dan konyol untuk menjawab pertanyaan itu tanpa pengujian yang sebenarnya. Jadi saya membandingkan empat solusi, memset vs. std :: fill vs. ZERO dari jawaban AnT vs solusi yang saya buat dengan menggunakan AVX intrinsics.

Perhatikan bahwa solusi ini tidak umum, ini hanya berfungsi pada data 32 atau 64 bit. Beri komentar jika kode ini melakukan kesalahan.

#include<immintrin.h>
#define intrin_ZERO(a,n){\
size_t x = 0;\
const size_t inc = 32 / sizeof(*(a));/*size of 256 bit register over size of variable*/\
for (;x < n-inc;x+=inc)\
    _mm256_storeu_ps((float *)((a)+x),_mm256_setzero_ps());\
if(4 == sizeof(*(a))){\
    switch(n-x){\
    case 3:\
        (a)[x] = 0;x++;\
    case 2:\
        _mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\
    case 1:\
        (a)[x] = 0;\
        break;\
    case 0:\
        break;\
    };\
}\
else if(8 == sizeof(*(a))){\
switch(n-x){\
    case 7:\
        (a)[x] = 0;x++;\
    case 6:\
        (a)[x] = 0;x++;\
    case 5:\
        (a)[x] = 0;x++;\
    case 4:\
        _mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\
    case 3:\
        (a)[x] = 0;x++;\
    case 2:\
        ((long long *)(a))[x] = 0;break;\
    case 1:\
        (a)[x] = 0;\
        break;\
    case 0:\
        break;\
};\
}\
}

Saya tidak akan mengklaim bahwa ini adalah metode tercepat, karena saya bukan ahli pengoptimalan tingkat rendah. Melainkan merupakan contoh implementasi dependen arsitektur yang benar yang lebih cepat daripada memset.

Sekarang, ke hasilnya. Saya menghitung kinerja untuk array ukuran 100 int dan panjang, baik secara statis maupun dinamis, tetapi dengan pengecualian D3D, yang melakukan penghapusan kode mati pada array statis, hasilnya sangat sebanding, jadi saya hanya akan menampilkan kinerja array dinamis. Penandaan waktu adalah ms untuk 1 juta iterasi, menggunakan fungsi jam presisi rendah time.h.

clang 3.8 (Menggunakan frontend clang-cl, flag pengoptimalan = / OX / arch: AVX / Oi / Ot)

int:
memset:      99
fill:        97
ZERO:        98
intrin_ZERO: 90

long long:
memset:      285
fill:        286
ZERO:        285
intrin_ZERO: 188

gcc 5.1.0 (tanda pengoptimalan: -O3 -march = native -mtune = native -mavx):

int:
memset:      268
fill:        268
ZERO:        268
intrin_ZERO: 91
long long:
memset:      402
fill:        399
ZERO:        400
intrin_ZERO: 185

msvc 2015 (tanda pengoptimalan: / OX / arch: AVX / Oi / Ot):

int
memset:      196
fill:        613
ZERO:        221
intrin_ZERO: 95
long long:
memset:      273
fill:        559
ZERO:        376
intrin_ZERO: 188

Ada banyak hal menarik yang terjadi di sini: llvm kill gcc, optimasi jerawatan khas MSVC (ia melakukan penghapusan kode mati yang mengesankan pada array statis dan kemudian memiliki kinerja yang buruk untuk diisi). Meskipun implementasi saya jauh lebih cepat, ini mungkin hanya karena ia mengenali bahwa pembersihan bit memiliki overhead yang jauh lebih sedikit daripada operasi pengaturan lainnya.

Penerapan Clang patut dilihat, karena jauh lebih cepat. Beberapa pengujian tambahan menunjukkan bahwa memset-nya sebenarnya dikhususkan untuk memset nol - bukan nol untuk 400 byte array jauh lebih lambat (~ 220ms) dan sebanding dengan gcc. Namun, memset bukan nol dengan array 800 byte tidak membuat perbedaan kecepatan, yang mungkin mengapa dalam kasus itu, memset mereka memiliki kinerja yang lebih buruk daripada implementasi saya - spesialisasi hanya untuk array kecil, dan cuttoff tepat sekitar 800 byte. Perhatikan juga bahwa gcc 'fill' dan 'ZERO' tidak dioptimalkan untuk memset (melihat kode yang dihasilkan), gcc hanya menghasilkan kode dengan karakteristik performa yang identik.

Kesimpulan: memset tidak benar-benar dioptimalkan untuk tugas ini sebagaimana orang akan berpura-pura (jika tidak, memset gcc dan msvc dan llvm akan memiliki kinerja yang sama). Jika kinerja penting, maka memset tidak boleh menjadi solusi akhir, terutama untuk larik berukuran sedang yang canggung ini, karena tidak dikhususkan untuk pembersihan bit, dan tidak dioptimalkan secara manual lebih baik daripada yang dapat dilakukan oleh kompiler sendiri.

Benjamin
sumber
4
Tolok ukur tanpa kode dan tanpa menyebutkan versi kompiler dan opsi yang digunakan? Hmm ...
Marc Glisse
Saya sudah memiliki versi kompilator (hanya sedikit tersembunyi), dan baru saja menambahkan opsi yang berlaku yang digunakan.
Benjamin
argumen jenis tidak valid dari unary '*' (memiliki 'size_t {aka unsigned int}') |
Piotr Wasilewicz
Menjadi begitu murah hati untuk menulis metode zeroing Anda sendiri yang dioptimalkan - bisakah Anda menyisihkan beberapa kata tentang CARA kerjanya, dan MENGAPA ini lebih cepat? kode ini cukup jelas.
Motti Shneor
1
@MottiShneor Ini terlihat lebih rumit dari yang sebenarnya. Register AVX memiliki ukuran 32 byte. Jadi dia menghitung berapa nilai yang amasuk ke dalam register. Setelah itu, dia mengulang semua blok 32 byte, yang harus sepenuhnya ditimpa menggunakan pointer arithmetics ( (float *)((a)+x)). Dua intrinsik (dimulai dengan _mm256) hanya membuat register 32byte yang diinisialisasi nol dan menyimpannya ke penunjuk saat ini. Ini adalah 3 baris pertama. Sisanya hanya menangani semua kasus khusus di mana blok 32byte terakhir tidak boleh ditimpa sepenuhnya. Ini lebih cepat karena vektorisasi. - Saya harap itu membantu.
wychmaster
11

Dari memset():

memset(myarray, 0, sizeof(myarray));

Kamu bisa memakai sizeof(myarray) jika ukuran myarraydiketahui pada waktu kompilasi. Jika tidak, jika Anda menggunakan larik berukuran dinamis, seperti yang diperoleh melalui mallocatau new, Anda perlu melacak panjangnya.

Alex Reynolds
sumber
2
sizeof akan berfungsi meskipun ukuran array tidak diketahui pada waktu kompilasi. (tentu saja, hanya jika itu array)
asaelr
2
@asaelr: Dalam C ++, sizeofselalu dievaluasi pada waktu kompilasi (dan tidak dapat digunakan dengan VLA). Di C99, ini bisa menjadi ekspresi runtime dalam kasus VLA.
Ben Voigt
@BenVoigt Nah, pertanyaannya adalah tentang keduanya cdan c++. Saya mengomentari jawaban Alex, yang mengatakan "Anda dapat menggunakan sizeof (myarray) jika ukuran myarray diketahui pada saat kompilasi".
asaelr
2
@asaelr: Dan di C ++, dia sepenuhnya benar. Komentar Anda tidak mengatakan apa-apa tentang C99 atau VLA, jadi saya ingin menjelaskannya.
Ben Voigt
5

Kamu bisa memakai memset , tetapi hanya karena pilihan tipe kami dibatasi untuk tipe integral.

Dalam kasus umum di C masuk akal untuk mengimplementasikan makro

#define ZERO_ANY(T, a, n) do{\
   T *a_ = (a);\
   size_t n_ = (n);\
   for (; n_ > 0; --n_, ++a_)\
     *a_ = (T) { 0 };\
} while (0)

Ini akan memberi Anda fungsionalitas seperti C ++ yang akan memungkinkan Anda "menyetel ulang ke nol" serangkaian objek jenis apa pun tanpa harus menggunakan peretasan seperti memset . Pada dasarnya, ini adalah C analog dari template fungsi C ++, kecuali Anda harus menentukan argumen type secara eksplisit.

Selain itu, Anda dapat membuat "template" untuk array yang tidak membusuk

#define ARRAY_SIZE(a) (sizeof (a) / sizeof *(a))
#define ZERO_ANY_A(T, a) ZERO_ANY(T, (a), ARRAY_SIZE(a))

Dalam contoh Anda, ini akan diterapkan sebagai

int a[100];

ZERO_ANY(int, a, 100);
// or
ZERO_ANY_A(int, a);

Perlu juga dicatat bahwa khusus untuk objek dengan tipe skalar, seseorang dapat mengimplementasikan makro tipe-independen

#define ZERO(a, n) do{\
   size_t i_ = 0, n_ = (n);\
   for (; i_ < n_; ++i_)\
     (a)[i_] = 0;\
} while (0)

dan

#define ZERO_A(a) ZERO((a), ARRAY_SIZE(a))

mengubah contoh di atas menjadi

 int a[100];

 ZERO(a, 100);
 // or
 ZERO_A(a);
Semut
sumber
1
Saya akan menghilangkan ;setelah while(0), sehingga orang dapat menelepon ZERO(a,n);, +1 jawaban bagus
0x90
@ 0x90: Ya, Anda benar sekali. Inti dari do{}while(0)idiom membutuhkan no ;dalam definisi makro. Tetap.
AnT
3

Untuk deklarasi statis, saya pikir Anda bisa menggunakan:

T myarray[100] = {0};

Untuk deklarasi dinamis, saya menyarankan cara yang sama: memset

Bruno Soares
sumber
2
Pertanyaannya mengatakan: "Tidak hanya untuk inisialisasi".
Ben Voigt
2

zero(myarray); adalah semua yang Anda butuhkan di C ++.

Tambahkan saja ini ke tajuk:

template<typename T, size_t SIZE> inline void zero(T(&arr)[SIZE]){
    memset(arr, 0, SIZE*sizeof(T));
}
Navin
sumber
1
Ini salah, SIZE byte akan dihapus. 'memset (arr, 0, SIZE * sizeof (T));' akan benar.
Kornel Kisielewicz
@Keluarga_keluarga Saya harap tidak ada yang menyalin-tempel fungsi ini dalam 1,5 tahun terakhir :(
Navin
1
harap tidak, saya berkomentar karena google membawa saya ke sini :)
Kornel Kisielewicz
1
Perhatikan bahwa fungsi zeroini juga benar untuk misalnya T=char[10]seperti yang dapat terjadi ketika arrargumennya adalah larik multidimensi misalnya char arr[5][10].
mandrake
1
Ya, saya menguji sejumlah casing dengan gcc 4.7.3. Saya menemukan ini akan baik untuk diperhatikan untuk jawaban ini, karena Anda seharusnya memiliki spesialisasi template untuk setiap hitungan dimensi array. Jawaban lain juga tidak digeneralisasi, seperti ARRAY_SIZEmakro, yang memberikan ukuran yang salah jika digunakan pada array multidimensi, nama yang lebih baik mungkin adalah ARRAY_DIM<n>_SIZE.
mandrake
1

Inilah fungsi yang saya gunakan:

template<typename T>
static void setValue(T arr[], size_t length, const T& val)
{
    std::fill(arr, arr + length, val);
}

template<typename T, size_t N>
static void setValue(T (&arr)[N], const T& val)
{
    std::fill(arr, arr + N, val);
}

Anda bisa menyebutnya seperti ini:

//fixed arrays
int a[10];
setValue(a, 0);

//dynamic arrays
int *d = new int[length];
setValue(d, length, 0);

Di atas lebih banyak cara C ++ 11 daripada menggunakan memset. Anda juga mendapatkan kesalahan waktu kompilasi jika Anda menggunakan array dinamis dengan menentukan ukurannya.

Shital Shah
sumber
pertanyaan asli ada di C, bukan C ++, maka std :: fill tidak bisa menjadi jawaban yang tepat
Motti Shneor