C ++ consejos de optimización de bajo nivel [cerrado]

Suponiendo que ya tiene el algoritmo de mejor opción, ¿qué soluciones de bajo nivel puede ofrecer para exprimir las últimas gotas de velocidad de fotogramas dulce y dulce del código C ++?

No hace falta decir que estos consejos solo se aplican a la sección de código crítico que ya ha resaltado en su generador de perfiles, pero deberían ser mejoras no estructurales de bajo nivel. He sembrado un ejemplo.

¡Optimice su diseño de datos! (Esto se aplica a más lenguajes que solo C ++)

Puede profundizar bastante haciendo que esto se ajuste específicamente para sus datos, su procesador, el manejo de múltiples núcleos, etc. Pero el concepto básico es el siguiente:

Cuando procesa cosas en un ciclo cerrado, desea que los datos para cada iteración sean lo más pequeños posible y lo más juntos posible en la memoria. Eso significa que lo ideal es una matriz o un vector de objetos (no punteros) que contengan solo los datos necesarios para el cálculo.

De esta manera, cuando la CPU obtiene los datos para la primera iteración de su ciclo, las siguientes iteraciones de datos se cargarán en la memoria caché.

Realmente la CPU es rápida y el compilador es bueno. Realmente no hay mucho que puedas hacer con menos instrucciones y más rápidas. La coherencia de caché es donde está (es un artículo aleatorio que busqué en Google; contiene un buen ejemplo de cómo obtener coherencia de caché para un algoritmo que no simplemente ejecuta datos linealmente).

Un consejo de muy, muy bajo nivel, pero que puede ser útil:

La mayoría de los compiladores admiten alguna forma de sugerencia condicional explícita. GCC tiene una función llamada __builtin_expect que le permite informar al compilador cuál es probablemente el valor de un resultado. GCC puede usar esos datos para optimizar los condicionales para que funcionen lo más rápido posible en el caso esperado, con una ejecución ligeramente más lenta en el caso inesperado.

if(__builtin_expect(entity->extremely_unlikely_flag, 0)) {
  // code that is rarely run
}

He visto una aceleración del 10-20% con el uso adecuado de esto.

Lo primero que debe comprender es el hardware en el que se está ejecutando. ¿Cómo maneja la ramificación? ¿Qué pasa con el almacenamiento en caché? ¿Tiene un conjunto de instrucciones SIMD? ¿Cuántos procesadores puede usar? ¿Tiene que compartir el tiempo del procesador con algo más?

Puede resolver el mismo problema de maneras muy diferentes, incluso su elección de algoritmo debería depender del hardware. En algunos casos, O (N) puede funcionar más lentamente que O (NlogN) (según la implementación).

Como una descripción general de la optimización, lo primero que haría es ver exactamente qué problemas y qué datos está tratando de resolver. Entonces optimice para eso. Si desea un rendimiento extremo, olvídese de las soluciones genéricas: puede hacer un caso especial de todo lo que no coincida con su caso más utilizado.

Luego perfil. Perfil, perfil, perfil. Mire el uso de la memoria, mire las penalizaciones de ramificación, mire la sobrecarga de llamadas de función, mire la utilización de la tubería. Calcule lo que está ralentizando su código. Probablemente sea acceso a datos (escribí un artículo llamado "The Latency Elephant" sobre la sobrecarga del acceso a datos - google. No puedo publicar 2 enlaces aquí porque no tengo suficiente "reputación"), así que examínelo detenidamente y luego optimice su diseño de datos (los arreglos planos grandes y homogéneos son impresionantes ) y el acceso a los datos (captura previa siempre que sea posible).

Una vez que haya minimizado la sobrecarga del subsistema de memoria, intente determinar si las instrucciones son ahora el cuello de botella (con suerte), luego observe las implementaciones SIMD de su algoritmo. Las implementaciones de estructura de matrices (SoA) pueden ser muy datos y caché de instrucciones eficiente. Si SIMD no es una buena combinación para su problema, entonces puede ser necesaria la codificación de nivel intrínseco y de ensamblador.

Si aún necesita más velocidad, vaya en paralelo. Si tiene la ventaja de correr en una PS3, las SPU son sus amigos. Úsalos, ámalos. Si ya ha escrito una solución SIMD, obtendrá un beneficio masivo al pasar a SPU.

Y luego, perfila un poco más. Prueba en escenarios de juego: ¿sigue siendo este código el cuello de botella? ¿Puede cambiar la forma en que se usa este código en un nivel superior para minimizar su uso (en realidad, este debería ser su primer paso)? ¿Pueden diferir los cálculos en varios cuadros?

Independientemente de la plataforma en la que se encuentre, aprenda todo lo que pueda sobre el hardware y los perfiladores disponibles. No asuma que sabe cuál es el cuello de botella: búsquelo con su generador de perfiles. Y asegúrate de tener una heurística para determinar si realmente has hecho que tu juego vaya más rápido.

Y luego perfilarlo de nuevo.

Primer paso: piense detenidamente sobre sus datos en relación con sus algoritmos. O (log n) no siempre es más rápido que O (n). Ejemplo simple: una tabla hash con solo unas pocas claves a menudo se reemplaza mejor con una búsqueda lineal.

Segundo paso: mira el ensamblaje generado. C ++ trae mucha generación de código implícito a la tabla. A veces, te acecha sin que lo sepas.

Pero suponiendo que sea realmente el momento del pedal al metal: Perfil. Seriamente. La aplicación aleatoria de "trucos de rendimiento" tiene tantas probabilidades de perjudicar como de ayudar.

Entonces, todo depende de cuáles sean sus cuellos de botella.

la memoria caché de datos falla => optimiza su diseño de datos. Aquí hay un buen punto de partida: http://gamesfromwithin.com/data-oriented-design

el caché de código falla => Observe las llamadas a funciones virtuales, la profundidad excesiva de la pila de llamadas, etc. Una causa común de un mal rendimiento es la creencia errónea de que las clases base deben ser virtuales.

Otros sumideros de rendimiento comunes de C ++:

• Asignación / desasignación excesiva. Si el rendimiento es crítico, no llame al tiempo de ejecución. Siempre.
• Copia de construcción. Evita donde puedas. Si puede ser una referencia constante, hágala una.

Todo lo anterior es inmediatamente obvio cuando mira el ensamblaje, así que vea arriba;)

Eliminar ramas innecesarias

En algunas plataformas y con algunos compiladores, las ramas pueden tirar toda su tubería, por lo que incluso los bloques if () pueden ser costosos.

La arquitectura PowerPC (PS3 / X360) ofrece la instrucción de selección de punto flotante, fsel. Esto se puede usar en lugar de una rama si los bloques son tareas simples:

float result = 0;
if (foo > bar) { result = 2.0f; }
else { result = 1.0f; }

Se convierte en:

float result = fsel(foo-bar, 2.0f, 1.0f);

Cuando el primer parámetro es mayor o igual a 0, se devuelve el segundo parámetro, de lo contrario, el tercero.

El precio de perder la rama es que tanto el bloque if {} como el bloque else {} se ejecutarán, por lo que si se trata de una operación costosa o desreferencia un puntero NULL, esta optimización no es adecuada.

A veces su compilador ya ha hecho este trabajo, así que primero verifique su ensamblaje.

Aquí hay más información sobre ramificación y fsel:

http://assemblyrequired.crashworks.org/tag/intrinsics/

Evite los accesos a la memoria y especialmente los aleatorios a toda costa.

Eso es lo más importante para optimizar en las CPU modernas. Puede hacer un montón de aritmética e incluso muchas ramas predichas mal en el tiempo que espera los datos de la RAM.

También puede leer esta regla al revés: haga tantos cálculos como sea posible entre los accesos a la memoria.

Utilice los intrínsecos del compilador.

Asegúrese de que el compilador esté generando el ensamblaje más eficiente para ciertas operaciones utilizando intrínsecos: construcciones que parecen llamadas a funciones que el compilador convierte en ensamblaje optimizado:

Aquí hay una referencia para Visual Studio , y aquí hay una para GCC

Eliminar llamadas a funciones virtuales innecesarias

El envío de una función virtual puede ser muy lento. Este artículo da una buena explicación de por qué. Si es posible, para funciones que se llaman muchas, muchas, muchas veces por cuadro, evítelas.

Puedes hacer esto de dos maneras. A veces puedes reescribir las clases para que no necesiten herencia; tal vez resulta que MachineGun es la única subclase de Arma, y ​​puedes amalgamarlas.

Puede usar plantillas para reemplazar el polimorfismo en tiempo de ejecución con el polimorfismo en tiempo de compilación. Esto solo funciona si conoce el subtipo de sus objetos en tiempo de ejecución, y puede ser una gran reescritura.

Mi principio básico es: no hagas nada que no sea necesario .

Si descubrió que una función en particular es un cuello de botella, podría optimizar la función, o podría tratar de evitar que se llame en primer lugar.

Esto no significa necesariamente que esté utilizando un algoritmo incorrecto. Puede significar que está ejecutando cálculos cada fotograma que se puede almacenar en caché por un corto tiempo (o completamente precalculado), por ejemplo.

Siempre intento este enfoque antes de cualquier intento de optimización de muy bajo nivel.

Use SIMD (por SSE), si aún no lo ha hecho. Gamasutra tiene un buen artículo sobre esto . Puede descargar el código fuente de la biblioteca presentada al final del artículo.

Minimice las cadenas de dependencia para hacer un mejor uso de la línea de CPU.

En casos simples, el compilador puede hacer esto por usted si habilita el desenrollado de bucles. Sin embargo, a menudo no lo hará, especialmente cuando hay flotantes involucrados, ya que reordenar las expresiones cambia el resultado.

Ejemplo:

float *data = ...;
int length = ...;

// Slow version
float total = 0.0f;
int i;
for (i=0; i < length; i++)
{
  total += data[i]
}

// Fast version
float total1, total2, total3, total4;
for (i=0; i < length-3; i += 4)
{
  total1 += data[i];
  total2 += data[i+1];
  total3 += data[i+2];
  total4 += data[i+3];
}
for (; i < length; i++)
{
  total += data[i]
}
total += (total1 + total2) + (total3 + total4);

No pase por alto su compilador: si está utilizando gcc en Intel, podría obtener fácilmente un aumento de rendimiento al cambiar al Compilador Intel C / C ++, por ejemplo. Si está apuntando a una plataforma ARM, consulte el compilador comercial de ARM. Si está en el iPhone, Apple simplemente permitió usar Clang a partir del SDK de iOS 4.0.

Un problema con el que probablemente se encontrará con la optimización, especialmente en el x86, es que muchas cosas intuitivas terminan trabajando en su contra en las implementaciones modernas de CPU. Desafortunadamente para la mayoría de nosotros, la capacidad de optimizar el compilador ya no existe. El compilador puede programar instrucciones en la secuencia en función de su propio conocimiento interno de la CPU. Además, la CPU también puede reprogramar las instrucciones en función de sus propias necesidades. Incluso si piensa en una forma óptima de organizar un método, lo más probable es que el compilador o la CPU ya lo haya logrado por sí mismo y ya haya realizado esa optimización.

Mi mejor consejo sería ignorar las optimizaciones de bajo nivel y centrarnos en las de nivel superior. El compilador y la CPU no pueden cambiar su algoritmo de un algoritmo O (n ^ 2) a un algoritmo O (1), sin importar cuán buenos sean. Eso requerirá que mire exactamente lo que está tratando de hacer y encuentre una mejor manera de hacerlo. Deje que el compilador y la CPU se preocupen por el nivel bajo y se concentre en los niveles medio a alto.

La palabra clave restrictiva es potencialmente útil, especialmente en los casos en que necesita manipular objetos con punteros. Permite que el compilador asuma que el objeto señalado no se va a modificar de ninguna otra manera, lo que a su vez le permite realizar una optimización más agresiva, como mantener partes del objeto en registros o reordenar lecturas y escrituras de manera más efectiva.

Una cosa buena de la palabra clave es que es una pista que puede aplicar una vez y ver los beneficios sin reorganizar su algoritmo. El lado malo es que si lo usa en el lugar equivocado, es posible que vea corrupción de datos. Pero, por lo general, es bastante fácil detectar dónde es legítimo usarlo: es uno de los pocos ejemplos en los que se puede esperar razonablemente que el programador sepa más de lo que el compilador puede asumir con seguridad, por lo que se ha introducido la palabra clave.

Técnicamente, 'restringir' no existe en C ++ estándar, pero los equivalentes específicos de la plataforma están disponibles para la mayoría de los compiladores de C ++, por lo que vale la pena considerarlo.

Ver también: http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

Const todo!

Cuanta más información le dé al compilador sobre los datos, mejores serán las optimizaciones (al menos en mi experiencia).

void foo(Bar * x) {...;}

se convierte

void foo(const Bar * const x) {...;}

El compilador ahora sabe que el puntero x no va a cambiar y que los datos a los que apunta tampoco cambiarán.

El otro beneficio adicional es que puede reducir la cantidad de errores accidentales, deteniéndose (u otros) modificando cosas que no deberían.

Muy a menudo, la mejor manera de ganar rendimiento es cambiar su algoritmo. Cuanto menos general sea la implementación, más cerca podrá llegar al metal.

Suponiendo que se haya hecho ...

Si realmente es un código crítico, trate de evitar lecturas de memoria, trate de evitar calcular cosas que puedan calcularse previamente (aunque no hay tablas de búsqueda ya que violan la regla número 1). Sepa lo que hace su algoritmo y escríbalo de una manera que el compilador también lo sepa. Verifique el ensamblaje para asegurarse de que lo haga.

Evite los errores de caché. Procese por lotes tanto como pueda. Evite funciones virtuales y otras indirecciones.

En definitiva, medir todo. Las reglas cambian todo el tiempo. Lo que solía acelerar el código hace 3 años ahora lo ralentiza. Un buen ejemplo es 'usar funciones matemáticas dobles en lugar de versiones flotantes'. No me habría dado cuenta de eso si no lo hubiera leído.

Lo olvidé: no los constructores predeterminados inicializan sus variables, o si insiste, al menos también cree constructores que no. Tenga en cuenta las cosas que no aparecen en los perfiles. Cuando pierde un ciclo innecesario por línea de código, no aparecerá nada en su generador de perfiles, pero perderá muchos ciclos en general. Nuevamente, sepa lo que está haciendo su código. Haga que su función principal sea delgada en lugar de infalible. Se pueden llamar versiones infalibles si es necesario, pero no siempre se necesitan. La versatilidad tiene un precio: el rendimiento es uno.

Editado para explicar por qué no hay inicialización predeterminada: una gran cantidad de código dice: Vector3 bla; bla = DoSomething ();

La inicialización en el constructor es tiempo perdido. Además, en este caso el tiempo perdido es pequeño (probablemente borrando el vector), sin embargo, si sus programadores hacen esto habitualmente, se acumula. Además, muchas funciones crean un temporal (piense en operadores sobrecargados), que se inicializa a cero y se asigna inmediatamente. Ciclos perdidos ocultos que son demasiado pequeños para ver un pico en su generador de perfiles, pero sangran ciclos en toda su base de código. Además, algunas personas hacen mucho más en constructores (que obviamente es un no-no). He visto ganancias de varios milisegundos de una variable no utilizada donde el constructor resultó ser un poco pesado. Tan pronto como el constructor cause efectos secundarios, el compilador no podrá desactivarlo, por lo que, a menos que nunca use el código anterior, prefiero un constructor que no se inicialice o, como dije,

Vector3 bla (noInit); bla = hacer algo ();

Reduce la evaluación de expresiones booleanas

Este es realmente desesperado, ya que es un cambio muy sutil pero peligroso en su código. Sin embargo, si tiene un condicional que se evalúa una cantidad excesiva de veces, puede reducir la sobrecarga de la evaluación booleana utilizando operadores bit a bit en su lugar. Entonces:

if ((foo && bar) || blah) { ... } 

Se convierte en:

if ((foo & bar) | blah) { ... }

Usando aritmética de enteros en su lugar. Si sus foos y barras son constantes o evaluados antes de if (), esto podría ser más rápido que la versión booleana normal.

Como beneficio adicional, la versión aritmética tiene menos ramas que la versión booleana regular. Que es otra forma de optimizar .

El gran inconveniente es que pierde la evaluación perezosa: se evalúa todo el bloque, por lo que no puede hacerlo foo != NULL & foo->dereference(). Debido a esto, es discutible que esto sea difícil de mantener, por lo que la compensación puede ser demasiado grande.

Vigila el uso de tu stack

Todo lo que agrega a la pila es un empuje y construcción adicionales cuando se llama a una función. Cuando se requiere una gran cantidad de espacio de pila, a veces puede ser beneficioso asignar memoria de trabajo con anticipación, y si la plataforma en la que está trabajando tiene una RAM rápida disponible para su uso, ¡mucho mejor!