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

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].

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.

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.

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ść.

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

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

T myarray[100] = {0};

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

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

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.