it-swarm-es.com

¿Qué técnicas simples utilizas para mejorar el rendimiento?

Estoy hablando de la forma en que escribimos rutinas simples para mejorar el rendimiento sin hacer que su código sea más difícil de leer ... por ejemplo, esto es lo típico que aprendimos:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

Pero, generalmente hago esto cuando un foreach no es aplicable:

for(int i = 0, j = collection.length(); i < j; i++ ){
   // stuff here
}

Creo que este es un mejor enfoque ya que llamará al método length solo una vez ... mi novia dice que es críptico. ¿Hay algún otro truco simple que uses en tus propios desarrollos?

21
Cristian

inserte una conferencia sobre discusión prematura es la raíz de todo mal

Dicho esto, aquí hay algunos hábitos que he adquirido para evitar una eficiencia innecesaria y, en algunos casos, hacer que mi código sea más simple y más correcto también.

Esto no es una discusión de principios generales, sino de algunas cosas a tener en cuenta para evitar la introducción de ineficiencias innecesarias en el código.

Conoce tu big-O

Esto probablemente debería fusionarse en la larga discusión anterior. Es de sentido común que un bucle dentro de un bucle, donde el bucle interno repite un cálculo, va a ser más lento. Por ejemplo:

for (i = 0; i < strlen(str); i++) {
    ...
}

Esto tomará una cantidad de tiempo horrible si la cadena es realmente larga, porque la longitud se recalcula en cada iteración del bucle. Tenga en cuenta que GCC en realidad optimiza este caso porque strlen() está marcado como una función pura.

Al ordenar un millón de enteros de 32 bits, la ordenación de burbujas sería el camino equivocado . En general, la clasificación se puede realizar en tiempo O (n * log n) (o mejor, en el caso de la clasificación por radix), por lo que, a menos que sepa que sus datos serán pequeños, busque un algoritmo que sea al menos O (n * log n).

Del mismo modo, cuando se trata de bases de datos, tenga en cuenta los índices. Si SELECT * FROM people WHERE age = 20, Y no tiene un índice de personas (edad), requerirá una exploración secuencial O(n)) en lugar de una O mucho más rápida ( registro n) exploración de índice.

Jerarquía aritmética de enteros

Al programar en C, tenga en cuenta que algunas operaciones aritméticas son más caras que otras. Para enteros, la jerarquía es algo como esto (menos costoso primero):

  • + - ~ & | ^
  • << >>
  • *
  • /

Por supuesto, el compilador generalmente optimizará cosas como n / 2 A n >> 1 Automáticamente si está apuntando a una computadora convencional, pero si está apuntando a un dispositivo integrado, es posible que no obtenga ese lujo.

Además, % 2 Y & 1 Tienen semánticas diferentes. La división y el módulo generalmente se redondea hacia cero, pero su implementación está definida. El buen ol '>> Y & Siempre se redondea hacia el infinito negativo, lo que (en mi opinión) tiene mucho más sentido. Por ejemplo, en mi computadora:

printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1

Por lo tanto, usa lo que tiene sentido. ¡No pienses que estás siendo un buen chico usando % 2 Cuando originalmente ibas a escribir & 1.

Operaciones costosas de coma flotante

Evite operaciones pesadas de coma flotante como pow() y log() en código que realmente no las necesita, especialmente cuando se trata de enteros. Tome, por ejemplo, leer un número:

int parseInt(const char *str)
{
    const char *p;
    int         digits;
    int         number;
    int         position;

    // Count the number of digits
    for (p = str; isdigit(*p); p++)
        {}
    digits = p - str;

    // Sum the digits, multiplying them by their respective power of 10.
    number = 0;
    position = digits - 1;
    for (p = str; isdigit(*p); p++, position--)
        number += (*p - '0') * pow(10, position);

    return number;
}

Este uso de pow() (y las conversiones int <-> double necesarias para usarlo) no solo es bastante costoso, sino que crea una oportunidad de pérdida de precisión (por cierto , el código anterior no tiene problemas de precisión). Es por eso que me estremezco cuando veo este tipo de función utilizada en un contexto no matemático.

Además, observe cómo el siguiente algoritmo "inteligente", que se multiplica por 10 en cada iteración, es en realidad más conciso que el código anterior:

int parseInt(const char *str)
{
    const char *p;
    int         number;

    number = 0;
    for (p = str; isdigit(*p); p++) {
        number *= 10;
        number += *p - '0';
    }

    return number;
}
28
Joey Adams

Por su pregunta y el hilo de comentarios, parece que "piensa" que este cambio de código mejora el rendimiento, pero realmente no sabe si lo hace o no.

Soy fanático de Kent Beck's filosofía:

"Haz que funcione, hazlo bien, hazlo rápido".

Mi técnica para mejorar el rendimiento del código, es primero obtener el código pasando las pruebas unitarias y bien factorizado y luego (particularmente para las operaciones de bucle) escribir una prueba unitaria que verifique el rendimiento y luego refactorizar el código o pensar en un algoritmo diferente si el I ' He elegido no funciona como se esperaba.

Por ejemplo, para probar la velocidad con código .NET, uso atributo de tiempo de espera de NUnit para escribir afirmaciones de que una llamada a un método en particular se ejecutará dentro de un cierto período de tiempo.

Usando algo como el atributo de tiempo de espera de NUnit con el ejemplo de código que proporcionó (y una gran cantidad de iteraciones para el bucle), en realidad podría probar si su "mejora" del código realmente ayudó con el rendimiento de ese bucle.

Un descargo de responsabilidad: si bien esto es efectivo en el nivel "micro", ciertamente no es la única forma de probar el rendimiento y no tiene en cuenta los problemas que puedan surgir en el nivel "macro", pero es un buen comienzo.

13
Paddyslacker

Tenga en cuenta que su compilador bien puede convertir:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

dentro:

int j = collection.length();
for(int i = 0; i < j; i++ ){
   // stuff here
}

o algo similar, si collection no cambia durante el ciclo.

Si este código se encuentra en una sección de tiempo crítico de su aplicación, valdría la pena averiguar si este es el caso o no, o de hecho si puede cambiar las opciones del compilador para hacerlo.

Esto mantendrá la legibilidad del código (ya que el primero es lo que la mayoría de la gente esperará ver), mientras le brinda esos pocos ciclos de máquina adicionales. Entonces eres libre de concentrarte en las otras áreas donde el compilador no puede ayudarte.

En una nota al margen: si cambia collection dentro del ciclo agregando o eliminando elementos (sí, sé que es una mala idea, pero sucede) entonces su segundo ejemplo tampoco se repetirá sobre todos los elementos o intentará acceder más allá del final de la matriz.

11
ChrisF

Este tipo de optimización generalmente no se recomienda. Esa compilación se puede hacer fácilmente por compilador, está trabajando con un lenguaje de programación de nivel superior en lugar de ensamblador, así que piense en el mismo nivel.

9
tactoth

Bueno, el primer consejo sería evitar tales optimizaciones prematuras hasta que sepa exactamente qué está sucediendo con el código, de modo que esté seguro de que realmente lo está haciendo más rápido y no más lento.

En C #, por ejemplo, el compilador optimizará el código si está recorriendo la longitud de una matriz, ya que sabe que no tiene que verificar el rango cuando accede a la matriz. Si intenta optimizarlo poniendo la longitud de la matriz en una variable, romperá la conexión entre el bucle y la matriz, y en realidad hará que el código sea mucho más lento.

Si va a realizar una micro optimización, debe limitarse a cosas que se sabe que utilizan muchos recursos. Si solo hay un ligero aumento en el rendimiento, debe optar por el código más fácil de leer y mantener. La forma en que el trabajo de la computadora cambia con el tiempo, por lo que algo que descubras es un poco más rápido ahora, puede que no permanezca así.

3
Guffa

Es posible que esto no se aplique tanto a la codificación de uso general, pero en la actualidad hago principalmente desarrollo integrado. Tenemos un procesador de destino específico (que no va a ser más rápido; parecerá obsoleto para cuando retiren el sistema en más de 20 años) y plazos de tiempo muy restrictivos para gran parte del código. El procesador, como todos los procesadores, tiene ciertas peculiaridades con respecto a qué operaciones son rápidas o lentas.

Tenemos una técnica utilizada para garantizar que estamos generando el código más eficiente, mientras mantenemos la legibilidad para todo el equipo. En aquellos lugares donde la construcción del lenguaje más natural no genera el código más eficiente, hemos creado una macros que aseguran el uso del código óptimo. Si hacemos un proyecto de seguimiento para un procesador diferente, podemos actualizar las macros para el método óptimo en ese procesador.

Como ejemplo específico, para nuestro procesador actual, las ramas vacían la tubería, deteniendo el procesador durante 8 ciclos. El compilador toma este código:

 bool isReady = (value > TriggerLevel);

y lo convierte en el equivalente de la Asamblea de

isReady = 0
if (value > TriggerLevel)
{
  isReady = 1;
}

Esto tomará 3 ciclos o 10 si salta sobre isReady=1;. Pero el procesador tiene una instrucción max de ciclo único, por lo que es mucho mejor escribir código para generar esta secuencia, que garantiza que siempre tomará 3 ciclos:

diff = value-TriggerLevel;
diff = max(diff, 0);
isReady = min(1,diff);

Obviamente, la intención aquí es menos clara que la original. Así que hemos creado una macro, que usamos siempre que queremos una comparación booleana Mayor que:

#define BOOL_GT(a,b) min(max((a)-(b),0),1)

//isReady = value > TriggerLevel;
isReady = BOOL_GT(value, TriggerLevel);

Podemos hacer cosas similares para otras comparaciones. Para un extraño, el código es un poco menos legible que si solo usáramos la construcción natural. Sin embargo, se aclara rápidamente después de pasar un poco de tiempo trabajando con el código, y es mucho mejor que dejar que cada programador experimente con sus propias técnicas de optimización.

3
AShelly

Tengo una técnica muy simple.

  1. Hago que mi código funcione.
  2. Lo pruebo para la velocidad.
  3. Si es rápido, vuelvo al paso 1 para alguna otra característica. Si es lento, lo perfilo para encontrar el cuello de botella.
  4. Arreglo el cuello de botella. Regrese al paso 1.

Hay muchas ocasiones en las que se ahorra tiempo para eludir este proceso, pero en general sabrá si ese es el caso. Si hay dudas, me quedo con esto por defecto.

3
Jason Baker

Aproveche el cortocircuito:

if(someVar || SomeMethod())

toma tanto tiempo codificar y es tan legible como:

if(someMethod() || someVar)

sin embargo, se evaluará más rápidamente con el tiempo.

2
realworldcoder
  1. Perfil. ¿Tenemos siquiera un problema? ¿Dónde?
  2. En el 90% de los casos donde de alguna manera es IO relacionado, aplique el almacenamiento en caché (y tal vez obtenga más memoria)
  3. Si está relacionado con la CPU, aplique el almacenamiento en caché
  4. Si el rendimiento sigue siendo un problema, hemos dejado el ámbito de las técnicas simples: hacer los cálculos.
1
Maglob

El más simple para mí es usar la pila cuando sea posible siempre que un patrón de uso de caso común se ajuste a un rango de, por ejemplo, [0, 64), pero tiene casos raros que no tienen un límite superior pequeño.

Ejemplo simple de C (antes):

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int* values = calloc(n, sizeof(int));

    // do stuff with values
    ...
    free(values);
}

Y después:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int values_mem[64] = {0}
    int* values = (n <= 64) ? values_mem: calloc(n, sizeof(int));

    // do stuff with values
    ...
    if (values != values_mem)
        free(values);
}

He generalizado esto así, ya que este tipo de puntos críticos surgen mucho en la creación de perfiles:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    MemFast values_mem;
    int* values = mf_calloc(&values_mem, n, sizeof(int));

    // do stuff with values
    ...

    mf_free(&values_mem);
}

Lo anterior usa la pila cuando los datos que se asignan son lo suficientemente pequeños en esos casos de 99.9%, y usa el montón de lo contrario.

En C++, he generalizado esto con una secuencia pequeña compatible con el estándar (similar a las implementaciones SmallVector) que gira en torno al mismo concepto.

No es una optimización épica (he obtenido reducciones de, por ejemplo, 3 segundos para que una operación se complete hasta 1,8 segundos), pero requiere un esfuerzo tan trivial para aplicar. Cuando puede bajar algo de 3 segundos a 1.8 segundos simplemente introduciendo una línea de código y cambiando dos, es una buena inversión para un dólar tan pequeño.

1
user204677

se las mejores herramientas que pueda encontrar - buen compilador, buen perfilador, buenas bibliotecas. Obtenga los algoritmos correctos, o mejor aún: use la biblioteca correcta para hacerlo por usted. Las optimizaciones de bucles triviales son pequeñas, además de que no eres tan inteligente como el compilador de optimización.

1
Job

Espere seis meses, haga que su jefe compre computadoras nuevas para todos. Seriamente. El tiempo del programador es mucho más costoso que el hardware a largo plazo. Las computadoras de alto rendimiento permiten a los codificadores escribir código de manera directa sin preocuparse por la velocidad.

1
Michael Kristofik

Intente no optimizar demasiado antes de tiempo, luego, cuando optimice, preocúpese un poco menos por la legibilidad.

Hay poco que odio más que la complejidad innecesaria, pero cuando llegas a una situación compleja, a menudo se requiere una solución compleja.

Si escribe el código de la manera más obvia, haga un comentario que explique por qué se ha modificado cuando realiza el cambio complejo.

Sin embargo, específicamente para su significado, encuentro que muchas veces hacer el enfoque booleano opuesto al enfoque predeterminado a veces ayuda:

for(int i = 0, j = collection.length(); i < j; i++ ){
// stuff here
}

puede llegar a ser

for(int i = collection.length(); i > 0; i-=1 ){
// stuff here
}

En muchos idiomas, siempre y cuando realice los ajustes apropiados a la parte "cosas" y aún sea legible. Simplemente no aborda el problema de la manera en que la mayoría de la gente pensaría en hacerlo primero porque cuenta al revés.

en c # por ejemplo:

        string[] collection = {"a","b"};

        string result = "";

        for (int i = 0, j = collection.Count() - 1; i < j; i++)
        {
            result += collection[i] + "~";
        }

también podría escribirse como:

        for (int i = collection.Count() - 1; i > 0; i -= 1)
        {
            result = collection[i] + "~" + result;
        }

(y sí, debería hacerlo con una unión o un generador de cadenas, pero estoy tratando de hacer un ejemplo simple)

Hay muchos otros trucos que se pueden usar que no son difíciles de seguir, pero muchos de ellos no se aplican en todos los idiomas, como usar el medio en el lado izquierdo de una tarea en vb antiguo para evitar la penalización de reasignación de cadenas o leer archivos de texto en modo binario en .net para superar la penalización de almacenamiento en búfer cuando el archivo es demasiado grande para una lectura final.

El único otro caso realmente genérico en el que puedo pensar que se aplicaría en todas partes sería aplicar un poco de álgebra booleana a condicionales complejos para tratar de transformar la ecuación en algo que tenga una mejor oportunidad de aprovechar un condicional de cortocircuito o convertir un complejo conjunto de declaraciones anidadas if-then o case en una ecuación completamente. Ninguno de estos funciona en todos los casos, pero pueden ahorrar mucho tiempo.

1
Bill

Tengo un punto de vista diferente. Simplemente seguir los consejos que recibes aquí no va a hacer mucha diferencia, porque hay algunos errores que debes cometer, que luego debes corregir, de los cuales debes aprender.

El error que debe cometer es diseñar su estructura de datos de la manera en que todos lo hacen. Es decir, con datos redundantes y muchas capas de abstracción, con propiedades y notificaciones que se propagan por toda la estructura tratando de mantenerla consistente.

Entonces usted necesita hacer ajustes de rendimiento (perfilado) y hacer que le muestre cómo, de muchas maneras, lo que le está costando montones de ciclos son las muchas capas de abstracción, con propiedades y notificaciones que se propagan a lo largo del estructura tratando de mantenerlo consistente.

Es posible que pueda solucionar estos problemas de alguna manera sin cambios importantes en el código.

Entonces, si tiene suerte, puede aprender que una estructura de datos menor es mejor, y que es mejor ser capaz de tolerar inconsistencias temporales que tratar de mantener muchas cosas estrechamente de acuerdo con las oleadas de mensajes.

La forma en que escribes bucles realmente no tiene nada que ver con eso.

0
Mike Dunlavey

Bueno, hay muchos cambios de rendimiento que puede hacer al acceder a los datos que tendrán un gran impacto en su aplicación. Si escribe consultas o usa un ORM para acceder a una base de datos, entonces necesita leer algunos libros de ajuste de rendimiento para la base de datos que utiliza. Lo más probable es que esté utilizando técnicas conocidas de bajo rendimiento. No hay razón para hacer esto, excepto la ignorancia. Esto no es una optimización prematura (maldigo al tipo que dijo esto porque ha sido tan ampliamente interpelado como para no preocuparse nunca por el rendimiento), este es un buen diseño.

Solo una muestra rápida de los mejoradores de rendimiento para SQL Server: use índices apropiados, evite los cursores: use lógica basada en conjuntos, use cláusulas sargable where, no acumule vistas encima de las vistas, no devuelva más datos de los que necesita o más columnas de las que necesita, no use subconsultas correlacionadas.

0
HLGEM

Si esto es C++, deberías acostumbrarte a ++i más bien que i++. ++i nunca será peor, significa exactamente lo mismo que una declaración independiente, y en algunos casos podría ser una mejora del rendimiento.

No vale la pena cambiar el código existente en caso de que sea útil, pero es un buen hábito.

0
David Thornley