Sé que solo debe optimizar las cosas cuando se considere necesario. Pero, si se considera necesario, ¿cuáles son sus trucos de optimización favoritos de bajo nivel (a diferencia del nivel algorítmico)?¿Cuáles son tus trucos favoritos de optimización de código de bajo nivel?
Por ejemplo: loop unrolling.
gcc -O2
Los compiladores hacen un trabajo mucho mejor que usted.
++i puede ser más rápido que i++, porque evita crear un temporal.
Si esto todavía se aplica a los compiladores modernos de C/C++/Java/C#, no lo sé. Puede ser diferente para los tipos definidos por el usuario con operadores sobrecargados, mientras que en el caso de los enteros simples, probablemente no importe.
Pero me ha gustado la sintaxis ... se lee como "incrementar i", lo cual es una orden sensata.
los compiladores más modernos no crearán el temporal si solo se usa como una declaración y no como una expresión. – Javier
Recogiendo una potencia de dos para los filtros, tampones circulares, etc.
Así que muy, muy conveniente.
-Adam
¿Puede alguien en palabras cortas explicar cuál es el truco? Lo encuentras todo el tiempo, pero nunca lo descubrí ... – daspostloch
@daspostloch - La idea es que a menudo tienes que realizar la comprobación de límites y el truncamiento en cosas que acceden a los datos. Esto significa hacer 'if (input> MAX_SIZE) input = input - MAX_SIZE;' por ejemplo. Sin embargo, si la estructura tiene una potencia de dos, entonces tanto la verificación como la matemática se pueden hacer con una operación 'Y'. Por ejemplo, si el tamaño de los datos es 128, entonces 'input = input & 0x7F;' truncará todo por encima de 128, y de lo contrario dejará 'input' solo, lo que significa que la instrucción' if' anterior puede eliminarse. –
gracias, un orificio cosido :) – daspostloch
Contando un ciclo. Es más barato con el que comparar 0 a N:
for (i = N; --i >= 0;) ...
cambiando y enmascaramiento por potencias de dos es más barato que la división y el resto,/y%
#define WORD_LOG 5
#define SIZE (1 << WORD_LOG)
#define MASK (SIZE - 1)
uint32_t bits[K]
void set_bit(unsigned i)
{
bits[i >> WORD_LOG] |= (1 << (i & MASK))
}
Editar
(i >> WORD_LOG) == (i/SIZE) and
(i & MASK) == (i % SIZE)
porque SIZE es 32 o 2^5.
Los compiladores son capaces de convertir un ciclo en el formulario de cuenta regresiva más rápido automáticamente, si la variable de índice no se usa en ninguna expresión. –
me gusta el conteo regresivo; pero principalmente porque hace que los bucles while() {..} sean más agradables que para (;;) {...} – Javier
Los compiladores son bastante inteligentes hoy en día sobre la implementación de divisiones mediante una constante usando cambios y otros trucos (ver http: // hexblog. com/2005/11/do_you_know_the_division_opera.html). Pero luego, a veces no están (http://hexblog.com/2005/12/the_longest_arithmetic_operati.html) –
vfork() en lugar de fork() antes exec()las implementaciones modernas de fork() usan copy on write, que junto con algunos hacks ampliamente utilizados, lo hacen tan rápido como vfork(). en Linux, vfork() llama a clone(), al igual que fork() – Javier
vfork() siempre será al menos un error de página más rápido, y verá el indicador en clone() que es CLONE_VFORK. El espacio de memoria del proceso principal todavía está allí. Pruébalo con una variable volátil si no me crees. – Joshua
+1 para generación de código, si algunos de los datos cambian muy pocas veces, es una gran victoria. No solo más rápido, pero quizás sorprendentemente, más simple de escribir. –
Inspeccione la salida del compilador, luego intente forzarlo para que haga algo más rápido.
sí, no hay nada mejor para matar un poco de tiempo de holgura. solo tenga cuidado de hacer que el código fuente sea más legible, no menos. (Agrega algo más al desafío :-) – Javier
Con los procesadores de hoy en día, no se puede decir qué es más rápido simplemente mirando la salida del compilador. Si lo perfila de diferentes maneras, es posible que pueda decir por qué un método es más rápido que otro, pero podría no aplicarse a la siguiente pieza de código. –
Puede hacerlo si el compilador emite patrones de código de operación que se sabe que son lentos. Por ejemplo, cambios variables en un chip PPC o en cualquier cantidad de tiendas cargadas. Es menos útil en el caso general, pero para los hotspots es definitivamente útil. – MSN
Por qué, bit twiddling hacks, por supuesto!
Asignando con nuevo en un búfer preasignado usando la colocación de C++ nueva.
Uso de metaprogramación de plantillas para calcular cosas en tiempo de compilación en lugar de en tiempo de ejecución.
eso es lo que me gusta de los lenguajes de scripting, puede hacer muchos cálculos en tiempo de carga para acelerar el tiempo de ejecución posterior.concedido, 'load time' es realmente solo parte del tiempo de ejecución, pero aun así separemos las preocupaciones sobre el rendimiento. – Javier
Nunca pensé en esto. ¿Tienes algún ejemplo? –
Uno de los códigos científicos más útiles es reemplazar pow(x,4) con x*x*x*x.Pow es casi siempre más caro que la multiplicación. Esto es seguido por
for(int i = 0; i < N; i++)
{
z += x/y;
}
a
double denom = 1/y;
for(int i = 0; i < N; i++)
{
z += x*denom;
}
Pero mi favorita optimización de bajo nivel es averiguar qué cálculos se pueden eliminar de un bucle. Siempre es más rápido hacer el cálculo una vez en lugar de N veces. Dependiendo de su compilador, algunos de estos se pueden hacer automáticamente por usted.
todos los compiladores ligeramente optimizados realizan al menos la eliminación de código muerto y el movimiento de código invariante de bucle (el que usted describe aquí). aún así, yo también tiendo a hacerlo manualmente. especialmente si hace que el algoritmo sea más claro. – Javier
Lo creas o no, he visto ganancias de rendimiento reales cuando el denominador es un poco más complicado. Incluso con el compilador de Intel. Además, no estoy hablando de un código muerto, sino de un código que no necesita ejecutarse dentro del ciclo. – Steve
Creo que los compiladores modernos pueden hacer fácilmente este tipo de optimizaciones – user
En SQL, si sólo necesita saber si existe o no algún dato, no se moleste con COUNT(*):
SELECT 1 FROM table WHERE some_primary_key = some_value
Si su cláusula WHERE es probable que volver varias filas, agregue un LIMIT 1 también.
(Recuerde que las bases de datos no pueden ver lo que el código está haciendo con sus resultados, así que no pueden optimizar estas cosas desaparecen por sí solos!)
¿Por qué no lanzar el LIMIT 1 independientemente? – strager
Sí, siempre LÍMITE 1/TOP 1 aquí. Fast-first-row es lo que quieres. – Joshua
Eché un vistazo al plan de consultas de Postgres con y sin, y poner un límite a una selección de una sola fila simplemente parece agregar sobrecarga. Sin embargo, tal vez sea diferente para otros sistemas DB. – flussence
que he encontrado que el cambio de un puntero al acceso indexado puede hacer una diferencia; el compilador tiene diferentes formularios de instrucciones y registra usos para elegir. Viceversa, también. Sin embargo, esto es de muy bajo nivel y dependiente del compilador, y solo es bueno cuando necesitas ese último porcentaje.
E.g.
for (i = 0; i < n; ++i)
*p++ = ...; // some complicated expression
vs
for (i = 0; i < n; ++i)
p[i] = ...; // some complicated expression
Eso me parece bastante obvio, dos incrementos contra uno. ¿Qué hay de poner 'p ++' dentro de 'for()' y abandonar 'i' en total? – flussence
Quiere decir para (end = p + n; p! = End; ++ p)? Aquello podría funcionar. Aunque no podría, porque el compilador podría optimizar el bucle 'i'. Realmente tienes que probar estas cosas y ver cuál es la más rápida, porque hay demasiadas variables. –
años con un compilier no tan inteligente, tengo un gran rendimiento de función línea, punteros en lugar de matrices de indexación caminar, y la iteración hasta llegar a cero en lugar de hasta a un máximo
En caso de duda, un poco de conocimiento de la asamblea le permitirá fijamos en lo que el compilador está produciendo y atacar a las partes ineficientes (en su idioma de origen, utilizando estructuras más amigable con su compilador.)
Con los procesadores de hoy en día, mirar el ensamblaje solo lo llevará tan lejos. Realmente necesitas medir el tiempo. –
Buen punto. Estaba pensando en un caso donde el compilador usó RAM cuando había muchos registros. Terminé reescribiendo ese programa en ensamblaje, pero los sistemas integrados son una especie de mundo diferente. –
Estoy de acuerdo. Y no me gusta un compilador demasiado inteligente. Solo quiero que sea una buena ASM para mí. –
que no lo haría necesariamente lo llamo una optimización de bajo nivel, pero he guardado órdenes de magnitud más ciclos a través de una aplicación juiciosa de almacenamiento en caché que el que tengo a través de todas mis aplicaciones de trucos de bajo nivel combinados. Muchos de estos métodos son aplicaciones específicas.
if o for declaraciones. CPUs y compiladoresestán cambiando constantemente. Cualquiera que sea el truco de código de bajo nivel que tuvo sentido hace 3 CPUs con un compilador diferente, en realidad puede ser más lento en la arquitectura actual y hay muchas posibilidades de que este truco pueda confundir a quien mantenga este código en el futuro.
En cualquier caché no trivial, debe preocuparse por la gestión del caché: tamaño, antigüedad, invalidación, corrección. Lo que agrega sobrecarga, complejidad y una nueva fuente de errores. Aún así, el almacenamiento en caché juicioso es enormemente efectivo. –
valores puede calcular previamente.
Por ejemplo, en lugar de sen (a) o cos (a), si su aplicación no necesita necesariamente ángulos para ser muy precisos, tal vez represente ángulos en 1/256 de un círculo y cree matrices de flotadores seno [] y coseno [] precalculando el pecado y el cos de esos ángulos.
Y, si necesita un vector en un ángulo de una determinada longitud con frecuencia, puede calcular previamente todos los senos y cosenos ya multiplicados por esa longitud.
O, para decirlo en términos más generales, cambie la memoria por velocidad.
O, aún más general, "Toda la programación es un ejercicio de almacenamiento en caché" - Terje Mathisen
Algunas cosas son menos evidentes. Por ejemplo atravesar una matriz de dos dimensiones, es posible hacer algo como
for (x=0;x<maxx;x++)
for (y=0;y<maxy;y++)
do_something(a[x,y]);
Es posible encontrar el caché del procesador le gusta más si lo hace:
for (y=0;y<maxy;y++)
for (x=0;x<maxx;x++)
do_something(a[x,y]);
o viceversa.
No realice el desenrollado del lazo. No hagas el dispositivo de Duff. Haga que sus bucles sean lo más pequeños posible, cualquier otra cosa inhibe el rendimiento x86 y el rendimiento del optimizador gcc.
Deshacerse de las ramas puede ser útil, por lo que deshacerse de los bucles por completo es bueno, y los trucos matemáticos sin sucursales realmente funcionan. Más allá de eso, intente nunca salir de la memoria caché L2, lo que significa que también debe evitarse mucho precálculo/almacenamiento en caché si desperdicia espacio en la caché.
Y, especialmente para x86, intente mantener baja la cantidad de variables en uso en cualquier momento. Es difícil decir qué harán los compiladores con ese tipo de cosas, pero generalmente tener menos variables de iteración de bucle/índices de matriz terminará con una mejor salida de asm.
Por supuesto, esto es para CPU de escritorio; una CPU lenta con acceso rápido a la memoria puede precalcular mucho más, pero en estos días podría ser un sistema integrado con poca memoria total de todos modos ...
Jon Bentley's Writing Efficient Programs es una gran fuente de técnicas de bajo y alto nivel - si puedes encontrar una copia.
ramas La eliminación (si/vigilara) mediante el uso de las matemáticas: booleano
if(x == 0)
x = 5;
// becomes:
x += (x == 0) * 5;
// if '5' was a base 2 number, let's say 4:
x += (x == 0) << 2;
// divide by 2 if flag is set
sum >>= (blendMode == BLEND);
Esto acelera realmente las cosas sobre todo cuando esos IFS están en un bucle o en algún lugar que se está llamando mucho.
Uso liberal de __restrict para eliminar los puestos de carga en la tienda.
El de ensamblador:
xor ax, ax
en lugar de:
mov ax, 0
optimización clásicos para el tamaño del programa y el rendimiento.
Optimización de la localidad de caché, por ejemplo, al multiplicar dos matrices que no se ajustan a la memoria caché.
Rolling up loops.
En serio, la última vez que necesité hacer algo como esto fue en una función que requirió el 80% del tiempo de ejecución, por lo que valía la pena tratar de micro-optimizar si podía obtener un aumento notable en el rendimiento.
Lo primero que hice fue enrollar el circuito. Esto me dio un aumento de velocidad muy significativo. Creo que esto era una cuestión de localidad de caché.
Lo siguiente que hice fue agregar una capa de direccionamiento indirecto, y poner un poco más de lógica en el ciclo, lo que me permitió recorrer solo las cosas que necesitaba. Esto no fue un aumento de velocidad, pero valió la pena hacerlo.
Si va a micro-optimizar, necesita tener una idea razonable de dos cosas: la arquitectura que está usando en realidad (que es muy diferente de los sistemas con los que crecí, al menos para micro- fines de optimización), y lo que el compilador hará por usted.
Muchas de las micro-optimizaciones tradicionales intercambian espacio por tiempo. Hoy en día, usar más espacio aumenta las posibilidades de que falte un caché, y ahí va tu desempeño. Además, muchos de ellos ahora los hacen los compiladores modernos y, por lo general, son mejores de lo que probablemente puedas hacer.
Actualmente, debe (a) hacer un perfil para ver si necesita micro-optimizar, y luego (b) tratar de intercambiar el cálculo por espacio, con la esperanza de mantener tanto como sea posible en el caché. Finalmente, realice algunas pruebas para saber si ha mejorado las cosas o las ha estropeado. Los compiladores y los chips modernos son demasiado complejos para que pueda mantener un buen modelo mental, y la única forma en que sabrá si una optimización funciona o no es poner a prueba.
Además de comentario de Joshua sobre la generación de código (una gran victoria), y otras buenas sugerencias, ...
no estoy seguro si lo llamaría "bajo nivel", pero (y esto es cebo abajo) 1) evite utilizar más niveles de abstracción que los absolutamente necesarios, y 2) evite la programación de estilo de notificación controlada por eventos, si es posible.
Si una computadora que ejecuta un programa es como un automóvil corriendo una carrera, una llamada a un método es como un desvío. Eso no es necesariamente malo, excepto que hay una fuerte tentación de anidar esas cosas, porque una vez que se escribe una llamada al método, se tiende a olvidar lo que la llamada podría costarle.
Si confía en eventos y notificaciones, es porque tiene múltiples estructuras de datos que deben mantenerse de acuerdo. Esto es costoso, y solo debe hacerse si no puede evitarlo.
En mi experiencia, los mayores asesinos de rendimiento son demasiada estructura de datos y demasiada abstracción.
Me quedé sorprendido por la aceleración llegué reemplazando una para los números de lazo añadiendo juntos en estructuras:
const unsigned long SIZE = 100000000;
typedef struct {
int a;
int b;
int result;
} addition;
addition *sum;
void start() {
unsigned int byte_count = SIZE * sizeof(addition);
sum = malloc(byte_count);
unsigned int i = 0;
if (i < SIZE) {
do {
sum[i].a = i;
sum[i].b = i;
i++;
} while (i < SIZE);
}
}
void test_func() {
unsigned int i = 0;
if (i < SIZE) { // this is about 30% faster than the more obvious for loop, even with O3
do {
addition *s1 = &sum[i];
s1->result = s1->b + s1->a;
i++;
} while (i<SIZE);
}
}
void finish() {
free(sum);
}
Por qué no gcc optimizar los bucles en esto? ¿O hay algo que eché de menos? ¿Algún efecto de caché?
¿Qué quiere decir exactamente con el "bucle for" al que está comparando esto? –
"... de lo que puedas" <- caso general. En algunas instancias específicas (como algoritmos, DSP, etc.), un humano puede codificar una rutina de C que parece bastante extraña, pero una vez compilada, genera un mejor ensamblaje para el propósito específico que el compilador. –
Principalmente debido al hecho de que incluso grandes optimizaciones del compilador solo miran ciertos tipos de optimización y secciones más pequeñas de código optimizable. Una vez que comprenda el compilador y el ensamblado, podrá optimizar a mano trozos de código mucho más grandes que el compilador no podría mejorar. –
... pero estoy partiendo los pelos: pocas personas necesitarían hacer esto. Es divertido ver cómo un compilador ha convertido una sección de código en ensamblado: algunas de las optimizaciones del compilador son bastante intrincadas e impares hasta que realmente lo estudias. –