Załóżmy a1, b1, c1, i d1punkt do pamięci sterty i kodzie numerycznym ma następującą pętlę rdzenia.

const int n = 100000;

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

Ta pętla jest wykonywana 10 000 razy przez inną zewnętrzną forpętlę. Aby przyspieszyć, zmieniłem kod na:

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

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

Skompilowany na MS Visual C ++ 10.0 z pełną optymalizacją i włączonym SSE2 dla 32-bitów na Intel Core 2 Duo (x64), pierwszy przykład zajmuje 5,5 sekundy, a przykład podwójnej pętli zajmuje tylko 1,9 sekundy. Moje pytanie brzmi: (Proszę odnieść się do mojego przeformułowanego pytania na dole)

PS: Nie jestem pewien, czy to pomoże:

Demontaż pierwszej pętli wygląda następująco (ten blok jest powtarzany około pięć razy w pełnym programie):

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]

Każda pętla w przykładzie z podwójną pętlą wytwarza ten kod (następujący blok jest powtarzany około trzy razy):

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

Pytanie okazało się nie mieć znaczenia, ponieważ zachowanie w znacznym stopniu zależy od rozmiarów tablic (n) i pamięci podręcznej procesora. Więc jeśli jest dalsze zainteresowanie, przeformułowuję pytanie:

Czy mógłbyś zapewnić rzetelny wgląd w szczegóły, które prowadzą do różnych zachowań pamięci podręcznej, co ilustruje pięć regionów na poniższym wykresie?

Interesujące może być również wskazanie różnic między architekturami procesorów / pamięci podręcznej poprzez zapewnienie podobnego wykresu dla tych procesorów.

PPS: Oto pełny kod. Używa TBB Tick_Count dla taktowania o wyższej rozdzielczości, które można wyłączyć, nie definiując TBB_TIMINGmakra:

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

(Pokazuje FLOP / s dla różnych wartości n.)

Po dalszej analizie tego uważam, że jest to (przynajmniej częściowo) spowodowane wyrównaniem danych czterech wskaźników. Spowoduje to pewien poziom konfliktów banku / drogi pamięci podręcznej.

Jeśli poprawnie zgadłem, w jaki sposób alokujesz tablice, prawdopodobnie zostaną one wyrównane do linii strony .

Oznacza to, że wszystkie twoje dostępy w każdej pętli spadną na tę samą pamięć podręczną. Jednak procesory Intel już od pewnego czasu mają 8-kierunkową asocjację pamięci podręcznej L1. Ale w rzeczywistości wydajność nie jest całkowicie jednolita. Dostęp do 4-kierunkowego jest wciąż wolniejszy niż powiedzmy 2-kierunkowy.

EDYCJA: Wygląda na to, że wszystkie tablice przydzielane są osobno. Zwykle, gdy wymagane są tak duże alokacje, alokator poprosi o nowe strony z systemu operacyjnego. Dlatego istnieje duże prawdopodobieństwo, że duże alokacje pojawią się przy tym samym przesunięciu względem granicy strony.

Oto kod testowy:

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

Wyniki testu:

EDYCJA: Wyniki na rzeczywistej maszynie architektury Core 2:

2 x Intel Xeon X5482 Harpertown @ 3,2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Obserwacje:

• 6,206 sekund przy jednej pętli i 2.116 sekund przy dwóch pętlach. Dokładnie odtwarza to wyniki PO.

• W pierwszych dwóch testach tablice są przydzielane osobno. Zauważysz, że wszystkie mają takie same wyrównanie względem strony.

• W dwóch drugich testach tablice są pakowane razem, aby przełamać to wyrównanie. Tutaj zauważysz, że obie pętle są szybsze. Co więcej, druga (podwójna) pętla jest teraz wolniejsza, jak można się normalnie spodziewać.

Jak zauważył @Stephen Cannon w komentarzach, jest bardzo prawdopodobne, że to wyrównanie spowoduje fałszywe aliasing w jednostkach load / store lub cache. Poszukałem tego w Google i zauważyłem, że Intel ma sprzętowy licznik do częściowego blokowania aliasingu adresów :

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

5 regionów - objaśnienia

Region 1:

Ten jest łatwy. Zestaw danych jest tak mały, że wydajność jest zdominowana przez koszty ogólne, takie jak zapętlenie i rozgałęzienie.

Region 2:

Tutaj, wraz ze wzrostem wielkości danych, maleje względny narzut i wydajność „nasyca się”. Tutaj dwie pętle są wolniejsze, ponieważ mają dwa razy więcej pętli i rozgałęzienia nad głową.

Nie jestem pewien, co dokładnie się tutaj dzieje ... Wyrównanie może nadal odgrywać rolę, ponieważ Agner Fog wspomina o konfliktach banków pamięci podręcznej . (Ten link dotyczy Sandy Bridge, ale pomysł powinien nadal dotyczyć rdzenia 2.)

Region 3:

W tym momencie dane nie mieszczą się już w pamięci podręcznej L1. Tak więc wydajność jest ograniczona przez przepustowość pamięci podręcznej L1 <-> L2.

Region 4:

Obserwujemy spadek wydajności w pojedynczej pętli. Jak wspomniano, wynika to z wyrównania, które (najprawdopodobniej) powoduje fałszywe zatrzymanie aliasingu w jednostkach ładowania / przechowywania procesora.

Aby jednak mogło dojść do fałszywego aliasingu, między zestawami danych musi być wystarczająco duży krok. Dlatego nie widzisz tego w regionie 3.

Region 5:

W tym momencie nic nie mieści się w pamięci podręcznej. Więc jesteś związany przepustowością pamięci.

OK, właściwa odpowiedź zdecydowanie musi coś zrobić z pamięcią podręczną procesora. Jednak użycie argumentu pamięci podręcznej może być dość trudne, szczególnie bez danych.

Istnieje wiele odpowiedzi, które doprowadziły do ​​wielu dyskusji, ale spójrzmy prawdzie w oczy: problemy z pamięcią podręczną mogą być bardzo złożone i nie są jednowymiarowe. Zależą one w dużej mierze od wielkości danych, więc moje pytanie było niesprawiedliwe: okazało się, że jest to bardzo interesujący punkt na wykresie pamięci podręcznej.

Odpowiedź @ Mysticial przekonała wiele osób (w tym mnie), prawdopodobnie dlatego, że jako jedyna zdawała się polegać na faktach, ale był to tylko jeden „punkt danych” prawdy.

Właśnie dlatego połączyłem jego test (przy użyciu ciągłego vs osobnego przydziału) i porady @Jamesa.

Poniższe wykresy pokazują, że większość odpowiedzi, a zwłaszcza większość komentarzy do pytania i odpowiedzi, można uznać za całkowicie błędną lub prawdziwą, w zależności od dokładnego scenariusza i zastosowanych parametrów.

Zauważ, że moje początkowe pytanie brzmiało n = 100 000 . Ten punkt (przez przypadek) wykazuje szczególne zachowanie:

1. Ma największą rozbieżność między wersją jedno- i dwupętlową (prawie trzykrotnie)

2. Jest to jedyny punkt, w którym jedna pętla (czyli z ciągłym przydziałem) pokonuje wersję z dwiema pętlami. (To w ogóle umożliwiło odpowiedź Mysticial.)

Wynik przy użyciu zainicjowanych danych:

Wynik przy użyciu niezainicjowanych danych (właśnie to przetestował Mysticial):

Jest to trudne do wytłumaczenia: Zainicjowane dane, które są przydzielane raz i ponownie wykorzystywane dla każdego kolejnego przypadku testowego o innym rozmiarze wektora:

Wniosek

Każde pytanie związane z wydajnością niskiego poziomu w przypadku przepełnienia stosu powinno być wymagane w celu dostarczenia informacji MFLOPS dla całego zakresu odpowiednich wielkości pamięci podręcznej! Strata czasu dla wszystkich na zastanawianie się nad odpowiedziami, a zwłaszcza omawianie ich z innymi osobami bez tych informacji.

Druga pętla wymaga znacznie mniejszej aktywności pamięci podręcznej, więc procesorowi łatwiej jest nadążyć za wymaganiami dotyczącymi pamięci.

Wyobraź sobie, że pracujesz na komputerze, na którym nbyła odpowiednia wartość, aby możliwe było tylko utrzymanie dwóch twoich tablic w pamięci jednocześnie, ale całkowita dostępna pamięć, dzięki buforowaniu dysku, była nadal wystarczająca do przechowywania wszystkich czterech.

Zakładając prostą politykę buforowania LIFO, ten kod:

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

najpierw przyczyny ai bbyć ładowane do pamięci RAM, a następnie poddawać obróbce w całości w pamięci RAM. Gdy druga pętla się uruchomi, ca dnastępnie zostanie załadowana z dysku do pamięci RAM i uruchomiona na.

druga pętla

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

będzie przewijać dwie tablice i przewijać pozostałe dwie za każdym razem wokół pętli . To oczywiście byłoby znacznie wolniejsze.

Prawdopodobnie nie widzisz buforowania dysku w swoich testach, ale prawdopodobnie widzisz skutki uboczne jakiejś innej formy buforowania.

Wydaje się, że jest tu trochę zamieszania / nieporozumień, więc postaram się trochę rozwinąć na przykładzie.

Powiedz n = 2i pracujemy z bajtami. W moim scenariuszu mamy więc tylko 4 bajty pamięci RAM, a reszta naszej pamięci jest znacznie wolniejsza (powiedzmy 100 razy dłuższy dostęp).

Zakładając dość głupie zasady buforowania, jeśli bajt nie znajduje się w pamięci podręcznej, umieść go tam i uzyskaj następujący bajt, gdy będziemy na nim , otrzymasz scenariusz podobny do tego:

• Z

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

• cache, a[0]a a[1]potem b[0]i b[1]i ustawione a[0] = a[0] + b[0]w cache - w pamięci podręcznej są teraz cztery bajty, a[0], a[1]i b[0], b[1]. Koszt = 100 + 100.

• ustawiony a[1] = a[1] + b[1]w pamięci podręcznej. Koszt = 1 + 1.
• Powtórz dla ci d.

• Koszt całkowity = (100 + 100 + 1 + 1) * 2 = 404

• Z

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

• cache, a[0]a a[1]potem b[0]i b[1]i ustawione a[0] = a[0] + b[0]w cache - w pamięci podręcznej są teraz cztery bajty, a[0], a[1]i b[0], b[1]. Koszt = 100 + 100.

• wysuń a[0], a[1], b[0], b[1]z pamięci podręcznej i pamięci podręcznej, c[0]a c[1]następnie d[0]i d[1]i ustaw c[0] = c[0] + d[0]w pamięci podręcznej. Koszt = 100 + 100.
• Podejrzewam, że zaczynasz widzieć, dokąd zmierzam.
• Koszt całkowity = (100 + 100 + 100 + 100) * 2 = 800

Jest to klasyczny scenariusz thrashu z pamięcią podręczną.

Nie wynika to z innego kodu, ale z buforowania: pamięć RAM jest wolniejsza niż rejestry procesora, a pamięć podręczna znajduje się wewnątrz procesora, aby uniknąć zapisywania pamięci RAM za każdym razem, gdy zmienia się zmienna. Ale pamięć podręczna nie jest duża, ponieważ pamięć RAM jest mapowana tylko ułamek tego.

Pierwszy kod modyfikuje odległe adresy pamięci, zmieniając je naprzemiennie w każdej pętli, co wymaga ciągłego unieważniania pamięci podręcznej.

Drugi kod nie zmienia się: po prostu przepływa dwa razy na sąsiednie adresy. To powoduje, że wszystkie zadania zostaną zakończone w pamięci podręcznej, co unieważnia je dopiero po uruchomieniu drugiej pętli.

Nie mogę powtórzyć omawianych tutaj wyników.

Nie wiem, czy winny jest słaby kod testu porównawczego, czy co, ale te dwie metody znajdują się w odległości 10% od siebie na moim komputerze za pomocą następującego kodu, a jedna pętla jest zwykle nieco szybsza niż dwie - tak jak byś oczekiwać.

Rozmiary tablic wahały się od 2 ^ 16 do 2 ^ 24, przy użyciu ośmiu pętli. Ostrożnie zainicjowałem tablice źródłowe, więc +=zadanie nie wymagało od FPU dodania śmieci pamięci interpretowanych jako podwójne.

Grałem około z różnych systemów, takich jak umieszczenie przypisania b[j], d[j]do InitToZero[j]wewnątrz pętli, a także z wykorzystaniem += b[j] = 1a += d[j] = 1i mam dość spójne wyniki.

Jak można się spodziewać, zainicjowanie bi dużycie w pętli InitToZero[j]dało przewagę podejścia łączonego, ponieważ wykonano je pojedynczo przed przypisaniami do ai c, ale nadal w granicach 10%. Domyśl.

Sprzęt to Dell XPS 8500 z generacją 3 Core i7 @ 3,4 GHz i 8 GB pamięci. Dla 2 ^ 16 do 2 ^ 24, przy użyciu ośmiu pętli, łączny czas wynosił odpowiednio 44,987 i 40,965. Visual C ++ 2010, w pełni zoptymalizowany.

PS: Zmieniłem pętle, aby odliczać do zera, a łączona metoda była nieznacznie szybsza. Drapie mnie po głowie. Zwróć uwagę na nowy rozmiar tablicy i liczbę pętli.

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

Nie jestem pewien, dlaczego zdecydowano, że MFLOPS jest odpowiednią miarą. Myślałem, że chodziło o skupienie się na dostępie do pamięci, więc starałem się zminimalizować czas obliczeń zmiennoprzecinkowych. Wyszedłem w +=, ale nie jestem pewien, dlaczego.

Proste przypisanie bez obliczeń byłoby czystszym testem czasu dostępu do pamięci i stworzyłoby test, który byłby jednolity niezależnie od liczby pętli. Może coś mi umknęło w rozmowie, ale warto pomyśleć dwa razy. Jeśli plusa nie ma w przypisaniu, łączny czas jest prawie identyczny po 31 sekund.

Jest tak, ponieważ procesor nie ma tak wielu braków pamięci podręcznej (gdzie musi czekać na dane z macierzy RAM). Interesujące byłoby ciągłe dostosowywanie rozmiaru tablic, aby przekraczać rozmiary pamięci podręcznej poziomu 1 (L1), a następnie pamięci podręcznej poziomu 2 (L2) procesora i wykreślić czas potrzebny na kod wykonać w stosunku do rozmiarów tablic. Wykres nie powinien być linią prostą, jak można się spodziewać.

Pierwsza pętla naprzemiennie zapisuje w każdej zmiennej. Drugi i trzeci wykonują tylko niewielkie skoki wielkości elementu.

Spróbuj napisać dwie równoległe linie po 20 krzyżyków za pomocą pióra i papieru oddzielonych 20 cm. Spróbuj raz ukończyć jedną, a następnie drugą linię i spróbuj innym razem, wpisując krzyżyk w każdej linii na przemian.

Pierwotne pytanie

Dlaczego jedna pętla jest o wiele wolniejsza niż dwie pętle?

Wniosek:

Przypadek 1 to klasyczny problem interpolacji, który okazuje się nieefektywny. Myślę też, że był to jeden z głównych powodów, dla których wiele architektur maszyn i programistów zakończyło budowę i projektowanie systemów wielordzeniowych z możliwością wykonywania aplikacji wielowątkowych, a także programowania równoległego.

Patrząc na to z tego rodzaju podejścia, bez angażowania sposobu, w jaki sprzęt, system operacyjny i kompilator (y) współpracują ze sobą, aby dokonać alokacji sterty obejmującej pracę z pamięcią RAM, pamięcią podręczną, plikami stron itp. matematyka, która leży u podstaw tych algorytmów, pokazuje nam, które z tych dwóch jest lepszym rozwiązaniem.

Możemy użyć analogii Bossbytu, Summationktóry będzie reprezentował coś For Loop, co musi podróżować między pracownikami Ai B.

Łatwo zauważyć, że przypadek 2 jest co najmniej o połowę szybszy, jeśli nie nieco większy niż przypadek 1, ze względu na różnicę w odległości potrzebnej do podróży i czas między pracownikami. Ta matematyka pokrywa się niemal wirtualnie i doskonale zarówno z BenchMark Times, jak i liczbą różnic w instrukcjach montażu.

Teraz zacznę wyjaśniać, jak to wszystko działa poniżej.

Ocena problemu

Kod PO:

const int n=100000;

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

I

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

Rozważanie

Biorąc pod uwagę pierwotne pytanie OP dotyczące 2 wariantów pętli for i jego poprawione pytanie dotyczące zachowania pamięci podręcznej, a także wiele innych doskonałych odpowiedzi i użytecznych komentarzy; Chciałbym spróbować zrobić tutaj coś innego, stosując inne podejście do tej sytuacji i problemu.

Podejście

Biorąc pod uwagę dwie pętle i całą dyskusję na temat pamięci podręcznej i archiwizacji stron, chciałbym przyjąć inne podejście, patrząc na to z innej perspektywy. Ten, który nie wymaga pamięci podręcznej i plików stron ani wykonywania alokacji pamięci, w rzeczywistości takie podejście nawet nie dotyczy rzeczywistego sprzętu ani oprogramowania.

Perspektywa

Po dłuższym spojrzeniu na kod stało się jasne, na czym polega problem i co go generuje. Rozłóżmy to na problem algorytmiczny i spójrzmy na to z perspektywy używania notacji matematycznych, a następnie zastosuj analogię do problemów matematycznych, a także do algorytmów.

Co wiemy

Wiemy, że ta pętla będzie działać 100 000 razy. Wiemy również, że a1, b1, c1i d1są wskaźnikami na architekturze 64-bitowej. W C ++ na maszynie 32-bitowej wszystkie wskaźniki mają 4 bajty, a na maszynie 64-bitowej mają 8 bajtów, ponieważ wskaźniki mają stałą długość.

Wiemy, że w obu przypadkach mamy 32 bajty. Jedyną różnicą jest to, że przydzielamy 32 bajty lub 2 zestawy 2-8 bajtów na każdą iterację, przy czym w drugim przypadku przydzielamy 16 bajtów na każdą iterację dla obu niezależnych pętli.

Obie pętle nadal mają 32 bajty w całkowitej alokacji. Dzięki tym informacjom przejdźmy teraz do przedstawienia ogólnej matematyki, algorytmów i analogii tych pojęć.

Wiemy, ile razy ten sam zestaw lub grupa operacji musi być wykonana w obu przypadkach. Wiemy, ile pamięci trzeba przydzielić w obu przypadkach. Możemy ocenić, że całkowity nakład pracy związany z przydziałami między obydwoma przypadkami będzie w przybliżeniu taki sam.

Czego nie wiemy

Nie wiemy, jak długo potrwa dla każdego przypadku, chyba że ustawimy licznik i przeprowadzimy test porównawczy. Jednak testy porównawcze zostały już uwzględnione w pierwotnym pytaniu, a także w niektórych odpowiedziach i komentarzach; i widzimy znaczącą różnicę między nimi i to jest całe uzasadnienie tej propozycji tego problemu.

Zbadajmy

Widać już, że wielu już to zrobiło, patrząc na przydział sterty, testy porównawcze, pamięć RAM, pamięć podręczną i pliki stronicowania. Uwzględniono także określone punkty danych i konkretne wskaźniki iteracji, a różne rozmowy na temat tego konkretnego problemu powodują, że wiele osób zaczyna kwestionować inne powiązane kwestie. Jak zacząć patrzeć na ten problem, stosując algorytmy matematyczne i stosując do niego analogię? Zaczynamy od kilku twierdzeń! Następnie stamtąd budujemy nasz algorytm.

Nasze twierdzenia:

• Pozwolimy, aby nasza pętla i jej iteracje były sumowaniem, które zaczyna się od 1, a kończy od 100000 zamiast od 0, ponieważ w pętlach, ponieważ nie musimy się martwić schematem indeksowania 0 adresowania pamięci, ponieważ jesteśmy zainteresowani sam algorytm.
• W obu przypadkach mamy 4 funkcje do pracy i 2 wywołania funkcji, przy czym dla każdego wywołania funkcji wykonywane są 2 operacje. Będziemy je skonfigurować jako funkcji i wywołań funkcji jak: F1(), F2(), f(a), f(b), f(c)i f(d).

Algorytmy:

Pierwszy przypadek: - Tylko jedno sumowanie, ale dwa niezależne wywołania funkcji.

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

Drugi przypadek: - Dwa podsumowania, ale każde ma swoje własne wywołanie funkcji.

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

Jeśli zauważyłeś, F2()istnieje tylko Sumz Case1którym F1()zawarta jest w Sumod Case1a zarówno Sum1i Sum2od Case2. Będzie to widoczne później, gdy zaczniemy wnioskować, że w drugim algorytmie odbywa się optymalizacja.

Iteracje przez pierwsze Sumwywołania przypadku f(a), które dodadzą do siebie, f(b)a następnie wywołania f(c), które zrobią to samo, ale dodadzą f(d)do siebie dla każdej 100000iteracji. W drugim przypadku mamy Sum1i Sum2oba działają tak samo, jakby były tą samą funkcją wywoływaną dwa razy z rzędu.

W tym przypadku możemy traktować Sum1i Sum2jak zwykły stary, Sumgdzie Sumw tym przypadku wygląda to tak: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }a teraz wygląda to na optymalizację, w której możemy po prostu uznać, że jest to ta sama funkcja.

Podsumowanie z analogią

Z tym, co widzieliśmy w drugim przypadku, wygląda na to, że istnieje optymalizacja, ponieważ obie pętle mają tę samą dokładną sygnaturę, ale to nie jest prawdziwy problem. Problemem nie jest praca, która jest wykonywana przez f(a), f(b), f(c), i f(d). W obu przypadkach i porównaniu między nimi, różnica w odległości, jaką musi pokonać Podsumowanie w każdym przypadku, daje różnicę w czasie wykonania.

Myśleć o For Loopsjak będąc Summationsktóre wykonuje iteracje jak bycie Boss, który wydawał rozkazy do dwóch osób Ai B, a ich praca jest do mięsa Ci Dodpowiednio i odebrać od nich jakąś paczkę i odesłać go. W tej analogii same pętle for lub iteracje sumowania i kontrole warunków nie reprezentują w rzeczywistości Boss. To, co tak naprawdę reprezentuje, Bossnie pochodzi z rzeczywistych algorytmów matematycznych, ale z rzeczywistej koncepcji Scopei Code Blockprocedury, podprogramu, metody, funkcji, jednostki tłumaczeniowej itp. Pierwszy algorytm ma 1 zakres, w którym drugi algorytm ma 2 kolejne zakresy.

W pierwszym przypadku na każdym odcinku połączenia Bossidzie do Ai wydaje zamówienie, a następnie Apobiera B'spaczkę, a następnie Bossidzie do Ci daje rozkazy, aby zrobić to samo i odebrać paczkę z Dkażdej iteracji.

W drugim przypadku Bossdziała bezpośrednio, Aaby przejść i pobrać B'spakiet, aż wszystkie pakiety zostaną odebrane. Następnie Bossdziała Ctak samo, aby uzyskać wszystkie D'spakiety.

Ponieważ pracujemy z 8-bajtowym wskaźnikiem i zajmujemy się przydzielaniem sterty, rozważmy następujący problem. Powiedzmy, że Bossjest 100 stóp od, Aa to Ajest 500 stóp od C. Nie musimy się martwić o to, jak daleko Bosspoczątkowo jest to z Cpowodu kolejności wykonywania. W obu przypadkach Bosspoczątkowo podróżuje od Apierwszego do następnego B. Ta analogia nie oznacza, że ​​odległość ta jest dokładna; jest to po prostu przydatny scenariusz testowy, który pokazuje działanie algorytmów.

W wielu przypadkach podczas przydzielania sterty i pracy z pamięcią podręczną i plikami stron odległości te między lokalizacjami adresów mogą się nie różnić tak bardzo lub mogą się znacznie różnić w zależności od rodzaju typów danych i rozmiarów tablicy.

Przypadki testowe:

Pierwszy przypadek: przy pierwszej iteracjiBossmusi początkowo przejść 100 stóp, aby przekazać dowód zamówienia,AiAznika, i robi swoje, ale potemBossmusi przebyć 500 stóp,Caby dać mu dowód zamówienia. Następnie przy następnej iteracji i każdej innej iteracji po tymBossmusi iść w tę iz powrotem 500 stóp między nimi.

Drugi przypadek:Boss ma do przebycia 100 stóp na pierwszej iteracji doA, ale po tym, on już tam jest i tylko czekaA, aby wrócić aż wszystkie zrazy są wypełniane. NastępnieBossmusi przejechać 500 stóp przy pierwszej iteracji do,CponieważCjest 500 stóp odA. PonieważBoss( Summation, For Loop )jest to wywoływane zaraz po pracy,Aon po prostu czeka tam, tak jak to zrobił,Aaż do wykonania wszystkichC'sodcinków zamówienia.

Różnica w przebytych odległościach

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;    

Porównanie wartości arbitralnych

Łatwo zauważyć, że 600 to znacznie mniej niż 10 milionów. Nie jest to do końca dokładne, ponieważ nie znamy faktycznej różnicy odległości między adresem pamięci RAM lub z którego pamięci podręcznej lub pliku strony każde wywołanie każdej iteracji będzie spowodowane wieloma innymi niewidocznymi zmiennymi. Jest to tylko ocena sytuacji, na którą należy zwrócić uwagę, i spojrzenie na nią z najgorszego scenariusza.

Z tych liczb wyglądałoby to prawie tak, jakby Algorytm pierwszy był 99%wolniejszy niż algorytm drugi; Jest to jednak tylko Boss'sczęść lub odpowiedzialność algorytmów i nie uwzględnia rzeczywistych pracowników A, B, C, i D, a co mają robić na każdej iteracji pętli. Tak więc praca szefa stanowi jedynie około 15 - 40% całkowitej wykonanej pracy. Większość pracy wykonanej przez pracowników ma nieco większy wpływ na utrzymanie stosunku różnic prędkości między prędkościami około 50-70%

Obserwacja: - Różnice między dwoma algorytmami

W tej sytuacji jest to struktura procesu wykonywanej pracy. Pokazuje to, że przypadek 2 jest bardziej efektywny zarówno od częściowej optymalizacji posiadania podobnej deklaracji funkcji, jak i definicji, gdy tylko zmienne różnią się nazwą i przebytą odległością.

Widzimy również, że całkowita odległość przebyta w przypadku 1 jest znacznie większa niż w przypadku 2 i możemy rozważyć tę odległość przebytą przez nasz współczynnik czasu między dwoma algorytmami. Przypadek 1 wymaga znacznie więcej pracy niż przypadek 2 .

Można to zaobserwować na podstawie dowodów ASMinstrukcji pokazanych w obu przypadkach. Wraz z tym, co już powiedziano o tych przypadkach, nie oznacza to, że w przypadku 1 szef będzie musiał poczekać na oba Ai Cwrócić, zanim będzie mógł wrócić do Akażdej iteracji. Nie bierze również pod uwagę faktu, że jeśli Alub Bzajmuje to bardzo dużo czasu, zarówno obaj, jak Bossi pozostali robotnicy czekają na wykonanie.

W przypadku 2 jedyną bezczynnością jest czas Bosspowrotu pracownika. Nawet to ma wpływ na algorytm.

Zmienione pytania PO

EDYCJA: Pytanie okazało się nie mieć znaczenia, ponieważ zachowanie w znacznym stopniu zależy od rozmiarów tablic (n) i pamięci podręcznej procesora. Więc jeśli jest dalsze zainteresowanie, przeformułowuję pytanie:

Czy mógłbyś zapewnić rzetelny wgląd w szczegóły, które prowadzą do różnych zachowań pamięci podręcznej, co ilustruje pięć regionów na poniższym wykresie?

Interesujące może być również wskazanie różnic między architekturami procesorów / pamięci podręcznej poprzez zapewnienie podobnego wykresu dla tych procesorów.

Odnośnie tych pytań

Jak wykazałem bez wątpienia, istnieje problem leżący u podstaw jeszcze przed zaangażowaniem sprzętu i oprogramowania.

Teraz jeśli chodzi o zarządzanie pamięcią i buforowaniem wraz z plikami stron itp., Które wszystkie działają razem w zintegrowanym zestawie systemów między następującymi elementami:

• The Architecture {Sprzęt, oprogramowanie układowe, niektóre sterowniki wbudowane, jądra i zestawy instrukcji ASM}.
• The OS{Systemy zarządzania plikami i pamięcią, sterowniki i rejestr}.
• The Compiler {Jednostki tłumaczeniowe i optymalizacje kodu źródłowego}.
• A nawet Source Codesam z zestawem charakterystycznych algorytmów.

Już teraz widać, że nie jest wąskim gardłem, co dzieje się w ciągu pierwszego algorytmu zanim jeszcze zastosować go do dowolnego urządzenia z dowolnym Architecture, OSoraz Programmable Languagew stosunku do drugiego algorytmu. Wystąpił już problem przed zaangażowaniem się we współczesny komputer.

Końcowe wyniki

Jednak; nie można powiedzieć, że te nowe pytania nie mają znaczenia, ponieważ same są i w końcu odgrywają pewną rolę. Wpływają one na procedury i ogólną wydajność, co widać na podstawie różnych wykresów i ocen wielu osób, które udzieliły odpowiedzi i / lub komentarzy.

Jeśli zwrócić uwagę na analogię Boss, a dwóch pracowników Ai Bktórzy mieli pójść i pobrać pakiety Ci Dodpowiednio i rozważa matematycznej notacji dwóch algorytmów w pytaniu; widać bez udziału sprzętu komputerowego, a oprogramowanie Case 2jest w przybliżeniu 60%szybsze niż Case 1.

Gdy spojrzysz na wykresy i wykresy po zastosowaniu tych algorytmów do jakiegoś kodu źródłowego, skompilowaniu, zoptymalizowaniu i wykonaniu przez system operacyjny w celu wykonania ich operacji na danym sprzęcie, możesz nawet zauważyć nieco większą degradację między różnicami w tych algorytmach.

Jeśli Datazestaw jest dość mały, na pierwszy rzut oka może się wydawać, że nie ma aż takiej różnicy. Ponieważ jednak Case 1jest o wiele 60 - 70%wolniejszy niż Case 2możemy spojrzeć na wzrost tej funkcji pod względem różnic w wykonywaniu czasu:

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)

To przybliżenie jest średnią różnicą między tymi dwiema pętlami, zarówno algorytmicznymi, jak i operacjami maszyny obejmującymi optymalizacje oprogramowania i instrukcje maszynowe.

Gdy zbiór danych rośnie liniowo, rośnie również różnica czasu między nimi. Algorytm 1 ma więcej pobrań niż algorytm 2, co jest oczywiste, gdy Bossmusi podróżować do przodu i do tyłu maksymalną odległość między Ai Cdla każdej iteracji po pierwszej iteracji, podczas gdy Algorytm 2 Bossmusi jechać Araz, a następnie po Azakończeniu musi podróżować maksymalna odległość tylko jeden raz, jadąc od Ado C.

Próba Bossskupienia się na robieniu dwóch podobnych rzeczy naraz i żonglowaniu nimi w jedną i drugą stronę zamiast skupiania się na podobnych kolejnych zadaniach sprawi, że pod koniec dnia będzie dość zły, ponieważ musiał dwukrotnie podróżować i pracować. Dlatego nie trać zakresu sytuacji, pozwalając szefowi dostać się do interpolowanego wąskiego gardła, ponieważ małżonek szefa i dzieci nie doceniliby tego.

Poprawka: Zasady projektowania oprogramowania

- Różnica między Local Stacki Heap Allocatedobliczenia zasięgu iteracyjny dla pętli, a różnica między ich zwyczajów, ich wydajności i skuteczności -

Algorytm matematyczny, który zaproponowałem powyżej, dotyczy głównie pętli, które wykonują operacje na danych przydzielonych na stercie.

• Kolejne operacje na stosie:
  • Jeśli pętle wykonują operacje na danych lokalnie w ramach pojedynczego bloku kodu lub zakresu, który znajduje się w ramce stosu, nadal będzie to miało zastosowanie, ale lokalizacje pamięci są znacznie bliżej tam, gdzie są zwykle sekwencyjne, a różnica w przebytej odległości lub czasie wykonania jest prawie nieistotne. Ponieważ w stercie nie są wykonywane przydziały, pamięć nie jest rozproszona, a pamięć nie jest pobierana przez RAM. Pamięć jest zwykle sekwencyjna i odnosi się do ramki stosu i wskaźnika stosu.
  • Podczas wykonywania kolejnych operacji na stosie, nowoczesny procesor buforuje powtarzalne wartości i adresy, utrzymując te wartości w lokalnych rejestrach pamięci podręcznej. Czas operacji lub instrukcji tutaj jest rzędu nanosekund.
• Kolejne przydzielone operacje sterty:
  • Kiedy zaczniesz stosować przydziały sterty, a procesor musi pobierać adresy pamięci podczas kolejnych wywołań, w zależności od architektury CPU, kontrolera magistrali i modułów pamięci RAM, czas operacji lub wykonania może być rzędu mikro do milisekundy. W porównaniu z buforowanymi operacjami stosu są one dość powolne.
  • Procesor będzie musiał pobrać adres pamięci z pamięci RAM i zazwyczaj wszystko w magistrali systemowej jest wolne w porównaniu do wewnętrznych ścieżek danych lub magistrali danych w samym CPU.

Kiedy więc pracujesz z danymi, które muszą znajdować się na stercie, i przechodzisz przez nie w pętlach, bardziej efektywne jest utrzymywanie każdego zestawu danych i odpowiadających mu algorytmów w ramach jednej pojedynczej pętli. Uzyskasz lepsze optymalizacje w porównaniu do próby wyodrębnienia kolejnych pętli poprzez umieszczenie wielu operacji różnych zestawów danych znajdujących się na stercie w jednej pętli.

Można to zrobić z danymi znajdującymi się na stosie, ponieważ są one często buforowane, ale nie w przypadku danych, które muszą mieć sprawdzany adres pamięci podczas każdej iteracji.

Tutaj zaczyna się gra Inżynieria oprogramowania i Projektowanie architektury oprogramowania. Jest to umiejętność wiedzieć, jak zorganizować dane, wiedzieć, kiedy je buforować, wiedzieć, kiedy przydzielić dane na stercie, jak zaprojektować i wdrożyć algorytmy oraz wiedzieć, kiedy i gdzie je wywołać.

Możesz mieć ten sam algorytm, który dotyczy tego samego zestawu danych, ale możesz chcieć jednego projektu implementacji dla jego wariantu stosu, a drugiego dla jego wariantu alokacji sterty tylko z powodu powyższego problemu, który wynika z jego O(n)złożoności algorytmu podczas pracy z kupą.

Z tego, co zauważyłem przez lata, wiele osób nie bierze tego pod uwagę. Będą mieli tendencję do projektowania jednego algorytmu, który działa na określonym zbiorze danych i będą go używać niezależnie od tego, czy zbiór danych jest lokalnie buforowany na stosie, czy też został przydzielony na stercie.

Jeśli chcesz prawdziwej optymalizacji, tak, może się to wydawać duplikacją kodu, ale uogólnienie byłoby bardziej wydajne, gdyby dwa warianty tego samego algorytmu. Jedna do operacji na stosie, a druga do operacji na stosie, które są wykonywane w pętlach iteracyjnych!

Oto pseudo przykład: dwie proste struktury, jeden algorytm.

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.

Do tego miałem na myśli osobne implementacje wariantów stosu w porównaniu do wariantów stosu. Same algorytmy nie mają większego znaczenia, to struktury zapętlające, w których będziesz ich używał.

Może to być stary C ++ i optymalizacje. Na moim komputerze uzyskałem prawie taką samą prędkość:

Jedna pętla: 1,577 ms

Dwie pętle: 1,507 ms

Używam Visual Studio 2015 na procesorze E5-1620 3,5 GHz z 16 GB pamięci RAM.