Código Speedup C++

optimization

Question

Estoy escribiendo una aplicación de procesamiento de números en C ++, donde el cuello de botella es una función que tiene que calcular para el doble:

 template<class T> inline T sqr(const T& x){return x*x;}

y otro que calcula

Base   dist2(const Point& p) const
       { return sqr(x-p.x) + sqr(y-p.y) + sqr(z-p.z); }

Estas operaciones toman el 80% del tiempo de cálculo. Me pregunto si puede sugerir enfoques para hacerlo más rápido, incluso si hay algún tipo de pérdida de precisión

Gracias

Answer 1

¿Estás usando Visual Studio? Si es así, es posible que desee consultar la especificación del control de unidad de punto flotante con /fp fast como un interruptor de compilación. Eche un vistazo a El modo fp: fast para semántica de coma flotante . GCC tiene una gran cantidad de optimizaciones de coma flotante -fOPTION que quizás desee considerar (si, como usted dice, la precisión no es una gran preocupación).

Answer 2

¿Hay alguna razón por la que está implementando su propio operador sqr?

¿Has probado el que está en la libma? Debería ser altamente optimizado.

Answer 3

¿Qué es Base ?

¿Es una clase con un constructor no explícito? Es posible que esté creando una buena cantidad de objetos Base temporales. Eso podría ser un gran cerdo de CPU.

template<class T> inline T sqr(const T& x){return x*x;}
Base   dist2(const Point& p) const {
  return sqr(x-p.x) + sqr(y-p.y) + sqr(z-p.z);
}

Si las variables miembro de p son de tipo Base , podría estar llamando a sqr en los objetos Base, que crearán temporales para las coordenadas restadas, en sqr , y luego para cada componente agregado.

(No podemos decir sin las definiciones de clase)

Probablemente puedas acelerarlo forzando a las llamadas sqr a estar en primitves y no usar Base hasta que llegues al tipo de retorno de dist2 .

Otras oportunidades de mejora del rendimiento son:

• Use operaciones de punto no flotante, si está bien con menos precisión.
• Utilice algoritmos que no necesiten llamar tanto a dist2 , posiblemente al almacenamiento en caché o al uso de la propiedad transitiva.
• (Esto es probablemente obvio, pero) Asegúrese de que está compilando con la optimización activada.

Answer 4

(¡raspe eso! sqr! = sqrt)

Vea si el "Fast sqrt" es aplicable en su caso:

http://en.wikipedia.org/wiki/Fast_inverse_square_root

Answer 5

A partir de un recuento de operaciones, no veo cómo se puede acelerar sin profundizar en las optimizaciones de hardware (como SSE) como otros han señalado. Una alternativa es usar una norma diferente , como la norma 1 es solo la suma de los valores absolutos de los términos. Entonces no se necesitan multiplicaciones. Sin embargo, esto cambia la geometría subyacente de su espacio reorganizando el espacio aparente de los objetos, pero puede no importar para su aplicación.

Answer 6

Creo que la optimización de estas funciones puede ser difícil, es mejor optimizar el código que llama a estas funciones para llamarlas menos o para hacer las cosas de manera diferente.

Answer 7

En primer lugar, asegúrese de que dist2 puede estar en línea (no está claro en su publicación si este es el caso), de ser definido en un archivo de cabecera si es necesario (generalmente tendrá que hacer esto, pero si su compilador genera código en tiempo de enlace, entonces ese no es necesariamente el caso).

Asumiendo la arquitectura x86, asegúrese de permitir que su compilador genere código usando las instrucciones SSE2 (un ejemplo de un conjunto de instrucciones SIMD) si están disponibles en la arquitectura de destino. Para dar al compilador la mejor oportunidad de optimizar estos, puede intentar agrupar sus operaciones sqr (las instrucciones SSE2 deberían poder hacer hasta 4 operaciones flotantes o 2 operaciones dobles a la vez según las instrucciones ... pero, por supuesto, puede solo haga esto si tiene las entradas para más de una operación en el listo). No sería demasiado optimista sobre la capacidad del compilador para darse cuenta de que puede procesarlos por lotes ... pero al menos puede configurar su código para que sea posible en teoría.

Si aún no está satisfecho con la velocidad y no confía en que su compilador lo está haciendo mejor, debería buscar el uso de compiladores intrínsecos que le permitan escribir instrucciones paralelas potenciales de forma explícita ... o alternativamente, puede ir a la derecha adelante y escriba el código de ensamblaje específico de la arquitectura para aprovechar SSE2 o las instrucciones más apropiadas para su arquitectura. (Advertencia: si codifica manualmente el ensamblaje, tenga especial cuidado de que aún quede grabado o conviértalo en una gran operación por lotes)

Para llevarlo más lejos, (y como ya ha mencionado el glowcoder), podría realizar estas operaciones en una GPU. Para su caso específico, tenga en cuenta que las GPU a menudo no son compatibles con el punto flotante de doble precisión ... aunque si es una buena opción para lo que está haciendo, obtendrá órdenes de mejor rendimiento de esta manera. Busque GPGPU o lo que sea y vea qué es lo mejor para usted.

Answer 8

Hay muchas respuestas que mencionan SSE ya ... pero como nadie ha mencionado cómo usarlo, lanzaré otro en ...

Su código tiene casi todo lo que necesita un vectorizador para funcionar, excepto dos restricciones: aliasing y alineación.

• Aliasing es el problema de dos nombres que hacen referencia a dos el mismo objeto. Por ejemplo, my_point.dist2( my_point ) operaría en dos copias de my_point . Esto ensucia con el vectorizador.

  C99 define la restrict palabra clave para que los punteros especifiquen que el objeto al que se hace referencia tiene una referencia única: no habrá otro puntero de restrict para ese objeto en el ámbito actual. La mayoría de los compiladores C ++ decentes también implementan C99 e importan esta característica de alguna manera.

  • GCC lo llama __restrict__ . Se puede aplicar a referencias o this .
  • __restrict lo llama __restrict . Me sorprendería si el soporte fuera diferente de GCC.

  (No está en C ++ 0x, sin embargo)

  #ifdef __GCC__
  #define restrict __restrict__
  #elif defined _MSC_VER
  #define restrict __restrict
  #endif
   
  Base   dist2(const Point& restrict p) const restrict

• La mayoría de las unidades SIMD requieren alineación con el tamaño del vector. C ++ y C99 dejan la implementación de la alineación definida, pero C ++ 0x gana esta carrera al introducir [[align(16)]] . Como eso todavía es un poco en el futuro, es probable que desee el soporte semi portátil de su compilador, a la restrict :

  #ifdef __GCC__
  #define align16 __attribute__((aligned (16)))
  #elif defined _MSC_VER
  #define align16 __declspec(align (16))
  #endif
   
  struct Point {
      double align16 xyz[ 3 ]; // separate x,y,z might work; dunno
      …
  };

Esto no está garantizado para producir resultados; tanto GCC como MSVC implementan comentarios útiles para informarle qué no se vectorizó y por qué. Busca tu vectorizador en Google para obtener más información.

Answer 9

Las operaciones de punto flotante son a menudo más lentas, ¿tal vez se puede pensar en modificar el código para usar solo la aritmética de enteros y ver si esto ayuda?

EDITAR: Después del comentario hecho por Paul RI, reformulé mi consejo de no afirmar que las operaciones de punto flotante son siempre más lentas. Gracias.

Answer 10

Lo primero que se me ocurre es la memorización (almacenamiento en memoria caché sobre la marcha de llamadas a función), pero tanto sqr como dist2 parecería que tienen un nivel demasiado bajo para compensar los gastos indirectos asociados con la memorización debido a los ahorros memorización. Sin embargo, en un nivel superior, puede encontrar que puede funcionar bien para usted.

Creo que se necesita un análisis más detallado de sus datos. Diciendo que la mayor parte del tiempo en el programa se usa para ejecutar MOV y los comandos JUMp pueden ser precisos, pero no va a ayudar a optimizar mucho. La información es de muy bajo nivel. Por ejemplo, si sabe que los argumentos enteros son lo suficientemente buenos para dist2, y los valores están entre 0 y 9, entonces una tabla precapsulada sería de 1000 elementos, no demasiado grandes. Siempre puedes usar código para generarlo.

¿Has desenrollado bucles? ¿Opción matricial analizada? Busqué lugares en los que pueda pasar con la búsqueda de tablas en lugar del cálculo real.

Lo más drástico sería adoptar las técnicas descritas en: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.8660&rep=rep1&type=pdf aunque es cierto que es una lectura difícil y debe obtener algunas ayuda de alguien que sepa Common Lisp si no lo hace.

Answer 11

Mira el contexto. No hay nada que pueda hacer para optimizar una operación tan simple como x*x . En su lugar, debe mirar a un nivel superior: ¿de dónde se llama la función? ¿Con qué frecuencia? ¿Por qué? ¿Puedes reducir la cantidad de llamadas? ¿Puedes usar instrucciones SIMD para realizar la multiplicación en múltiples elementos a la vez?

¿Puede quizás descargar partes completas del algoritmo a la GPU?

¿Está definida la función para que pueda estar en línea? (básicamente, es su definición visible en los sitios de llamadas)

¿El resultado se necesita inmediatamente después del cálculo? Si es así, la latencia de las operaciones de FP podría perjudicarlo. Intente organizar su código para que las cadenas de dependencia se dividan o intercalen con instrucciones no relacionadas.

Y, por supuesto, examine el ensamblaje generado y vea si es lo que espera.

Answer 12

No dice si las llamadas a dist2 pueden ser paralelas o no. Si pueden, entonces puedes construir un grupo de subprocesos y dividir este trabajo en trozos más pequeños por subproceso.

¿Qué te dice tu perfilador que está pasando dentro de dist2 ? ¿Estás usando 100% de CPU todo el tiempo o caché y esperando que se carguen los datos?

Para ser sincero, realmente necesitamos más detalles para darle una respuesta definitiva.

Answer 13

Si sqr() se usa solo en tipos primitivos, puede intentar tomar el argumento por valor en lugar de referencia. Eso te ahorraría una indirección.

Answer 14

Si puede organizar sus datos adecuadamente, entonces es probable que pueda usar la optimización SIMD aquí. Para una implementación eficiente, es probable que desee rellenar su estructura de Point para que tenga 4 elementos (es decir, agregue un cuarto elemento ficticio para el relleno).

Answer 15

Si realmente necesita todos los valores de dist2, entonces debe calcularlos. Ya es de bajo nivel y no puede imaginar aceleraciones además de la distribución en múltiples núcleos.

Por otro lado, si está buscando la cercanía, puede suministrar a la función dist2 () su valor mínimo actual. De esta forma, si sqr(xp.x) ya es más grande que tu mínimo actual, puedes evitar calcular los 2 cuadrados restantes.

Además, puedes evitar el primer cuadrado profundizando en la representación doble. Comparando directamente el valor del exponente con tu miminum actual puedes ahorrar aún más ciclos.

Answer 16

Si tiene varias de estas opciones para hacer, y está haciendo tareas gráficas o "gráficas" (modelado térmico, casi cualquier modelado en 3D) puede considerar usar OpenGL y descargar las tareas a una GPU. Esto permitiría que los cálculos se ejecuten en paralelo, con una capacidad operativa altamente optimizada. Después de todo, es de esperar que algo como distancia o distanciasq tenga su propio código de operación en una GPU.

Un investigador de una universidad local descarga casi todos sus cálculos 3d para el trabajo de inteligencia artificial a la GPU y logra resultados mucho más rápidos.

Answer 17

Solo algunos pensamientos, aunque poco probable que agregue algo de valor después de 18 respuestas :)

Si está invirtiendo un 80% de tiempo en estas dos funciones, puedo imaginar dos escenarios típicos:

Su algoritmo es al menos polinomial
Como sus datos parecen espaciales, ¿puede bajar el O (n) introduciendo índices espaciales?

Estás recorriendo cierto conjunto
Si este conjunto proviene de datos en el disco (¿está ordenado?) O de un bucle, es posible que haya caché, o utilice cálculos previos para calcular más rápido el sqrt.

También con respecto a la memoria caché, debe definir la precisión requerida (y el rango de entrada). ¿Tal vez se puede usar algún tipo de búsqueda / caché?

Answer 18

Su mejor esperanza es verificar dos veces que cada llamada dist2 es realmente necesaria: ¿quizás el algoritmo que lo llama puede ser refactorizado para ser más eficiente? Si se calculan varias distancias varias veces, ¿pueden almacenarse en caché?

Si está seguro de que todas las llamadas son necesarias, es posible que pueda exprimir la última gota de rendimiento mediante el uso de un compilador compatible con arquitectura. He obtenido buenos resultados utilizando el compilador de Intel en x86, por ejemplo.

Answer 19

Sugiero dos técnicas:

1. Mueva los miembros de la estructura a las variables locales al principio.
2. Realice operaciones similares juntas.

Estas técnicas pueden no hacer la diferencia, pero valen la pena intentarlo. Antes de realizar cualquier cambio, imprima el lenguaje ensamblador primero. Esto le dará una línea base para la comparación.

Aquí está el código:

Base   dist2(const Point& p) const
{
    //  Load the cache with data values.
    register x1 = p.x;
    register y1 = p.y;
    register z1 = p.z;

    // Perform subtraction together
    x1 = x - x1;
    y1 = y - y1;
    z1 = z - z2;

    // Perform multiplication together
    x1 *= x1;
    y1 *= y1;
    z1 *= z1;

    // Perform final sum
    x1 += y1;
    x1 += z1;

    // Return the final value
    return x1;
}

La otra alternativa es agrupar por dimensión. Por ejemplo, realice primero todas las operaciones ''X'', luego Y y seguido de Z Esto puede mostrarle al compilador que las piezas son independientes y puede delegar en otro núcleo o procesador.

Si no puede obtener más rendimiento de esta función, debe buscar en otra parte como lo sugirieron otras personas. Lea también sobre Diseño impulsado por datos . Hay ejemplos en que la reorganización de la carga de datos puede acelerar el rendimiento en más del 25%.

Además, es posible que desee investigar el uso de otros procesadores en el sistema. Por ejemplo, el Proyecto BOINC puede delegar cálculos a un procesador de gráficos.

Espero que esto ayude.

Answer 20

Tengo curiosidad por saber por qué hiciste esta plantilla cuando dijiste que el cálculo se hace usando dobles. ¿Por qué no escribir un método estándar, una función o simplemente ''x * x''?

Si sus entradas se pueden restringir de manera predecible y realmente necesita velocidad, cree una matriz que contenga todas las salidas que su función puede producir. Use la entrada como el índice en la matriz (un hash disperso). Una evaluación de función se convierte en una comparación (para probar los límites de la matriz), una adición y una referencia de memoria. No será mucho más rápido que eso.

Answer 21

Ver las instrucciones SUBPD, MULPD y DPPD. (DPPD requirió SSE4)

Depende de tu código, pero en algunos casos un diseño de estructura de matrices puede ser más amigable con la vectorización que un diseño de matriz de estructuras.