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


Suponer a1, b1, c1y d1 apuntar a la memoria del montón y mi código numérico tiene el siguiente ciclo central.

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 externo for lazo. 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 tarda 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 desmontaje para el primer ciclo básicamente se ve así (este bloque se repite unas 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 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 arquitecturas de CPU / caché, al proporcionar un gráfico similar para estas CPU.

PPS: aquí está el código completo. Usa TBB  Tick_Count para un tiempo de resolución más alto, que se puede desactivar al no definir el TBB_TIMING Macro:

#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.)

enter image description here


1995
2017-12-17 20:40


origen


Respuestas:


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 alineados 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<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 un real Máquina de arquitectura Core 2:

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 ciclo 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 @Stephen Cannon señala en los comentarios, es muy probable que esta alineación cause falso aliasing en las unidades de carga / almacenamiento o el caché. Busqué en Google esto y descubrí que Intel en realidad tiene un contador de hardware para aliasing de direcciones parciales establos:

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 todavía podría tener un efecto ya que Agner Fog menciona conflictos bancarios en 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 falso aliasing puestos 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 @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1544
2017-12-17 21:17



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 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 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:

Enter image description here

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

Enter image description here

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:

Enter image description here

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.


194
2017-12-18 01:29



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.


63
2017-12-17 20:47



Imagina que estás trabajando en una máquina donde n era el valor justo para que solo fuera posible mantener dos de tus arrays en la memoria al mismo tiempo, 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<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

primero causaría a y b para ser cargado en la RAM y luego se trabajó completamente en la memoria RAM. Cuando comience el segundo ciclo, c y d luego se carga desde el disco a la RAM y se opera.

el otro lazo

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

abrirá dos matrices y una página en las otras dos cada vez que pasa 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.

Decir n = 2 y estamos trabajando con bytes. En mi escenario, así tenemos solo 4 bytes de caché y el resto de nuestra memoria es significativamente más lenta (por ejemplo, un acceso 100 veces más largo).

Asumiendo una política de almacenamiento en caché bastante tonta si el byte no está en la memoria caché, colóquelo allí y obtenga el siguiente byte también mientras estamos en ello 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];
    }
    
  • cache a[0] y a[1] entonces 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.

  • conjunto a[1] = a[1] + b[1] en caché Costo = 1 + 1.
  • Repita para c y 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];
    }
    
  • cache a[0] y a[1] entonces 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] entonces 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é.


37
2017-12-18 01:36



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.


27
2017-12-17 20:49



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 para que el += asignación no estaba preguntando al FPU para agregar basura de memoria interpretada como un doble.

Jugué 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 += b[j] = 1 y += d[j] = 1, y obtuve resultados bastante consistentes.

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

Hardware es Dell XPS 8500 con la generación 3 Core i7 @ 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 <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 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 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.


16
2017-12-30 01:34



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 las matrices. caché de nivel 1 (L1), y luego el caché de nivel 2 (L2), de su CPU y graficar el tiempo que toma su código para ejecutarse contra los tamaños de las matrices. El gráfico no debe ser una línea recta como cabría esperar.


14
2017-12-17 20:52



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.


12
2017-08-17 15:23



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<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 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 & d1 son 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 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 pila, 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 suma 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 configuraremos esto como funciones y llamadas a funciones para ser F1(), F2(), f(a), f(b), f(c) y f(d).

Los algoritmos:

Primer caso: - Solo una suma, 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);  }

2 ° caso: - Dos sumas 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 lo notaste F2() solo existe en Sum donde ambos Sum1 y Sum2 solo contiene F1(). Esto también será evidente más adelante cuando comencemos a concluir que hay una especie de optimización que está sucediendo desde el segundo algoritmo.

Las iteraciones a través del primer caso Sum llamadas f(a) eso se agregará a sí mismo f(b) entonces llama f(c) eso hará lo mismo pero agrega f(d) a sí mismo para cada 100000 iterations. En el segundo caso tenemos Sum1 y Sum2 Y ambos actúan igual que si fueran la misma función que se llama dos veces seguidas. En este caso podemos tratar Sum1 y Sum2 como simplemente viejo Sum dónde Sum en este caso se ve así: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } y ahora esto parece una optimización donde podemos considerar que es la misma función.


Resumen con Analogy

Con lo que vimos en el segundo caso, casi parece que hay optimización, ya que ambos bucles tienen la misma firma exacta, pero este no es el verdadero problema. El problema no es el trabajo que está haciendo f(a),f(b),f(c)&f(d) en ambos casos y la comparación entre los dos es la diferencia en la distancia que tiene que recorrer el Sumatorio en ambos casos, lo que le da la diferencia en la ejecución del tiempo.

Pensar en For Loops como siendo el Summations eso hace que las iteraciones sean una Boss eso es dar órdenes a dos personas A & B y que sus trabajos son para la carne C & D respectivamente y para recoger un paquete de ellos y devolverlo. En la analogía aquí, las iteraciones forzadas o sumatorias y las comprobaciones de condición en sí mismas no representan realmente el Boss. Lo que realmente representa el Boss aquí no es directamente de los algoritmos matemáticos reales, sino del concepto real de Scope y Code Block dentro 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 lista de llamadas, Boss va a A y da la orden y A sale a buscar B's paquete entonces el Boss va a C y da las órdenes de hacer lo mismo y recibir el paquete de D en cada iteración.

En el segundo caso, Boss trabaja directamente con A ir a buscar B's paquete hasta que se reciban todos los paquetes. Entonces el Bossfunciona con C hacer lo mismo para obtener todos D's paquetes.

Como estamos trabajando con un puntero de 8 bytes y tratando con la asignación de Heap, consideremos este problema aquí. Digamos que el Boss está a 100 pies de A y eso A está a 500 pies de C. No tenemos que preocuparnos de cuán lejos el Boss es inicialmente de C debido al orden de las ejecuciones. En ambos casos, Boss inicialmente viaja desde A primero luego a B. Esta analogía no quiere decir que esta distancia sea exacta; es solo un escenario de caso de prueba de uso para mostrar el funcionamiento de los algoritmos. En muchos casos, al hacer asignaciones de montón y trabajar con la caché y los archivos de página, estas distancias entre ubicaciones de direcciones pueden no variar mucho en cuanto a las diferencias o pueden variar significativamente dependiendo de la naturaleza de los tipos de datos y los tamaños de las matrices.


Los casos de prueba:

Primer caso: En la primera iteración, Boss tiene que ir inicialmente 100 pies para dar el comprobante de pedido a A y A se va y hace lo suyo, pero luego el Boss tiene que viajar 500 pies a C para darle su nota de pedido. Luego, en la siguiente iteración y en cualquier otra iteración después del Boss tiene que ir y venir a 500 pies entre los dos.

Segundo caso:  The Boss tiene que viajar 100 pies en la primera iteración a A, pero después de eso él ya está allí y solo espera A para volver hasta que todos los resbalones estén llenos. Entonces el Boss tiene que viajar 500 pies en la primera iteración a C porque C está a 500 pies de A desde esto Boss( Summation, For Loop ) se llama justo después de trabajar con A y luego simplemente espera como lo hizo con A hasta que todos C's los resbalones de orden están hechos.


La diferencia en las 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 bien, esto no es exacto, porque no conocemos la diferencia real en la distancia entre cada dirección de la RAM o desde la cual el Caché o el Archivo de la Página cada llamada en cada iteración va a ser debida a muchas otras variables no vistas, pero esto es solo una evaluación de la situación a tener en cuenta e intentar verla desde el peor de los casos.

Entonces, según estos números, casi parecería que el Algoritmo Uno debería ser un 99% más lento que el Algoritmo Dos; sin embargo, esto es solo el The Boss's parte o responsabilidad de los algoritmos y no cuenta para los trabajadores reales A, B, C, Y D y lo que tienen que hacer en cada iteración del Loop. Por lo tanto, el trabajo de los jefes solo representa entre el 15 y el 40% del trabajo total realizado. Por lo tanto, la mayor parte del trabajo que se realiza a través de los trabajadores tiene un impacto levemente mayor para mantener la relació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 está realizando y muestra que Caso 2es más eficiente desde ambos esa optimización parcial de tener una declaración y declaración de función similar donde solo son las variables las que difieren por su nombre. Y también vemos que la distancia total viajó en Caso 1 está mucho más lejos que en Caso 2 y podemos considerar esta distancia recorrida nuestra Factor de tiempo entre los dos algoritmos. Caso 1 tiene mucho más trabajo que hacer que Caso 2 hace. Esto también se vio en la evidencia de la ASM eso se mostró entre ambos casos. Incluso con lo que ya se dijo sobre estos casos, tampoco tiene en cuenta el hecho de que Caso 1 el jefe tendrá que esperar por ambos A & C para volver antes de que pueda volver a A de nuevo en la próxima iteración y tampoco tiene en cuenta el hecho de que si A o B está tomando un tiempo extremadamente largo, entonces tanto el Boss y el otro trabajador (s) también está esperando al ralentí. En Caso 2 el único que está inactivo es el Boss hasta que el trabajador regrese. Entonces, incluso esto tiene un impacto en el algoritmo.


Conclusión:

Caso 1 es un problema clásico de interpolación que resulta ser ineficiente. También creo que esta fue una de las principales razones por las que muchas arquitecturas y desarrolladores de máquinas terminaron construyendo y diseñando sistemas multi-core con la capacidad de realizar aplicaciones de subprocesos múltiples y programación paralela.

Así que incluso mirándolo desde este enfoque sin siquiera involucrar la manera en que el Hardware, el SO y el Compilador trabajan juntos para hacer distribuciones de pila que involucran trabajar con RAM, Caché, Archivos de Página, etc .; las matemáticas detrás de esto ya nos muestran cuál de estos dos es la mejor solución al usar la analogía anterior donde el Boss o el Summations siendo esos los For Loops que tuvo que viajar entre trabajadores A & B. Podemos ver fácilmente eso Caso 2 es al menos tan 1/2 como rápido si no es un poco más que Caso 1 debido a la diferencia en la distancia recorrida y el tiempo empleado. Y esta matemática se alinea casi de manera virtual y perfecta tanto con el Bench Mark Times como con la cantidad de diferencia en la cantidad de instrucciones de ensamblaje.



Las OP enmendadas Pregunta (s)

EDITAR: 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 arquitecturas de CPU / caché, al proporcionar un gráfico similar para estas CPU.


En cuanto a estas preguntas

Como lo he demostrado sin lugar a dudas, hay un problema subyacente incluso antes de que se involucre el Hardware y el Software. Ahora, en cuanto a la gestión de la memoria y el almacenamiento en caché junto con los archivos de página, etc., que funcionan todos juntos en un conjunto integrado de sistemas entre: The Architecture {Hardware, firmware, algunos controladores incrustados, kernels y conjuntos de instrucciones ASM}, The OS{Sistemas de administració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 Code en sí mismo con su (s) conjunto (s) de algoritmos distintivos; ya podemos ver que hay un cuello de botella que está sucediendo dentro del primer algoritmo incluso antes de que lo apliquemos a cualquier máquina con cualquier arbitrario Architecture, OSy Programmable Languagecomparado con el segundo algoritmo. Entonces, ya existía un problema antes de involucrar las características intrínsecas de una computadora moderna.


Los resultados finales

Sin embargo; no quiere decir que estas nuevas preguntas no sean importantes porque ellas mismas sí lo son y desempeñan un papel después de todo. Tienen un impacto en los procedimientos y en el rendimiento general, y eso es evidente con los diversos gráficos y evaluaciones de muchos que dieron sus respuestas y / o comentarios. Si prestas atención a la analogía de la Boss y los dos trabajadores A & B quien tuvo que ir y recuperar paquetes de C & D respectivamente y teniendo en cuenta las notaciones matemáticas de los dos algoritmos en cuestión, se puede ver que sin la participación de la computadora Case 2 es aproximadamente un 60% más rápido que Case 1 y cuando mira los gráficos y tablas después de que estos algoritmos se hayan aplicado al código fuente, compilados, optimizados y ejecutados a través del sistema operativo para realizar operaciones en el hardware dado, incluso se observa una degradación un poco mayor entre las diferencias en estos algoritmos.

Ahora bien, si el conjunto de "Datos" es bastante pequeño, puede que no parezca una diferencia tan mala al principio, pero desde Case 1 es sobre 60 - 70% más lento que Case 2 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)

Y esta aproximación es la diferencia promedio entre estos dos bucles, tanto algorítmicamente como operaciones de máquina que involucran optimizaciones de software e instrucciones de máquina. Entonces, cuando el conjunto de datos crece linealmente, también lo hace la diferencia de tiempo entre los dos. El algoritmo 1 tiene más recuperaciones que el algoritmo 2, que es evidente cuando Boss tuvo que viajar hacia adelante y hacia atrás la distancia máxima entre A & C para cada iteración después de la primera iteración mientras que el Algoritmo 2 Boss tuvo que viajar a A una vez y luego de haber terminado con A tenía que viajar una distancia máxima solo una vez cuando iba desde A a C.

Intentando tener el Boss centrarse en hacer dos cosas similares a la vez y hacer malabares con ellas en lugar de concentrarse en tareas similares consecutivas lo pondrá bastante enojado al final del día porque tuvo que viajar y trabajar el doble. Por lo tanto, no pierda el alcance de la situación dejando que su jefe se meta en un cuello de botella interpolado porque la esposa y los hijos del jefe no lo apreciarían.


3
2018-01-30 14:00



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

un bucle: 1.577ms dos bucles: 1.507ms

Ejecuto VS2015 en un procesador E5-1620 3.5Ghz con 16Gb RAM


0
2017-07-11 07:00