Zresetuj tablicę int C do zera: najszybszy sposób?

102

Zakładając, że mamy a T myarray[100]z T = int, unsigned int, long long int lub unsigned long long int, jaki jest najszybszy sposób na zresetowanie całej jego zawartości do zera (nie tylko do inicjalizacji, ale do resetowania zawartości kilka razy w moim programie) ? Może z memsetem?

To samo pytanie dla tablicy dynamicznej, takiej jak T *myarray = new T[100].

Vincent
źródło
16
@BoPersson: cóż, new to C ++ ...
Matteo Italia
@Matteo - cóż, tak. Nie wpłynęło to zbytnio na odpowiedzi (do tej pory :-).
Bo Persson,
3
@BoPersson: Źle się czułem, mówiąc tylko o tym, memsetże C ++ jest w jakiś sposób zaangażowany ... :)
Matteo Italia
2
W nowoczesnym kompilatorze nie można pokonać prostej forpętli. Ale, co zaskakujące, możesz zrobić znacznie gorzej, starając się być sprytnym.
David Schwartz,
Użyj struktury i umieść w niej tablicę. Utwórz instancję składającą się z samych zer. Użyj tego, aby wyzerować innych, których tworzysz. To dobrze działa. Nie zawiera, nie ma funkcji, dość szybko.
Xofo

Odpowiedzi:

170

memset(from <string.h>) jest prawdopodobnie najszybszym standardowym sposobem, ponieważ zwykle jest to procedura napisana bezpośrednio w asemblerze i zoptymalizowana ręcznie.

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

Nawiasem mówiąc, w C ++ idiomatycznym sposobem byłoby użycie std::fill(from <algorithm>):

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

który może zostać automatycznie zoptymalizowany do postaci memset; Jestem pewien, że będzie działać tak szybko, jak memsetdla ints, podczas gdy może działać nieco gorzej dla mniejszych typów, jeśli optymalizator nie jest wystarczająco inteligentny. Mimo to, jeśli masz wątpliwości, podaj profil.

Matteo Italia
źródło
10
Począwszy od normy ISO C z 1999 r., Nie było w rzeczywistości gwarantowane memsetustawienie liczby całkowitej na 0; nie było konkretnego stwierdzenia, którego reprezentacją są wszystkie bity-zero 0. Taką gwarancję dodano w sprostowaniu technicznym zawartym w normie ISO C z 2011 roku. Uważam, że wszystkie bity-zero poprawną reprezentacją 0wszystkich typów liczb całkowitych we wszystkich istniejących implementacjach C i C ++, dlatego komisja mogła dodać to wymaganie. (Nie ma podobnej gwarancji dla typów zmiennoprzecinkowych lub wskaźnikowych.)
Keith Thompson
3
Dodając do komentarza @ KeithThompsona: ta gwarancja została dodana do 6.2.6.2/5 jako zwykły tekst w TC2 (2004); jednak jeśli nie ma bitów wypełniających, to 6.2.6.2/1 i / 2 już gwarantowały, że wszystkie bity-zero były 0. (Przy wypełnianiu bitów istnieje możliwość, że wszystkie bity-zero mogą być reprezentacją pułapki). Ale w każdym razie TC powinien potwierdzić i wymienić wadliwy tekst, więc od 2004 roku powinniśmy postępować tak, jakby C99 zawsze zawierał ten tekst.
MM
W C, jeśli poprawnie przydzielisz tablicę dynamiczną , nie będzie różnicy między dwoma zestawami memów. Prawidłowa alokacja dynamiczna to int (*myarray)[N] = malloc(sizeof(*myarray));.
Lundin
@Lundin: oczywiście - jeśli wiesz w czasie kompilacji, jak duże Njest, ale w zdecydowanej większości przypadków, jeśli używasz malloc, wiedziałeś tylko w czasie wykonywania.
Matteo Italia
@MatteoItalia Od 1999 roku mamy VLA.
Lundin,
20

To pytanie, choć dość stare, wymaga pewnych wzorców, ponieważ wymaga nie najbardziej idiomatycznego sposobu lub sposobu, w jaki można zapisać jak najmniejszą liczbę wierszy, ale w najszybszy sposób. I głupio jest odpowiadać na to pytanie bez rzeczywistych testów. Porównałem więc cztery rozwiązania, memset vs. std :: fill vs. ZERO odpowiedzi AnT z rozwiązaniem, które stworzyłem przy użyciu funkcji AVX intrinsics.

Zauważ, że to rozwiązanie nie jest ogólne, działa tylko na danych 32- lub 64-bitowych. Prosimy o komentarz, jeśli ten kod działa nieprawidłowo.

#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;\
};\
}\
}

Nie twierdzę, że jest to najszybsza metoda, ponieważ nie jestem ekspertem od optymalizacji niskiego poziomu. Jest to raczej przykład poprawnej implementacji zależnej od architektury, która jest szybsza niż memset.

Teraz przejdźmy do wyników. Obliczyłem wydajność dla tablic int i long long o rozmiarze 100, zarówno przydzielonych statycznie, jak i dynamicznie, ale z wyjątkiem msvc, który eliminował martwy kod na tablicach statycznych, wyniki były niezwykle porównywalne, więc pokażę tylko wydajność tablicy dynamicznej. Oznaczenia czasu są ms dla 1 miliona iteracji, przy użyciu funkcji zegara o niskiej precyzji time.h.

clang 3.8 (Używając nakładki clang-cl, flagi optymalizacji = / 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 (flagi optymalizacji: -O3 -march = natywne -mtune = natywne -mavx):

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

msvc 2015 (flagi optymalizacji: / 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

Dzieje się tu wiele interesujących rzeczy: llvm zabijanie gcc, typowe nieregularne optymalizacje MSVC (robi imponującą eliminację martwego kodu na statycznych tablicach, a następnie ma okropną wydajność wypełniania). Chociaż moja implementacja jest znacznie szybsza, może to wynikać tylko z tego, że uznaje, że czyszczenie bitów ma znacznie mniejszy narzut niż jakakolwiek inna operacja ustawiania.

Wdrożenie Clanga zasługuje na dokładniejsze przyjrzenie się, ponieważ jest znacznie szybsze. Niektóre dodatkowe testy pokazują, że jego memset jest w rzeczywistości wyspecjalizowany dla zerowego - niezerowe zestawy memów dla tablicy 400-bajtowej są znacznie wolniejsze (~ 220 ms) i są porównywalne z gcc. Jednak niezerowe memsetting z tablicą 800-bajtową nie robi różnicy w szybkości, i prawdopodobnie dlatego w tym przypadku ich memset ma gorszą wydajność niż moja implementacja - specjalizacja dotyczy tylko małych tablic, a odcięcie wynosi około 800 bajtów. Zauważ również, że gcc 'fill' i 'ZERO' nie optymalizują się do memset (patrząc na wygenerowany kod), gcc po prostu generuje kod o identycznej charakterystyce wydajności.

Wniosek: memset nie jest tak naprawdę zoptymalizowany do tego zadania, jak ludzie by to udawali (w przeciwnym razie gcc i msvc oraz memset llvm miałyby taką samą wydajność). Jeśli wydajność ma znaczenie, to memset nie powinien być ostatecznym rozwiązaniem, szczególnie w przypadku tych niewygodnych tablic średniej wielkości, ponieważ nie jest wyspecjalizowany w czyszczeniu bitów i nie jest zoptymalizowany ręcznie ani lepiej, niż może to zrobić sam kompilator.

Benzoes
źródło
4
Benchmark bez kodu i bez wzmianki o wersji kompilatora i zastosowanych opcji? Hmm ...
Marc Glisse
Miałem już wersje kompilatora (były po prostu trochę ukryte) i właśnie dodałem odpowiednie używane opcje.
Benjamin,
niepoprawny argument typu jednoargumentowego „*” (ma „size_t {aka unsigned int}”) |
Piotr Wasilewicz
Będąc tak hojnym, by napisać własną zoptymalizowaną metodę zerowania - czy mógłbyś poświęcić kilka słów na temat JAK to działa i DLACZEGO jest szybsze? kod nie wymaga wyjaśnień.
Motti Shneor
1
@MottiShneor Wygląda na bardziej skomplikowane niż w rzeczywistości. Rejestr AVX ma rozmiar 32 bajtów. Więc oblicza, ile wartości apasuje do rejestru. Następnie wykonuje pętlę po wszystkich 32-bajtowych blokach, które powinny zostać całkowicie nadpisane przy użyciu arytmetyki wskaźników ( (float *)((a)+x)). Dwie _mm256funkcje wewnętrzne (zaczynające się od ) po prostu tworzą zainicjowany zerem rejestr 32-bajtowy i przechowują go w bieżącym wskaźniku. To są pierwsze 3 wiersze. Reszta obsługuje tylko wszystkie specjalne przypadki, w których ostatni 32-bajtowy blok nie powinien zostać całkowicie nadpisany. Jest szybszy dzięki wektoryzacji. - Mam nadzieję że to pomogło.
wychmaster
11

Od memset():

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

Możesz użyć, sizeof(myarray)jeśli rozmiar myarrayjest znany w czasie kompilacji. W przeciwnym razie, jeśli używasz tablicy o rozmiarze dynamicznym, takiej jak uzyskana za pośrednictwem malloclub new, będziesz musiał śledzić długość.

Alex Reynolds
źródło
2
sizeof zadziała nawet jeśli rozmiar tablicy nie jest znany w czasie kompilacji. (oczywiście tylko wtedy, gdy jest tablicą)
asaelr
2
@asaelr: w C ++ sizeofjest zawsze oceniany w czasie kompilacji (i nie może być używany z VLA). W C99 może to być wyrażenie środowiska wykonawczego w przypadku VLA.
Ben Voigt,
@BenVoigt Cóż, pytanie dotyczy obu ci c++. Skomentowałem odpowiedź Alexa, która mówi: „Możesz użyć sizeof (myarray), jeśli rozmiar myarray jest znany w czasie kompilacji”.
asaelr
2
@asaelr: A w C ++ jest całkowicie poprawny. Twój komentarz nie mówił nic o C99 ani VLA, więc chciałem to wyjaśnić.
Ben Voigt,
5

Możesz użyć memset, ale tylko dlatego, że nasz wybór typów jest ograniczony do typów całkowitych.

W ogólnym przypadku w C ma sens implementacja makra

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

To da ci funkcjonalność podobną do C ++, która pozwoli ci "zresetować do zera" tablicę obiektów dowolnego typu bez konieczności uciekania się do takich hacków memset. Zasadniczo jest to analog C ++ do szablonu funkcji, z tą różnicą, że musisz jawnie określić argument typu.

Oprócz tego możesz zbudować „szablon” dla niezepsutych tablic

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

W twoim przykładzie zostanie zastosowany jako

int a[100];

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

Warto również zauważyć, że specjalnie dla obiektów typu skalarnego można zaimplementować makro niezależne od typu

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

i

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

zmieniając powyższy przykład w

 int a[100];

 ZERO(a, 100);
 // or
 ZERO_A(a);
Mrówka
źródło
1
Chciałbym pominąć ;po while(0), tak można nazwać ZERO(a,n);, +1 wielką odpowiedź
0x90
@ 0x90: Tak, masz absolutną rację. Cały sens do{}while(0)idiomu nie wymaga ;definicji makra. Naprawiony.
AnT
3

Myślę, że do deklaracji statycznej można użyć:

T myarray[100] = {0};

W przypadku deklaracji dynamicznej proponuję ten sam sposób: memset

Bruno Soares
źródło
2
Pytanie brzmi: „Nie tylko do inicjalizacji”.
Ben Voigt,
2

zero(myarray); to wszystko, czego potrzebujesz w C ++.

Po prostu dodaj to do nagłówka:

template<typename T, size_t SIZE> inline void zero(T(&arr)[SIZE]){
    memset(arr, 0, SIZE*sizeof(T));
}
Navin
źródło
1
To jest niepoprawne, spowoduje wyczyszczenie SIZE bajtów. 'memset (arr, 0, SIZE * sizeof (T));' byłoby poprawne.
Kornel Kisielewicz
@KornelKisielewicz D'oh! Mam nadzieję, że nikt nie kopiował i nie wklejał tej funkcji w ciągu ostatnich 1,5 roku :(
Navin
1
mam nadzieję, że nie, skomentowałem, bo google mnie tu sprowadziło :)
Kornel Kisielewicz
1
Zauważ, że ta funkcja zerojest również poprawna np. Tak, T=char[10]jak mogłoby być w przypadku, gdy arrargumentem jest tablica wielowymiarowa, np char arr[5][10].
mandragora
1
Tak, przetestowałem wiele przypadków z gcc 4.7.3. Uważam, że dobrze byłoby to odnotować w przypadku tej odpowiedzi, ponieważ w przeciwnym razie musiałbyś mieć specjalizacje szablonów dla każdej liczby wymiarów tablicy. Inne odpowiedzi również nie generalizują, na przykład ARRAY_SIZEmakro, które podaje niewłaściwy rozmiar, jeśli jest używane w wielowymiarowej tablicy, być może lepsza byłaby nazwa ARRAY_DIM<n>_SIZE.
mandragora
1

Oto funkcja, której używam:

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);
}

Możesz to nazwać tak:

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

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

Powyżej jest bardziej C ++ 11 niż użycie memset. Otrzymujesz również błąd czasu kompilacji, jeśli używasz tablicy dynamicznej z określeniem rozmiaru.

Shital Shah
źródło
oryginalne pytanie dotyczy C, a nie C ++, stąd std :: fill nie może być poprawną odpowiedzią
Motti Shneor