operaciones básicas costo de tiempo de la CPU

Question

Me preguntaba cómo optimizar bucles para sistemas con recursos muy limitados. Digamos que, si tenemos un bucle básico for, como (escrito en javascript):

---

for(var i = someArr.length - 1; i > -1; i--) { someArr[i] }

---

Sinceramente, no sé, no es más barato que !=>?

Estaría agradecido por cualquier recurso que cubren el costo de computación en el contexto de los operadores básicos, como el ya mencionado, >>, ~, !, y así sucesivamente.

Answer 1

El rendimiento en una CPU moderna no es nada trivial. Aquí hay un par de cosas que lo complican:

• Las computadoras son rápidas. Su CPU puede ejecutar más de 6 mil millones de instrucciones por segundo. Por lo que incluso la instrucción más lenta puede ejecutar millones de veces por segundo, lo que significa que en realidad sólo se importa si lo usa muy a menudo
• de haber CPU moderna cientos de instrucciones en vuelo al mismo tiempo. Se canalizan, lo que significa que mientras se lee una instrucción, otra lee de los registros, una tercera se está ejecutando y una cuarta está escribiendo de nuevo en un registro. Las CPU modernas tienen 15-20 de esas etapas. Además de esto, pueden ejecutar 3-4 instrucciones al mismo tiempo en cada una de estas etapas. Y pueden reordenar estas instrucciones. Si la unidad de multiplicación está siendo utilizada por otra instrucción, quizás podamos encontrar una instrucción de adición para ejecutar, por ejemplo.Entonces, incluso si tiene algunas instrucciones lentas mezcladas, su costo puede ocultarse muy bien la mayor parte del tiempo, ejecutando otras instrucciones mientras espera que el lento termine.
• La memoria es cientos de veces más lenta que la CPU. Las instrucciones que se están ejecutando realmente no importan si su costo es empequeñecido por la recuperación de datos de la memoria. E incluso esto no es confiable, porque la CPU tiene sus propias memorias caché a bordo para intentar ocultar este costo.

Así que la respuesta corta es "no intentes burlar al compilador". Si puede elegir entre dos expresiones equivalentes, el compilador probablemente podrá hacer lo mismo y seleccionará la más eficiente. El costo de una instrucción varía, dependiendo de todos los factores anteriores. Qué otras instrucciones se están ejecutando, qué datos hay en la memoria caché de la CPU, qué modelo exacto de CPU es el código que se está ejecutando, y así sucesivamente. El código que es súper eficiente en un caso puede ser muy ineficiente en otros casos. El compilador intentará elegir las instrucciones más eficientes y programarlas lo mejor posible. A menos que sepa algo más que el compilador sobre esto, es poco probable que pueda hacer un mejor trabajo al respecto.

No intente tales microoptimizaciones a menos que realmente sepa lo que está haciendo. Como muestra lo anterior, el rendimiento de bajo nivel es un tema ridículamente complejo, y es muy fácil escribir "optimizaciones" que resultan en el código más lento. O que solo sacrifica la legibilidad en algo que no hace diferencia en absoluto.

Además, la mayoría de su código simplemente no tiene un impacto medible en el rendimiento. La gente en general les encanta citar (o citar erróneamente) Knuth sobre este tema:

Debemos olvidarnos de pequeñas eficiencias, dicen que alrededor del 97% del tiempo: la optimización prematura es la raíz de todo mal

personas a menudo interpretan esto como "no te molestes en tratar de optimizar tu código". Si realmente lee la cita completa, algunas consecuencias mucho más interesantes deberían quedar claras:

La mayoría de las veces, debemos olvidarnos de las microoptimizaciones. La mayoría del código se ejecuta de manera que rara vez las optimizaciones no importen. Teniendo en cuenta el número de instrucciones que una CPU puede ejecutar por segundo, es obvio que se debe ejecutar un bloque de código muy a menudo para que las optimizaciones tengan algún efecto. Entonces, aproximadamente el 97% de las veces, sus optimizaciones serán una pérdida de tiempo. Pero también dice que a veces (3% de las veces), sus optimizaciones serán materia. Y obviamente, buscar esos 3% es como buscar una aguja en un pajar. Si decide "optimizar su código" en general, perderá su tiempo en el primer 97%. En cambio, primero debe localizar el 3% que realmente necesita optimizar. En otras palabras, ejecute su código a través de un generador de perfiles y deje que le indique qué código ocupa la mayor cantidad de tiempo de CPU. Entonces sabes dónde optimizar. Y entonces tus optimizaciones ya no son prematuras.

Answer 2

La mayoría de las comparaciones tienen el mismo costo, porque el procesador simplemente lo compara en todos los aspectos, luego toma una decisión basada en los indicadores generados por esta comparación previa, por lo que la señal de comparación no importa en absoluto. Pero algunas arquitecturas intentan acelerar este proceso en función del valor con el que comparan, como las comparaciones contra 0.

Hasta donde yo sé, las operaciones a nivel de bit son las operaciones más baratas, ligeramente más rápidas que la suma y la resta. Las operaciones de multiplicación y división son un poco más costosas, y la comparación es la operación de costa más alta.

Answer 3

Es extraordinariamente poco probable que tales micro-optimizaciones hagan una diferencia notable en su código en cualquiera de las circunstancias más extremas (¿sistemas integrados en tiempo real?). Su tiempo probablemente sería mejor servido preocupándose por hacer su código legible y mantenible.

En caso de duda, siempre empezar por preguntar Donald Knuth:

http://shreevatsa.wordpress.com/2008/05/16/premature-optimization-is-the-root-of-all-evil/

O, para un alto el ceño ligeramente menos asumir micro-optimización:

http://www.codinghorror.com/blog/archives/000185.html

Answer 4

optimización prematura puede ser peligroso, el mejor enfoque sería escribir su aplicación sin preocuparse por eso y luego encontrar los puntos lentos y optimizarlos. Si está realmente preocupado por esto, use un lenguaje de nivel inferior. Un lenguaje interpretado como javascript le costará algo de poder de procesamiento en comparación con un lenguaje de nivel inferior como C.

Answer 5

En este caso particular,> vs = probablemente no sea un problema de rendimiento. SIN EMBARGO> generalmente es una opción más segura porque evita que los casos en los que modificó el código se escapen hacia las malas hierbas y se atasquen en un bucle infinito.

Answer 6

Eso es como pedir un pez, cuando prefiero enseñarte a pescar.

Hay formas sencillas de comprobar por ti mismo cuánto tiempo tardan las cosas. Mi favorito es copiar el código 10 veces y luego envolverlo en un bucle de 10^8 veces.Si lo ejecuto y miro mi reloj, la cantidad de segundos que tarda se traduce en nanosegundos.

Decir que no hacer la optimización prematura es un "no se". Si desea un "do be", puede probar una técnica de ajuste de rendimiento proactiva como this.

Por cierto mi forma favorita de codificación de su bucle es:

for (i = N; --i >= 0;){...}