c++ - Boost:: pregunta de rendimiento multi_array

performance boost-multi-array (15)

Estoy intentando comparar el rendimiento de boost :: multi_array con las matrices nativas dinámicamente asignadas, con el siguiente programa de prueba:

#include <windows.h> #define _SCL_SECURE_NO_WARNINGS #define BOOST_DISABLE_ASSERTS #include <boost/multi_array.hpp> int main(int argc, char* argv[]) { const int X_SIZE = 200; const int Y_SIZE = 200; const int ITERATIONS = 500; unsigned int startTime = 0; unsigned int endTime = 0; // Create the boost array typedef boost::multi_array<double, 2> ImageArrayType; ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]); // Create the native array double *nativeMatrix = new double [X_SIZE * Y_SIZE]; //------------------Measure boost---------------------------------------------- startTime = ::GetTickCount(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { boostMatrix[x][y] = 2.345; } } } endTime = ::GetTickCount(); printf("[Boost] Elapsed time: %6.3f seconds/n", (endTime - startTime) / 1000.0); //------------------Measure native----------------------------------------------- startTime = ::GetTickCount(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { nativeMatrix[x + (y * X_SIZE)] = 2.345; } } } endTime = ::GetTickCount(); printf("[Native]Elapsed time: %6.3f seconds/n", (endTime - startTime) / 1000.0); return 0; }

Obtengo los siguientes resultados:

[Boost] Elapsed time: 12.500 seconds [Native]Elapsed time: 0.062 seconds

No puedo creer que los multi_arrays sean mucho más lentos. ¿Alguien puede detectar lo que estoy haciendo mal?

Supongo que el almacenamiento en caché no es un problema ya que estoy escribiendo en la memoria.

EDITAR: Esta fue una construcción de depuración. Per Laserallan sugiere que hice una compilación de lanzamiento:

[Boost] Elapsed time: 0.266 seconds [Native]Elapsed time: 0.016 seconds

Mucho más cerca. Pero 16 a 1 todavía me parece alto.

Bueno, no hay una respuesta definitiva, pero voy a seguir adelante y dejar mi código real con arreglos nativos por ahora.

Aceptando la respuesta de Laserallan porque fue la mayor falla en mi prueba.

Gracias a todos.

¿Estás construyendo versión o depuración?

Si se ejecuta en modo de depuración, la matriz de impulso puede ser muy lenta porque su magia de plantilla no está en línea correctamente, lo que genera mucha sobrecarga en las llamadas a funciones. No estoy seguro de cómo se implementa multi array, así que esto podría estar totalmente fuera de lugar :)

Quizás también exista alguna diferencia en el orden de almacenamiento, por lo que podría tener su imagen almacenada columna por columna y escribirla fila por fila. Esto daría un comportamiento pobre de caché y puede ralentizar las cosas.

Intenta cambiar el orden de los bucles X e Y y ve si ganas algo. Hay información sobre el orden de almacenamiento aquí: http://www.boost.org/doc/libs/1_37_0/libs/multi_array/doc/user.html

EDITAR: dado que pareces estar usando la matriz bidimensional para el procesamiento de imágenes, es posible que te interese retirar la biblioteca de procesamiento de imágenes gil .

Puede tener matrices con menos sobrecarga que funcione perfectamente para su situación.

Considere usar Blitz ++ en su lugar. Probé Blitz, ¡y su rendimiento está a la par con la matriz tipo C!

Revisa tu código con Blitz añadido a continuación:

#include <windows.h> #define _SCL_SECURE_NO_WARNINGS #define BOOST_DISABLE_ASSERTS #include <boost/multi_array.hpp> #include <blitz/array.h> int main(int argc, char* argv[]) { const int X_SIZE = 200; const int Y_SIZE = 200; const int ITERATIONS = 500; unsigned int startTime = 0; unsigned int endTime = 0; // Create the boost array typedef boost::multi_array<double, 2> ImageArrayType; ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]); //------------------Measure boost---------------------------------------------- startTime = ::GetTickCount(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { boostMatrix[x][y] = 2.345; } } } endTime = ::GetTickCount(); printf("[Boost] Elapsed time: %6.3f seconds/n", (endTime - startTime) / 1000.0); //------------------Measure blitz----------------------------------------------- blitz::Array<double, 2> blitzArray( X_SIZE, Y_SIZE ); startTime = ::GetTickCount(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { blitzArray(x,y) = 2.345; } } } endTime = ::GetTickCount(); printf("[Blitz] Elapsed time: %6.3f seconds/n", (endTime - startTime) / 1000.0); //------------------Measure native----------------------------------------------- // Create the native array double *nativeMatrix = new double [X_SIZE * Y_SIZE]; startTime = ::GetTickCount(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { nativeMatrix[x + (y * X_SIZE)] = 2.345; } } } endTime = ::GetTickCount(); printf("[Native]Elapsed time: %6.3f seconds/n", (endTime - startTime) / 1000.0); return 0; }

Aquí está el resultado en depuración y lanzamiento.

DEPURAR:

Boost 2.093 secs Blitz 0.375 secs Native 0.078 secs

LANZAMIENTO:

Boost 0.266 secs Blitz 0.016 secs Native 0.015 secs

Usé el compilador MSVC 2008 SP1 para esto.

¿Podemos decir adiós a C-stlye array? = p

Construya en modo de lanzamiento, use objdump y mire el conjunto. Pueden estar haciendo cosas completamente diferentes, y podrás ver qué optimizaciones está usando el compilador.

Creo que sé cuál es el problema ... tal vez.

Para que la implementación de boost tenga una sintaxis como: matriz [x] [y]. eso significa que la matriz [x] tiene que devolver una referencia a un objeto que actúa como una columna de matriz 1D, en cuyo punto la referencia [y] le da su elemento.

El problema aquí es que está iterando en el orden principal de la fila (que es típico en c / c ++ ya que las matrices nativas son el IIRC principal de la fila. El compilador tiene que volver a ejecutar la matriz [x] para cada y en este caso. orden principal de la columna cuando se utiliza la matriz de impulso, es posible que vea un mejor rendimiento.

Solo una teoría

EDITAR: en mi sistema Linux (con algunos cambios menores) probé mi teoría, y sí mostró alguna mejora en el rendimiento al cambiar x e y, pero aún era más lenta que una matriz nativa. Esto podría ser una simple cuestión de que el compilador no pueda optimizar el tipo de referencia temporal.

En mi máquina usando

g++ -O3 -march=native -mtune=native --fast-math -DNDEBUG test.cpp -o test && ./test

yo obtengo

[Boost] Elapsed time: 0.020 seconds [Native]Elapsed time: 0.020 seconds

Sin embargo, cambiando const int ITERATIONS a 5000 me sale

[Boost] Elapsed time: 0.240 seconds [Native]Elapsed time: 0.180 seconds

luego con ITERATIONS vuelta a 500 pero X_SIZE y Y_SIZE configurados a 400 , obtengo una diferencia mucho más significativa

[Boost] Elapsed time: 0.460 seconds [Native]Elapsed time: 0.070 seconds

finalmente invirtiendo el lazo interno para el caso [Boost] para que se vea como

for (int x = 0; x < X_SIZE; ++x) { for (int y = 0; y < Y_SIZE; ++y) {

y manteniendo ITERATIONS , X_SIZE y Y_SIZE en 500 , 400 y 400 obtengo

[Boost] Elapsed time: 0.060 seconds [Native]Elapsed time: 0.080 seconds

Si invierto el bucle interno también para el caso [Native] (por lo que está en el orden incorrecto para ese caso), me sale, como era de esperar,

[Boost] Elapsed time: 0.070 seconds [Native]Elapsed time: 0.450 seconds

Estoy usando gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5 en Ubuntu 10.10

Entonces, en conclusión:

Con un impulso de optimización adecuado :: multi_array hace su trabajo como se esperaba
El orden en el que accede a sus datos sí importa

Estaba viendo esta pregunta porque tenía la misma pregunta. Tenía algunos pensamientos para dar una prueba más rigurosa.

Como señaló rodrigob , hay fallas en el orden de los bucles, de modo que cualquier resultado en el código que adjuntó originalmente dará datos engañosos.
Además, hay matrices de tamaño bastante pequeño que se establecen con constantes. El compilador puede optimizar los bucles, cuando en realidad el compilador no sabrá el tamaño de los arrays. Los tamaños de las matrices y el número de iteraciones deben ser entradas de tiempo de ejecución por si acaso.

En una Mac, el siguiente código está configurado para dar respuestas más significativas. Hay 4 pruebas aquí.

#define BOOST_DISABLE_ASSERTS #include "boost/multi_array.hpp" #include <sys/time.h> #include <stdint.h> #include<string> uint64_t GetTimeMs64() { struct timeval tv; gettimeofday( &tv, NULL ); uint64_t ret = tv.tv_usec; /* Convert from micro seconds (10^-6) to milliseconds (10^-3) */ ret /= 1000; /* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */ ret += ( tv.tv_sec * 1000 ); return ret; } void function1( const int X_SIZE, const int Y_SIZE, const int ITERATIONS ) { double nativeMatrix1add[X_SIZE*Y_SIZE]; for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { nativeMatrix1add[y + ( x * Y_SIZE )] = rand(); } } // Create the native array double* __restrict const nativeMatrix1p = new double[X_SIZE * Y_SIZE]; uint64_t startTime = GetTimeMs64(); for( int i = 0 ; i < ITERATIONS ; ++i ) { for( int xy = 0 ; xy < X_SIZE*Y_SIZE ; ++xy ) { nativeMatrix1p[xy] += nativeMatrix1add[xy]; } } uint64_t endTime = GetTimeMs64(); printf( "[Native Pointer] Elapsed time: %6.3f seconds/n", ( endTime - startTime ) / 1000.0 ); } void function2( const int X_SIZE, const int Y_SIZE, const int ITERATIONS ) { double nativeMatrix1add[X_SIZE*Y_SIZE]; for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { nativeMatrix1add[y + ( x * Y_SIZE )] = rand(); } } // Create the native array double* __restrict const nativeMatrix1 = new double[X_SIZE * Y_SIZE]; uint64_t startTime = GetTimeMs64(); for( int i = 0 ; i < ITERATIONS ; ++i ) { for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { nativeMatrix1[y + ( x * Y_SIZE )] += nativeMatrix1add[y + ( x * Y_SIZE )]; } } } uint64_t endTime = GetTimeMs64(); printf( "[Native 1D Array] Elapsed time: %6.3f seconds/n", ( endTime - startTime ) / 1000.0 ); } void function3( const int X_SIZE, const int Y_SIZE, const int ITERATIONS ) { double nativeMatrix2add[X_SIZE][Y_SIZE]; for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { nativeMatrix2add[x][y] = rand(); } } // Create the native array double nativeMatrix2[X_SIZE][Y_SIZE]; uint64_t startTime = GetTimeMs64(); for( int i = 0 ; i < ITERATIONS ; ++i ) { for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { nativeMatrix2[x][y] += nativeMatrix2add[x][y]; } } } uint64_t endTime = GetTimeMs64(); printf( "[Native 2D Array] Elapsed time: %6.3f seconds/n", ( endTime - startTime ) / 1000.0 ); } void function4( const int X_SIZE, const int Y_SIZE, const int ITERATIONS ) { boost::multi_array<double, 2> boostMatrix2add( boost::extents[X_SIZE][Y_SIZE] ); for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { boostMatrix2add[x][y] = rand(); } } // Create the native array boost::multi_array<double, 2> boostMatrix( boost::extents[X_SIZE][Y_SIZE] ); uint64_t startTime = GetTimeMs64(); for( int i = 0 ; i < ITERATIONS ; ++i ) { for( int x = 0 ; x < X_SIZE ; ++x ) { for( int y = 0 ; y < Y_SIZE ; ++y ) { boostMatrix[x][y] += boostMatrix2add[x][y]; } } } uint64_t endTime = GetTimeMs64(); printf( "[Boost Array] Elapsed time: %6.3f seconds/n", ( endTime - startTime ) / 1000.0 ); } int main( int argc, char* argv[] ) { srand( time( NULL ) ); const int X_SIZE = std::stoi( argv[1] ); const int Y_SIZE = std::stoi( argv[2] ); const int ITERATIONS = std::stoi( argv[3] ); function1( X_SIZE, Y_SIZE, ITERATIONS ); function2( X_SIZE, Y_SIZE, ITERATIONS ); function3( X_SIZE, Y_SIZE, ITERATIONS ); function4( X_SIZE, Y_SIZE, ITERATIONS ); return 0; }

Una con solo una matriz dimensional usando el [] con matemáticas enteras y un bucle doble
Uno con la misma matriz dimensional única usando incremento de puntero
Una matriz C multidimensional
Un impulso multi_array

así que ejecuta desde una línea de comando, ejecuta

./test_array xsize ysize iterations"

y puede tener una buena idea de cómo funcionarán estos enfoques. Esto es lo que obtuve con los siguientes indicadores del compilador:

g++4.9.2 -O3 -march=native -funroll-loops -mno-avx --fast-math -DNDEBUG -c -std=c++11 ./test_array 51200 1 20000 [Native 1-Loop ] Elapsed time: 0.537 seconds [Native 1D Array] Elapsed time: 2.045 seconds [Native 2D Array] Elapsed time: 2.749 seconds [Boost Array] Elapsed time: 1.167 seconds ./test_array 25600 2 20000 [Native 1-Loop ] Elapsed time: 0.531 seconds [Native 1D Array] Elapsed time: 1.241 seconds [Native 2D Array] Elapsed time: 1.631 seconds [Boost Array] Elapsed time: 0.954 seconds ./test_array 12800 4 20000 [Native 1-Loop ] Elapsed time: 0.536 seconds [Native 1D Array] Elapsed time: 1.214 seconds [Native 2D Array] Elapsed time: 1.223 seconds [Boost Array] Elapsed time: 0.798 seconds ./test_array 6400 8 20000 [Native 1-Loop ] Elapsed time: 0.540 seconds [Native 1D Array] Elapsed time: 0.845 seconds [Native 2D Array] Elapsed time: 0.878 seconds [Boost Array] Elapsed time: 0.803 seconds ./test_array 3200 16 20000 [Native 1-Loop ] Elapsed time: 0.537 seconds [Native 1D Array] Elapsed time: 0.661 seconds [Native 2D Array] Elapsed time: 0.673 seconds [Boost Array] Elapsed time: 0.708 seconds ./test_array 1600 32 20000 [Native 1-Loop ] Elapsed time: 0.532 seconds [Native 1D Array] Elapsed time: 0.592 seconds [Native 2D Array] Elapsed time: 0.596 seconds [Boost Array] Elapsed time: 0.764 seconds ./test_array 800 64 20000 [Native 1-Loop ] Elapsed time: 0.546 seconds [Native 1D Array] Elapsed time: 0.594 seconds [Native 2D Array] Elapsed time: 0.606 seconds [Boost Array] Elapsed time: 0.764 seconds ./test_array 400 128 20000 [Native 1-Loop ] Elapsed time: 0.536 seconds [Native 1D Array] Elapsed time: 0.560 seconds [Native 2D Array] Elapsed time: 0.564 seconds [Boost Array] Elapsed time: 0.746 seconds

Por lo tanto, creo que es seguro decir que el boost multi_array funciona bastante bien. No hay nada mejor que una evaluación de bucle único, pero dependiendo de la dimensión de la matriz, el boost :: multi_array puede vencer a una matriz c estándar con un bucle doble.

He compilado el código (con ligeras modificaciones) en VC ++ 2010 con la optimización activada ("Maximizar velocidad" junto con la incorporación de funciones "Cualquier Adecuado" y "Favorecer código rápido") y obtuve los tiempos 0.015 / 0.391. He generado una lista de ensamblaje y, aunque soy un novato de ensamblaje terrible, hay una línea dentro del lazo de medición de refuerzo que no se ve bien para mí:

call ??A?$multi_array_ref@N$01@boost@@QAE?AV?$sub_array@N$00@multi_array@detail@1@H@Z ; boost::multi_array_ref<double,2>::operator[]

¡Uno de los operadores [] no se innsistió! El procedimiento llamado realiza otra llamada, esta vez a multi_array::value_accessor_n<...>::access<...>() :

call ??$access@V?$sub_array@N$00@multi_array@detail@boost@@PAN@?$value_accessor_n@N$01@multi_array@detail@boost@@IBE?AV?$sub_array@N$00@123@U?$type@V?$sub_array@N$00@multi_array@detail@boost@@@3@HPANPBIPBH3@Z ; boost::detail::multi_array::value_accessor_n<double,2>::access<boost::detail::multi_array::sub_array<double,1>,double *>

En general, los dos procedimientos son bastante código para acceder a un solo elemento en la matriz. Mi impresión general es que la biblioteca es tan compleja y de alto nivel que Visual Studio no puede optimizarla tanto como quisiéramos (los carteles que usan gcc aparentemente tienen mejores resultados).

En mi humilde opinión, un buen compilador debería haber resumido y optimizado los dos procedimientos: ambos son bastante cortos y directos, no contienen ningún bucle, etc. Se puede perder mucho tiempo simplemente pasando sus argumentos y resultados.

Hubiera esperado que Multiarray fuera igual de eficiente. Pero estoy obteniendo resultados similares en una Mac PPC usando gcc. También probé multiarrayref, por lo que ambas versiones usaban el mismo almacenamiento sin diferencias. Esto es bueno saberlo, ya que uso multiarray en algunos de mis códigos, y simplemente asumí que era similar a la codificación manual.

Me pregunto dos cosas:

1) comprobación de límites: defina la macro del preprocesador BOOST_DISABLE_ASSERTS antes de incluir multi_array.hpp en su aplicación. Esto desactiva la verificación encuadernada. no estoy seguro de si esto es deshabilitado cuando está NDEBUG.

2) índice base: MultiArray puede indexar matrices desde bases diferentes de 0. Eso significa que multi_array almacena un número base (en cada dimensión) y utiliza una fórmula más complicada para obtener la ubicación exacta en la memoria, me pregunto si se trata de todo ese.

De lo contrario, no entiendo por qué el multiarray debería ser más lento que los C-arrays.

Mirando el ensamblado generado por g ++ 4.8.2 con -O3 -DBOOST_DISABLE_ASSERTS y utilizando las formas operator() y [][] para acceder a los elementos, es evidente que la única operación adicional en comparación con los arrays nativos y el cálculo manual del índice es la Además de la base. Sin embargo, no he medido el costo de esto.

Modifiqué el código anterior en Visual Studio 2008 v9.0.21022 y apliqué las rutinas de contenedor de las rutinas de Recetas Numéricas para C y C ++

http://www.nrbook.com/nr3/ usando sus rutinas autorizadas dmatrix y MatDoub respectivamente

dmatrix usa el operador malloc sintaxis desactualizado y no se recomienda ... MatDoub usa el comando Nuevo

La velocidad en segundos está en la versión de lanzamiento:

Boost: 0.437

Nativo: 0.032

Recetas Numéricas C: 0.031

Recetas numéricas C ++: 0.031

Por lo tanto, desde el bombardeo anterior parece la mejor alternativa gratuita.

Otra cosa que debes probar es usar iteradores en lugar de un índice directo para la matriz de impulso.

Probé en un Snow Leopard Mac OS usando gcc 4.2.1

Debug: [Boost] Elapsed time: 2.268 seconds [Native]Elapsed time: 0.076 seconds Release: [Boost] Elapsed time: 0.065 seconds [Native]Elapsed time: 0.020 seconds

Aquí está el código (modificado para que pueda compilarse en Unix):

#define BOOST_DISABLE_ASSERTS #include <boost/multi_array.hpp> #include <ctime> int main(int argc, char* argv[]) { const int X_SIZE = 200; const int Y_SIZE = 200; const int ITERATIONS = 500; unsigned int startTime = 0; unsigned int endTime = 0; // Create the boost array typedef boost::multi_array<double, 2> ImageArrayType; ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]); // Create the native array double *nativeMatrix = new double [X_SIZE * Y_SIZE]; //------------------Measure boost---------------------------------------------- startTime = clock(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { boostMatrix[x][y] = 2.345; } } } endTime = clock(); printf("[Boost] Elapsed time: %6.3f seconds/n", (endTime - startTime) / (double)CLOCKS_PER_SEC); //------------------Measure native----------------------------------------------- startTime = clock(); for (int i = 0; i < ITERATIONS; ++i) { for (int y = 0; y < Y_SIZE; ++y) { for (int x = 0; x < X_SIZE; ++x) { nativeMatrix[x + (y * X_SIZE)] = 2.345; } } } endTime = clock(); printf("[Native]Elapsed time: %6.3f seconds/n", (endTime - startTime) / (double)CLOCKS_PER_SEC); return 0; }

Una pregunta similar fue hecha y respondida aquí:

http://www.codeguru.com/forum/archive/index.php/t-300014.html

La respuesta corta es que es más fácil para el compilador optimizar las matrices simples y no tan fácil optimizar la versión de Boost. Por lo tanto, un compilador particular puede no dar a la versión de Boost todos los mismos beneficios de optimización.

Los compiladores también pueden variar en qué tan bien se optimizarán y qué tan conservadores serán (por ejemplo, con código de plantilla u otras complicaciones).

Tu prueba es defectuosa

En una versión DEBUG, boost :: MultiArray carece del pase de optimización que necesita urgentemente. (Mucho más que una matriz nativa)
En una compilación RELEASE, su compilador buscará código que pueda eliminarse directamente y la mayoría de su código esté en esa categoría .

Lo que probablemente vea es el resultado de que su compilador de optimización vea que la mayoría o todos sus bucles de "matriz nativa" pueden eliminarse. Lo mismo es teóricamente cierto de su boost :: Loops MultiArray, pero MultiArray es probablemente lo suficientemente complejo como para vencer a su optimizador.

Haga este pequeño cambio en su banco de pruebas y verá resultados más reales: cambie ambas ocurrencias de " = 2.345 " con " *= 2.345 " y vuelva a compilar con optimizaciones. Esto evitará que su compilador descubra que el bucle externo de cada prueba es redundante.

Lo hice y obtuve una comparación de velocidad más cercana a 2: 1.