Pregunta Restaure C int array 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)? ¿Tal vez con Memset?

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


73
2018-02-05 02:22


origen


Respuestas:


memset (de <string.h>) es probablemente la forma estándar más rápida, ya que generalmente es una rutina escrita directamente en el ensamblaje 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 (de <algorithm>)

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

cual mayo ser optimizado automáticamente en una memset; Estoy bastante seguro de que funcionará tan rápido como memset para 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í, cuando tienes dudas, perfil.


129
2018-02-05 02:25



De memset():

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

Puedes usar sizeof(myarray) si el tamaño de myarray es conocido 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 malloc o new, necesitarás hacer un seguimiento de la duración.


10
2018-02-05 02:25



Esta pregunta, aunque bastante antigua, necesita algunos puntos de referencia, ya que no pide la forma más idiomática, o la forma en que se puede escribir en el menor número de líneas, pero el lo más rápido camino. Y es tonto responder a esa pregunta sin algunas pruebas reales. Así que comparé cuatro soluciones, memset vs. std :: fill vs. ZERO de la respuesta de AnT frente a una solución que hice usando AVX intrinsics.

Tenga en cuenta que esta solución no es genérica, solo funciona con datos de 32 o 64 bits. 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, en los resultados. Calculé el rendimiento para matrices de tamaño 100 int y largo, asignadas estática y dinámicamente, pero a 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, usando la función de reloj de baja precisión de time.h.

clang 3.8 (Utilizando la interfaz de usuario 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 mucho más interesante aquí: llvm killing gcc, las típicas optimizaciones de manchas de MSVC (hace una impresionante eliminación de código muerto en arreglos estáticos y luego tiene un rendimiento horrible para el relleno). Aunque mi implementación es significativamente más rápida, esto solo puede deberse a que reconoce que la eliminación de bits tiene mucha 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 memset está de hecho especializado para zero - los conjuntos de datos que no son cero para una matriz de 400 bytes son mucho más lentos (~ 220 ms) y son comparables a los gcc. Sin embargo, la memetrificación distinta de cero con una matriz de 800 bytes no marca la diferencia de velocidad, lo que probablemente explica por qué su memset tiene peor rendimiento que mi implementación: la especialización es solo para arreglos pequeños y el corte es de aproximadamente 800 bytes. También tenga en cuenta que gcc 'fill' y 'ZERO' no se están optimizando para memset (mirando el código generado), gcc simplemente genera código con características de rendimiento idénticas.

Conclusión: memset no está realmente optimizado para esta tarea, así como la gente lo fingiría (de lo contrario, el memset gcc y msvc y llvm tendrían el mismo rendimiento). Si el rendimiento es importante, memset no debería ser una solución final, especialmente para estos arreglos torpes de tamaño medio, porque no está especializado para la eliminación de bits, y no está optimizado a mano mejor de lo que el compilador puede hacer por sí mismo.


10
2017-09-21 08:56



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

En 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á funcionalidad tipo C ++ que le permitirá "restablecer a cero" una matriz de objetos de cualquier tipo sin tener que recurrir a hacks como memset. Básicamente, este es un análogo C de la plantilla de función C ++, excepto que debe especificar el argumento tipo explícitamente.

Además de eso, puedes construir una "plantilla" para matrices no decaídas

#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 tipo escalar uno 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);

5
2018-06-15 21:58



Para la declaración estática, creo que podrías usar:

T myarray[100] = {0};

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


2
2018-02-06 12:52



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

Solo agrega esto en otro archivo:

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

1
2018-01-27 05:35



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

Por encima es más C ++ 11 que usar memset. También obtendrá un error de tiempo de compilación si utiliza una matriz dinámica con la especificación del tamaño.


0
2017-12-02 23:58