Optimización de matrices C++ 2-D

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 hecho algunas de distribución en varias máquinas Linux Unix/y las versiones de gcc. Un vector de STL de vectores, declarado como:

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

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

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

acceder a través de una función de índice inline matrix[index(i,j)] , donde index(i,j) evalúa a 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] - se ejecutan casi a 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 vectorial de STL casi con la misma eficacia que el código no STL cuando se activan las optimizaciones, pero esto es algo dependiente de la máquina.

me gustaría utilizar STL, si es posible, sino que 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 de matriz y cambiar el orden en la memoria en ciertos casos. La bandera compilador de magia se define como:

-fipa-matrix-reorg 

Realizar aplanamiento de la matriz y transposición. El aplanamiento de matriz intenta para reemplazar una matriz m-dimensional con su matriz n-dimensional equivalente, donde n < m. Esto reduce el nivel de indirectamente necesario para acceder a los elementos de la matriz. La segunda optimización es la matriz de transposición que intenta cambiar el orden de las dimensiones de la matriz para mejorar la localidad de la memoria caché. Ambas optimizaciones de necesitan un indicador de todo el programa. La transposición está habilitada solo si la información de perfilado está disponible.

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

Answer 2

Mi conjetura sería el más rápido es, por una matriz, para usar array STL 1D y anular el operador() para utilizarlo como matriz 2D.

Sin embargo, el STL también define un tipo específicamente para las matrices numéricas no resizeable: valarray. También tiene varias optimizaciones para operaciones in situ.

valarray aceptan como argumento un tipo numérico:

valarray<double> a; 

A continuación, puede utilizar rebanadas, matrices indirectos, ... y por supuesto, puede heredar el valarray y definir su propio operador() (int i, int j) para las matrices 2D ...

Answer 3

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

Answer 4

Es muy probable que se trate de un problema de localización 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 ser una distancia larga si la memoria ya está fragmentada cuando los asigna. Es probable que diferentes filas de la matriz incurran al menos en un error de línea de caché y podrían incurrir en un error de página; si tiene mala suerte, dos filas adyacentes podrían estar en líneas de memoria que comparten una ranura TLB y el acceso a una desalojará 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 de líneas de caché posible.

vector está diseñado para matrices de tamaño variable. Si no necesita cambiar el tamaño de las matrices, use una matriz regular de C++. Las operaciones STL generalmente pueden operar en matrices C++.

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

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 los datos por filas porque casi no tiene sobrecarga además de una multiplicación y adición y porque sus filas son datos empaquetados que serán coherentes en la caché.

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

Intente hacer algunas investigaciones dirigidas al tipo de uso y algoritmos que está utilizando. Esto es especialmente importante si la matriz es muy grande, ya que las fallas de caché pueden dañar su rendimiento mucho más que la necesidad de 1 o 2 operaciones matemáticas adicionales para acceder a cada dirección.

Answer 6

Igual de fácil sería hacer el vector < double> (n * m);

Answer 7

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 8

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

Answer 9

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

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

Answer 10

He hecho esto un tiempo atrás para las imágenes en bruto al declarar mis propias clases de matriz bidimensional.

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

array [2] [3]. Ahora para obtener ese efecto, tendría una matriz de clase con un acceso a la matriz [] sobrecargado. Pero, esencialmente, esto devolvería otra matriz, lo que le da a la la segunda dimensión.

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

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

Por lo tanto, en lugar de matriz [2] [3], cambio tuve que hacer esta matriz de estilo (2,3).

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

Ver este enlace para el concepto general de que: http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

Puede la plantilla del tipo si es necesario.
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 sabía dónde comenzaba la siguiente fila en mi secuencia de bytes. El acceso fue optimizado para acceder a los 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.