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

12 minutos de lectura

Restablecer la matriz C int a cero ¿la forma mas
Vicente

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

  • @BoPersson: bueno, new es C++…

    – Mateo Italia

    5 de febrero de 2012 a las 20:06

  • @Matteo – bueno, sí. No afectó mucho las respuestas (hasta ahora :-).

    – Bo Person

    5 de febrero de 2012 a las 20:12


  • @BoPersson: Me sentí mal hablando solo de memset cuando C++ está involucrado de alguna manera… 🙂

    – Mateo Italia

    5 de febrero de 2012 a las 20:15

  • En un compilador moderno, no puedes vencer a un simple for lazo. Pero, sorprendentemente, puedes hacerlo mucho peor si tratas de ser inteligente.

    –David Schwartz

    21 de septiembre de 2015 a las 8:58


  • Use una estructura y pegue una matriz dentro de ella. Cree una instancia que sea todo ceros. Úselo para poner a cero otros que cree. Funciona bien. Sin incluye, sin funciones, bastante rápido.

    – Xofo

    5 de marzo de 2019 a las 8:24

Restablecer la matriz C int a cero ¿la forma mas
Mateo Italia

memset (desde <string.h>) es probablemente la forma estándar más rápida, ya que suele ser 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 (desde <algorithm>):

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

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

  • A partir de la norma ISO C de 1999, en realidad no se garantizaba que memset establecería un número entero en 0; no hubo una declaración específica de que todos los bits cero es una representación de 0. Un corrigendum técnico agregó dicha garantía, que está incluida en la norma ISO C de 2011. Yo creo que todo-bits-cero es una representación válida de 0 para todos los tipos de enteros en todas las implementaciones existentes de C y C++, razón por la cual el comité pudo agregar ese requisito. (No existe una garantía similar para los tipos de punto flotante o de puntero).

    –Keith Thompson

    16 de junio de 2013 a las 0:17

  • Agregando al comentario de @KeithThompson: esta garantía se agregó a 6.2.6.2/5 en texto sin formato en TC2 (2004); sin embargo, si no hay bits de relleno, 6.2.6.2/1 y /2 ya garantizaron que todos los bits cero eran 0. (Con los bits de relleno existe la posibilidad de que todos los bits cero puedan ser una representación trampa). Pero en cualquier caso, se supone que el TC reconoce y reemplaza el texto defectuoso, por lo que a partir de 2004 deberíamos actuar como si C99 siempre hubiera contenido este texto.

    –MM

    29 de mayo de 2015 a las 11:02

  • En C, si asignó la matriz dinámica correctamente, entonces no habrá diferencia entre los dos conjuntos de memoria. La asignación dinámica correcta sería int (*myarray)[N] = malloc(sizeof(*myarray));.

    – Lundin

    21 de septiembre de 2015 a las 9:04


  • @Lundin: por supuesto, si sabe en tiempo de compilación qué tan grande N es, pero en la gran mayoría de los casos si usó malloc solo lo sabías en tiempo de ejecución.

    – Mateo Italia

    21 de septiembre de 2015 a las 9:12

  • @MatteoItalia Tenemos VLA desde el año 1999.

    – Lundin

    21 de septiembre de 2015 a las 9:15

1646750056 444 Restablecer la matriz C int a cero ¿la forma mas
Benjamín

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 la menor cantidad de líneas, sino la lo más rápido manera. Y es una tontería responder a esa pregunta sin algunas pruebas reales. Así que comparé cuatro soluciones, memset vs. std::fill vs. ZERO de la respuesta de AnT vs una solución que hice usando los intrínsecos de AVX.

Tenga en cuenta que esta solución no es genérica, solo funciona en 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 diré 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 correcta implementación dependiente de la arquitectura que es más rápida que memset.

Ahora, a los resultados. Calculé el rendimiento para matrices de tamaño 100 int y long long, tanto estática como dinámicamente asignadas, pero con la excepción de msvc, que eliminó el código inactivo en matrices estáticas, los resultados fueron extremadamente comparables, por lo que solo mostraré el rendimiento de la 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, banderas 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 (marcas 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

Están sucediendo muchas cosas interesantes aquí: llvm matando a gcc, las optimizaciones irregulares típicas de MSVC (hace una eliminación impresionante de código muerto en matrices estáticas y luego tiene un rendimiento horrible para el relleno). Aunque mi implementación es significativamente más rápida, esto puede deberse solo a que reconoce que la limpieza de bits tiene una sobrecarga mucho menor 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 conjuntos de memorias cero-distintos de cero para matrices de 400 bytes que son mucho más lentos (~220 ms) y son comparables a los de gcc. Sin embargo, la configuración de mem distinta de cero con una matriz de 800 bytes no hace ninguna diferencia de velocidad, lo que probablemente explica por qué, en ese caso, su conjunto 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 están optimizando para 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 pretende (de lo contrario, gcc, msvc y llvm’s memset tendrían el mismo rendimiento). Si el rendimiento es importante, entonces memset no debería ser una solución final, especialmente para estas incómodas matrices de tamaño mediano, porque no está especializado en la limpieza de bits y no está optimizado a mano mejor que lo que el compilador puede hacer por sí solo.

  • ¿Un punto de referencia sin código y sin mencionar la versión del compilador y las opciones utilizadas? Mmm…

    – Marc Glisse

    21/09/2015 a las 20:57

  • Ya tenía las versiones del compilador (estaban un poco ocultas) y solo agregué las opciones aplicables utilizadas.

    – Benjamín

    22/09/2015 a las 22:31

  • argumento de tipo no válido de unario ‘*’ (tiene ‘size_t {también conocido como int sin firmar}’) |

    –Piotr Wasilewicz

    25 de junio de 2017 a las 8:08


  • Siendo tan generoso como para escribir su propio método de reducción a cero optimizado, ¿podría dedicar algunas palabras sobre CÓMO funciona y POR QUÉ es más rápido? el código es casi autoexplicativo.

    –Motti Shneor

    31 de diciembre de 2019 a las 14:15

  • @MottiShneor Parece más complicado de lo que es. Un registro AVX tiene un tamaño de 32 bytes. Así que calcula cuántos valores de a encajar en un registro. Luego, recorre todos los bloques de 32 bytes, que deben sobrescribirse por completo usando aritmética de punteros ((float *)((a)+x)). Los dos intrínsecos (comenzando con _mm256) simplemente cree un registro de 32 bytes inicializado en cero y guárdelo en el puntero actual. Estas son las primeras 3 líneas. El resto solo maneja todos los casos especiales en los que el último bloque de 32 bytes no debe sobrescribirse por completo. Es más rápido debido a la vectorización. – Espero que eso ayude.

    – maestro brujo

    5 de marzo de 2020 a las 11:41

Desde memset():

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

Puedes usar sizeof(myarray) si el tamaño de myarray se conoce 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 newdeberá realizar un seguimiento de la longitud.

  • sizeof funcionará incluso si el tamaño de la matriz no se conoce en tiempo de compilación. (por supuesto, solo cuando es una matriz)

    – asaelr

    5 de febrero de 2012 a las 2:28

  • @asaelr: En C++, sizeof siempre se evalúa en tiempo de compilación (y no se puede usar con VLA). En C99, puede ser una expresión de tiempo de ejecución en el caso de los VLA.

    – Ben Voigt

    15 de junio de 2013 a las 22:53


  • @BenVoigt Bueno, la pregunta es sobre ambos c y c++. Comenté la respuesta de Alex, que dice “Puedes usar sizeof (myarray) si el tamaño de myarray se conoce en tiempo de compilación”.

    – asaelr

    15 de junio de 2013 a las 23:44

  • @asaelr: Y en C++, tiene toda la razón. Su comentario no decía nada sobre C99 o VLA, así que quería aclararlo.

    – Ben Voigt

    16 de junio de 2013 a las 0:27

1646750056 649 Restablecer la matriz C int a cero ¿la forma mas
bruno soares

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

T myarray[100] = {0};

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

  • omitiría el ; después de la while(0)para que uno pueda llamar ZERO(a,n);+1 gran respuesta

    – 0x90

    15 de junio de 2013 a las 22:24

  • @0x90: Sí, tienes toda la razón. Todo el punto de do{}while(0) idioma no requiere ; en la definición de macros. Reparado.

    – Ant

    16 de junio de 2013 a las 0:15

1646750057 478 Restablecer la matriz C int a cero ¿la forma mas
Navin

zero(myarray); es todo lo que necesitas 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));
}

  • Esto es incorrecto, borrará SIZE bytes. ‘memset(arr, 0, TAMAÑO*tamaño(T));’ seria correcto

    – Kornel Kisielewicz

    27 mayo 2015 a las 14:05


  • @KornelKisielewicz D’oh! Espero que nadie haya copiado y pegado esta función en los últimos 1,5 años 🙁

    – Navin

    29 mayo 2015 a las 9:40


  • espero que no, lo comenté porque google me trajo aquí 🙂

    – Kornel Kisielewicz

    2 jun 2015 a las 22:32

  • Tenga en cuenta que esta función zero también es correcto para por ejemplo T=char[10] como podría ser el caso cuando el arr argumento es una matriz multidimensional, por ejemplo char arr[5][10].

    – mandrágora

    23 de octubre de 2015 a las 12:24

  • Sí, probé varios casos con gcc 4.7.3. Considero que sería bueno tener esto en cuenta para esta respuesta, ya que, de lo contrario, necesitaría tener especializaciones de plantilla para cada conteo de dimensión de matriz. Otras respuestas tampoco generalizan, como la ARRAY_SIZE macro, que da el tamaño incorrecto si se usa en una matriz multidimensional, tal vez un mejor nombre sería ARRAY_DIM<n>_SIZE.

    – mandrágora

    26 de octubre de 2015 a las 7:23

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 es más una forma de C ++ 11 que usar memset. También obtiene un error de tiempo de compilación si usa una matriz dinámica con la especificación del tamaño.

  • Esto es incorrecto, borrará SIZE bytes. ‘memset(arr, 0, TAMAÑO*tamaño(T));’ seria correcto

    – Kornel Kisielewicz

    27 mayo 2015 a las 14:05


  • @KornelKisielewicz D’oh! Espero que nadie haya copiado y pegado esta función en los últimos 1,5 años 🙁

    – Navin

    29 mayo 2015 a las 9:40


  • espero que no, lo comenté porque google me trajo aquí 🙂

    – Kornel Kisielewicz

    2 jun 2015 a las 22:32

  • Tenga en cuenta que esta función zero también es correcto para por ejemplo T=char[10] como podría ser el caso cuando el arr argumento es una matriz multidimensional, por ejemplo char arr[5][10].

    – mandrágora

    23 de octubre de 2015 a las 12:24

  • Sí, probé varios casos con gcc 4.7.3. Considero que sería bueno tener esto en cuenta para esta respuesta, ya que, de lo contrario, necesitaría tener especializaciones de plantilla para cada conteo de dimensión de matriz. Otras respuestas tampoco generalizan, como la ARRAY_SIZE macro, que da el tamaño incorrecto si se usa en una matriz multidimensional, tal vez un mejor nombre sería ARRAY_DIM<n>_SIZE.

    – mandrágora

    26 de octubre de 2015 a las 7:23

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad