¿Cuál es el significado de la regla 90/10 de optimización de programas?

67

Según Wikipedia, la regla 90/10 de optimización de programas establece que "el 90% del tiempo de ejecución de un programa se gasta en la ejecución del 10% del código" (vea el segundo párrafo aquí ).

Realmente no entiendo esto. ¿Qué significa esto exactamente? ¿Cómo puede gastarse el 90% del tiempo de ejecución solo ejecutando el 10% del código? ¿Qué pasa con el otro 90% del código entonces? ¿Cómo se pueden ejecutar en solo el 10% del tiempo?

Rakshith Ravi
fuente
50
Algunas partes del código pueden ejecutarse con más frecuencia que otras partes. Para eso están los bucles, después de todo. En la práctica, casi siempre algunas partes se ejecutan manera más frecuencia que otros.
Kilian Foth
147
Espere hasta que escuche la regla 90/10 para la duración del proyecto de software: “el 90% del proyecto ocupará el primer 90% del tiempo asignado; el último 10% del proyecto ocupará el otro 90% del tiempo asignado ".
Paul D. Waite
3
Confusión aquí: "se pasa tiempo ejecutando". Considere a++; for(i=0;i<100;i++){b++;} for(i=0;i<100;i++){print(xyz);}. Claro que el primer ciclo for gasta mucho más que la primera instrucción, pero el segundo ciclo for gasta ~ 1000 veces más tiempo que el primer ciclo for, pero no se ejecuta . La gasta esperando la impresión . Entonces, hay una diferencia entre el tiempo dedicado a la ejecución y el tiempo del que es responsable el código .
Mike Dunlavey
32
@ Paul_D._Waite Pensé que era que el 90% del proyecto tomó el 90% del tiempo, el 90% de lo que queda toma otro 90% del tiempo, y así sucesivamente una serie no convergente a la conclusión de que ningún proyecto es alguna vez terminado o completamente eliminado en menos de un tiempo infinito.
nigel222
9
Para ejemplos prácticos, un par de códigos en los que trabajé (modelos científicos) usaron una gran cantidad de código (~ 10K líneas) para leer y configurar el modelo, luego hicieron un ciclo a través de unos cientos de líneas para hacer los cálculos reales. Pero ese bucle corto era n ^ 4 (tres dimensiones espaciales iteradas a través de miles de pasos de tiempo), por lo que tomó días para calcular. Entonces, la proporción real fue probablemente más del 99% / 1% :-)
jamesqf

Respuestas:

184

Aquí hay dos principios básicos en juego:

  • Algunos códigos se ejecutan con mucha más frecuencia que otros. Por ejemplo, es posible que algún código de manejo de errores nunca se use. Algunos códigos se ejecutarán solo cuando inicie su programa. Otro código se ejecutará una y otra vez mientras se ejecuta su programa.
  • Algunos códigos tardan mucho más en ejecutarse que otros. Por ejemplo, una sola línea que ejecuta una consulta en una base de datos o extrae un archivo de Internet probablemente llevará más tiempo que millones de operaciones matemáticas.

La regla 90/10 no es literalmente cierta. Varía según el programa (y dudo que haya alguna base para los números específicos 90 y 10; alguien probablemente los sacó de la nada). Pero el punto es que si necesita que su programa se ejecute más rápido, probablemente solo un pequeño número de líneas es importante para que eso suceda. Identificar las partes lentas de su software es a menudo la mayor parte de la optimización.

Esta es una idea importante, y significa que las decisiones que parecen contradictorias para un nuevo desarrollador a menudo pueden ser correctas. Por ejemplo:

  • Hay un montón de código que no vale la pena hacer "mejor" , incluso si está haciendo las cosas de una manera tonta y simplista. ¿Podría escribir un algoritmo de búsqueda más eficiente para la aplicación XYZ? Sí, pero en realidad una comparación simple de cada valor lleva una cantidad de tiempo trivial, a pesar de que hay miles de valores. Entonces no vale la pena. Puede ser difícil para los nuevos desarrolladores evitar una optimización innecesaria, porque en su programa de grado se dedicó mucho tiempo a escribir el algoritmo "correcto" (es decir, el más eficiente). Pero en el mundo real, el algoritmo correcto es cualquiera que funcione y funcione lo suficientemente rápido.
  • Los cambios que hacen que su código sea mucho más largo y complejo aún pueden ser una ganancia de rendimiento. Por ejemplo, en la aplicación FOO puede valer la pena agregar cientos de líneas de nueva lógica, solo para evitar una sola llamada a la base de datos.

fuente
66
De particular interés, con cosas como las funciones de clasificación, es mucho más rápido (en tiempo de desarrollo) y más fácil hacer que algo simple y tonto haga lo correcto en todos los casos que obtener un algo elegante completamente funcional y sin errores. (Aunque las únicas razones para escribir algo así fuera de acadamea son si estás construyendo una biblioteca o trabajando en una plataforma sin una ...)
StarWeaver
55
Creo que necesita agregar el enlace a shouldioptimize.com :)
Ivan Kolmychek
13
Creo que el 90/10 proviene del conocido Principio de Pareto 80/20 en.wikipedia.org/wiki/Pareto_principle
fernando.reyes
2
@StarWeaver Es por eso que los lenguajes que hacen que la escritura de tipos súper eficientes sea tan fácil o más fácil que una clasificación de burbujas horrible son importantes allí, como C ++. Tales algoritmos y códigos "preenvasados" pueden optimizarse realmente sin causar complejidad en el punto de uso.
Yakk
66
@IvanKolmychek Ese sitio es engañoso. Claro, ese tipo de análisis de costos es un factor a considerar, pero hay otros factores como la experiencia del usuario. Puede no ahorrar mucho dinero al no optimizar, pero también puede perder muchos ingresos si las personas abandonan su sitio frustrado.
jpmc26
21

Esta no es una ley de la naturaleza, sino una regla general nacida de una amplia experiencia. También se conoce como la regla 80/20, y solo es una aproximación aproximada.

Bucles, ramas y otro control de flujo.

Cada lugar que tenga un if, tendrá una rama que se toma con más frecuencia que la otra rama. Por lo tanto, se pasa más tiempo de ejecución ejecutando esa parte del programa, y ​​no la otra parte.

Cada lugar que tiene un bucle que se ejecuta más de una vez, tiene un código que se ejecuta más que el código circundante. Por lo tanto, se pasa más tiempo allí.

Como ejemplo, considere:

def DoSomeWork():
    for i in range(1000000):
        DoWork(i)
    except WorkExeption:
        print("Oh No!")

Aquí print("Oh No!")solo se ejecutará un máximo de una vez, y a menudo nunca, mientras DoWork(i)que ocurrirá aproximadamente un millón de veces.

Caleth
fuente
77
Llamarlo la regla 80/20 puede causar confusión con el principio de Pareto , que se aplica más ampliamente que solo a la programación. Quizás 90 y 10 son solo números convenientes que no tienen esta superposición de significado.
Trichoplax
29
Es una instancia del director de Pareto. Ambos pares de números son igualmente arbitrarios
Caleth
2
Hay una base matemática para la división 80/20 en el principio de Pareto. No son solo algunas figuras imaginarias para representar "mucho" y "un poco".
Moyli
1
@Moyli - Sí, "Hay una base matemática para la división 80/20 ...", pero en el mundo real, nunca (OK, por coincidencia, rara vez) será exactamente 80/20.
Kevin Fegan
2
@trichoplax el principio de pareto se aplica muy bien aquí. El 20% de las causas (las líneas de código) causan el 80% de los efectos (el tiempo de ejecución)
njzk2
16

Bucles.

Estoy tentado de parar allí! :-)

Considera este programa

1. do_something

2. loop 10 times
3.    do_another_thing

4.    loop 5 times
5.        do_more_stuff

La línea 1 se ejecuta una vez, mientras que la línea 3 se ejecuta 10 veces. Mirando cada línea por turno

1 1   0.8%
2 10  8.3%
3 10  8.3%
4 50 41.3%
5 50 41.3%

Dos líneas representan el 83% del tiempo de ejecución (suponiendo que todas las líneas tarden aproximadamente el mismo tiempo en ejecutarse. Por lo tanto, el 40% del programa toma> 80%.

Con ejemplos más grandes y del mundo real, esto aumenta, por lo que solo una pequeña cantidad de líneas representa gran parte del tiempo de ejecución.

La regla 90/10 (o como a veces se pone 80/20) es una "regla de oro", solo aproximadamente cierta.

Ver también Principio de Pareto

Nick Keighley
fuente
2
En lugar de decir que solo es aproximadamente cierto, diría que en muchos casos, al menos el 90% del tiempo se dedicará a ejecutar una pequeña fracción del código, como máximo el 10%. Obviamente, sería posible tener programas en los que todas las porciones pasaran aproximadamente la misma cantidad de tiempo ejecutando, pero eso es raro.
supercat
+1 para hacer referencia al Principio de Pareto. Se puede ver una explicación más profunda en este fantástico video de Vsauce .
Radu Murzea
5

Como preguntó solo sobre el tiempo de ejecución, este ejemplo podría ser útil:

int main() {
    sleep(90); // approximately 10% of the program.
    // other 90% of the program:
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    return 0;
}

Si es un poco más serio, significa que en el código de la vida real casi siempre se llama una función pesada en un bucle (en lugar de sleep(90);), mientras que el resto del 10% del tiempo realiza algunos cálculos de un solo paso.

Otro ejemplo es el manejo de errores en algunos servicios de alta disponibilidad. Cualquier servicio de alta disponibilidad está diseñado para trabajar una cantidad de tiempo infinita en condiciones normales. Funciona normalmente el 99% del tiempo, pero ocasionalmente, en caso de error, ejecuta un manejo y recuperación de errores, que puede ser aún más lógicamente complejo que el servicio en sí.

Sergey
fuente
Agradable, esperaba que alguien publicara este ejemplo extremo, que muestra la diferencia claramente.
djechlin
3

El razonamiento 90/10 significa que una pequeña parte de su código se repetirá o usará más que otros. Esto se usa a menudo para sugerir que debe concentrar el 90% de su esfuerzo de desarrollo / optimización en este 10% de su código.

Piense en un procesador de texto normal, como Microsoft Word u OpenOffice :

  • El diálogo de preferencias, no se usa mucho;
  • Las subrutinas que dibujan caracteres se usan todo el tiempo.

Este dicho también se usa en las ciencias de gestión ... Esta es una lección para la vida misma ... Significado: concentra la mayor parte de tus esfuerzos donde obtengas más resultados.

Lucas
fuente
66
Si Microsoft Word es simple, ¿cuál es un ejemplo complejo?
Peter Mortensen
@PeterMortensen que no tiene sentido.
El gran pato el
@PeterMortensen Emacs, obviamente.
muru
2

Imagina un programa como este:

print "H"
print "e"
print "l"
print "l"
print "o"
for i=0 to 1,000,000
    print "How long now?"
next
print "B"
print "y"
print "e"

Observe cómo hay 11 líneas aquí, donde 3 de las 11 son el ciclo for, ¿cuánto tiempo se dedica a este pequeño código? Bastante mientras las otras 8 líneas simplemente imprimen un solo carácter. Por lo tanto, tenga en cuenta que si bien algunos códigos pueden ser cortos, eso no le dice con qué frecuencia se ejecuta y cuánto tiempo llevará.

JB King
fuente
0

Además del bucle, como lo mencionan otras excelentes respuestas, también hay que considerar los principios DRY. Bien escrito, el código orientado a objetos tiene muchas partes reutilizables. Esas partes que se reutilizan, por definición, se usan al menos el doble de veces que algo que solo se ejecuta una vez. Si tiene una gran cantidad de código OO, podría estar reutilizando algunas clases y métodos muchas veces, y algunas otras piezas de código solo una vez.

Como se menciona en otras respuestas, probablemente sea mejor gastar esfuerzo haciendo que el código que se usa con más frecuencia sea mejor que mejorar el código que solo se usa una vez.

Marshall Tigerus
fuente
2
Podría reutilizar una gran cantidad de código, pero todo podría ejecutarse con poca frecuencia (sin dejar de ser crucial).
Peter Mortensen
@PeterMortensen "crucial pero no frecuente" no es lo mismo que "reutilizado casi cada segundo y necesita ser lo más rápido posible"
El Gran Pato
@TheGreatDuck y no creo que eso sea lo que quiso decir. Porque puede tener código que se ejecuta con poca frecuencia pero desea que suceda lo más rápido posible. Por ejemplo, tomemos la recuperación de errores: dependiendo de la aplicación, podría estar bien tomarse un tiempo (5 minutos, una hora, tal vez más) para que el sistema vuelva a estar operativo. Sin embargo, si, por ejemplo, un sistema de vuelo encuentra un error, realmente lo desea lo más rápido posible. Porque si no lo hace, "caerá" y "chocará" en un sentido muy literal.
VLAZ
Esto parece implicar que DRY requiere OO, lo que por supuesto no es cierto. La reutilización se ve igualmente facilitada por las funciones gratuitas, etc.
underscore_d
@vlaz eso es cierto, pero la cosa es que en un avión ... TODO necesita correr rápido.
El gran pato
0

Esa no es una regla, es solo un tipo que editó Wikipedia con un par de números sacados de la nada y lo calificó como una regla. Compárese con el Principio de Pareto, que está más firmemente establecido en otros contextos. Me gustaría ver qué investigaciones se han realizado (si las hay) sobre la precisión de esta "regla".

Pero, básicamente, la respuesta a su pregunta es que algunos códigos se ejecutan con mucha más frecuencia que otros. Los bucles son a menudo la razón de esto. Otras razones son llamadas que requieren mucho tiempo, por ejemplo, a recursos externos como servicios web o medios de almacenamiento.

Brad Thomas
fuente
Es una cosa legítima que la gente usa como regla general.
The Great Duck
Si sugiere que esto es de uso generalizado como regla general, ¡me interesaría ver evidencia de eso también! ¿O es solo otra opinión sacada de la nada pero implícita como objetiva?
Brad Thomas
Si realmente lees el artículo de Wikipedia, verías que la cita a la que hace referencia el autor de la pregunta tiene esta cita: amazon.com/Every-Computer-Performance-Book-Computers/dp/… Nunca lo he visto en uso, pero su publicación me pareció grosera y descartada en mi opinión, así que respondí. Obviamente el 10% es un número que alguien inventó. Puedo hacer el número que quiera haciendo que mi programa sea ineficiente. Sin embargo, si es o no un término utilizado en ingeniería de software, claramente no es discutible, ya que cuántas personas aquí están de acuerdo con su existencia.
El gran pato el
Bueno, no voy a comprar el libro solo para ver la investigación a la que supuestamente se refiere ... ¿puedes publicar una cita que muestre la evidencia? ¿O de hecho no has visto ninguno?
Brad Thomas el
1
@BradThomas: La evidencia en contra de la teoría de que la regla 90-10 fue inventada por alguien que estaba editando Wikipedia es que fue ampliamente citada, con los números 90 y 10, muchos años antes de que Wikipedia existiera; El principio real no es que exactamente el 10% del código represente el 90% del tiempo de ejecución, sino que en la mayoría de los programas una pequeña porción del código, el 10% o menos , representa una porción tan grande del tiempo de ejecución. -90% o más que incluso una mejora del 10% en el rendimiento de esa pequeña parte del código reduciría el tiempo de ejecución general más de una mejora de 1000x en todo lo demás.
supercat
0

Es una reinterpretación del "principio de Pareto", que establece "para muchos eventos, aproximadamente el 80% de los efectos provienen del 20% de las causas", también conocida como la regla 80/20. Esta regla se aplica principalmente a la economía, por lo que tiene sentido que sea destinada a la programación.

Es solo un patrón que se ha observado durante un largo período de tiempo.

Aquí hay un video muy agradable sobre patrones como este, y también explica el Principio de Pareto.

https://www.youtube.com/watch?v=fCn8zs912OE&ab_channel=Vsauce

imnota4
fuente