for - loop range c++




Por que adições elementares são muito mais rápidas em loops separados do que em um loop combinado? (7)

É porque a CPU não tem tantas falhas de cache (onde tem que esperar que os dados da matriz venham dos chips de RAM). Seria interessante para você ajustar o tamanho das matrizes continuamente para que você exceda os tamanhos do cache de nível 1 (L1) e, em seguida, o cache de nível 2 (L2) de sua CPU e plotar o tempo gasto para seu código para executar contra os tamanhos dos arrays. O gráfico não deve ser uma linha reta como você esperaria.

Suponha que a1 , b1 , c1 e d1 apontem para a memória heap e meu código numérico tenha o seguinte loop principal.

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 loop externo. Para acelerar, mudei 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 processador Intel Core 2 Duo (x64), o primeiro exemplo leva 5,5 segundos e o exemplo de loop duplo leva apenas 1,9 segundo. Minha pergunta é: (Por favor, consulte a minha pergunta reformulada na parte inferior)

PS: Não tenho certeza se isso ajuda:

A desmontagem do 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 bloco a seguir é 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 sendo irrelevante, pois o comportamento depende severamente dos tamanhos das matrizes (n) e do cache da CPU. Então, se houver mais interesse, eu reformulo a pergunta:

Você poderia fornecer uma visão sólida dos detalhes que levam a 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 as arquiteturas de CPU / cache, fornecendo um gráfico semelhante para essas CPUs.

PPS: Aqui está o código completo. Ele usa Tick_Count TBB para maior tempo de resolução, que pode ser desabilitado por não definir a macro TBB_TIMING :

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

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


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

Se eu adivinhar corretamente como você está alocando suas matrizes, elas provavelmente estarão alinhadas à linha da página .

Isso significa que todos os seus acessos em cada loop estarão no mesmo cache. No entanto, os processadores Intel tiveram uma associação de cache L1 de 8 vias por um tempo. Mas, na realidade, o desempenho não é completamente uniforme. Acessar quatro vias ainda é mais lento do que dizer de duas maneiras.

EDIT: De fato, parece que você está alocando todos os arrays separadamente. Geralmente, quando grandes alocações são solicitadas, o alocador solicitará 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 real de arquitetura 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

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, os arrays são alocados separadamente. Você notará que todos eles têm o mesmo alinhamento em relação à página.

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

Como aponta o @Stephen Cannon nos comentários, é muito provável que esse alinhamento cause falsa aliasing nas unidades de carga / armazenamento ou no cache. Eu pesquisei por isso e descobri que a Intel realmente tem um contador de hardware para barracas de aliasing de endereços parciais :

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 looping e ramificação.

Região 2:

Aqui, conforme os tamanhos dos dados aumentam, a quantidade de sobrecarga relativa diminui e o desempenho "satura". Aqui, dois loops são mais lentos porque possuem duas vezes mais voltas e ramificações.

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

Região 3:

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

Região 4:

A queda de desempenho no circuito único é o que estamos observando. E, como mencionado, isso se deve ao alinhamento que (muito provavelmente) causa falsas aliasing stalls nas unidades de carga / armazenamento do processador.

No entanto, para que o aliasing falso ocorra, deve haver um passo grande o suficiente 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.


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

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

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


O primeiro loop alterna a escrita em cada variável. O segundo e o terceiro apenas fazem pequenos saltos de tamanho de elemento.

Tente escrever duas linhas paralelas de 20 cruzes 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.


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

Há muitas respostas que levaram a muita discussão, mas vamos encarar: problemas de cache podem ser muito complexos e não são unidimensionais. Eles dependem muito do tamanho dos dados, então minha pergunta era injusta: acabou se mostrando em um ponto muito interessante no gráfico do cache.

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

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

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

Note que minha pergunta inicial foi em 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 loop (quase um fator de três)

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

O resultado usando dados inicializados:

O resultado usando dados não inicializados (isso é 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 seguinte de tamanho de vetor diferente:

Proposta

Todas as questões relacionadas a desempenho de baixo nível no devem ser obrigadas a fornecer informações MFLOPS para toda a gama de tamanhos de dados relevantes ao cache! É um desperdício de tempo de todos pensarem em respostas e especialmente discuti-las com outras pessoas sem essa informação.


A pergunta original

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

Conclusão:

O caso 1 é um problema clássico de interpolação que é ineficiente. Eu também acho que esta foi uma das principais razões pelas quais muitas arquiteturas de máquinas e desenvolvedores acabaram construindo e projetando sistemas multi-core com a capacidade de fazer aplicações multi-threaded, bem como programação paralela.

Olhando para isto deste tipo de abordagem sem envolver como o Hardware, SO e Compilador (es) trabalham juntos para fazer alocações de pilha que envolvem trabalhar com RAM, Cache, Arquivos de Página, etc .; as matemáticas que estão na base desses algoritmos nos mostram qual dessas duas é a melhor solução. Podemos usar uma analogia onde um Boss ou Summation que represente um For Loop que tenha que viajar entre trabalhadores A e B , podemos facilmente ver que o Caso 2 é pelo menos 1/2 tão rápido se não um pouco mais que o Caso 1 devido a a diferença na distância necessária para viajar e o tempo gasto entre os trabalhadores. Esta matemática se alinha quase virtualmente e perfeitamente tanto com o Bench Mark Times quanto com a quantidade 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 questão emendada em relação ao comportamento dos caches, juntamente com muitas outras excelentes respostas e comentários úteis; Eu gostaria de tentar fazer algo diferente aqui, adotando uma abordagem diferente sobre essa situação e problema.

A abordagem

Considerando os dois loops e toda a discussão sobre o cache e o preenchimento de páginas, eu gostaria de ter uma outra abordagem de olhar para isso de uma perspectiva diferente. Uma que não envolva o cache e os arquivos de paginação nem as execuções para alocar memória, na verdade, essa abordagem nem sequer diz respeito ao hardware ou ao software em si.

A perspectiva

Depois de olhar para o código por algum tempo, ficou claro qual é o problema e o que está gerando. Vamos dividir isso em um problema algorítmico e examiná-lo a partir da perspectiva de usar notações matemáticas, em seguida, aplicar uma analogia aos problemas de matemática, bem como aos algoritmos.

O que sabemos

Sabemos que o loop dele será executado 100.000 vezes.Sabemos também que a1, b1, c1ed1são ponteiros em uma arquitetura de 64 bits. Em C ++ em uma máquina de 32 bits, todos os ponteiros são de 4 bytes e, em uma máquina de 64 bits, eles têm 8 bytes de tamanho, pois os ponteiros são de comprimento fixo. Sabemos que temos 32 bytes nos quais alocar para ambos os casos. A única diferença é que estamos alocando 32 bytes ou 2 conjuntos de 2-8bytes em cada iteração, onde no segundo caso estamos alocando 16 bytes para cada iteração para ambos os loops independentes. Portanto, ambos os loops ainda são iguais a 32 bytes no total de alocações. Com esta informação vamos em frente e mostrar a matemática geral, algoritmo e analogia do mesmo. Sabemos a quantidade de vezes que o mesmo conjunto ou grupo de operações 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 global 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, os pontos de referência já foram incluídos a partir da pergunta original e de algumas das respostas e comentários, e podemos ver uma diferença significativa entre os dois e este é todo o raciocínio desta questão para este problema e para a resposta do mesmo começar com.

Vamos investigar

Já é evidente que muitos já fizeram isso observando as alocações de heap, testes de benchmark, olhando para RAM, Cache e Arquivos de Página. Olhando para pontos de dados específicos e índices de iteração específicos também foi incluído e as várias conversas sobre este problema específico tem muitas pessoas começando a questionar outras coisas relacionadas sobre isso. Então, como começamos a olhar para esse problema usando algoritmos matemáticos e aplicando uma analogia a ele? Nós começamos fazendo algumas afirmações! Então nós construímos nosso algoritmo de lá.

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, uma vez que estamos apenas interessados ​​em o algoritmo em si.
  • Em ambos os casos temos 4 funções para trabalhar e 2 chamadas de função com 2 operações sendo feitas em cada chamada de função. Então, vamos configurá-los como funções e chamadas de função a ser 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: - Duas somas, mas cada uma 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ê percebeu F2()apenas existe em Sumonde ambos Sum1e Sum2somente contém F1(). Isso também será evidente mais tarde, quando começarmos a concluir que há uma espécie de otimização acontecendo a partir do segundo algoritmo.

As iterações através do primeiro caso Sumchamam f(a)que se somarão a si próprio, f(b)então ele chama de f(c)que fará o mesmo, mas adicionará f(d)a si mesmo para cada um 100000 iterations. No segundo caso temos Sum1e Sum2E ambos agem da mesma forma como se fossem a mesma função sendo chamados duas vezes seguidas. Neste caso, podemos tratar Sum1e Sum2como simplesmente antigo, Sumonde Sumneste caso é assim: 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 haver otimização, já que os dois 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)em ambos os casos e a comparação entre os dois é a diferença na distância que o somatório tem que viajar em ambos os casos que lhe dá a diferença de 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. Na analogia aqui, as iterações de loop for ou soma e as verificações de condição em si não representam realmente o Boss. O que realmente representa o Bossaqui não é dos algoritmos matemáticos reais diretamente, 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 possui 1 escopo onde o 2º algoritmo possui 2 escopos consecutivos.

No primeiro caso, em cada chamada, a pessoa Bossvai Ae dá a ordem e Asai para buscar o B'spacote, então o Bossvai para Ce dá as ordens para fazer o mesmo e receber o pacote de Dcada iteração.

No segundo caso, o Bossmétodo funciona diretamente Apara ir buscar o B'spacote até que todos os pacotes sejam recebidos. Em seguida, o Bosstrabalho com Ca 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 esse problema aqui. Vamos dizer que o Bossé de 100 metros Ae que Aé de 500 metros de distância C. Nós não precisamos nos preocupar com o quão longe a Bossinicial é por Ccausa da ordem das execuções. Em ambos os casos, o Bossprimeiro viaja de Aprimeiro e depois para B. Essa analogia não quer dizer que essa distância é exata; é apenas um cenário de caso de teste de uso para mostrar o funcionamento dos algoritmos. Em muitos casos, ao fazer alocações de heap e trabalhar com o cache e os arquivos de paginação, essas distâncias entre locais de endereço podem não variar muito em diferenças ou podem variar muito dependendo da natureza dos tipos de dados e dos tamanhos das matrizes.

Os Casos de Teste:

Primeiro caso: Na primeira iteração doBosstem que ir inicialmente 100 pés para dar o deslize paraAeAapaga-se e faz sua coisa, mas então oBosstem que viajar 500 pés paraCdar-lhe o seu deslizamento ordem. Então, na próxima iteração e em todas as outras iterações, depois deBosster que ir e voltar 500 pés entre os dois.

Segundo caso: The Boss tem que viajar 100 pés na primeira iteraçãoA, mas depois disso ele já está lá e apenas esperaAvoltar até que todos os lapsos sejam preenchidos. Em seguida, eleBosstem que percorrer 500 pés na primeira iteração,CporqueCestá a 150 metros de distância,Ajá que issoBoss( Summation, For Loop )é chamado logo após o trabalhoAe, em seguida, apenas espera como ele fezAaté que todos osC'spedidos sejam feitos.

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 de RAM ou a partir do qual Cache ou Arquivo de Páginas cada chamada em cada iteração será devido a muitas outras variáveis ​​não vistas, mas isso é apenas uma avaliação da situação para estar ciente e tentar olhar para ela do pior cenário possível.

Então, por esses números, quase pareceria que o Algoritmo Um deveria ser 99% mais lento do que o Algoritmo Dois; no entanto, esta é apenas a The 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. Assim, o trabalho dos chefes representa apenas cerca de 15 a 40% do total de trabalho realizado. Assim, a maior parte do trabalho que é feito através dos trabalhadores tem um impacto ligeiramente maior no sentido de manter a proporção das diferenças de taxa de velocidade para cerca de 50-70%

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

Nessa situação, é a estrutura do processo do trabalho que está sendo feito e mostra que o Caso 2 é mais eficiente, tanto da otimização parcial de ter uma declaração e definição de função semelhante, em que apenas as variáveis ​​diferem pelo nome. . E 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 em nosso Fator de Tempo entre os dois algoritmos. O caso 1 tem muito mais trabalho a fazer do que o Caso 2 . Isso também foi visto na evidência doASMque foi mostrado entre os dois casos. Mesmo com o que já foi dito sobre esses casos, isso também não explica o fato de que no Caso 1 o chefe terá que esperar por ambos Ae Cvoltar antes que ele possa voltar para Aa próxima iteração e também não 'conta t para o fato de que se Aou Bestá tomando um tempo extremamente longo, em seguida, tanto o Bosseo outro trabalhador (s) estão também à espera em um ocioso. No Caso 2, o único que está inativo é o Bossaté que o trabalhador retorne. Então, mesmo isso tem um impacto no algoritmo.

Os POs Alterou a (s) Pergunta (s)

EDIT: A questão acabou por ser de pouca relevância, como o comportamento depende severamente dos tamanhos das matrizes (n) e do cache da CPU. Então, se houver mais interesse, eu reformulo a pergunta:

Você poderia fornecer uma visão sólida dos detalhes que levam a 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 as arquiteturas de CPU / cache, fornecendo um gráfico semelhante para essas CPUs.

Sobre estas questões

Como demonstrei sem dúvida, há um problema subjacente mesmo antes de o Hardware e o Software se envolverem. Agora, como para a gestão de memória e cache juntamente com arquivos de páginas, etc, que tudo funciona em conjunto em um conjunto integrado de sistemas entre: The Architecture{hardware, firmware, alguns drivers embutidos, sementes e Instrução ASM Conjuntos}, The OS{sistemas de gerenciamento de arquivos e memória , Drivers e o Registro}, The Compiler{Unidades de Tradução e Otimizações do Código-Fonte}, e até mesmo o Source Codepróprio com seu (s) conjunto (s) 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, OSeProgrammable Languageem comparação com o segundo algoritmo. Então já existia um problema antes de envolver os intrínsecos de um computador moderno.

Os resultados finais

Contudo; isso não quer dizer que essas novas perguntas não tenham importância, porque elas mesmas são e desempenham um papel afinal. Eles afetam os procedimentos e o desempenho geral e isso é evidente com os vários gráficos e avaliações de muitos que deram suas respostas e / ou comentários. Se você prestar atenção à analogia do Bosse os 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 que, mesmo sem o envolvimento do computador Case 2é de aproximadamente 60% mais rápido queCase 1 e quando você olha para os gráficos e gráficos depois que esses algoritmos são aplicados ao código-fonte, compilados, otimizados e executados através do SO para executar operações no hardware, você vê um pouco mais de degradação entre as diferenças nesses algoritmos.

Agora, se o conjunto "Data" for bem pequeno, pode não parecer tão ruim de uma diferença no início, mas como Case 1é mais 60 - 70%lento do Case 2que podemos considerar o crescimento dessa função como sendo 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)

E essa aproximação é a diferença média entre esses dois loops, tanto algoritmicamente quanto operações de máquina envolvendo otimizações de software e instruções de máquina. Então, quando o conjunto de dados cresce linearmente, o mesmo acontece com a diferença de tempo entre os dois. Algoritmo 1 tem mais buscas do que o algoritmo 2, que é evidente quando ele Bossteve que percorrer a distância máxima entre Ae Cpara cada iteração após a primeira iteração, enquanto o Algoritmo 2 Bossteve que viajar Auma vez e depois de terminar Aele teve que viajar uma distância máxima apenas uma vez ao ir de Apara C.

Portanto, tentar Bossconcentrar-se em fazer duas coisas semelhantes ao mesmo tempo e fazer malabarismos com elas, em vez de se concentrar em tarefas consecutivas semelhantes, vai deixá-lo bastante irritado até o final do dia, pois precisou viajar e trabalhar duas vezes mais. Portanto, não perca o escopo da situação deixando que seu chefe entre em um gargalo interpolado porque o cônjuge e os filhos do chefe não o apreciam.


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

Um loop: 1,577 ms

Dois loops: 1.507 ms

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







vectorization