Rendimiento de romperse un bucle en dos bucles

Question

buen día,

Suponga que tiene un simple bucle for como a continuación ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
    //statement 2 
} 

Suponga que la declaración declaración 1 y 2 eran O (1) Además de la pequeña sobrecarga de "comenzar" otro ciclo, ¿sería tan rápido como el bucle for en dos bucles (no anidados, sino secuenciales)? Por ejemplo ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
} 
for(int i=0;i<10;i++) 
{ 
    //statement 2 
} 

Por qué hago una pregunta tan tonta es que tengo un sistema de detección de colisiones (CDS) que tiene que recorrer todos los objetos. Quiero "compartimentar" la funcionalidad de mi sistema CDS por lo que se puede llamar simplemente

cds.update(objectlist); 

en lugar de tener que romper mi sistema cds arriba. (No se preocupe demasiado por la implementación de mi CDS ... Creo que sé lo que estoy haciendo, simplemente no sé cómo explicarlo, lo que realmente necesito saber es si aprovecho un gran golpe de rendimiento para hacer bucles a través de todos los objetos de mi nuevo .

Answer 1

Depende de su aplicación.

Posibles desventajas (de división):

• sus datos no cabe en la caché de datos L1, por lo tanto, se carga una vez para el primer bucle y luego vuelve a cargar para el segundo bucle

posible ganancia (de división):

• su cont bucle Ains muchas variables, la división ayuda a reducir la presión de registro/pila y el optimizador la convierte en un mejor código de máquina
• las funciones que utiliza trash el caché de instrucciones L1 para que el caché se cargue en cada iteración, mientras que al dividirlo lo gestiona para cargarlo una vez (sólo) en la primera iteración de cada bucle

Estas listas no son ciertamente amplio, pero ya se puede sentir que hay una tensión entre código y los datos . Por lo tanto, es difícil para nosotros tomar una conjetura educada/salvaje cuando no sabemos ninguna de las dos cosas.

En duda: perfil. Use callgrind, verifique el error de caché en cada caso, verifique el número de instrucciones ejecutadas. Mida el tiempo pasado.

Answer 2

en lo que se refiere a la gran-o complejidad, esto no hace una diferencia si 1 bucle es O (n), entonces también lo es la solución 2 bucle.
como en cuanto a la micro-optimización, es difícil de decir. El costo de un ciclo es bastante pequeño, no sabemos cuál es el costo de acceder a tus objetos (si están en un vector, entonces también debería ser bastante pequeño) , pero hay mucho que considerar para dar una respuesta útil.

Answer 3

Tiene razón en señalar que habrá una sobrecarga de rendimiento al crear un segundo ciclo. Por lo tanto, no puede ser "igualmente rápido"; ya que esta sobrecarga, aunque pequeña, todavía está sobrecargada.

no voy a tratar de hablar inteligentemente acerca de cómo se deben construir sistemas de colisión, pero si usted está tratando de optimizar el rendimiento es mejor evitar la construcción de estructuras de control innecesarios si se puede administrar sin tirar de los pelos.

Recuerde que la optimización prematura es una de las peores cosas que puede hacer. Preocuparse por la optimización cuando tiene un problema de rendimiento, en mi opinión.

Answer 4

En términos de complejidad algorítmica, dividir los bucles no hace diferencia.

En cuanto a la división de rendimiento real de los bucles podría mejorar el desempeño, rendimiento o empeorar ninguna diferencia - que depende del sistema operativo, hardware y - por supuesto - lo statement 1 y statement 2 son.

Answer 5

Con dos bucles que va a pagar por:

• aumento del tamaño del código generado
• 2x tantos rama predice
• dependiendo lo que el diseño de los datos de la declaración 1 y 2 se le podría recargando los datos en el caché.

El último punto podría tener un gran impacto en cualquier dirección. Debe medir como con cualquier optimización de perf.

Answer 6

Como se señaló, la complejidad persiste.

Pero en el mundo real, es imposible para nosotros predecir qué versión se ejecuta más rápido. Los siguientes son factores que juegan un papel, unos enormes:

• almacenamiento en caché de datos
• almacenamiento en caché de instrucciones
• Ejecución especulativa
• predicción de saltos
• destino del salto amortigua
• Número de registros disponibles en la CPU
• Tamaños de caché

(nota: sobre todos ellos, está la espada de predicción errónea de Damocles; todos son wikipedibles y googlables)

Especialmente el último factor hace que a veces sea imposible compilar el código verdadero para código cuyo rendimiento se basa en tamaños de caché específicos. Algunas aplicaciones se ejecutarán más rápido en la CPU con enormes cachés, mientras que se ejecutarán más lentamente en cachés pequeños, y para algunas otras aplicaciones será lo contrario.

Soluciones:

• Deje que su compilador de hacer el trabajo de transformación de bucle. Los g ++ modernos son bastante buenos en esa disciplina. Otra disciplina en la que g ++ es bueno es la vectorización automática. Tenga en cuenta que los compiladores saben más acerca de la arquitectura de la computadora que casi todas las personas.
• Envíe diferentes binarios y un despachador.
• Use cache-oblivious data structures/layouts and algorithms que se adaptan a la caché de destino.

Siempre es una buena idea esforzarse por un software que se adapte al objetivo, idealmente sin sacrificar la calidad del código. Y antes de realizar una optimización manual, ya sea microscópica o macroscópica, mida ejecuciones en el mundo real, luego, y solo después, optimice.

Literatura: * Agner Fog's Guides * Intel's Guides