Restablecer la matriz C int a cero: ¿la forma más rápida?

Suponiendo que tenemos un T myarray[100]con T = int, unsigned int, long long int o unsigned long long int, cuál es la forma más rápida de restablecer todo su contenido a cero (no solo para la inicialización sino para restablecer el contenido varias veces en mi programa) ? ¿Quizás con memset?

La misma pregunta para una matriz dinámica como T *myarray = new T[100].

memset(from <string.h>) es probablemente la forma estándar más rápida, ya que generalmente es una rutina escrita directamente en ensamblador y optimizada a mano.

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

Por cierto, en C ++ la forma idiomática sería usar std::fill(from <algorithm>):

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

que puede optimizarse automáticamente en a memset; Estoy bastante seguro de que funcionará tan rápido como memsetpara ints, mientras que puede funcionar un poco peor para tipos más pequeños si el optimizador no es lo suficientemente inteligente. Aún así, en caso de duda, perfil.

Esta pregunta, aunque bastante antigua, necesita algunos puntos de referencia, ya que no pide la forma más idiomática, ni la forma en que se puede escribir en el menor número de líneas, sino la forma más rápida. Y es una tontería responder esa pregunta sin algunas pruebas reales. Así que comparé cuatro soluciones, memset versus std :: fill versus CERO de la respuesta de AnT versus una solución que hice usando intrínsecos AVX.

Tenga en cuenta que esta solución no es genérica, solo funciona con datos de 32 o 64 bits. Por favor comente si este código está haciendo algo incorrecto.

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

No afirmaré que este es el método más rápido, ya que no soy un experto en optimización de bajo nivel. Más bien es un ejemplo de una implementación dependiente de la arquitectura correcta que es más rápida que Memset.

Ahora, sobre los resultados. Calculé el rendimiento para matrices de tamaño 100 int y long long, asignadas tanto estática como dinámicamente, pero con la excepción de msvc, que eliminó el código muerto en matrices estáticas, los resultados fueron extremadamente comparables, por lo que mostraré solo el rendimiento de matriz dinámica. Las marcas de tiempo son ms para 1 millón de iteraciones, utilizando la función de reloj de baja precisión de time.h.

clang 3.8 (Usando la interfaz clang-cl, indicadores de optimización = / 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 (indicadores de optimización: -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 (indicadores de optimización: / 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

Hay muchas cosas interesantes sucediendo aquí: llvm matando a gcc, las típicas optimizaciones irregulares de MSVC (hace una eliminación impresionante de código muerto en matrices estáticas y luego tiene un rendimiento terrible para el relleno). Aunque mi implementación es significativamente más rápida, esto puede deberse solo a que reconoce que el borrado de bits tiene mucho menos sobrecarga que cualquier otra operación de configuración.

La implementación de Clang merece más atención, ya que es significativamente más rápida. Algunas pruebas adicionales muestran que su conjunto de memorias está de hecho especializado para memsets de cero o distintos de cero para una matriz de 400 bytes que son mucho más lentos (~ 220ms) y son comparables a los de gcc. Sin embargo, la configuración de memoria distinta de cero con una matriz de 800 bytes no hace ninguna diferencia de velocidad, lo que probablemente sea la razón por la que en ese caso, su configuración de memoria tiene un rendimiento peor que mi implementación: la especialización es solo para matrices pequeñas y el límite es de alrededor de 800 bytes. También tenga en cuenta que gcc 'fill' y 'ZERO' no optimizan memset (mirando el código generado), gcc simplemente está generando código con características de rendimiento idénticas.

Conclusión: memset no está realmente optimizado para esta tarea tan bien como la gente pretendería (de lo contrario, gcc, msvc y memset de llvm tendrían el mismo rendimiento). Si el rendimiento importa, entonces Memset no debería ser una solución final, especialmente para estos arreglos de tamaño medio incómodos, porque no está especializado en la eliminación de bits y no está optimizado a mano mejor que el compilador por sí solo.

De memset():

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

Puede usar sizeof(myarray)si myarrayse conoce el tamaño de en tiempo de compilación. De lo contrario, si está utilizando una matriz de tamaño dinámico, como la obtenida a través de malloco new, deberá realizar un seguimiento de la longitud.

Puede usar memset, pero solo porque nuestra selección de tipos está restringida a tipos integrales.

En el caso general en C, tiene sentido implementar una 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)

Esto le dará una funcionalidad similar a C ++ que le permitirá "restablecer a ceros" una serie de objetos de cualquier tipo sin tener que recurrir a hacks como memset. Básicamente, esta es una plantilla de función C análoga a C ++, excepto que debe especificar el argumento de tipo explícitamente.

Además de eso, puede crear una "plantilla" para matrices no deterioradas

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

En su ejemplo, se aplicaría como

int a[100];

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

También vale la pena señalar que específicamente para objetos de tipos escalares se puede implementar una macro independiente del tipo

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

y

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

convirtiendo el ejemplo anterior en

 int a[100];

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

Para una declaración estática, creo que podría usar:

T myarray[100] = {0};

Para la declaración dinámica sugiero la misma manera: memset

zero(myarray); es todo lo que necesita en C ++.

Simplemente agregue esto a un encabezado:

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

Aquí está la función 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);
}

Puedes llamarlo así:

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

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

Arriba hay más forma de C ++ 11 que usar memset. También obtiene un error de tiempo de compilación si usa una matriz dinámica especificando el tamaño.