¿Por qué las adiciones de elementos son mucho más rápidas en bucles separados que en un bucle combinado?

Supongamos que a1 , b1 , c1 y d1 apuntan a la memoria del montón y mi código numérico tiene el siguiente ciclo del núcleo.

 const int n = 100000; for (int j = 0; j < n; j++) { a1[j] += b1[j]; c1[j] += d1[j]; } 

Este ciclo se ejecuta 10.000 veces a través de otro ciclo for externo. Para acelerarlo, cambié el código a:

 for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } 

Comstackdo en MS Visual C ++ 10.0 con optimización completa y SSE2 habilitado para 32 bits en un Intel Core 2 Duo (x64), el primer ejemplo toma 5.5 segundos y el ejemplo de doble bucle solo demora 1.9 segundos. Mi pregunta es: (Por favor refiérase a la pregunta reformulada en la parte inferior)

PD: No estoy seguro, si esto ayuda:

El desassembly para el primer ciclo básicamente se ve así (este bloque se repite unas cinco veces en el progtwig completo):

 movsd xmm0,mmword ptr [edx+18h] addsd xmm0,mmword ptr [ecx+20h] movsd mmword ptr [ecx+20h],xmm0 movsd xmm0,mmword ptr [esi+10h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [edx+20h] addsd xmm0,mmword ptr [ecx+28h] movsd mmword ptr [ecx+28h],xmm0 movsd xmm0,mmword ptr [esi+18h] addsd xmm0,mmword ptr [eax+38h] 

Cada ciclo del ejemplo de bucle doble produce este código (el siguiente bloque se repite aproximadamente tres veces):

 addsd xmm0,mmword ptr [eax+28h] movsd mmword ptr [eax+28h],xmm0 movsd xmm0,mmword ptr [ecx+20h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [ecx+28h] addsd xmm0,mmword ptr [eax+38h] movsd mmword ptr [eax+38h],xmm0 movsd xmm0,mmword ptr [ecx+30h] addsd xmm0,mmword ptr [eax+40h] movsd mmword ptr [eax+40h],xmm0 

La pregunta resultó ser irrelevante, ya que el comportamiento depende mucho de los tamaños de las matrices (n) y la memoria caché de la CPU. Entonces, si hay más interés, vuelvo a formular la pregunta:

¿Podría proporcionarnos una visión sólida de los detalles que conducen a los diferentes comportamientos de caché, tal como lo ilustran las cinco regiones en el siguiente gráfico?

También podría ser interesante señalar las diferencias entre las architectures de CPU / caché, al proporcionar un gráfico similar para estas CPU.

PPS: aquí está el código completo. Utiliza TBB Tick_Count para una resolución más alta, que se puede desactivar al no definir la macro TBB_TIMING :

 #include  #include  #include  #include  //#define TBB_TIMING #ifdef TBB_TIMING #include  using tbb::tick_count; #else #include  #endif using namespace std; //#define preallocate_memory new_cont enum { new_cont, new_sep }; double *a1, *b1, *c1, *d1; void allo(int cont, int n) { switch(cont) { case new_cont: a1 = new double[n*4]; b1 = a1 + n; c1 = b1 + n; d1 = c1 + n; break; case new_sep: a1 = new double[n]; b1 = new double[n]; c1 = new double[n]; d1 = new double[n]; break; } for (int i = 0; i < n; i++) { a1[i] = 1.0; d1[i] = 1.0; c1[i] = 1.0; b1[i] = 1.0; } } void ff(int cont) { switch(cont){ case new_sep: delete[] b1; delete[] c1; delete[] d1; case new_cont: delete[] a1; } } double plain(int n, int m, int cont, int loops) { #ifndef preallocate_memory allo(cont,n); #endif #ifdef TBB_TIMING tick_count t0 = tick_count::now(); #else clock_t start = clock(); #endif if (loops == 1) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++){ a1[j] += b1[j]; c1[j] += d1[j]; } } } else { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } } } double ret; #ifdef TBB_TIMING tick_count t1 = tick_count::now(); ret = 2.0*double(n)*double(m)/(t1-t0).seconds(); #else clock_t end = clock(); ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC); #endif #ifndef preallocate_memory ff(cont); #endif return ret; } void main() { freopen("C:\\test.csv", "w", stdout); char *s = " "; string na[2] ={"new_cont", "new_sep"}; cout << "n"; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) #ifdef preallocate_memory cout << s << i << "_loops_" << na[preallocate_memory]; #else cout << s << i << "_loops_" << na[j]; #endif cout << endl; long long nmax = 1000000; #ifdef preallocate_memory allo(preallocate_memory, nmax); #endif for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2))) { const long long m = 10000000/n; cout << n; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) cout << s << plain(n, m, j, i); cout << endl; } } 

(Muestra FLOP / s para diferentes valores de n .)

enter image description here

Tras un análisis más detallado de esto, creo que esto (al menos parcialmente) es causado por la alineación de datos de los cuatro apuntadores. Esto causará cierto nivel de conflictos de banco / camino de caché.

Si he adivinado correctamente cómo está asignando sus matrices, es probable que estén alineadas con la línea de la página .

Esto significa que todos sus accesos en cada ciclo caerán en la misma forma de caché. Sin embargo, los procesadores Intel han tenido asociatividad de caché L1 de 8 vías por un tiempo. Pero en realidad, el rendimiento no es completamente uniforme. Acceder a 4 vías es aún más lento que decir 2 vías.

EDITAR: de hecho parece que estás asignando todas las matrices por separado. Por lo general, cuando se solicitan asignaciones tan grandes, el asignador solicitará nuevas páginas del sistema operativo. Por lo tanto, hay una alta probabilidad de que las grandes asignaciones aparezcan en el mismo desplazamiento desde un límite de página.

Aquí está el código de prueba:

 int main(){ const int n = 100000; #ifdef ALLOCATE_SEPERATE double *a1 = (double*)malloc(n * sizeof(double)); double *b1 = (double*)malloc(n * sizeof(double)); double *c1 = (double*)malloc(n * sizeof(double)); double *d1 = (double*)malloc(n * sizeof(double)); #else double *a1 = (double*)malloc(n * sizeof(double) * 4); double *b1 = a1 + n; double *c1 = b1 + n; double *d1 = c1 + n; #endif // Zero the data to prevent any chance of denormals. memset(a1,0,n * sizeof(double)); memset(b1,0,n * sizeof(double)); memset(c1,0,n * sizeof(double)); memset(d1,0,n * sizeof(double)); // Print the addresses cout < < a1 << endl; cout << b1 << endl; cout << c1 << endl; cout << d1 << endl; clock_t start = clock(); int c = 0; while (c++ < 10000){ #if ONE_LOOP for(int j=0;j 

Resultados de referencia:

EDITAR: resultados en una máquina de architecture Core 2 real :

2 x Intel Xeon X5482 Harpertown a 3.2 GHz:

 #define ALLOCATE_SEPERATE #define ONE_LOOP 00600020 006D0020 007A0020 00870020 seconds = 6.206 #define ALLOCATE_SEPERATE //#define ONE_LOOP 005E0020 006B0020 00780020 00850020 seconds = 2.116 //#define ALLOCATE_SEPERATE #define ONE_LOOP 00570020 00633520 006F6A20 007B9F20 seconds = 1.894 //#define ALLOCATE_SEPERATE //#define ONE_LOOP 008C0020 00983520 00A46A20 00B09F20 seconds = 1.993 

Observaciones:

  • 6.206 segundos con un bucle y 2.116 segundos con dos bucles. Esto reproduce los resultados de OP exactamente.

  • En las primeras dos pruebas, las matrices se asignan por separado. Notarás que todos tienen la misma alineación con respecto a la página.

  • En las segundas dos pruebas, las matrices se agrupan para romper esa alineación. Aquí notará que ambos bucles son más rápidos. Además, el segundo bucle (doble) es ahora el más lento, como cabría esperar.

Como señala @Stephen Cannon en los comentarios, es muy probable que esta alineación provoque falsos alias en las unidades de carga / almacenamiento o en la memoria caché. Busqué en Google esto y descubrí que Intel en realidad tiene un contador de hardware para puestos de aliasing de dirección parcial :

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 Regiones - Explicaciones

Región 1:

Este es fácil. El conjunto de datos es tan pequeño que el rendimiento está dominado por sobrecarga, como bucles y ramificaciones.

Región 2:

Aquí, a medida que aumenta el tamaño de los datos, la cantidad de sobrecarga relativa disminuye y el rendimiento "se satura". Aquí dos bucles son más lentos porque tienen el doble de la sobrecarga de bucle y bifurcación.

No estoy seguro exactamente de lo que está pasando aquí ... La alineación aún podría tener un efecto ya que Agner Fog menciona conflictos en los bancos de caché . (Ese enlace es sobre Sandy Bridge, pero la idea debería ser aplicable a Core 2)

Región 3:

En este punto, los datos ya no caben en la memoria caché L1. Así que el rendimiento está limitado por el ancho de banda de caché L1 < -> L2.

Región 4:

La caída de rendimiento en el lazo simple es lo que estamos observando. Y como se mencionó, esto se debe a la alineación que (lo más probable) causa puestos de alias falsos en las unidades de carga / almacenamiento del procesador.

Sin embargo, para que ocurra aliasing falso, debe haber una zancada lo suficientemente grande entre los conjuntos de datos. Es por eso que no se ve esto en la región 3.

Región 5:

En este punto, nada encaja en el caché. Entonces estás limitado por el ancho de banda de la memoria.


2 x Intel X5482 Harpertown a 3.2 GHzIntel Core i7 870 @ 2.8 GHzIntel Core i7 2600K a 4.4 GHz

OK, la respuesta correcta definitivamente tiene que hacer algo con la memoria caché de la CPU. Pero usar el argumento de caché puede ser bastante difícil, especialmente sin datos.

Hay muchas respuestas que condujeron a mucha discusión, pero seamos sinceros: los problemas de caché pueden ser muy complejos y no son unidimensionales. Dependen en gran medida del tamaño de los datos, por lo que mi pregunta fue injusta: Resultó ser un punto muy interesante en el gráfico de caché.

La respuesta de @Mysticial convenció a mucha gente (incluyéndome a mí), probablemente porque era la única que parecía confiar en los hechos, pero era solo un “punto de datos” de la verdad.

Es por eso que combiné su prueba (usando una asignación continua vs. separada) y los consejos de @James ‘Answer.

Los gráficos a continuación muestran que la mayoría de las respuestas y especialmente la mayoría de los comentarios a las preguntas y respuestas se pueden considerar completamente erróneas o verdaderas dependiendo del escenario exacto y los parámetros utilizados.

Tenga en cuenta que mi pregunta inicial fue n = 100.000 . Este punto (por accidente) exhibe un comportamiento especial:

  1. Posee la mayor discrepancia entre la versión de uno y dos bucles (casi un factor de tres)

  2. Es el único punto donde un ciclo (es decir, con asignación continua) supera a la versión de dos bucles. (Esto hizo posible la respuesta de Mysticial, en absoluto).

El resultado usando datos inicializados:

Ingrese la descripción de la imagen aquí

El resultado utilizando datos no inicializados (esto es lo que Mysticial probó):

Ingrese la descripción de la imagen aquí

Y esto es difícil de explicar: datos inicializados, que se asignan una vez y se reutilizan para cada caso de prueba siguiente de tamaño de vector diferente:

Ingrese la descripción de la imagen aquí

Propuesta

¡Toda pregunta relacionada con el rendimiento de bajo nivel en Stack Overflow debería ser necesaria para proporcionar información MFLOPS para todo el rango de tamaños de datos relevantes de caché! Es un desperdicio de tiempo de todos pensar en respuestas y especialmente discutirlas con otras personas sin esta información.

El segundo ciclo implica mucha menos actividad de caché, por lo que es más fácil para el procesador mantenerse al día con las demandas de memoria.

Imagine que está trabajando en una máquina donde n el valor justo para que solo sea posible mantener dos de sus matrices en la memoria a la vez, pero la memoria total disponible, a través del almacenamiento en caché de disco, era suficiente para mantener los cuatro.

Suponiendo una política simple de almacenamiento en caché LIFO, este código:

 for(int j=0;j 

primero causaría que a y b se carguen en la RAM y luego se trabajen por completo en la RAM. Cuando comience el segundo bucle, c y d se cargarán desde el disco en la RAM y se operarán.

el otro lazo

 for(int j=0;j 

desplegará dos matrices y una página en las otras dos cada vez que circule por el ciclo . Esto obviamente sería mucho más lento.

Probablemente no esté viendo el caché de disco en sus pruebas, pero probablemente esté viendo los efectos secundarios de alguna otra forma de almacenamiento en caché.


Parece que hay un poco de confusión / malentendido aquí, así que intentaré elaborar un poco usando un ejemplo.

Digamos n = 2 y estamos trabajando con bytes. En mi escenario, tenemos solo 4 bytes de caché y el rest de nuestra memoria es significativamente más lento (digamos 100 veces más acceso).

Asumiendo una política de almacenamiento en caché bastante tonta de si el byte no está en el caché, póngalo allí y obtenga el siguiente byte también mientras estamos en ello , obtendrá un escenario como este:

  • Con

     for(int j=0;j 
  • guarda a[0] caché a[0] y a[1] luego b[0] b[1] y establece a[0] = a[0] + b[0] en caché - ahora hay cuatro bytes en el caché, a[0], a[1] y b[0], b[1] . Costo = 100 + 100.

  • establezca a[1] = a[1] + b[1] en la memoria caché. Costo = 1 + 1.
  • Repita para d .
  • Costo total = (100 + 100 + 1 + 1) * 2 = 404

  • Con

     for(int j=0;j 
  • guarda a[0] caché a[0] y a[1] luego b[0] b[1] y establece a[0] = a[0] + b[0] en caché - ahora hay cuatro bytes en el caché, a[0], a[1] y b[0], b[1] . Costo = 100 + 100.

  • expulsar a[0], a[1], b[0], b[1] de la memoria caché y la memoria caché c[0] y c[1] luego d[0] y d[1] y establecer c[0] = c[0] + d[0] en caché. Costo = 100 + 100.
  • Sospecho que estás empezando a ver hacia dónde voy.
  • Costo total = (100 + 100 + 100 + 100) * 2 = 800

Este es un escenario clásico de thrash caché.

No es debido a un código diferente, sino a causa del almacenamiento en caché: la RAM es más lenta que la CPU registra y hay una memoria caché dentro de la CPU para evitar escribir la RAM cada vez que una variable está cambiando. Pero la memoria caché no es tan grande como la RAM, por lo tanto, mapea solo una fracción de ella.

El primer código modifica direcciones de memoria distantes alternando en cada bucle, requiriendo continuamente invalidar la memoria caché.

El segundo código no se alterna: simplemente fluye en direcciones adyacentes dos veces. Esto hace que todo el trabajo se complete en la caché, invalidando solo después de que se inicia el segundo ciclo.

No puedo replicar los resultados discutidos aquí.

No sé si el culpable es el código de referencia pobre, o qué, pero los dos métodos están dentro del 10% de cada uno en mi máquina usando el siguiente código, y un bucle suele ser ligeramente más rápido que dos, como esperar.

Los tamaños de matriz variaron de 2 ^ 16 a 2 ^ 24, usando ocho bucles. Tuve el cuidado de inicializar las matrices de origen por lo que la asignación += no le estaba pidiendo a la FPU que agregara la basura de memoria interpretada como un doble.

InitToZero[j] con varios esquemas, como poner la asignación de b[j] , d[j] a InitToZero[j] dentro de los bucles, y también con el uso de += b[j] = 1 y += d[j] = 1 , y obtuve resultados bastante consistentes.

Como era de esperar, la inicialización de b y d dentro del ciclo utilizando InitToZero[j] dio una ventaja al enfoque combinado, ya que se realizaron de forma consecutiva antes de las asignaciones InitToZero[j] c , pero aún dentro del 10%. Imagínate.

El hardware es Dell XPS 8500 con generación 3 Core i7 a 3.4 GHz y 8 GB de memoria. Para 2 ^ 16 a 2 ^ 24, usando ocho bucles, el tiempo acumulado fue 44.987 y 40.965 respectivamente. Visual C ++ 2010, totalmente optimizado.

PD: Cambié los bucles para contar hasta cero, y el método combinado fue marginalmente más rápido. Rascándome la cabeza. Tenga en cuenta el nuevo tamaño de matriz y recuentos de bucles.

 // MemBufferMystery.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include  #include  #include  #include 

No estoy seguro de por qué se decidió que MFLOPS era una medida relevante. Pensé que la idea era centrarme en los accesos a la memoria, así que traté de minimizar la cantidad de tiempo de computación en coma flotante. Me fui en el += , pero no estoy seguro de por qué.

Una asignación directa sin cálculo sería una prueba más limpia del tiempo de acceso a la memoria y crearía una prueba que es uniforme independientemente del recuento de bucles. Tal vez me perdí algo en la conversación, pero vale la pena pensarlo dos veces. Si el más se deja fuera de la asignación, el tiempo acumulativo es casi idéntico a 31 segundos cada uno.

Es porque la CPU no tiene tantas fallas de caché (donde tiene que esperar que los datos de la matriz provengan de los chips de RAM). Sería interesante para usted ajustar el tamaño de las matrices continuamente para que exceda los tamaños de la memoria caché de nivel 1 (L1) y luego de la memoria caché de nivel 2 (L2) de su CPU y trazar el tiempo necesario para su código para ejecutar contra los tamaños de las matrices. El gráfico no debe ser una línea recta como cabría esperar.

El primer ciclo alterna la escritura en cada variable. El segundo y el tercero solo hacen pequeños saltos de tamaño de elemento.

Intente escribir dos líneas paralelas de 20 cruces con un lápiz y un papel separados por 20 cm. Pruebe una vez terminando una y luego la otra y pruebe otra vez escribiendo una cruz en cada línea alternativamente.

La pregunta original

¿Por qué un ciclo es mucho más lento que dos bucles?


Evaluar el problema

El código de OP:

 const int n=100000; for(int j=0;j 

Y

 for(int j=0;j 

La consideración

Considerando la pregunta original de OP sobre las 2 variantes de los ciclos for y su pregunta modificada sobre el comportamiento de los cachés junto con muchas de las otras respuestas excelentes y comentarios útiles; Me gustaría tratar de hacer algo diferente aquí tomando un enfoque diferente sobre esta situación y problema.


El enfoque

Teniendo en cuenta los dos bucles y toda la discusión sobre la caché y la presentación de la página, me gustaría tomar otro enfoque para ver esto desde una perspectiva diferente. Uno que no involucra el caché y los archivos de página ni las ejecuciones para asignar memoria, de hecho este enfoque ni siquiera concierne al hardware real o al software en absoluto.


La perspectiva

Después de mirar el código durante un tiempo, se hizo bastante evidente cuál es el problema y qué lo está generando. Analicemos esto en un problema algorítmico y miremos desde la perspectiva del uso de notaciones matemáticas, luego apliquemos una analogía a los problemas matemáticos así como también a los algoritmos.


Lo que sabemos

Sabemos que su ciclo funcionará 100,000 veces. También sabemos que a1 , b1 , c1 y d1 son punteros en una architecture de 64 bits. Dentro de C ++ en una máquina de 32 bits, todos los punteros son de 4 bytes y en una máquina de 64 bits tienen un tamaño de 8 bytes, ya que los punteros son de una longitud fija. Sabemos que tenemos 32 bytes para asignar en ambos casos. La única diferencia es que estamos asignando 32 bytes o 2 conjuntos de 2-8bytes en cada iteración, donde en el segundo caso estamos asignando 16 bytes para cada iteración para ambos bucles independientes. Entonces, ambos bucles aún equivalen a 32 bytes en asignaciones totales. Con esta información, avancemos y mostremos la matemática general, el algoritmo y la analogía de la misma. Sabemos la cantidad de veces que el mismo conjunto o grupo de operaciones tendrá que realizarse en ambos casos. Sabemos la cantidad de memoria que debe asignarse en ambos casos. Podemos estimar que la carga de trabajo total de las asignaciones entre ambos casos será aproximadamente la misma.


Lo que no sabemos

No sabemos cuánto tiempo tomará para cada caso a menos que establezcamos un contador y ejecutemos una prueba de punto de referencia. Sin embargo, los puntos de referencia ya se incluyeron a partir de la pregunta original y de algunas de las respuestas y comentarios, y podemos ver una diferencia significativa entre los dos y este es todo el razonamiento de esta pregunta para este problema y para su respuesta a empezar con.


Investiguemos

Ya es evidente que muchos ya lo han hecho mirando las asignaciones de stack, las pruebas de benchmark, mirando la memoria RAM, la caché y los archivos de página. También se incluyeron los puntos de datos específicos y los índices de iteración específicos, y las diversas conversaciones sobre este problema específico hacen que muchas personas comiencen a cuestionar otras cuestiones relacionadas al respecto. Entonces, ¿cómo comenzamos a ver este problema mediante el uso de algoritmos matemáticos y la aplicación de una analogía a la misma? ¡Comenzamos haciendo un par de afirmaciones! Luego construimos nuestro algoritmo a partir de ahí.


Nuestras Afirmaciones

  • Dejaremos que nuestro bucle y sus iteraciones sean una sum que comience en 1 y termine en 100000 en lugar de comenzar con 0 como en los bucles, ya que no tenemos que preocuparnos por el esquema de indexación 0 de direccionamiento de memoria ya que solo estamos interesados ​​en el algoritmo en sí.
  • En ambos casos, tenemos 4 funciones para trabajar y 2 llamadas a funciones con 2 operaciones realizadas en cada llamada de función. Así que los configuraremos como funciones y llamadas a funciones para que sean F1() , F2() , f(a) , f(b) , f(c) y f(d) .

Los algoritmos:

1er caso: - Solo una sum, pero dos llamadas de función independientes.

 Sum n=1 : [1,100000] = F1(), F2(); F1() = { f(a) = f(a) + f(b); } F2() = { f(c) = f(c) + f(d); } 

Segundo caso: - Dos sums pero cada una tiene su propia llamada de función.

 Sum1 n=1 : [1,100000] = F1(); F1() = { f(a) = f(a) + f(b); } Sum2 n=1 : [1,100000] = F1(); F1() = { f(c) = f(c) + f(d); } 

Si notó que F2() solo existe en Sum donde tanto Sum1 como Sum2 solo contienen F1() . This will also be evident later on as well when we begin to conclude that there is sort of an optimization happening from the second algorithm.

The iterations through the first case Sum calls f(a) that will add to its self f(b) then it calls f(c) that will do the same but add f(d) to itself for each 100000 iterations . In the second case we have Sum1 and Sum2 And both act the same as if they were the same function being called twice in a row. In this case we can treat Sum1 and Sum2 as just plain old Sum where Sum in this case looks like this: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } and now this looks like an optimization where we can just consider it to be the same function.


Summary with Analogy

With what we seen in the second case it almost appears as if there is optimization since both for loops have the same exact signature, but this isn't the real issue. The issue isn't the work that is being done by f(a) , f(b) , f(c) & f(d) in both cases and the comparison between the two it is the difference in the distance that the Summation has to travel in both cases that gives you the difference in time execution.

Think of the For Loops as being the Summations that does the iterations as being a Boss that is giving orders to two people A & B and that their jobs are to meat C & D respectively and to pick up some package from them and return it. In the analogy here the for loop or summation iterations and condition checks themselves doesn't actually represent the Boss . What actually represents the Boss here is not from the actual mathematical algorithms directly, but from the actual concept of Scope and Code Block within a routine or sub-routine, method, function, translation unit, etc. The first algorithm has 1 scope where the 2nd algorithm has 2 consecutive scopes.

Within the first case on each call slip the Boss goes to A and gives the order and A goes off to fetch B's package then the Boss goes to C and gives the orders to do the same and receive the package from D on each iteration.

Within the second case the Boss works directly with A to go and fetch B's package until all packages are received. Then the Boss works with C to do the same for getting all of D's packages.

Since we are working with an 8 byte pointer and dealing with Heap allocation let's consider this problem here. Let us say that the Boss is 100 feet from A and that A is 500 feet from C . We don't need to worry about how far the Boss is initially from C because of the order of executions. In both cases the Boss initially travels from A first then to B . This analogy isn't to say that this distance is exact; it is just a use test case scenario to show the workings of the algorithms. In many cases when doing heap allocations and working with the cache and page files, these distances between address locations may not vary that much in differences or they can very significantly depending on the nature of the data types and the array sizes.


The Test Cases:

First Case: On first iteration the Boss has to initially go 100 feet to give the order slip to A and A goes off and does his thing, but then the Boss has to travel 500 feet to C to give him his order slip. Then on the next iteration and every other iteration after the Boss has to go back and forth 500 feet between the two.

Second Case: The Boss has to travel 100 feet on the first iteration to A , but after that he is already there and just waits for A to get back until all slips are filled. Then the Boss has to travel 500 feet on the first iteration to C because C is 500 feet from A since this Boss( Summation, For Loop ) is being called right after working with A and then just waits like he did with A until all of C's order slips are done.


The Difference In Distances Traveled

 const n = 100000 distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); // Simplify distTraveledOfFirst = 600 + (99999*100); distTraveledOfFirst = 600 + 9999900; distTraveledOfFirst = 10000500; // Distance Traveled On First Algorithm = 10,000,500ft distTraveledOfSecond = 100 + 500 = 600; // Distance Traveled On Second Algorithm = 600ft; 

The Comparison of Arbitrary Values

We can easily see that 600 is far less than 10 million. Now this isn't exact, because we don't know the actual difference in distance between which address of RAM or from which Cache or Page File each call on each iteration is going to be due to many other unseen variables, but this is just an assessment of the situation to be aware of and trying to look at it from the worst case scenario.

So by these numbers it would almost look as if Algorithm One should be 99% slower than Algorithm Two; however, this is only the The Boss's part or responsibility of the algorithms and it doesn't account for the actual workers A , B , C , & D and what they have to do on each and every iteration of the Loop. So the bosses job only accounts for about 15 - 40% of the total work being done. So the bulk of the work which is done through the workers has a slight bigger impact towards keeping the ratio of the speed rate differences to about 50-70%


The Observation: - The differences between the two algorithms

In this situation it is the structure of the process of the work being done and it does go to show that Case 2 is more efficient from both that partial optimization of having a similar function declaration and definition where it is only the variables that differ by name. And we also see that the total distance traveled in Case 1 is much farther than it is in Case 2 and we can consider this distance traveled our Time Factor between the two algorithms. Case 1 has considerable more work to do than Case 2 does. This was also seen in the evidence of the ASM that was shown between both cases. Even with what was already said about these cases, it also doesn't account for the fact that in Case 1 the boss will have to wait for both A & C to get back before he can go back to A again on the next iteration and it also doesn't account for the fact that if A or B is taking an extremely long time then both the Boss and the other worker(s) are also waiting at an idle. In Case 2 the only one being idle is the Boss until the worker gets back. So even this has an impact on the algorithm.


Conclusión:

Case 1 is a classic interpolation problem that happens to be an inefficient one. I also think that this was one of the leading reasons of why many machine architectures and developers ended up building and designing multi-core systems with the ability to do multi-threaded applications as well as parallel programming.

So even looking at it from this approach without even involving how the Hardware, OS and Compiler works together to do heap allocations that involves working with RAM, Cache, Page Files, etc.; the mathematics behind it already shows us which of these two is the better solution from using the above analogy where the Boss or the Summations being those the For Loops that had to travel between Workers A & B . We can easily see that Case 2 is at least as 1/2 as fast if not a little more than Case 1 due to the difference in the distanced traveled and the time taken. And this math lines up almost virtually and perfectly with both the Bench Mark Times as well as the Amount of difference in the amount of Assembly Instructions.



The OPs Amended Question(s)

EDIT: The question turned out to be of no relevance, as the behavior severely depends on the sizes of the arrays (n) and the CPU cache. So if there is further interest, I rephrase the question:

Could you provide some solid insight into the details that lead to the different cache behaviors as illustrated by the five regions on the following graph?

It might also be interesting to point out the differences between CPU/cache architectures, by providing a similar graph for these CPUs.


Regarding These Questions

As I have demonstrated without a doubt, there is an underlying issue even before the Hardware and Software becomes involved. Now as for the management of memory and caching along with page files, etc. which all works together in an integrated set of systems between: The Architecture { Hardware, Firmware, some Embedded Drivers, Kernels and ASM Instruction Sets }, The OS { File and Memory Management systems, Drivers and the Registry }, The Compiler { Translation Units and Optimizations of the Source Code }, and even the Source Code itself with its set(s) of distinctive algorithms; we can already see that there is a bottleneck that is happening within the first algorithm before we even apply it to any machine with any arbitrary Architecture , OS , and Programmable Language compared to the second algorithm. So there already existed a problem before involving the intrinsics of a modern computer.


The Ending Results

Sin embargo; it is not to say that these new questions are not of importance because they themselves are and they do play a role after all. They do impact the procedures and the overall performance and that is evident with the various graphs and assessments from many who have given their answer(s) and or comment(s). If you pay attention to the analogy of the Boss and the two workers A & B who had to go and retrieve packages from C & D respectively and considering the mathematical notations of the two algorithms in question you can see that without even the involvement of the computer Case 2 is approximately 60% faster than Case 1 and when you look at the graphs and charts after these algorithms have been applied to source code, compiled and optimized and executed through the OS to perform operations on the given hardware you even see a little more degradation between the differences in these algorithms.

Now if the "Data" set is fairly small it may not seem all that bad of a difference at first but since Case 1 is about 60 - 70% slower than Case 2 we can look at the growth of this function as being in terms of the differences in time executions:

 DeltaTimeDifference approximately = Loop1(time) - Loop2(time) //where Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately // So when we substitute this back into the difference equation we end up with DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time) // And finally we can simplify this to DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time) 

And this approximation is the average difference between these two loops both algorithmically and machine operations involving software optimizations and machine instructions. So when the data set grows linearly, so does the difference in time between the two. Algorithm 1 has more fetches than algorithm 2 which is evident when the Boss had to travel back and forth the maximum distance between A & C for every iteration after the first iteration while Algorithm 2 the Boss had to travel to A once and then after being done with A he had to travel a maximum distance only one time when going from A to C .

So trying to have the Boss focusing on doing two similar things at once and juggling them back and forth instead of focusing on similar consecutive tasks is going to make him quite angry by the end of the day because he had to travel and work twice as much. Therefor do not lose the scope of the situation by letting your boss getting into an interpolated bottleneck because the boss's spouse and children wouldn't appreciate it.

May be old C++ and optimizations. In my computer I obtained almost the same speed:

one loop: 1.577ms two loops: 1.507ms

I run VS2015 on E5-1620 3.5Ghz processor with 16Gb ram