Optimización de matrices 2-D de C++

Question

Necesito una forma de representar una matriz 2-D (una matriz densa) de dobles en C++, con una sobrecarga de acceso mínima absoluta.

He cronometrado algo en varias máquinas Linux/Unix y versiones de gcc.Un vector STL de vectores, declarado como:

vector<vector<double> > matrix(n,vector<double>(n));

y se accede a través de matrix[i][j] tiene un acceso entre un 5% y un 100% más lento que una matriz declarada como:

double *matrix = new double[n*n];

Se accede a través de una función de índice en línea. matrix[index(i,j)], dónde index(i,j) se evalúa como i+n*j.Otras formas de organizar una matriz 2-D sin STL: una matriz de n punteros al inicio de cada fila, o definir todo en la pila como un tamaño constante matrix[n][n] - ejecutar casi exactamente la misma velocidad que el método de función de índice.

Las versiones recientes de GCC (> 4.0) parecen ser capaces de compilar el vector de vectores STL con casi la misma eficiencia que el código que no es STL cuando las optimizaciones están activadas, pero esto depende en cierta medida de la máquina.

Me gustaría usar STL si es posible, pero tendré que elegir la solución más rápida.¿Alguien tiene alguna experiencia en la optimización de STL con GCC?

Answer 1

Si está utilizando GCC, el compilador puede analizar sus accesos a la matriz y cambiar el orden en la memoria en ciertos casos. El indicador del compilador mágico se define como:

-fipa-matrix-reorg

  

Realizar el aplanamiento matricial y   transposición Intentos de aplanamiento de matrices   para reemplazar una matriz m-dimensional con   su matriz n-dimensional equivalente,   donde n < metro. Esto reduce el nivel de   indirección necesaria para acceder a la   elementos de la matriz. El segundo   la optimización es la transposición de matrices   que intenta cambiar el orden de   las dimensiones de la matriz para   mejorar la localidad de caché. Ambos   las optimizaciones necesitan un programa completo   bandera. La transposición está habilitada solo si   la información de perfil está disponible.

Tenga en cuenta que esta opción no está habilitada por -O2 u -O3. Tienes que pasarlo tú mismo.

Answer 2

Supongo que lo más rápido es, para una matriz, usar la matriz 1D STL y anular el operador () para usarla como matriz 2D.

Sin embargo, el STL también define un tipo específicamente para matrices numéricas no redimensionables: valarray. También tiene varias optimizaciones para operaciones en el lugar.

valarray acepta como argumento un tipo numérico:

valarray<double> a;

Luego, puede usar sectores, matrices indirectas, ... y, por supuesto, puede heredar el valarray y definir su propio operador () (int i, int j) para matrices 2D ...

Answer 3

Muy probablemente este es un problema de localidad de referencia. vector usa new para asignar su matriz interna, por lo que cada fila estará al menos un poco separada en la memoria debido al encabezado de cada bloque; podría estar a una gran distancia si la memoria ya está fragmentada cuando los asigna. Es probable que diferentes filas de la matriz al menos incurran en un error de línea de caché y podrían incurrir en un error de página; si no tiene suerte, dos filas adyacentes podrían estar en líneas de memoria que comparten una ranura TLB y acceder a una desalojará a la otra.

En contraste, sus otras soluciones garantizan que todos los datos sean adyacentes. Podría ayudar a su rendimiento si alinea la estructura para que cruce la menor cantidad posible de líneas de caché.

<=> está diseñado para matrices redimensionables . Si no necesita cambiar el tamaño de las matrices, use una matriz C ++ normal. Las operaciones STL generalmente pueden operar en matrices C ++.

Asegúrese de caminar la matriz en la dirección correcta, es decir, a través de (direcciones de memoria consecutivas) en lugar de hacia abajo. Esto reducirá las fallas de caché.

Answer 4

Mi recomendación sería utilizar Boost.UBLAS, que proporciona clases rápidas de matriz / vector.

Answer 5

Para ser justos, depende de los algoritmos que esté utilizando en la matriz.

El formato de doble nombre [n*m] es muy rápido cuando se accede a datos por filas porque casi no tiene gastos generales además de una multiplicación y suma y porque sus filas son datos empaquetados que serán coherentes en el caché.

Si sus algoritmos acceden a datos ordenados por columnas, otros diseños podrían tener una coherencia de caché mucho mejor.Si su algoritmo accede a datos en cuadrantes de la matriz, incluso otros diseños podrían ser mejores.

Intente realizar una investigación dirigida al tipo de uso y algoritmos que está utilizando.Esto es especialmente importante si la matriz es muy grande, ya que los errores de caché pueden afectar su rendimiento mucho más que necesitar 1 o 2 operaciones matemáticas adicionales para acceder a cada dirección.

Answer 6

Podrías hacer fácilmente el vector < doble > (n * m);

Answer 7

Es posible que desee consultar la biblioteca de plantillas de Eigen C ++ en http://eigen.tuxfamily.org/. Genera código AltiVec o sse2 para optimizar los cálculos de vectores / matrices.

Answer 8

Existe la implementación de uBLAS en Boost. Vale la pena echarle un vistazo.

http: //www.boost .org / doc / libs / 1_36_0 / libs / numeric / ublas / doc / matrix.htm

Answer 9

Otra biblioteca relacionada es Blitz ++: http://www.oonumerics.org/blitz /docs/blitz.html

Blitz ++ está diseñado para optimizar la manipulación de la matriz.

Answer 10

He hecho esto hace algún tiempo para imágenes en bruto declarando mis propias clases de matriz de 2 dimensiones.

En una matriz 2D normal, accede a los elementos como:

matriz [2] [3]. Ahora para obtener ese efecto, tendrías una matriz de clase con una sobrecarga [] array de acceso. Pero, esto esencialmente devolvería otra matriz, dando así usted la segunda dimensión.

El problema con este enfoque es que tiene una sobrecarga de llamadas de doble función.

La forma en que lo hice fue usar la sobrecarga de estilo ().

Entonces, en lugar de array [2] [3], cambio Lo hice hacer este estilo de matriz (2,3).

Esa función () era muy pequeña y me aseguré de que estuviera en línea.

Vea este enlace para el concepto general de eso: http://www.learncpp.com/cpp-tutorial / 99-sobrecarga-el-paréntesis-operador /

Puede crear una plantilla del tipo si lo necesita.
La diferencia que tuve fue que mi matriz era dinámica. Tenía un bloque de memoria char que declararía. Y empleé un caché de columna, así que supe en qué parte de mi secuencia de bytes comenzó la siguiente fila. El acceso se optimizó para acceder a valores vecinos, porque lo estaba usando para el procesamiento de imágenes.

Es difícil de explicar sin el código, pero esencialmente el resultado fue tan rápido como C, y mucho más fácil de entender y usar.