c++ rendimento brayton - Perché le aggiunte elementwise sono molto più veloci in cicli separati rispetto a un ciclo combinato?




5 Answers

Dopo un'ulteriore analisi di ciò, ritengo che questo sia (almeno parzialmente) causato dall'allineamento dei dati dei quattro puntatori. Ciò causerà un certo livello di conflitti banca / via della cache.

Se ho indovinato correttamente su come stai allocando i tuoi array, è probabile che siano allineati alla linea della pagina .

Ciò significa che tutti gli accessi in ogni ciclo ricadranno nello stesso modo di cache. Tuttavia, i processori Intel hanno avuto l'associatività della cache L1 a 8 vie per un po '. Ma in realtà, la performance non è completamente uniforme. L'accesso a 4 vie è ancora più lento di dire 2 vie.

EDIT: Sembra infatti che stiate allocando tutti gli array separatamente. Di solito, quando vengono richieste allocazioni di questo tipo, l'allocatore richiederà nuove pagine dal sistema operativo. Pertanto, esiste un'alta probabilità che le allocazioni di grandi dimensioni vengano visualizzate allo stesso offset da un limite di pagina.

Ecco il codice di prova:

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

Risultati del benchmark:

EDIT: risultati su una macchina di architettura Core 2 attuale :

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

osservazioni:

  • 6,206 secondi con un loop e 2,161 secondi con due loop. Questo riproduce esattamente i risultati dell'OP.

  • Nei primi due test, gli array vengono assegnati separatamente. Noterai che tutti hanno lo stesso allineamento relativo alla pagina.

  • Nei secondi due test, gli array vengono imballati insieme per interrompere quell'allineamento. Qui noterai che entrambi i cicli sono più veloci. Inoltre, il secondo ciclo (doppio) è ora il più lento come normalmente ti aspetteresti.

Come @Stephen Cannon fa notare nei commenti, è molto probabile che questo allineamento causi falsi alias nelle unità di caricamento / archivio o nella cache. Ho cercato su Google per questo e ho scoperto che Intel ha effettivamente un contatore hardware per bancarelle di aliasing parziali degli indirizzi :

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

5 regioni - spiegazioni

Regione 1:

Questo è facile. Il set di dati è così piccolo che le prestazioni sono dominate da overhead come il looping e il branching.

Regione 2:

Qui, all'aumentare delle dimensioni dei dati, la quantità di overhead relativo diminuisce e la performance "si satura". Qui due loop sono più lenti perché ha il doppio del loop e della ramificazione in testa.

Non sono sicuro di cosa stia succedendo qui ... L'allineamento potrebbe ancora avere un effetto mentre Agner Fog accenna ai conflitti bancari nella cache . (Quel collegamento riguarda Sandy Bridge, ma l'idea dovrebbe essere ancora applicabile al Core 2.)

Regione 3:

A questo punto, i dati non si adattano più alla cache L1. Quindi le prestazioni sono limitate dalla larghezza di banda della cache L1 <-> L2.

Regione 4:

Il calo delle prestazioni nel single-loop è ciò che stiamo osservando. E come detto, ciò è dovuto all'allineamento che (molto probabilmente) causa falsi stacks di aliasing nelle unità di carico / archivio del processore.

Tuttavia, affinché si verifichi un falso alias, è necessario che ci sia un passo abbastanza lungo tra i set di dati. Questo è il motivo per cui non lo vedi nella regione 3.

Regione 5:

A questo punto, niente si inserisce nella cache. Quindi sei legato dalla larghezza di banda della memoria.

camera elettrico

Supponiamo che a1 , b1 , c1 e d1 puntino alla memoria heap e il mio codice numerico abbia il seguente ciclo centrale.

const int n = 100000;

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

Questo ciclo viene eseguito 10.000 volte tramite un altro ciclo for esterno. Per accelerarlo, ho cambiato il codice in:

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

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

Compilato su MS Visual C ++ 10.0 con ottimizzazione completa e SSE2 abilitato per 32-bit su Intel Core 2 Duo (x64), il primo esempio impiega 5,5 secondi e l'esempio di doppio ciclo richiede solo 1,9 secondi. La mia domanda è: (Si prega di fare riferimento alla mia domanda riformulata in fondo)

PS: non sono sicuro, se questo aiuta:

Il disassemblaggio del primo loop è essenzialmente simile a questo (questo blocco viene ripetuto circa cinque volte nel programma 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]

Ogni loop dell''esempio double loop produce questo codice (il seguente blocco viene ripetuto circa tre volte):

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 domanda si è rivelata priva di rilevanza, in quanto il comportamento dipende fortemente dalle dimensioni degli array (n) e dalla cache della CPU. Quindi, se c'è ulteriore interesse, riformulo la domanda:

Potresti fornire alcune informazioni dettagliate sui dettagli che portano ai diversi comportamenti della cache, come illustrato dalle cinque regioni nel seguente grafico?

Potrebbe anche essere interessante sottolineare le differenze tra le architetture CPU / cache, fornendo un grafico simile per queste CPU.

PPS: ecco il codice completo. Utilizza TBB Tick_Count per tempi di risoluzione più elevata, che può essere disabilitato non definendo la 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 per diversi valori di n .)




Il secondo ciclo coinvolge molto meno attività di cache, quindi è più facile per il processore tenere il passo con le richieste di memoria.




Non è a causa di un codice diverso, ma a causa del caching: la RAM è più lenta dei registri della CPU e una memoria cache è all'interno della CPU per evitare di scrivere la RAM ogni volta che una variabile sta cambiando. Ma la cache non è grande come la RAM, quindi ne mappa solo una parte.

Il primo codice modifica gli indirizzi distanti della memoria alternandoli ad ogni ciclo, richiedendo così continuamente di invalidare la cache.

Il secondo codice non si alterna: scorre solo sugli indirizzi adiacenti due volte. Questo rende tutto il lavoro da completare nella cache, invalidandolo solo dopo l'avvio del secondo ciclo.




È perché la CPU non ha così tanti errori di cache (dove deve aspettare che i dati dell'array provengano dai chip RAM). Sarebbe interessante per te regolare continuamente la dimensione degli array in modo da superare le dimensioni della cache di livello 1 (L1) e quindi la cache di livello 2 (L2), della tua CPU e tracciare il tempo impiegato per il tuo codice eseguire contro le dimensioni degli array. Il grafico non dovrebbe essere una linea retta come ci si aspetterebbe.




La domanda originale

Perché un loop è molto più lento di due loop?

Valutare il problema

Il codice dell'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];
}

La considerazione

Considerando la domanda originale dell'OP circa le 2 varianti dei cicli for e la sua domanda modificata sul comportamento delle cache insieme a molte altre risposte eccellenti e commenti utili; Mi piacerebbe provare e fare qualcosa di diverso qui adottando un approccio diverso riguardo a questa situazione e problema.

L'approccio

Considerando i due cicli e tutta la discussione sulla cache e sul deposito delle pagine, vorrei prendere un altro approccio per considerare questo da una prospettiva diversa. Uno che non coinvolge i file di cache e di pagina, né le esecuzioni per allocare memoria, in realtà questo approccio non riguarda nemmeno l'hardware o il software.

La prospettiva

Dopo aver osservato il codice per un po 'è diventato del tutto evidente quale sia il problema e cosa lo sta generando. Consente di suddividerlo in un problema algoritmico e di esaminarlo dal punto di vista dell'utilizzo delle notazioni matematiche, quindi applicare un'analogia con i problemi matematici e con gli algoritmi.

Cosa sappiamo

Sappiamo che il suo ciclo verrà eseguito 100.000 volte. Sappiamo anche che a1 , b1 , c1 e d1 sono puntatori su un'architettura a 64 bit. All'interno di C ++ su una macchina a 32 bit tutti i puntatori sono 4 byte e su una macchina a 64 bit hanno dimensioni di 8 byte poiché i puntatori hanno una lunghezza fissa. Sappiamo che abbiamo 32 byte in cui allocare per entrambi i casi. L'unica differenza è che stiamo allocando 32 byte o 2 set di 2-8 byte su ciascuna iterazione, mentre nel 2 ° caso stiamo allocando 16 byte per ogni iterazione per entrambi i loop indipendenti. Quindi entrambi i cicli sono uguali a 32 byte in allocazioni totali. Con queste informazioni andiamo avanti e mostriamo la matematica generale, l'algoritmo e l'analogia di esso. Conosciamo la quantità di volte in cui lo stesso insieme o gruppo di operazioni dovrà essere eseguito in entrambi i casi. Conosciamo la quantità di memoria che deve essere allocata in entrambi i casi. Possiamo valutare che il carico di lavoro complessivo delle allocazioni tra i due casi sarà approssimativamente lo stesso.

Quello che non sappiamo

Non sappiamo quanto tempo ci vorrà per ogni caso, a meno che non venga impostato un contatore ed eseguito un test del benchmark. Tuttavia, i punti di riferimento erano già inclusi nella domanda iniziale e da alcune delle risposte e dei commenti e possiamo notare una differenza significativa tra i due e questo è l'intero ragionamento di questa domanda a questo problema e per la sua risposta a iniziare con.

Investigiamo

È già evidente che molti lo hanno già fatto esaminando le allocazioni dell'heap, i benchmark test, esaminando RAM, Cache e Page Files. Sono stati inclusi anche specifici punti di dati e specifici indici di iterazione e le varie conversazioni su questo problema specifico hanno molte persone che iniziano a mettere in discussione altri aspetti correlati a riguardo. Quindi, come possiamo iniziare a guardare a questo problema utilizzando algoritmi matematici e applicando un'analogia ad esso? Iniziamo facendo un paio di asserzioni! Quindi costruiamo il nostro algoritmo da lì.

Le nostre asserzioni:

  • Lasciamo che il nostro ciclo e le sue iterazioni siano una Summazione che inizia da 1 e finisce a 100000 invece di iniziare con 0 come nei loop perché non dobbiamo preoccuparci dello schema di indicizzazione 0 dell'indirizzamento di memoria poiché siamo solo interessati l'algoritmo stesso.
  • In entrambi i casi abbiamo 4 funzioni con cui lavorare e 2 chiamate di funzione con 2 operazioni eseguite su ciascuna chiamata di funzione. Quindi dovremo impostare questi in su come funzioni e la funzione chiama ad essere F1(), F2(), f(a), f(b), f(c)e f(d).

Gli algoritmi:

Primo caso: - Solo una somma, ma due chiamate di funzione indipendenti.

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

2 ° caso: - Due sommatorie ma ognuna ha una propria chiamata di funzione.

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 hai notato F2()esiste solo in Sumcui entrambi Sum1e Sum2solo contiene F1(). Questo sarà anche evidente più avanti quando inizieremo a concludere che c'è una sorta di ottimizzazione che si verifica dal secondo algoritmo.

Le iterazioni attraverso le prime Sumchiamate di casi f(a)che si aggiungeranno a se stesse f(b)poi chiameranno quelle f(c)che faranno lo stesso ma aggiungeranno f(d)a se stesse per ciascuna 100000 iterations. Nel secondo caso abbiamo Sum1ed Sum2entrambi agiscono come se fossero la stessa funzione chiamata due volte di seguito. In questo caso possiamo trattare Sum1e Sum2come semplicemente semplice Sumdove Sumin questo caso assomiglia a questo: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }e ora questo sembra un'ottimizzazione in cui possiamo semplicemente considerare che sia la stessa funzione.

Riepilogo con analogia

Con quello che abbiamo visto nel secondo caso sembra quasi che ci sia un'ottimizzazione poiché entrambi i loop hanno la stessa firma esatta, ma questo non è il vero problema. Il problema non è il lavoro che è stato fatto da f(a), f(b), f(c)e f(d)in entrambi i casi e il confronto tra i due è la differenza nella distanza che la somma deve percorrere in entrambi i casi che ti dà la differenza di tempo di esecuzione.

Pensate del For Loopscome il Summationsche fa le iterazioni come una Bossche sta dando ordini a due persone Ae Be che i loro posti di lavoro sono a base di carne Ce D, rispettivamente, e per raccogliere qualche pacchetto da loro e restituirlo. Nell'analogia qui le iterazioni di loop o di sommatoria e i controlli di condizione stessi non rappresentano effettivamente il Boss. Ciò che in realtà rappresenta il Bossqui non è direttamente dagli algoritmi matematici effettivi, ma dal concetto reale di Scopee Code Blockall'interno di una routine o sub-routine, metodo, funzione, unità di traduzione, ecc. Il primo algoritmo ha 1 ambito in cui il 2 ° algoritmo ha 2 ambiti consecutivi.

All'interno del primo caso su ogni slittamento della chiamata, il giocatore Bossva Ae dà l'ordine e Ava a prendere il B'spacchetto, quindi Bossva a Cdare gli ordini di fare lo stesso e ricevere il pacchetto da Dogni iterazione.

Nel secondo caso, il Bosslavoro viene eseguito direttamente Aper andare a recuperare il B'spacchetto fino a quando non vengono ricevuti tutti i pacchetti. Quindi Bosslavora Cper fare lo stesso per ottenere tutti i D'spacchetti.

Poiché stiamo lavorando con un puntatore da 8 byte e gestiamo l'allocazione degli heap, consideriamo questo problema qui. Diciamo che Bossè a 100 piedi da Ae che Aè a 500 piedi da C. Non abbiamo bisogno di preoccuparci di quanto Bosssia inizialmente iniziale a Ccausa dell'ordine delle esecuzioni. In entrambi i casi Bossinizialmente viaggia da Aprima a poi a B. Questa analogia non vuol dire che questa distanza sia esatta; è solo uno scenario di test di utilizzo per mostrare il funzionamento degli algoritmi. In molti casi quando si eseguono allocazioni di heap e si lavora con i file di cache e di pagina, queste distanze tra le posizioni degli indirizzi potrebbero non variare molto nelle differenze o possono essere molto significative a seconda della natura dei tipi di dati e delle dimensioni dell'array.

I casi di test:

Primo Caso: Alla prima iterazione, il primoBossdeve andare a 100 piedi per dare l'ordine di scivolareAeAva fuori e fa il suo dovere, ma poiBossdeve percorrere 500 piediCper dargli il suo ordine di scivolare. Quindi nella prossima iterazione e in ogni altra iterazione dopo ilBossdover andare avanti e indietro di 500 piedi tra i due.

Secondo Caso: The Boss deve percorrere 100 piedi alla prima iterazioneA, ma dopo è già lì e aspetta soloAdi tornare indietro fino a quando tutti gli slittamenti sono stati riempiti. QuindiBossbisogna percorrere 500 piedi alla prima iterazioneCperchéCè a 500 piedi daAquandoBoss( Summation, For Loop )viene chiamato subito dopo aver lavoratoAe poi aspetta come ha fattoAfinoaquandononC'ssono stati eseguititutti gliordini.

La differenza nelle distanze percorsa

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;    

Il confronto dei valori arbitrari

Possiamo facilmente vedere che 600 è molto meno di 10 milioni. Ora questo non è esatto, perché non conosciamo la differenza effettiva nella distanza tra quale indirizzo della RAM o da quale cache o file di paging ogni chiamata su ogni iterazione sarà dovuta a molte altre variabili non viste, ma questo è solo una valutazione della situazione da conoscere e provare a guardarla dallo scenario peggiore.

Quindi con questi numeri sembrerebbe quasi che Algorithm One dovrebbe essere il 99% più lento dell'algoritmo Due; Tuttavia, questa è solo la The Boss'sparte o la responsabilità degli algoritmi e non tiene conto per i lavoratori attuali A, B, C, & De che cosa hanno a che fare su ogni iterazione del ciclo. Quindi il lavoro dei padroni rappresenta solo il 15 - 40% del lavoro totale svolto. Quindi la maggior parte del lavoro svolto attraverso i lavoratori ha un impatto leggermente maggiore nel mantenere il rapporto tra le differenze di velocità e il 50-70% circa

L'osservazione: - Le differenze tra i due algoritmi

In questa situazione è la struttura del processo del lavoro in corso e va a dimostrare che Case 2 è più efficiente sia dall'ottimizzazione parziale di avere una dichiarazione e una definizione di una funzione simile dove sono solo le variabili che differiscono per nome . E vediamo anche che la distanza totale percorsa nel caso 1 è molto più lontana di quella del caso 2 e possiamo considerare che questa distanza ha percorso il nostro fattore di tempo tra i due algoritmi. Il caso 1 ha molto più lavoro da fare rispetto al caso 2 . Questo è stato anche visto nelle prove delASMquesto è stato mostrato tra entrambi i casi. Anche con ciò che è già stato detto su questi casi, non tiene conto del fatto che nel caso 1 il boss dovrà aspettare entrambi Ae Ctornare prima che possa tornare di Anuovo alla successiva iterazione e anche non Tengo conto del fatto che se Ao Bsta impiegando un tempo estremamente lungo, sia l'uno Bossche l'altro lavoratore (i) stanno anche aspettando inattivo. Nel caso 2, l'unico inattivo è il Bossfino a quando il lavoratore non ritorna. Quindi anche questo ha un impatto sull'algoritmo.

Conclusione:

Il caso 1 è un classico problema di interpolazione che sembra essere inefficiente. Penso anche che questo sia stato uno dei motivi principali per cui molte architetture e sviluppatori di macchine hanno finito per costruire e progettare sistemi multi-core con la possibilità di fare applicazioni multi-thread e anche di programmazione parallela.

Quindi, anche guardandolo da questo approccio senza nemmeno coinvolgere il modo in cui l'hardware, il sistema operativo e il compilatore lavorano insieme per fare allocazioni di heap che implicano il lavoro con RAM, cache, file di pagina, ecc .; la matematica dietro di esso ci mostra già quale di questi due è la migliore soluzione di utilizzare l'analogia sopra dove la Bosso Summationssono quelli la For Loopscui doveva viaggiare tra lavoratori Ae B. Possiamo facilmente vedere che il caso 2 è almeno 1/2 come veloce se non poco più del caso 1 a causa della differenza tra la distanza percorsa e il tempo impiegato. E questa matematica si allinea quasi virtualmente e perfettamente sia con il Bench Mark Times sia con la quantità di differenza nella quantità di istruzioni di assemblaggio.

Le domande modificate sui PO

EDIT: la domanda non ha avuto rilevanza, in quanto il comportamento dipende in gran parte dalle dimensioni degli array (n) e dalla cache della CPU. Quindi, se c'è ulteriore interesse, riformulo la domanda:

Potresti fornire alcune informazioni dettagliate sui dettagli che portano ai diversi comportamenti della cache, come illustrato dalle cinque regioni nel seguente grafico?

Potrebbe anche essere interessante sottolineare le differenze tra le architetture CPU / cache, fornendo un grafico simile per queste CPU.

Riguardo a queste domande

Come ho dimostrato senza dubbio, c'è un problema di fondo anche prima che l'hardware e il software vengano coinvolti. Ora come per la gestione della memoria e del caching insieme ai file di pagina, ecc. Che funzionano tutti insieme in un insieme integrato di sistemi tra: The ArchitectureHardware, Firmware, alcuni driver incorporati, Kernel e set di istruzioni ASM, The OS{File e sistemi di gestione della memoria , Driver e il Registro}, The Compiler{Unità di traduzione e Ottimizzazioni del codice sorgente}, e anche la Source Codestessa con i suoi set di algoritmi distintivi; Possiamo già vedere che c'è un collo di bottiglia che sta accadendo all'interno del primo algoritmo prima ancora applicare a qualsiasi macchina con un qualsiasi arbitrario Architecture, OSeProgrammable Languagerispetto al secondo algoritmo. Quindi esisteva già un problema prima di coinvolgere l'intrinseco di un computer moderno.

I risultati finali

Però;non è per dire che queste nuove domande non sono importanti perché sono loro stesse e svolgono un ruolo dopo tutto. Hanno un impatto sulle procedure e sulle prestazioni complessive e ciò è evidente con i vari grafici e le valutazioni di molti che hanno fornito le loro risposte e / o commenti (s). Se si presta attenzione all'analogia dei Bossdue e dei lavoratori Ae di Bchi doveva andare a recuperare i pacchi da Ce Drispettivamente e considerando le notazioni matematiche dei due algoritmi in questione si può vedere che senza nemmeno il coinvolgimento del computer Case 2è di circa il 60% più veloce diCase 1 e quando si guardano i grafici e i grafici dopo che questi algoritmi sono stati applicati al codice sorgente, compilati e ottimizzati ed eseguiti attraverso il sistema operativo per eseguire operazioni sull'hardware dato, si vede anche un po 'più di degrado tra le differenze in questi algoritmi.

Ora, se il set di "Dati" è piuttosto piccolo, all'inizio potrebbe non sembrare poi così male di una differenza, ma poiché Case 1è più 60 - 70%lento di quanto Case 2possiamo osservare la crescita di questa funzione in termini di differenze nelle esecuzioni temporali:

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 questa approssimazione è la differenza media tra questi due cicli sia dal punto di vista algoritmico che da quello delle operazioni della macchina che riguardano l'ottimizzazione del software e le istruzioni della macchina. Quindi, quando il set di dati cresce in modo lineare, aumenta anche la differenza di tempo tra i due. Algoritmo 1 ha più recuperi dell'algoritmo 2 che è evidente quando si Bossdoveva percorrere avanti e indietro la distanza massima tra A& Cper ogni iterazione dopo la prima iterazione mentre Algorithm 2 Bossdoveva viaggiare per Auna volta e poi dopo aver finito con Alui doveva viaggiare una distanza massima solo una volta quando si va da Aa C.

Quindi, cercare di Bossconcentrarsi sul fare due cose simili in una volta sola e destreggiarle avanti e indietro invece di concentrarsi su compiti consecutivi simili, lo renderà piuttosto arrabbiato per la fine della giornata perché ha dovuto viaggiare e lavorare il doppio. Perciò non perdere la portata della situazione lasciando che il tuo capo si imbagli in un collo di bottiglia interpolato perché il coniuge ei figli del padrone non lo apprezzerebbero.




Related