Suponha a1, b1, c1, e d1ponto de memória heap e meu código numérico tem o seguinte ciclo núcleo.

const int n = 100000;

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

Este loop é executado 10.000 vezes através de outro forloop externo . Para acelerar, alterei o código para:

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

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

Compilado no MS Visual C ++ 10.0 com otimização total e SSE2 habilitado para 32 bits em um Intel Core 2 Duo (x64), o primeiro exemplo leva 5,5 segundos e o exemplo de loop duplo leva apenas 1,9 segundos. Minha pergunta é: (Consulte a minha pergunta reformulada na parte inferior)

PS: Não tenho certeza, se isso ajuda:

A desmontagem para o primeiro loop basicamente se parece com isso (este bloco é repetido cerca de cinco vezes no 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 loop do exemplo de loop duplo produz esse código (o seguinte bloco é repetido cerca de três vezes):

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

A questão acabou não sendo relevante, pois o comportamento depende muito dos tamanhos das matrizes (n) e do cache da CPU. Portanto, se houver mais interesse, refiz a pergunta:

Você poderia fornecer uma visão sólida dos detalhes que levam aos diferentes comportamentos de cache, conforme ilustrado pelas cinco regiões no gráfico a seguir?

Também pode ser interessante apontar as diferenças entre arquiteturas de CPU / cache, fornecendo um gráfico semelhante para essas CPUs.

PPS: Aqui está o código completo. Ele usa o TBB Tick_Count para um tempo de resolução mais alto, que pode ser desativado por não definir a 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;
    }
}

(Ele mostra FLOP / s para diferentes valores de n.)

Após uma análise mais aprofundada, acredito que isso seja (pelo menos parcialmente) causado pelo alinhamento de dados dos quatro ponteiros. Isso causará algum nível de conflitos de banco / via de cache.

Se eu adivinhei corretamente como você está alocando suas matrizes, é provável que elas estejam alinhadas à linha da página .

Isso significa que todos os seus acessos em cada loop caem no mesmo caminho de cache. No entanto, os processadores Intel têm associatividade de cache L1 de 8 vias por um tempo. Mas, na realidade, o desempenho não é completamente uniforme. O acesso a 4 vias ainda é mais lento do que 2 vias.

EDIT: De fato, parece que você está alocando todas as matrizes separadamente. Geralmente, quando solicitações de grandes alocações são solicitadas, o alocador solicita novas páginas do sistema operacional. Portanto, há uma grande chance de que grandes alocações apareçam no mesmo deslocamento de um limite de página.

Aqui está o código de teste:

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 referência:

EDIT: Resultados em uma máquina de arquitetura 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

Observações:

• 6,206 segundos com um loop e 2,116 segundos com dois loops. Isso reproduz exatamente os resultados do OP.

• Nos dois primeiros testes, as matrizes são alocadas separadamente. Você notará que todos eles têm o mesmo alinhamento em relação à página.

• Nos dois segundos testes, as matrizes são agrupadas para quebrar esse alinhamento. Aqui você notará que os dois loops são mais rápidos. Além disso, o segundo loop (duplo) agora é o mais lento, como você normalmente esperaria.

Como o @Stephen Cannon aponta nos comentários, é muito provável que esse alinhamento cause aliases falsos nas unidades de carregamento / armazenamento ou no cache. Pesquisei no Google e descobri que a Intel realmente tem um contador de hardware para barragens de alias de endereço parcial :

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

5 Regiões - Explicações

Região 1:

Este é fácil. O conjunto de dados é tão pequeno que o desempenho é dominado por sobrecarga, como loop e ramificação.

Região 2:

Aqui, à medida que os tamanhos dos dados aumentam, a quantidade de sobrecarga relativa diminui e o desempenho "satura". Aqui, dois loops são mais lentos porque possuem o dobro de loop e sobrecarga ramificada.

Não sei exatamente o que está acontecendo aqui ... O alinhamento ainda pode ter efeito, já que Agner Fog menciona conflitos bancários em cache . (Esse link é sobre Sandy Bridge, mas a ideia ainda deve ser aplicável ao Core 2.)

Região 3:

Nesse ponto, os dados não se encaixam mais no cache L1. Portanto, o desempenho é limitado pela largura de banda do cache L1 <-> L2.

Região 4:

A queda de desempenho no loop único é o que estamos observando. E, como mencionado, isso ocorre devido ao alinhamento que (provavelmente) causa paradas de aliasing falsas nas unidades de carregamento / armazenamento do processador.

No entanto, para que o falso alias ocorra, deve haver um passo suficientemente grande entre os conjuntos de dados. É por isso que você não vê isso na região 3.

Região 5:

Neste ponto, nada se encaixa no cache. Então você está limitado pela largura de banda da memória.

OK, a resposta certa definitivamente tem a ver com o cache da CPU. Mas usar o argumento de cache pode ser bastante difícil, especialmente sem dados.

Há muitas respostas que levaram a muita discussão, mas vamos ser sinceros: os problemas de cache podem ser muito complexos e não são unidimensionais. Como eles dependem muito do tamanho dos dados, minha pergunta foi injusta: acabou sendo um ponto muito interessante no gráfico de cache.

@ A resposta de Mysticial convenceu muitas pessoas (inclusive eu), provavelmente porque era a única que parecia confiar nos fatos, mas era apenas um "ponto de dados" da verdade.

É por isso que eu combinei o teste dele (usando uma alocação contínua versus separada) e os conselhos do @James 'Answer.

Os gráficos abaixo mostram que a maioria das respostas e principalmente a maioria dos comentários para as perguntas e respostas podem ser consideradas completamente erradas ou verdadeiras, dependendo do cenário exato e dos parâmetros utilizados.

Observe que minha pergunta inicial era n = 100.000 . Este ponto (por acidente) exibe um comportamento especial:

1. Possui a maior discrepância entre a versão de um e dois circuitos (quase um fator de três)

2. É o único ponto em que um loop (ou seja, com alocação contínua) supera a versão de dois loop. (Isso tornou possível a resposta de Mysticial.)

O resultado usando dados inicializados:

O resultado usando dados não inicializados (é o que Mysticial testou):

E isso é difícil de explicar: Dados inicializados, que são alocados uma vez e reutilizados para cada caso de teste a seguir de tamanho diferente de vetor:

Proposta

Todas as questões relacionadas ao desempenho de baixo nível no Stack Overflow devem ser necessárias para fornecer informações sobre o MFLOPS para toda a gama de tamanhos de dados relevantes do cache! É uma perda de tempo de todos pensar em respostas e discuti-las especialmente com outras pessoas sem essas informações.

O segundo loop envolve muito menos atividade de cache, por isso é mais fácil para o processador acompanhar as demandas de memória.

Imagine que você está trabalhando em uma máquina na qual nhavia apenas o valor certo para que fosse possível armazenar duas de suas matrizes na memória de uma só vez, mas a memória total disponível, via cache de disco, ainda era suficiente para armazenar todas as quatro.

Assumindo uma política simples de armazenamento em cache 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];
}

causaria primeiro ae bseria carregado na RAM e depois trabalhado inteiramente na RAM. Quando o segundo loop iniciar, ced , então, ser carregado a partir do disco para a memória RAM e operado.

o outro loop

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

pagina duas matrizes e pagina nas outras duas sempre em volta do loop . Obviamente, isso seria muito mais lento.

Você provavelmente não está vendo o cache de disco em seus testes, mas provavelmente está vendo os efeitos colaterais de alguma outra forma de cache.

Parece haver um pouco de confusão / mal-entendido aqui, então tentarei elaborar um pouco usando um exemplo.

Diga n = 2e estamos trabalhando com bytes. No meu cenário, temos apenas 4 bytes de RAM e o restante da memória é significativamente mais lento (digamos, acesso 100 vezes mais longo).

Supondo uma política de armazenamento em cache bastante estúpida, se o byte não estiver no cache, coloque-o lá e obtenha também o seguinte byte enquanto estivermos nele, você terá um cenário parecido com o seguinte:

• Com

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

• de cache a[0]e a[1], em seguida, b[0]e b[1]e conjunto a[0] = a[0] + b[0]no cache - existem agora quatro bytes de cache, a[0], a[1]e b[0], b[1]. Custo = 100 + 100.

• definido a[1] = a[1] + b[1]no cache. Custo = 1 + 1.
• Repita para ce d.

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

• Com

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

• de cache a[0]e a[1], em seguida, b[0]e b[1]e conjunto a[0] = a[0] + b[0]no cache - existem agora quatro bytes de cache, a[0], a[1]e b[0], b[1]. Custo = 100 + 100.

• ejeção a[0], a[1], b[0], b[1]do cache eo cache c[0]e c[1], em seguida, d[0]e d[1]e conjuntoc[0] = c[0] + d[0] em cache. Custo = 100 + 100.
• Eu suspeito que você está começando a ver para onde estou indo.
• Custo total = (100 + 100 + 100 + 100) * 2 = 800

Este é um cenário clássico de thrash de cache.

Não é por causa de um código diferente, mas por causa do armazenamento em cache: a RAM é mais lenta do que a CPU registra e há uma memória cache dentro da CPU para evitar gravar a RAM toda vez que uma variável está sendo alterada. Mas o cache não é grande como a RAM, portanto, mapeia apenas uma fração dele.

O primeiro código modifica os endereços de memória distantes, alternando-os a cada loop, exigindo continuamente a invalidação do cache.

O segundo código não se alterna: apenas flui nos endereços adjacentes duas vezes. Isso faz com que todo o trabalho seja concluído no cache, invalidando-o somente após o início do segundo loop.

Não consigo replicar os resultados discutidos aqui.

Não sei se o código de referência ruim é o culpado, ou o quê, mas os dois métodos estão dentro de 10% um do outro na minha máquina usando o código a seguir, e um loop geralmente é apenas um pouco mais rápido que dois - como você Espero.

Os tamanhos das matrizes variaram de 2 ^ 16 a 2 ^ 24, usando oito loops. Tomei o cuidado de inicializar as matrizes de origem para que a +=atribuição não pedisse à FPU para adicionar lixo de memória interpretado como duplo.

Eu brinquei com vários esquemas, tais como colocar a atribuição de b[j], d[j]para InitToZero[j]dentro dos loops, e também com o uso += b[j] = 1e+= d[j] = 1 , e eu tenho resultados bastante consistentes.

Como era de se esperar, a inicialização be do uso do loop InitToZero[j]deram à abordagem combinada uma vantagem, pois eles eram feitos lado a lado antes das atribuições aec , mas ainda dentro de 10%. Vai saber.

O hardware é o Dell XPS 8500 com a geração 3 Core i7 3,4 GHz e 8 GB de memória. Para 2 ^ 16 a 2 ^ 24, usando oito loops, o tempo acumulado foi de 44.987 e 40.965, respectivamente. Visual C ++ 2010, totalmente otimizado.

PS: Alterei os loops para contar até zero e o método combinado foi marginalmente mais rápido. Coçando a cabeça. Observe o novo dimensionamento da matriz e as contagens de loop.

// 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;
}

Não sei por que foi decidido que MFLOPS era uma métrica relevante. Embora a ideia fosse focar nos acessos à memória, tentei minimizar a quantidade de tempo de computação do ponto flutuante. Eu saí no +=, mas não sei por que.

Uma atribuição direta sem cálculo seria um teste mais limpo do tempo de acesso à memória e criaria um teste uniforme, independentemente da contagem de loop. Talvez eu tenha perdido algo na conversa, mas vale a pena pensar duas vezes. Se o sinal de mais for deixado de fora da atribuição, o tempo acumulado é quase idêntico em 31 segundos cada.

É porque a CPU não possui tantas falhas de cache (onde é necessário aguardar os dados da matriz virem dos chips de RAM). Seria interessante você ajustar o tamanho das matrizes continuamente para exceder os tamanhos do cache de nível 1 (L1) e, em seguida, o cache de nível 2 (L2) da sua CPU e plotar o tempo necessário para o seu código para executar de acordo com o tamanho das matrizes. O gráfico não deve ser uma linha reta como você esperaria.

O primeiro loop alterna a gravação em cada variável. O segundo e o terceiro fazem apenas pequenos saltos do tamanho do elemento.

Tente escrever duas linhas paralelas de 20 cruzamentos com uma caneta e papel separados por 20 cm. Tente terminar uma vez e depois a outra linha e tente outra vez escrevendo uma cruz em cada linha alternadamente.

A questão original

Por que um loop é muito mais lento que dois loops?

Conclusão:

Caso 1 é um problema clássico de interpolação que é ineficiente. Eu também acho que esse foi um dos principais motivos pelos quais muitas arquiteturas e desenvolvedores de máquinas acabaram construindo e projetando sistemas com vários núcleos, com a capacidade de executar aplicativos multithread e programação paralela.

Analisando esse tipo de abordagem sem envolver como o Hardware, o SO e o Compilador (s) trabalham juntos para fazer alocações de heap que envolvem o trabalho com RAM, Cache, Arquivos de Página, etc .; a matemática que está na base desses algoritmos nos mostra qual desses dois é a melhor solução.

Podemos usar uma analogia de um Bossser Summationque representará um For Loopque deve viajar entre trabalhadores Ae B.

Podemos ver facilmente que o Caso 2 é pelo menos metade da velocidade, se não um pouco mais que o Caso 1, devido à diferença na distância necessária para viajar e ao tempo gasto entre os trabalhadores. Essa matemática está alinhada quase virtualmente e perfeitamente com o BenchMark Times e com o número de diferenças nas instruções de montagem.

Agora vou começar a explicar como tudo isso funciona abaixo.

Avaliando o problema

O código do OP:

const int n=100000;

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

E

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

A consideração

Considerando a pergunta original do OP sobre as 2 variantes dos loops for e sua pergunta alterada em relação ao comportamento dos caches, juntamente com muitas das outras excelentes respostas e comentários úteis; Gostaria de tentar fazer algo diferente aqui, adotando uma abordagem diferente sobre essa situação e esse problema.

A abordagem

Considerando os dois loops e toda a discussão sobre cache e arquivamento de páginas, gostaria de adotar outra abordagem para analisar isso de uma perspectiva diferente. Um que não envolva os arquivos de cache e de página nem as execuções para alocar memória, de fato, essa abordagem nem sequer diz respeito ao hardware ou software real.

A perspectiva

Depois de analisar o código por um tempo, ficou bastante claro qual é o problema e o que está gerando. Vamos dividir isso em um problema algorítmico e analisá-lo da perspectiva de usar notações matemáticas e aplicar uma analogia aos problemas matemáticos e aos algoritmos.

O que sabemos

Sabemos que esse loop será executado 100.000 vezes. Sabemos também que a1, b1, c1ed1 são ponteiros em uma arquitetura de 64 bits. No C ++ em uma máquina de 32 bits, todos os ponteiros têm 4 bytes e em uma máquina de 64 bits, têm 8 bytes de tamanho, pois os ponteiros têm um comprimento fixo.

Sabemos que temos 32 bytes para alocar nos dois casos. A única diferença é que estamos alocando 32 bytes ou 2 conjuntos de 2-8 bytes em cada iteração, em que no segundo caso estamos alocando 16 bytes para cada iteração para os dois loops independentes.

Ambos os loops ainda são iguais a 32 bytes no total de alocações. Com essas informações, vamos agora em frente e mostrar a matemática geral, algoritmos e analogia desses conceitos.

Sabemos o número de vezes que o mesmo conjunto ou grupo de operações que terá que ser executado nos dois casos. Nós sabemos a quantidade de memória que precisa ser alocada nos dois casos. Podemos avaliar que a carga de trabalho geral das alocações entre os dois casos será aproximadamente a mesma.

O que não sabemos

Não sabemos quanto tempo levará para cada caso, a menos que definamos um contador e executemos um teste de benchmark. No entanto, as referências já foram incluídas na pergunta original e também em algumas respostas e comentários; e podemos ver uma diferença significativa entre os dois, e esse é todo o raciocínio desta proposta para esse problema.

Vamos investigar

Já é aparente que muitos já fizeram isso examinando as alocações de heap, testes de benchmark, analisando RAM, cache e arquivos de página. Analisando pontos de dados específicos e índices de iteração específicos também foram incluídos e as várias conversas sobre esse problema específico fazem com que muitas pessoas comecem a questionar outras coisas relacionadas a ele. Como começamos a analisar esse problema usando algoritmos matemáticos e aplicando uma analogia a ele? Começamos fazendo algumas afirmações! Então construímos nosso algoritmo a partir daí.

Nossas afirmações:

• Vamos deixar nosso loop e suas iterações serem uma soma que começa em 1 e termina em 100000, em vez de começar com 0, como nos loops, pois não precisamos nos preocupar com o esquema de indexação 0 do endereçamento de memória, pois estamos apenas interessados ​​em o próprio algoritmo.
• Nos dois casos, temos 4 funções para trabalhar e 2 chamadas de função, com 2 operações sendo executadas em cada chamada de função. Vamos configurá-los como funções e chamadas a funções como o seguinte: F1(), F2(), f(a), f(b), f(c)e f(d).

Os algoritmos:

1º Caso: - Apenas um somatório, mas duas chamadas de função independentes.

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

2º Caso: - Dois somatórios, mas cada um tem sua própria chamada de função.

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); }

Se você notou, F2()existe apenas Sumde Case1onde F1()está contido em Sumde Case1e em ambos Sum1e Sum2de Case2. Isso ficará evidente mais tarde, quando começarmos a concluir que há uma otimização que está acontecendo dentro do segundo algoritmo.

As iterações no primeiro caso Sumchamam f(a)que serão adicionadas a si mesmas f(b)e, em seguida, chamam f(c)que farão o mesmo, mas serão adicionadas f(d)a si mesmas para cada 100000iteração. No segundo caso, temos Sum1e Sum2que ambos agem da mesma forma como se fossem a mesma função sendo chamada duas vezes seguidas.

Nesse caso, podemos tratar Sum1e Sum2simplesmente como antigos, Sumonde Sum, neste caso, se parece com isso: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }e agora isso parece uma otimização, onde podemos apenas considerar que é a mesma função.

Resumo com Analogia

Com o que vimos no segundo caso, quase parece que há otimização, já que ambos os loops têm a mesma assinatura exata, mas esse não é o problema real. A questão não é o trabalho que está sendo feito por f(a), f(b), f(c), e f(d). Nos dois casos e na comparação entre os dois, é a diferença na distância que o somatório deve percorrer em cada caso que fornece a diferença no tempo de execução.

Pense no For Loopscomo sendo o Summationsque faz as iterações como sendo um Bossque está dando ordens para duas pessoas Ae Be que seus empregos são a carne Ce D, respectivamente, e para pegar algum pacote a partir deles e devolvê-lo. Nessa analogia, os loops for ou as iterações de somatória e as verificações de condição em si não representam realmente o Boss. O que realmente representa Bossnão é diretamente dos algoritmos matemáticos reais, mas do conceito real de Scopee Code Blockdentro de uma rotina ou sub-rotina, método, função, unidade de tradução etc. O primeiro algoritmo tem um escopo, enquanto o segundo algoritmo possui dois escopos consecutivos.

No primeiro caso de cada recibo de chamada, ele Bossacessa Ae fornece o pedido e Asai para buscar o B'spacote, depois Bossacessa Ce fornece os pedidos para fazer o mesmo e receber o pacote Dem cada iteração.

No segundo caso, ele Bosstrabalha diretamente Apara buscar o B'spacote até que todos os pacotes sejam recebidos. Em seguida, ele Bosstrabalha Cpara fazer o mesmo para obter todos os D'spacotes.

Como estamos trabalhando com um ponteiro de 8 bytes e lidando com a alocação de heap, vamos considerar o seguinte problema. Digamos que Bossseja a 100 pés Ae a A500 pés C. Não precisamos nos preocupar com o quão longe isso Bossestá inicialmente Cdevido à ordem das execuções. Nos dois casos, o Bossprimeiro viaja do Aprimeiro para o depois B. Essa analogia não quer dizer que essa distância seja exata; é apenas um cenário de caso de teste útil para mostrar o funcionamento dos algoritmos.

Em muitos casos, ao fazer alocações de heap e trabalhar com os arquivos de cache e de página, essas distâncias entre os locais de endereço podem não variar muito ou podem variar significativamente, dependendo da natureza dos tipos de dados e dos tamanhos da matriz.

Os casos de teste:

Primeiro Caso: Na primeira iteração, o usuárioBossdeve inicialmente percorrer 100 pés para dar o escorregão do pedidoAeAdisparar e faz o que quer, mas depoisBossprecisa percorrer 500 pésCpara dar o escorregão do pedido. Em seguida, na próxima iteração e em todas as outras iterações após a etapa,Bossé necessário ir e voltar 500 pés entre as duas.

Segundo caso: ABosstem que viajar 100 pés na primeira iteração paraA, mas depois disso, ele já está lá e apenas espera paraAvoltar até que todos os deslizamentos são preenchidos. Em seguida, eleBossprecisa percorrer 500 pés na primeira iteração paraCporqueCfica a 500 pésA. Como issoBoss( Summation, For Loop )está sendo chamado logo após o trabalho comAele, ele apenas espera lá, como fezAaté que todos osC'spedidos sejam concluídos.

A diferença nas distâncias percorridas

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;    

A comparação de valores arbitrários

Podemos ver facilmente que 600 é muito menos que 10 milhões. Agora, isso não é exato, porque não sabemos a diferença real na distância entre qual endereço da RAM ou de qual cache ou arquivo de página cada chamada em cada iteração será devida a muitas outras variáveis ​​invisíveis. Esta é apenas uma avaliação da situação a ser observada e analisada do pior cenário possível.

A partir desses números, quase pareceria que o Algoritmo Um deveria ser 99%mais lento que o Algoritmo Dois; no entanto, esta é apenas a Boss'sparte ou a responsabilidade dos algoritmos e não conta para os trabalhadores reais A, B, C, e De o que tem que fazer em cada iteração do loop. Portanto, o trabalho do chefe é responsável por apenas 15 a 40% do total do trabalho que está sendo realizado. A maior parte do trabalho realizado através dos trabalhadores tem um impacto um pouco maior no sentido de manter a proporção das diferenças da taxa de velocidade em cerca de 50-70%

A observação: - As diferenças entre os dois algoritmos

Nesta situação, é a estrutura do processo do trabalho que está sendo realizado. Isso mostra que o Caso 2 é mais eficiente, tanto pela otimização parcial de uma declaração de função e definição semelhantes, onde são apenas as variáveis ​​que diferem por nome quanto pela distância percorrida.

Também vemos que a distância total percorrida no Caso 1 é muito maior do que no Caso 2 e podemos considerar essa distância percorrida como nosso Fator de Tempo entre os dois algoritmos. O caso 1 tem muito mais trabalho a fazer do que o caso 2 .

Isso é observável a partir das evidências das ASMinstruções mostradas nos dois casos. Junto com o que já foi declarado sobre esses casos, isso não explica o fato de que, no Caso 1, o chefe terá que esperar pelos dois Ae Cvoltar antes que possa voltar a Acada iteração. Também não leva em conta o fato de que, se Aou Bestiver demorando muito tempo, os dois Bosstrabalhadores ficarão ociosos aguardando a execução.

No caso 2, o único que está ocioso é o Bossaté que o trabalhador volte. Portanto, mesmo isso afeta o algoritmo.

Pergunta (s) alterada (s) do PO

EDIT: A questão acabou por não ter relevância, pois o comportamento depende muito dos tamanhos das matrizes (n) e do cache da CPU. Portanto, se houver mais interesse, refiz a pergunta:

Você poderia fornecer uma visão sólida dos detalhes que levam aos diferentes comportamentos de cache, conforme ilustrado pelas cinco regiões no gráfico a seguir?

Também pode ser interessante apontar as diferenças entre arquiteturas de CPU / cache, fornecendo um gráfico semelhante para essas CPUs.

Sobre estas perguntas

Como demonstrei sem dúvida, há um problema subjacente antes mesmo de o hardware e o software serem envolvidos.

Agora, quanto ao gerenciamento de memória e cache, juntamente com os arquivos de paginação, etc., que trabalham juntos em um conjunto integrado de sistemas entre os seguintes:

• The Architecture {Hardware, Firmware, alguns Drivers Incorporados, Kernels e Conjuntos de Instruções ASM}.
• The OS{Sistemas de gerenciamento de arquivos e memória, drivers e registro}.
• The Compiler {Unidades de tradução e otimizações do código fonte}.
• E até o Source Codepróprio com seu conjunto de algoritmos distintos.

Já podemos ver que há um gargalo que está acontecendo dentro do primeiro algoritmo antes mesmo de aplicá-la a qualquer máquina com qualquer arbitrária Architecture, OSe, Programmable Languageem comparação com o segundo algoritmo. Já existia um problema antes de envolver as intrínsecas de um computador moderno.

Os resultados finais

Contudo; não quer dizer que essas novas questões não sejam importantes porque são elas mesmas e, afinal, desempenham um papel. Eles impactam os procedimentos e o desempenho geral, e isso é evidente nos vários gráficos e avaliações de muitos que deram suas respostas e / ou comentários.

Se você prestasse atenção à analogia dos Bosse dos dois trabalhadores Ae Bque tiveram que ir e recuperar pacotes de C& Drespectivamente e considerando as notações matemáticas dos dois algoritmos em questão; você pode ver sem o envolvimento do hardware e software do computador Case 2é aproximadamente 60%mais rápido que Case 1.

Quando você olha para os gráficos e tabelas depois que esses algoritmos foram aplicados a algum código-fonte, compilado, otimizado e executado através do sistema operacional para executar suas operações em uma determinada peça de hardware, você pode ver um pouco mais de degradação entre as diferenças nesses algoritmos.

Se o Dataaparelho for razoavelmente pequeno, pode não parecer uma diferença tão ruim a princípio. No entanto, como Case 1é mais 60 - 70%lento do Case 2que podemos observar o crescimento dessa função em termos das diferenças nas execuções de tempo:

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)

Essa aproximação é a diferença média entre esses dois loops, tanto algoritmicamente quanto nas operações da máquina, envolvendo otimizações de software e instruções da máquina.

Quando o conjunto de dados cresce linearmente, o mesmo ocorre com a diferença de tempo entre os dois. O algoritmo 1 tem mais buscas do que o algoritmo 2, o que é evidente quando ele Bossprecisa percorrer a distância máxima entre Ae Cpara cada iteração após a primeira iteração, enquanto o algoritmo 2 Bossprecisa percorrer Auma vez e depois de terminar, Aele precisa percorrer uma distância máxima apenas uma vez quando passar de Apara C.

Tentar Bossconcentrar-se em fazer duas coisas semelhantes ao mesmo tempo e manipulá-las para frente e para trás, em vez de focar em tarefas consecutivas semelhantes, o deixará bastante irritado no final do dia, já que ele teve que viajar e trabalhar duas vezes mais. Portanto, não perca o escopo da situação deixando seu chefe entrar em um gargalo interpolado porque a esposa e os filhos do chefe não o apreciariam.

Alteração: Princípios de Design de Engenharia de Software

- A diferença entre Local Stacke Heap Allocatedcálculos na iterativa para loops e a diferença entre seus usos, eficiências e eficácia -

O algoritmo matemático que propus acima se aplica principalmente a loops que executam operações em dados alocados no heap.

• Operações consecutivas de pilha:
  • Se os loops estiverem executando operações nos dados localmente em um único bloco de código ou escopo que esteja dentro do quadro da pilha, ele ainda será aplicado, mas os locais da memória estarão muito mais próximos onde normalmente são seqüenciais e a diferença na distância percorrida ou no tempo de execução é quase insignificante. Como não há alocações sendo feitas dentro do heap, a memória não é dispersa e a memória não está sendo buscada através do ram. A memória é tipicamente seqüencial e relativa ao quadro da pilha e ao ponteiro da pilha.
  • Quando operações consecutivas estão sendo realizadas na pilha, um processador moderno armazenará em cache valores e endereços repetitivos, mantendo esses valores nos registros de cache local. O tempo das operações ou instruções aqui é da ordem de nanossegundos.
• Operações Alocadas de Pilha Consecutiva:
  • Quando você começa a aplicar alocações de heap e o processador precisa buscar os endereços de memória em chamadas consecutivas, dependendo da arquitetura da CPU, do controlador de barramento e dos módulos Ram, o tempo de operação ou execução pode ser da ordem de micro a milissegundos. Em comparação com as operações de pilha em cache, elas são bastante lentas.
  • A CPU precisará buscar o endereço de memória do Ram e, normalmente, qualquer coisa no barramento do sistema é lenta em comparação com os caminhos de dados internos ou com os barramentos de dados da própria CPU.

Portanto, quando você estiver trabalhando com dados que precisam estar no heap e percorrê-los em loops, é mais eficiente manter cada conjunto de dados e seus algoritmos correspondentes em seu próprio loop único. Você obterá otimizações melhores em comparação à tentativa de fatorar loops consecutivos colocando várias operações de conjuntos de dados diferentes que estão no heap em um único loop.

Não há problema em fazer isso com os dados que estão na pilha, pois eles são frequentemente armazenados em cache, mas não para os dados que precisam ter seu endereço de memória consultado a cada iteração.

É aqui que entra em cena a engenharia de software e o design da arquitetura de software. É a capacidade de saber como organizar seus dados, saber quando armazená-los em cache, saber quando alocá-los na pilha, saber como projetar e implementar seus algoritmos e saber quando e onde chamá-los.

Você pode ter o mesmo algoritmo que pertence ao mesmo conjunto de dados, mas pode desejar um design de implementação para sua variante de pilha e outro para sua variante alocada ao heap apenas por causa do problema acima, visto pela O(n)complexidade do algoritmo ao trabalhar com a pilha.

Pelo que notei ao longo dos anos, muitas pessoas não levam esse fato em consideração. Eles tenderão a projetar um algoritmo que funcione em um conjunto de dados específico e o usarão independentemente do conjunto de dados armazenado em cache localmente na pilha ou se foi alocado no heap.

Se você deseja uma otimização verdadeira, sim, pode parecer uma duplicação de código, mas, para generalizar, seria mais eficiente ter duas variantes do mesmo algoritmo. Um para operações de pilha e outro para operações de heap que são executadas em loops iterativos!

Aqui está um pseudo exemplo: duas estruturas simples, um 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.

Isso é o que eu estava me referindo por ter implementações separadas para variantes de pilha versus variantes de heap. Os algoritmos em si não importam muito, são as estruturas de loop que você as utilizará.

Pode ser C ++ antigo e otimizações. No meu computador, obtive quase a mesma velocidade:

Um loop: 1,577 ms

Dois loops: 1,507 ms

Executo o Visual Studio 2015 em um processador E5-1620 de 3,5 GHz com 16 GB de RAM.