Supongamos a1, b1, c1, y el d1punto de la pila de memoria y mi código numérico tiene el siguiente bucle central.

const int n = 100000;

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

Este bucle se ejecuta 10,000 veces a través de otro forbucle 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];
}

Compilado 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 toma solo 1.9 segundos. Mi pregunta es: (Por favor, consulte mi pregunta reformulada en la parte inferior)

PD: No estoy seguro, si esto ayuda:

El desmontaje para el primer ciclo básicamente se ve así (este bloque se repite aproximadamente cinco veces en el programa 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 bucle del ejemplo de doble bucle 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 en gran medida de los tamaños de las matrices (n) y el caché de la CPU. Entonces, si hay más interés, reformulo la pregunta:

¿Podría proporcionar una idea sólida de los detalles que conducen a los diferentes comportamientos de caché como se ilustra en las cinco regiones en el siguiente gráfico?

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

PPS: Aquí está el código completo. Utiliza TBB Tick_Count para temporización de mayor resolución, que se puede deshabilitar al no definir la TBB_TIMINGMacro:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#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.)

Tras un análisis más detallado de esto, creo que esto es (al menos parcialmente) causado por la alineación de datos de los cuatro punteros. 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á asignando todas las matrices por separado. Por lo general, cuando se solicitan asignaciones tan grandes, el asignador solicitará páginas nuevas del sistema operativo. Por lo tanto, existe una alta probabilidad de que aparezcan grandes asignaciones 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<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

Resultados de referencia:

EDITAR: Resultados en una máquina de arquitectura Core 2 real :

2 x Intel Xeon X5482 Harpertown @ 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 del OP exactamente.

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

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

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

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 la sobrecarga, como los bucles y la ramificación.

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 tiene el doble de bucles y ramificaciones en la parte superior.

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

Región 3:

En este punto, los datos ya no caben en el caché L1. Por lo tanto, el rendimiento está limitado por el ancho de banda de caché L1 <-> L2.

Región 4:

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

Sin embargo, para que se produzca un alias falso, debe haber un paso lo suficientemente grande entre los conjuntos de datos. Es por eso que no ves esto en la región 3.

Región 5:

En este punto, nada cabe en el caché. Por lo tanto, está sujeto al ancho de banda de la memoria.

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

Hay muchas respuestas que llevaron 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ó estar en 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 versus una asignación separada) y el consejo 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 la pregunta y las respuestas pueden considerarse completamente incorrectas o verdaderas dependiendo del escenario exacto y los parámetros utilizados.

Tenga en cuenta que mi pregunta inicial fue en 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 bucle (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 utilizando datos inicializados:

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

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

Propuesta

¡Todas las preguntas relacionadas con el rendimiento de bajo nivel sobre el desbordamiento de pila deben ser requeridas para proporcionar información MFLOPS para toda la gama de tamaños de datos relevantes de caché! Es una pérdida de tiempo para todos pensar en respuestas y especialmente discutirlas con otros 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 en la que ntenía el valor justo para que solo fuera posible mantener dos de sus matrices en la memoria al mismo tiempo, pero la memoria total disponible, a través del almacenamiento en caché de disco, todavía era suficiente para contener las cuatro.

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

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

primero causaría ay bse cargaría en la RAM y luego se trabajaría por completo en la RAM. Cuando comienza el segundo bucle, cy dluego se carga desde el disco a la RAM y se opera.

el otro bucle

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

buscará dos matrices y buscará en las otras dos cada vez alrededor del bucle . Obviamente, esto sería mucho más lento.

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

Parece que hay una pequeña confusión / malentendido aquí, así que intentaré elaborar un poco con un ejemplo.

Digamos n = 2y estamos trabajando con bytes. En mi caso, tenemos solo 4 bytes de RAM y el resto de nuestra memoria es significativamente más lenta (digamos un acceso 100 veces más largo).

Suponiendo 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 él , obtendrá un escenario como este:

• Con

  for(int j=0;j<n;j++){
   a[j] += b[j];
  }
  for(int j=0;j<n;j++){
   c[j] += d[j];
  }

• caché a[0]y a[1]luego b[0]y b[1]y establecer a[0] = a[0] + b[0]en caché: ahora hay cuatro bytes en caché, a[0], a[1]y b[0], b[1]. Costo = 100 + 100.

• establecido a[1] = a[1] + b[1]en caché. Costo = 1 + 1.
• Repita para cy d.

• Costo total = (100 + 100 + 1 + 1) * 2 = 404

• Con

  for(int j=0;j<n;j++){
   a[j] += b[j];
   c[j] += d[j];
  }

• caché a[0]y a[1]luego b[0]y b[1]y establecer a[0] = a[0] + b[0]en caché: ahora hay cuatro bytes en caché, a[0], a[1]y b[0], b[1]. Costo = 100 + 100.

• expulsar a[0], a[1], b[0], b[1]de caché y 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 a dónde voy.
• Costo total = (100 + 100 + 100 + 100) * 2 = 800

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

No se debe a un código diferente, sino al almacenamiento en caché: la RAM es más lenta que los registros de la CPU y hay una memoria caché dentro de la CPU para evitar escribir la RAM cada vez que cambia una variable. Pero el caché no es grande como lo es la RAM, por lo tanto, asigna solo una fracción.

El primer código modifica las direcciones de memoria distantes alternando en cada bucle, lo que requiere invalidar continuamente 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 memoria caché, invalidándolo solo después de que comience el segundo bucle.

No puedo replicar los resultados discutidos aquí.

No sé si el código de referencia deficiente es el culpable, o qué, pero los dos métodos están dentro del 10% entre sí en mi máquina usando el siguiente código, y un bucle suele ser un poco más rápido que dos, como lo haría esperar.

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

He jugado un poco con diferentes esquemas, como poner la asignación de b[j], d[j]al InitToZero[j]interior de los bucles, y también con el uso de += b[j] = 1y += d[j] = 1, y me dieron resultados bastante consistentes.

Como era de esperar, la inicialización by del uso dentro del ciclo InitToZero[j]le dieron una ventaja al enfoque combinado, ya que se hicieron consecutivamente antes de las asignaciones a ay c, pero aún dentro del 10%. Imagínate.

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

PD: cambié los bucles para contar a 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 los recuentos de bucles.

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

No estoy seguro de por qué se decidió que MFLOPS era una métrica relevante. Pensé que la idea era centrarme en los accesos a la memoria, así que intenté minimizar la cantidad de tiempo de cálculo de 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 sea uniforme independientemente del recuento de bucles. Tal vez me perdí algo en la conversación, pero vale la pena pensarlo dos veces. Si el plus se deja fuera de la tarea, el tiempo acumulado es casi idéntico a 31 segundos cada uno.

Se debe a que la CPU no tiene tantos errores de caché (donde tiene que esperar a que los datos de la matriz provengan de los chips RAM). Sería interesante para usted ajustar el tamaño de las matrices continuamente para que exceda los tamaños de la caché de nivel 1 (L1), y luego la caché de nivel 2 (L2), de su CPU y graficar el tiempo necesario para su código ejecutar contra los tamaños de las matrices. El gráfico no debería 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 del tamaño del elemento.

Intente escribir dos líneas paralelas de 20 cruces con un bolígrafo y un papel separados por 20 cm. Intente terminar una y luego la otra línea e intente otra vez escribiendo una cruz en cada línea alternativamente.

La pregunta original

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

Conclusión:

El caso 1 es un problema clásico de interpolación que resulta ineficiente. También creo que esta fue una de las principales razones por las que muchas arquitecturas de máquinas y desarrolladores terminaron construyendo y diseñando sistemas de múltiples núcleos con la capacidad de hacer aplicaciones de múltiples subprocesos, así como programación paralela.

Mirándolo desde este tipo de enfoque sin involucrar cómo el hardware, el sistema operativo y el compilador (es) trabajan juntos para realizar asignaciones de almacenamiento dinámico que implican trabajar con RAM, caché, archivos de página, etc. La matemática que está en la base de estos algoritmos nos muestra cuál de estos dos es la mejor solución.

Podemos usar una analogía de un Bossser Summationque representará un For Loopque tiene que viajar entre trabajadores Ay B.

Podemos ver fácilmente que el Caso 2 es al menos la mitad de rápido si no un poco más que el Caso 1 debido a la diferencia en la distancia que se necesita para viajar y el tiempo que toman los trabajadores. Esta matemática se alinea casi virtualmente y perfectamente tanto con el BenchMark Times como con la cantidad de diferencias en las Instrucciones de ensamblaje.

Ahora comenzaré a explicar cómo funciona todo esto a continuación.

Evaluar el problema

El código del OP:

const int n=100000;

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

Y

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

La consideración

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

El enfoque

Teniendo en cuenta los dos bucles y toda la discusión sobre la caché y la presentación de páginas, me gustaría adoptar 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 se refiere al hardware o software real.

La perspectiva

Después de mirar el código por un tiempo, se hizo bastante evidente cuál es el problema y qué lo está generando. Vamos a dividir esto en un problema algorítmico y analizarlo desde la perspectiva del uso de anotaciones matemáticas y luego aplicar una analogía a los problemas matemáticos, así como a los algoritmos.

Lo que sabemos

Sabemos que este ciclo se ejecutará 100,000 veces. También sabemos que a1, b1, c1y d1son punteros en una arquitectura 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 tienen 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-8 bytes en cada iteración, en el segundo caso, estamos asignando 16 bytes para cada iteración para ambos bucles independientes.

Ambos bucles aún equivalen a 32 bytes en asignaciones totales. Con esta información, avancemos y muestremos las matemáticas generales, los algoritmos y la analogía de estos conceptos.

Sí sabemos la cantidad de veces que el mismo conjunto o grupo de operaciones tendrá que realizarse en ambos casos. Sí sabemos la cantidad de memoria que debe asignarse en ambos casos. Podemos evaluar que la carga de trabajo general 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 realicemos una prueba de referencia. Sin embargo, los puntos de referencia ya estaban incluidos en la pregunta original y también en algunas de las respuestas y comentarios; y podemos ver una diferencia significativa entre los dos y este es el razonamiento completo de esta propuesta para este problema.

Investiguemos

Ya es evidente que muchos ya lo han hecho al observar las asignaciones del montón, las pruebas de referencia, la RAM, la caché y los archivos de página. Al observar puntos de datos específicos e índices de iteración específicos también se incluyeron y las diversas conversaciones sobre este problema específico han hecho que muchas personas comiencen a cuestionar otras cosas relacionadas al respecto. ¿Cómo comenzamos a ver este problema usando algoritmos matemáticos y aplicando una analogía? ¡Comenzamos haciendo un par de afirmaciones! Luego desarrollamos nuestro algoritmo a partir de ahí.

Nuestras afirmaciones:

• Dejaremos que nuestro bucle y sus iteraciones sean una Sumatoria que comience en 1 y termine en 100000 en lugar de comenzar con 0 como en los bucles, ya que no debemos preocuparnos por el esquema de indexación 0 del direccionamiento de memoria ya que solo estamos interesados ​​en El algoritmo mismo.
• En ambos casos, tenemos 4 funciones para trabajar y 2 llamadas de función con 2 operaciones que se realizan en cada llamada de función. Vamos a establecer estas arriba como funciones y llamadas a funciones como las siguientes: F1(), F2(), f(a), f(b), f(c)y f(d).

Los algoritmos

Primer caso: - Solo una suma pero dos llamadas a funciones 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 sumas pero cada una tiene su propia llamada a la 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 Sumdesde Case1donde F1()está contenido en Sumdesde Case1y en ambos Sum1y Sum2desde Case2. Esto será evidente más adelante cuando comencemos a concluir que existe una optimización dentro del segundo algoritmo.

Las iteraciones a través de las Sumllamadas de primer caso f(a)que se sumarán a sí mismas, f(b)luego llama a f(c)que harán lo mismo pero se sumarán f(d)a sí mismas para cada 100000iteración. En el segundo caso, tenemos Sum1y Sum2que ambos actúan igual que si fueran la misma función que se llama dos veces seguidas.

En este caso, podemos tratar Sum1y Sum2, simplemente, como antes, Sumdonde Sumen este caso se ve así: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }y ahora esto parece una optimización en la que podemos considerar que es la misma función.

Resumen con analogía

Con lo que hemos visto en el segundo caso, casi parece que hay una optimización, ya que ambos bucles tienen la misma firma exacta, pero este no es el problema real. El problema no es el trabajo que se está realizando f(a), f(b), f(c), y f(d). En ambos casos y en la comparación entre los dos, es la diferencia en la distancia que tiene que recorrer la suma en cada caso lo que le da la diferencia en el tiempo de ejecución.

Piense en el For Loopscomo el Summationsque hace las iteraciones como ser una Bossque está dando órdenes a dos personas Ay By que sus puestos de trabajo son a la carne Cy D, respectivamente, y para recoger algún paquete de ellos y lo devuelve. En esta analogía, los bucles for o las iteraciones de suma y las comprobaciones de condición no representan realmente el Boss. Lo que en realidad representa Bossno es de los algoritmos matemáticos reales directamente, sino del concepto real Scopey Code Blockdentro de una rutina o subrutina, método, función, unidad de traducción, etc. El primer algoritmo tiene 1 alcance donde el segundo algoritmo tiene 2 ámbitos consecutivos.

Dentro del primer caso en cada recibo de llamada, el Bossva Ay da la orden y Asale a buscar el B'spaquete, luego Bossva Cy da las órdenes para hacer lo mismo y recibir el paquete Den cada iteración.

Dentro del segundo caso, Bossfunciona directamente con Air y buscar el B'spaquete hasta que se reciban todos los paquetes. Luego, Bossfunciona Cpara hacer lo mismo para obtener todos los D'spaquetes.

Dado que estamos trabajando con un puntero de 8 bytes y tratando con la asignación del montón, consideremos el siguiente problema. Digamos que Bossestá a 100 pies de distancia Ay que Aestá a 500 pies de distancia C. No tenemos que preocuparnos de cuán lejos Bossestá inicialmente Cdebido al orden de las ejecuciones. En ambos casos, el Bossviaje inicial desde el Aprimero hasta el B. Esta analogía no quiere decir que esta distancia sea exacta; es solo un caso de prueba útil para mostrar el funcionamiento de los algoritmos.

En muchos casos, cuando se realizan asignaciones de almacenamiento dinámico y se trabaja con el caché y los archivos de página, estas distancias entre las ubicaciones de las direcciones pueden no variar mucho o pueden variar significativamente según la naturaleza de los tipos de datos y los tamaños de los arreglos.

Los casos de prueba:

Primer caso: en la primera iteración,Bossinicialmente tiene que avanzar 100 pies para dar el deslizamiento de la ordenAyAse apaga y hace lo suyo, pero luegoBosstiene que viajar 500 piesCpara darle su deslizamiento de la orden. Luego, en la siguiente iteración y cada dos iteraciones después de queBosstenga que ir y venir 500 pies entre los dos.

Segundo caso: ElBosstiene que viajar 100 pies en la primera iteración paraA, pero después de eso, él ya está ahí y simplemente espera aAque volver hasta que todas las hojas están llenas. Entonces elBosstiene que viajar 500 pies en la primera iteraciónCporqueCes 500 pies deA. Dado que estoBoss( Summation, For Loop )se llama justo después de trabajar conAél, solo espera allí como lo hizoAhasta que seC'scompletentodos losresbalonesdepedidos.

La diferencia en distancias recorridas

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;    

La comparación de valores arbitrarios

Podemos ver fácilmente que 600 es mucho menos de 10 millones. Ahora, esto no es exacto, porque no sabemos la diferencia real en la distancia entre qué dirección de RAM o desde qué caché o archivo de página cada llamada en cada iteración se debe a muchas otras variables invisibles. Esto es solo una evaluación de la situación a tener en cuenta y mirarla desde el peor de los casos.

A partir de estos números, casi parecería que el Algoritmo Uno debería ser 99%más lento que el Algoritmo Dos; Sin embargo, esto es sólo la Boss'sparte o la responsabilidad de los algoritmos y no da cuenta de los trabajadores reales A, B, C, Y Dy lo que tienen que hacer en cada iteración del bucle. Por lo tanto, el trabajo del jefe solo representa entre el 15 y el 40% del trabajo total realizado. La mayor parte del trabajo que se realiza a través de los trabajadores tiene un impacto ligeramente mayor para mantener la proporción de las diferencias de velocidad en aproximadamente 50-70%

La observación: - Las diferencias entre los dos algoritmos

En esta situación, es la estructura del proceso del trabajo que se realiza. Demuestra que el Caso 2 es más eficiente tanto por la optimización parcial de tener una declaración de función similar como por una definición en la que solo las variables difieren por nombre y la distancia recorrida.

También vemos que la distancia total recorrida en el caso 1 está mucho más lejos que en el caso 2 y podemos considerar esta distancia recorrida como nuestro factor de tiempo entre los dos algoritmos. El caso 1 tiene mucho más trabajo que hacer que el caso 2 .

Esto es observable a partir de la evidencia de las ASMinstrucciones que se mostraron en ambos casos. Junto con lo que ya se dijo sobre estos casos, esto no explica el hecho de que en el Caso 1 el jefe tendrá que esperar a ambos Ay Cvolver antes de poder volver a Avolver para cada iteración. Tampoco tiene en cuenta el hecho de que si Ao Bestá tardando mucho tiempo, tanto el Bosso los otros trabajadores están inactivos esperando a ser ejecutados.

En el caso 2, el único que está inactivo es Bosshasta que el trabajador regrese. Entonces, incluso esto tiene un impacto en el algoritmo.

Los PO pregunta (s) modificada (s)

EDITAR: La pregunta resultó ser irrelevante, ya que el comportamiento depende en gran medida de los tamaños de las matrices (n) y el caché de la CPU. Entonces, si hay más interés, reformulo la pregunta:

¿Podría proporcionar una idea sólida de los detalles que conducen a los diferentes comportamientos de caché como se ilustra en las cinco regiones en el siguiente gráfico?

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

Sobre estas preguntas

Como he demostrado sin lugar a dudas, hay un problema subyacente incluso antes de que el Hardware y el Software se involucren.

Ahora, en cuanto a la gestión de la memoria y el almacenamiento en caché junto con los archivos de página, etc., todos trabajan juntos en un conjunto integrado de sistemas entre los siguientes:

• The Architecture {Hardware, firmware, algunos controladores integrados, kernels y conjuntos de instrucciones ASM}.
• The OS{Sistemas de gestión de archivos y memoria, controladores y el registro}.
• The Compiler {Unidades de traducción y optimizaciones del código fuente}.
• E incluso el Source Codemismo con su (s) conjunto (s) de algoritmos distintivos.

Ya podemos ver que hay un cuello de botella que está sucediendo dentro del primer algoritmo antes de que incluso lo aplicamos a cualquier máquina con cualquier arbitraria Architecture, OSy Programmable Languageen comparación con el segundo algoritmo. Ya existía un problema antes de involucrar a los intrínsecos de una computadora moderna.

Los resultados finales

Sin embargo; no quiere decir que estas nuevas preguntas no sean importantes porque ellas mismas lo son y juegan un papel después de todo. Impactan los procedimientos y el rendimiento general y eso es evidente con los diversos gráficos y evaluaciones de muchos que han dado sus respuestas y / o comentarios.

Si prestó atención a la analogía de los Bossdos trabajadores Ay Bquién tuvo que ir y recuperar paquetes de C& Drespectivamente y considerando las anotaciones matemáticas de los dos algoritmos en cuestión; puede ver sin la participación del hardware y el software de la computadora Case 2es aproximadamente 60%más rápido que Case 1.

Cuando observa los gráficos y cuadros después de que estos algoritmos se hayan aplicado a algún código fuente, compilado, optimizado y ejecutado a través del sistema operativo para realizar sus operaciones en una determinada pieza de hardware, incluso puede ver un poco más de degradación entre las diferencias en estos algoritmos

Si el Dataconjunto es bastante pequeño, puede no parecer una gran diferencia al principio. Sin embargo, dado que Case 1es 60 - 70%más lento de Case 2lo que podemos ver el crecimiento de esta función en términos de las diferencias en las ejecuciones de tiempo:

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)

Esta aproximación es la diferencia promedio entre estos dos bucles tanto algorítmicamente como las operaciones de la máquina que implican optimizaciones de software e instrucciones de la máquina.

Cuando el conjunto de datos crece linealmente, también lo hace la diferencia de tiempo entre los dos. El algoritmo 1 tiene más alcances que el algoritmo 2, lo cual es evidente cuando Bosstiene que viajar de ida y vuelta la distancia máxima entre Ay Cpara cada iteración después de la primera iteración, mientras que el Algoritmo 2 Bosstiene que viajar Auna vez y luego de haber terminado con Aél tiene que viajar una distancia máxima solo una vez al pasar de Aa C.

Intentar Bossconcentrarse en hacer dos cosas similares a la vez y hacer malabares entre ellas en lugar de enfocarse en tareas consecutivas similares lo enojará bastante al final del día ya que tuvo que viajar y trabajar el doble. Por lo tanto, no pierda el alcance de la situación permitiendo que su jefe se meta en un cuello de botella interpolado porque el cónyuge y los hijos del jefe no lo apreciarían.

Enmienda: Principios de diseño de ingeniería de software

- La diferencia Local Stacky los Heap Allocatedcálculos dentro de iterativos para bucles y la diferencia entre sus usos, sus eficiencias y efectividad -

El algoritmo matemático que propuse anteriormente se aplica principalmente a los bucles que realizan operaciones en los datos que se asignan en el montón.

• Operaciones consecutivas de apilamiento:
  • Si los bucles están realizando operaciones en los datos localmente dentro de un solo bloque de código o alcance que está dentro del marco de la pila, todavía se aplicará, pero las ubicaciones de la memoria están mucho más cerca donde generalmente son secuenciales y la diferencia en la distancia recorrida o el tiempo de ejecución Es casi insignificante. Como no se realizan asignaciones dentro del montón, la memoria no está dispersa y la memoria no se recupera a través de la memoria RAM. La memoria es típicamente secuencial y relativa al marco de la pila y al puntero de la pila.
  • Cuando se realizan operaciones consecutivas en la pila, un procesador moderno almacenará en caché valores repetitivos y direcciones manteniendo estos valores dentro de los registros de caché local. El tiempo de operaciones o instrucciones aquí es del orden de nano-segundos.
• Operaciones asignadas de montón consecutivas:
  • Cuando comienza a aplicar asignaciones de almacenamiento dinámico y el procesador tiene que buscar las direcciones de memoria en llamadas consecutivas, dependiendo de la arquitectura de la CPU, el controlador de bus y los módulos Ram, el tiempo de operaciones o ejecución puede ser del orden de micro a milisegundos En comparación con las operaciones de pila en caché, estas son bastante lentas.
  • La CPU tendrá que obtener la dirección de memoria de Ram y, por lo general, cualquier cosa en el bus del sistema es lenta en comparación con las rutas de datos internas o los buses de datos dentro de la CPU.

Entonces, cuando trabaja con datos que deben estar en el montón y los atraviesa en bucles, es más eficiente mantener cada conjunto de datos y sus algoritmos correspondientes dentro de su propio bucle único. Obtendrá mejores optimizaciones en comparación con intentar factorizar bucles consecutivos al colocar múltiples operaciones de diferentes conjuntos de datos que están en el montón en un solo bucle.

Está bien hacer esto con los datos que están en la pila, ya que con frecuencia se almacenan en caché, pero no para los datos que deben consultar su dirección de memoria en cada iteración.

Aquí es donde entra en juego la ingeniería de software y el diseño de arquitectura de software. Es la capacidad de saber cómo organizar sus datos, saber cuándo almacenar en caché sus datos, saber cuándo asignar sus datos en el montón, saber cómo diseñar e implementar sus algoritmos, y saber cuándo y dónde llamarlos.

Es posible que tenga el mismo algoritmo que pertenece al mismo conjunto de datos, pero es posible que desee un diseño de implementación para su variante de pila y otro para su variante asignada en el montón solo por el problema anterior que se ve por su O(n)complejidad del algoritmo cuando funciona con el montón

Por lo que he notado a lo largo de los años, muchas personas no tienen en cuenta este hecho. Tienden a diseñar un algoritmo que funcione en un conjunto de datos en particular y lo usarán independientemente del conjunto de datos que se almacena en caché local en la pila o si se asignó en el montón.

Si desea una verdadera optimización, sí, puede parecer una duplicación de código, pero para generalizar sería más eficiente tener dos variantes del mismo algoritmo. ¡Uno para las operaciones de pila y el otro para las operaciones de montón que se realizan en bucles iterativos!

Aquí hay un pseudo ejemplo: dos estructuras simples, un algoritmo.

struct A {
    int data;
    A() : data{0}{}
    A(int a) : data{a}{} 
};
struct B {
    int data;
    B() : data{0}{}
    A(int b) : data{b}{}
}                

template<typename T>
void Foo( T& t ) {
    // do something with t
}

// some looping operation: first stack then heap.

// stack data:
A dataSetA[10] = {};
B dataSetB[10] = {};

// For stack operations this is okay and efficient
for (int i = 0; i < 10; i++ ) {
   Foo(dataSetA[i]);
   Foo(dataSetB[i]);
}

// If the above two were on the heap then performing
// the same algorithm to both within the same loop
// will create that bottleneck
A* dataSetA = new [] A();
B* dataSetB = new [] B();
for ( int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]); // dataSetA is on the heap here
    Foo(dataSetB[i]); // dataSetB is on the heap here
} // this will be inefficient.

// To improve the efficiency above, put them into separate loops... 

for (int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]);
}
for (int i = 0; i < 10; i++ ) {
    Foo(dataSetB[i]);
}
// This will be much more efficient than above.
// The code isn't perfect syntax, it's only psuedo code
// to illustrate a point.

Esto es a lo que me refería al tener implementaciones separadas para las variantes de pila frente a las variantes de montón. Los algoritmos en sí mismos no importan demasiado, son las estructuras de bucle las que usará en eso.

Puede ser viejo C ++ y optimizaciones. En mi computadora obtuve casi la misma velocidad:

Un bucle: 1.577 ms

Dos bucles: 1.507 ms

Ejecuto Visual Studio 2015 en un procesador E5-1620 3.5 GHz con 16 GB de RAM.