Redefinir a matriz C int para zero: a maneira mais rápida?

Supondo que temos a T myarray[100]com T = int, unsigned int, long long int ou unsigned long long int, qual é a maneira mais rápida de redefinir todo o seu conteúdo para zero (não apenas para inicialização, mas para redefinir o conteúdo várias vezes em meu programa) ? Talvez com o memset?

Mesma pergunta para um array dinâmico como T *myarray = new T[100].

memset(de <string.h>) é provavelmente a forma padrão mais rápida, já que geralmente é uma rotina escrita diretamente em assembly e otimizada à mão.

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

A propósito, em C ++ a forma idiomática seria usar std::fill(de <algorithm>):

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

que pode ser otimizado automaticamente em um memset; Tenho certeza de que funcionará tão rápido quanto memsetpara ints, embora possa ter um desempenho um pouco pior para tipos menores se o otimizador não for inteligente o suficiente. Ainda assim, em caso de dúvida, perfil.

Esta questão, embora bastante antiga, precisa de alguns benchmarks, pois pede não a forma mais idiomática, ou a forma que pode ser escrita com o menor número de linhas, mas a forma mais rápida. E é bobagem responder a essa pergunta sem alguns testes reais. Então, comparei quatro soluções, memset vs. std :: fill vs. ZERO da resposta da AnT vs. uma solução que fiz usando intrínseco AVX.

Observe que esta solução não é genérica, ela só funciona com dados de 32 ou 64 bits. Por favor, comente se este código está fazendo algo incorreto.

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

Não vou afirmar que esse é o método mais rápido, já que não sou um especialista em otimização de baixo nível. Em vez disso, é um exemplo de uma implementação dependente de arquitetura correta que é mais rápida do que o memset.

Agora, vamos aos resultados. Calculei o desempenho para o tamanho 100 int e arrays longos longos, tanto estaticamente quanto dinamicamente alocados, mas com exceção do msvc, que eliminou o código morto em arrays estáticos, os resultados foram extremamente comparáveis, então mostrarei apenas o desempenho do array dinâmico. As marcações de tempo são ms para 1 milhão de iterações, usando a função de relógio de baixa precisão de time.h.

clang 3.8 (usando a interface clang-cl, sinalizadores de otimização = / 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 (sinalizadores de otimização: -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 (sinalizadores de otimização: / 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

Há muita coisa interessante acontecendo aqui: llvm kill gcc, as otimizações irregulares típicas do MSVC (ele faz uma eliminação impressionante de código morto em arrays estáticos e então tem um desempenho péssimo para preencher). Embora minha implementação seja significativamente mais rápida, isso pode ser apenas porque ela reconhece que a limpeza de bits tem muito menos sobrecarga do que qualquer outra operação de configuração.

A implementação do Clang merece mais atenção, pois é significativamente mais rápida. Alguns testes adicionais mostram que seu memset é de fato especializado para zero - diferente de zero memsets para matriz de 400 bytes são muito mais lentos (~ 220ms) e são comparáveis ​​aos do gcc. No entanto, o memsetting diferente de zero com um array de 800 bytes não faz diferença na velocidade, o que provavelmente é porque, nesse caso, o memset deles tem pior desempenho do que a minha implementação - a especialização é apenas para pequenos arrays e o corte está em torno de 800 bytes. Observe também que gcc 'fill' e 'ZERO' não estão otimizando para memset (olhando para o código gerado), gcc está simplesmente gerando código com características de desempenho idênticas.

Conclusão: o memset não é realmente otimizado para essa tarefa tão bem quanto as pessoas fingem que está (caso contrário, o memset do gcc e do msvc e do llvm teria o mesmo desempenho). Se o desempenho é importante, o memset não deve ser a solução final, especialmente para esses arrays de tamanho médio desajeitados, porque não é especializado para limpeza de bits e não é otimizado manualmente melhor do que o compilador pode fazer sozinho.

De memset():

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

Você pode usar sizeof(myarray)se o tamanho de myarrayfor conhecido em tempo de compilação. Caso contrário, se você estiver usando uma matriz de tamanho dinâmico, como obtida por meio de mallocou new, será necessário controlar o comprimento.

Você pode usar memset, mas apenas porque nossa seleção de tipos é restrita a tipos integrais.

No caso geral em C, faz sentido implementar uma macro

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

Isso lhe dará uma funcionalidade semelhante à do C ++ que permitirá que você "redefina para zeros" uma série de objetos de qualquer tipo sem ter que recorrer a hacks memset. Basicamente, este é um C análogo ao template de função C ++, exceto que você deve especificar o argumento type explicitamente.

Além disso, você pode construir um "modelo" para matrizes não deterioradas

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

Em seu exemplo, seria aplicado como

int a[100];

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

Também é importante notar que especificamente para objetos de tipos escalares, pode-se implementar uma macro independente de tipo

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

e

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

transformando o exemplo acima em

 int a[100];

 ZERO(a, 100);
 // or
 ZERO_A(a);

Para declaração estática, acho que você poderia usar:

T myarray[100] = {0};

Para declaração dinâmica, sugiro da mesma forma: memset

zero(myarray); é tudo o que você precisa em C ++.

Basta adicionar a um cabeçalho:

template<typename T, size_t SIZE> inline void zero(T(&arr)[SIZE]){
    memset(arr, 0, SIZE*sizeof(T));
}

Esta é a função que uso:

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

Você pode chamá-lo assim:

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

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

Acima está mais em C ++ 11 do que usando memset. Além disso, você obterá um erro de tempo de compilação se usar uma matriz dinâmica com a especificação do tamanho.