Misalkan a1, b1, c1, dan d1arahkan ke memori tumpukan dan kode numerik saya memiliki loop inti berikut.

const int n = 100000;

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

Loop ini dijalankan 10.000 kali melalui forloop luar lainnya . Untuk mempercepatnya, saya mengubah kode menjadi:

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

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

Dikompilasi pada MS Visual C ++ 10.0 dengan optimasi penuh dan SSE2 diaktifkan untuk 32-bit pada Intel Core 2 Duo (x64), contoh pertama membutuhkan 5,5 detik dan contoh loop ganda hanya membutuhkan 1,9 detik. Pertanyaan saya adalah: (Silakan merujuk ke pertanyaan saya yang ditulis ulang di bagian bawah)

PS: Saya tidak yakin kalau ini membantu:

Pembongkaran untuk loop pertama pada dasarnya terlihat seperti ini (blok ini diulang sekitar lima kali dalam program penuh):

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]

Setiap loop dari contoh loop ganda menghasilkan kode ini (blok berikut diulang sekitar tiga kali):

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

Pertanyaan itu ternyata tidak ada relevansinya, karena perilakunya sangat tergantung pada ukuran array (n) dan cache CPU. Jadi jika ada minat lebih lanjut, saya ulangi pertanyaannya:

Bisakah Anda memberikan beberapa wawasan yang mendalam tentang detail yang mengarah pada perilaku cache yang berbeda seperti yang diilustrasikan oleh lima wilayah pada grafik berikut?

Mungkin juga menarik untuk menunjukkan perbedaan antara arsitektur CPU / cache, dengan menyediakan grafik yang sama untuk CPU ini.

PPS: Ini kode lengkapnya. Ini menggunakan TBB Tick_Count untuk pengaturan waktu resolusi yang lebih tinggi, yang dapat dinonaktifkan dengan tidak mendefinisikan TBB_TIMINGMakro:

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

(Ini menunjukkan FLOP / s untuk nilai yang berbeda dari n.)

Setelah analisis lebih lanjut tentang ini, saya percaya ini (setidaknya sebagian) disebabkan oleh penyelarasan data dari empat-pointer. Ini akan menyebabkan beberapa level bank cache / konflik jalan.

Jika saya telah menebak dengan benar tentang bagaimana Anda mengalokasikan array Anda, mereka cenderung disejajarkan dengan baris halaman .

Ini berarti bahwa semua akses Anda di setiap loop akan jatuh pada cara cache yang sama. Namun, prosesor Intel memiliki 8-way L1 cache associativity untuk sementara waktu. Namun dalam kenyataannya, kinerjanya tidak sepenuhnya seragam. Mengakses 4-arah masih lebih lambat daripada mengatakan 2-arah.

EDIT: Itu sebenarnya terlihat seperti Anda mengalokasikan semua array secara terpisah. Biasanya ketika alokasi besar seperti itu diminta, pengalokasi akan meminta halaman baru dari OS. Oleh karena itu, ada kemungkinan besar bahwa alokasi besar akan muncul pada offset yang sama dari batas halaman.

Inilah kode tes:

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

Hasil Benchmark:

EDIT: Hasil dari mesin arsitektur Core 2 yang sebenarnya :

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

Pengamatan:

• 6,206 detik dengan satu loop dan 2,116 detik dengan dua loop. Ini mereproduksi hasil OP persis.

• Dalam dua tes pertama, array dialokasikan secara terpisah. Anda akan melihat bahwa mereka semua memiliki perataan yang relatif relatif terhadap halaman.

• Dalam dua tes kedua, array dikemas bersama untuk memecah keselarasan itu. Di sini Anda akan melihat kedua loop lebih cepat. Selain itu, loop (ganda) kedua sekarang lebih lambat seperti yang biasanya Anda harapkan.

Seperti @Stephen Cannon tunjukkan dalam komentar, ada kemungkinan besar bahwa perataan ini menyebabkan alias palsu di unit load / store atau cache. Saya mencari-cari di Google untuk ini dan menemukan bahwa Intel sebenarnya memiliki penghitung perangkat keras untuk warung aliasing alamat parsial :

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

5 Wilayah - Penjelasan

Wilayah 1:

Yang ini mudah. Dataset sangat kecil sehingga kinerjanya didominasi oleh overhead seperti looping dan branching.

Wilayah 2:

Di sini, ketika ukuran data meningkat, jumlah overhead relatif turun dan kinerja "jenuh". Di sini dua loop lebih lambat karena memiliki loop dua kali lebih banyak dan overhead bercabang.

Saya tidak yakin persis apa yang terjadi di sini ... Keselarasan masih dapat berpengaruh sebagai Agner Fog menyebutkan konflik bank cache . (Tautan itu tentang Sandy Bridge, tetapi idenya harus tetap berlaku untuk Core 2.)

Wilayah 3:

Pada titik ini, data tidak lagi sesuai dengan cache L1. Jadi kinerjanya dibatasi oleh L1 <-> L2 cache bandwidth.

Wilayah 4:

Penurunan kinerja dalam satu-loop adalah apa yang kami amati. Dan seperti yang disebutkan, ini adalah karena penyejajaran yang (kemungkinan besar) menyebabkan warung aliasing palsu di unit pemuatan / penyimpanan prosesor.

Namun, agar kesalahan alias terjadi, harus ada langkah yang cukup besar antara set data. Inilah sebabnya mengapa Anda tidak melihat ini di wilayah 3.

Wilayah 5:

Pada titik ini, tidak ada yang cocok dengan cache. Jadi Anda terikat oleh bandwidth memori.

OK, jawaban yang benar pasti ada hubungannya dengan cache CPU. Tetapi untuk menggunakan argumen cache bisa sangat sulit, terutama tanpa data.

Ada banyak jawaban, yang mengarah ke banyak diskusi, tetapi mari kita hadapi: masalah cache bisa sangat kompleks dan tidak satu dimensi. Mereka sangat bergantung pada ukuran data, jadi pertanyaan saya tidak adil: Ternyata pada titik yang sangat menarik dalam grafik cache.

Jawaban @ Mysticial meyakinkan banyak orang (termasuk saya), mungkin karena itu satu-satunya yang tampaknya mengandalkan fakta, tetapi itu hanya satu "titik data" dari kebenaran.

Itu sebabnya saya menggabungkan tesnya (menggunakan alokasi kontinu vs terpisah) dan saran @James 'Answers.

Grafik di bawah ini menunjukkan, bahwa sebagian besar jawaban dan terutama sebagian besar komentar terhadap pertanyaan dan jawaban dapat dianggap sepenuhnya salah atau benar tergantung pada skenario dan parameter yang digunakan.

Perhatikan bahwa pertanyaan awal saya adalah n = 100.000 . Poin ini (secara tidak sengaja) menunjukkan perilaku khusus:

1. Ini memiliki perbedaan terbesar antara versi satu dan dua loop (hampir faktor tiga)

2. Ini adalah satu-satunya titik, di mana satu loop (yaitu dengan alokasi kontinu) mengalahkan versi dua loop. (Ini memungkinkan jawaban Mysticial, sama sekali.)

Hasilnya menggunakan data yang diinisialisasi:

Hasilnya menggunakan data yang tidak diinisialisasi (inilah yang diuji Mysticial):

Dan ini yang sulit dijelaskan: Data diinisialisasi, yang dialokasikan satu kali dan digunakan kembali untuk setiap uji kasus berikut dengan ukuran vektor yang berbeda:

Usul

Setiap pertanyaan terkait kinerja tingkat rendah pada Stack Overflow harus diminta untuk memberikan informasi MFLOPS untuk seluruh jajaran ukuran data yang relevan dengan cache! Buang-buang waktu semua orang untuk memikirkan jawaban dan terutama mendiskusikannya dengan orang lain tanpa informasi ini.

Loop kedua melibatkan aktivitas cache yang jauh lebih sedikit, sehingga prosesor lebih mudah untuk mengikuti tuntutan memori.

Bayangkan Anda sedang mengerjakan mesin di mana nnilai yang tepat hanya memungkinkan untuk menahan dua array Anda dalam memori pada satu waktu, tetapi total memori yang tersedia, melalui cache disk, masih cukup untuk menampung keempatnya.

Dengan asumsi kebijakan caching LIFO sederhana, kode ini:

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

pertama-tama akan menyebabkan adan bdimuat ke dalam RAM dan kemudian dikerjakan sepenuhnya dalam RAM. Ketika loop kedua dimulai,c dan dkemudian akan dimuat dari disk ke dalam RAM dan dioperasikan.

loop lainnya

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

akan mengeluarkan dua array dan halaman di dua lainnya setiap kali di loop . Ini jelas akan banyak lebih lambat.

Anda mungkin tidak melihat caching disk dalam tes Anda, tetapi Anda mungkin melihat efek samping dari beberapa bentuk caching lainnya.

Tampaknya ada sedikit kebingungan / kesalahpahaman di sini jadi saya akan mencoba menguraikan sedikit menggunakan contoh.

Katakan n = 2dan kami bekerja dengan byte. Dalam skenario saya demikian kita miliki hanya 4 byte RAM dan sisa memori kami secara signifikan lebih lambat (katakanlah akses 100 kali lebih lama).

Dengan asumsi kebijakan caching yang cukup bodoh jika byte tidak ada dalam cache, letakkan di sana dan dapatkan byte berikut juga saat kita berada di dalamnya, Anda akan mendapatkan skenario seperti ini:

• Dengan

  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]dan a[1]kemudian b[0]dan b[1]dan diatur a[0] = a[0] + b[0]dalam cache - sekarang ada empat byte dalam cache, a[0], a[1]danb[0], b[1] . Biaya = 100 + 100.

• set a[1] = a[1] + b[1] dalam cache. Biaya = 1 + 1.
• Ulangi untuk cdand .

• Total biaya = (100 + 100 + 1 + 1) * 2 = 404

• Dengan

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

• cache a[0]dan a[1]kemudian b[0]dan b[1]dan diatur a[0] = a[0] + b[0]dalam cache - sekarang ada empat byte dalam cache, a[0], a[1]danb[0], b[1] . Biaya = 100 + 100.

• eject a[0], a[1], b[0], b[1]dari cache dan cache c[0]dan c[1]kemudian d[0]dan d[1]dan setc[0] = c[0] + d[0] dalam cache. Biaya = 100 + 100.
• Saya curiga Anda mulai melihat ke mana saya pergi.
• Total biaya = (100 + 100 + 100 + 100) * 2 = 800

Ini adalah skenario thrash cache klasik.

Ini bukan karena kode yang berbeda, tetapi karena caching: RAM lebih lambat dari register CPU dan memori cache ada di dalam CPU untuk menghindari penulisan RAM setiap kali variabel berubah. Tetapi cache tidak sebesar RAM, karenanya hanya memetakan sebagian saja.

Kode pertama memodifikasi alamat memori jauh secara bergantian di setiap loop, sehingga membutuhkan terus menerus untuk membatalkan cache.

Kode kedua tidak berganti: hanya mengalir di alamat yang berdekatan dua kali. Ini membuat semua pekerjaan harus diselesaikan dalam cache, membatalkannya hanya setelah loop kedua dimulai.

Saya tidak bisa meniru hasil yang dibahas di sini.

Saya tidak tahu apakah kode tolok ukur yang salah harus disalahkan, atau apa, tetapi kedua metode tersebut berada dalam jarak 10% satu sama lain pada mesin saya menggunakan kode berikut, dan satu putaran biasanya hanya sedikit lebih cepat dari dua - seperti yang Anda inginkan mengharapkan.

Ukuran array berkisar dari 2 ^ 16 hingga 2 ^ 24, menggunakan delapan loop. Saya berhati-hati untuk menginisialisasi array sumber sehingga +=tugas tidak meminta FPU untuk menambahkan memori sampah yang ditafsirkan sebagai ganda.

Saya bermain-main dengan berbagai skema, seperti menempatkan penugasan b[j], d[j]ke InitToZero[j]dalam loop, dan juga dengan menggunakan += b[j] = 1dan+= d[j] = 1 , dan saya mendapatkan hasil yang cukup konsisten.

Seperti yang Anda harapkan, menginisialisasi bdan ddi dalam loop menggunakan InitToZero[j]memberi pendekatan gabungan keuntungan, karena mereka dilakukan back-to-back sebelum penugasan ke adanc , tetapi masih dalam 10%. Sosok pergi.

Perangkat kerasnya adalah Dell XPS 8500 dengan generasi 3 Core i7 @ 3.4 GHz dan memori 8 GB. Untuk 2 ^ 16 hingga 2 ^ 24, menggunakan delapan loop, waktu kumulatif adalah masing-masing 44,987 dan 40,965. Visual C ++ 2010, sepenuhnya dioptimalkan.

PS: Saya mengubah loop untuk menghitung mundur ke nol, dan metode gabungan sedikit lebih cepat. Menggaruk kepalaku. Perhatikan ukuran array dan jumlah loop baru.

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

Saya tidak yakin mengapa diputuskan bahwa MFLOPS adalah metrik yang relevan. Saya pikir idenya adalah untuk fokus pada akses memori, jadi saya mencoba untuk meminimalkan jumlah waktu komputasi floating point. Saya pergi di +=, tetapi saya tidak yakin mengapa.

Tugas lurus tanpa perhitungan akan menjadi tes yang lebih bersih dari waktu akses memori dan akan membuat tes yang seragam terlepas dari jumlah loop. Mungkin saya melewatkan sesuatu dalam percakapan itu, tetapi perlu dipikirkan dua kali. Jika plus ditinggalkan dari tugas, waktu kumulatif hampir identik pada 31 detik masing-masing.

Itu karena CPU tidak memiliki cache yang terlalu banyak (di mana ia harus menunggu data array datang dari chip RAM). Akan menarik bagi Anda untuk menyesuaikan ukuran array secara terus-menerus sehingga Anda melebihi ukuran cache level 1 (L1), dan kemudian cache level 2 (L2), dari CPU Anda dan plot waktu yang diperlukan untuk kode Anda untuk mengeksekusi terhadap ukuran array. Grafik tidak boleh berupa garis lurus seperti yang Anda harapkan.

Loop pertama bergantian menulis di setiap variabel. Yang kedua dan ketiga hanya membuat lompatan kecil dari ukuran elemen.

Cobalah menulis dua garis sejajar 20 salib dengan pena dan kertas yang dipisahkan 20 cm. Cobalah sekali menyelesaikan satu dan kemudian baris lainnya dan coba lain waktu dengan menuliskan tanda silang di setiap baris secara bergantian.

Pertanyaan Asli

Mengapa satu loop jauh lebih lambat dari dua loop?

Kesimpulan:

Kasus 1 adalah masalah interpolasi klasik yang kebetulan tidak efisien. Saya juga berpikir bahwa ini adalah salah satu alasan utama mengapa banyak arsitektur dan pengembang mesin akhirnya membangun dan merancang sistem multi-inti dengan kemampuan untuk melakukan aplikasi multi-berulir serta pemrograman paralel.

Melihatnya dari pendekatan semacam ini tanpa melibatkan bagaimana Perangkat Keras, OS, dan Kompiler bekerja bersama untuk melakukan alokasi tumpukan yang melibatkan bekerja dengan RAM, Cache, File Halaman, dll .; matematika yang merupakan dasar dari algoritma ini menunjukkan kepada kita yang mana dari dua ini adalah solusi yang lebih baik.

Kita dapat menggunakan analogi Bossmakhluk Summationyang akan mewakili For Loopyang harus bepergian antara pekerja A& B.

Kita dapat dengan mudah melihat bahwa Kasus 2 setidaknya setengah lebih cepat jika tidak sedikit lebih dari Kasus 1 karena perbedaan jarak yang diperlukan untuk melakukan perjalanan dan waktu yang diambil antara pekerja. Matematika ini berbaris hampir secara virtual dan sempurna dengan BenchMark Times serta jumlah perbedaan dalam Instruksi Majelis.

Sekarang saya akan mulai menjelaskan bagaimana semua ini bekerja di bawah ini.

Menilai Masalahnya

Kode OP:

const int n=100000;

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

Dan

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

Pertimbangannya

Mempertimbangkan pertanyaan awal OP tentang 2 varian for for loop dan pertanyaannya yang diubah terhadap perilaku cache bersama dengan banyak jawaban luar biasa lainnya dan komentar yang berguna; Saya ingin mencoba dan melakukan sesuatu yang berbeda di sini dengan mengambil pendekatan berbeda tentang situasi dan masalah ini.

Pendekatan

Mempertimbangkan dua loop dan semua diskusi tentang cache dan pengarsipan halaman saya ingin mengambil pendekatan lain untuk melihat ini dari perspektif yang berbeda. Salah satu yang tidak melibatkan cache dan file halaman atau eksekusi untuk mengalokasikan memori, pada kenyataannya, pendekatan ini bahkan tidak menyangkut perangkat keras atau perangkat lunak yang sebenarnya sama sekali.

Perspektif

Setelah melihat kode untuk sementara waktu menjadi sangat jelas apa masalahnya dan apa yang menghasilkannya. Mari kita memecah ini menjadi masalah algoritmik dan melihatnya dari perspektif menggunakan notasi matematika kemudian menerapkan analogi untuk masalah matematika dan juga algoritma.

Apa Yang Kita Ketahui

Kita tahu bahwa loop ini akan berjalan 100.000 kali. Kita juga tahu bahwa a1, b1, c1&d1 adalah pointer pada arsitektur 64-bit. Dalam C ++ pada mesin 32-bit, semua pointer berukuran 4 byte dan pada mesin 64-bit, semuanya berukuran 8 byte karena pointer memiliki panjang yang tetap.

Kami tahu bahwa kami memiliki 32 byte untuk dialokasikan dalam kedua kasus. Satu-satunya perbedaan adalah kita mengalokasikan 32 byte atau 2 set 2-8bytes pada setiap iterasi di mana kasus ke-2 kita mengalokasikan 16 byte untuk setiap iterasi untuk kedua loop independen.

Kedua loop masih sama 32 byte dalam alokasi total. Dengan informasi ini, mari kita lanjutkan dan tunjukkan matematika umum, algoritma, dan analogi dari konsep-konsep ini.

Kami tahu berapa kali set atau kelompok operasi yang sama yang harus dilakukan dalam kedua kasus. Kami tahu jumlah memori yang perlu dialokasikan dalam kedua kasus. Kita dapat menilai bahwa beban kerja keseluruhan dari alokasi antara kedua kasus akan kira-kira sama.

Yang Tidak Kami Ketahui

Kami tidak tahu berapa lama untuk setiap kasus kecuali jika kami menetapkan penghitung dan menjalankan tes benchmark. Namun, tolok ukur sudah termasuk dari pertanyaan awal dan dari beberapa jawaban dan komentar juga; dan kita dapat melihat perbedaan yang signifikan antara keduanya dan ini adalah alasan keseluruhan untuk proposal ini untuk masalah ini.

Mari selidiki

Sudah jelas bahwa banyak yang telah melakukan ini dengan melihat alokasi heap, tes benchmark, melihat RAM, Cache, dan File Halaman. Melihat titik data spesifik dan indeks iterasi spesifik juga dimasukkan dan berbagai percakapan tentang masalah khusus ini membuat banyak orang mulai mempertanyakan hal-hal terkait lainnya tentang hal itu. Bagaimana kita mulai melihat masalah ini dengan menggunakan algoritma matematika dan menerapkan analogi untuk itu? Kami memulai dengan membuat beberapa pernyataan! Lalu kami membangun algoritma kami dari sana.

Pernyataan Kami:

• Kita akan membiarkan loop dan iterasi-nya menjadi Penjumlahan yang dimulai pada 1 dan berakhir pada 100000 alih-alih dimulai dengan 0 seperti pada loop karena kita tidak perlu khawatir tentang skema pengindeksan pengalamatan memori 0 karena kita hanya tertarik pada algoritma itu sendiri.
• Dalam kedua kasus kami memiliki 4 fungsi untuk bekerja dengan dan 2 panggilan fungsi dengan 2 operasi yang dilakukan pada setiap panggilan fungsi. Kami akan mengatur ini sebagai fungsi dan panggilan ke fungsi sebagai berikut: F1(), F2(), f(a), f(b), f(c)dan f(d).

Algoritma:

Kasus 1: - Hanya satu penjumlahan tetapi dua panggilan fungsi independen.

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

Kasus 2: - Dua penjumlahan tetapi masing-masing memiliki panggilan fungsi tersendiri.

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

Jika Anda perhatikan F2()hanya ada di Sumdari Case1mana F1()terkandung Sumdari Case1dan di keduanya Sum1dan Sum2dari Case2. Ini akan menjadi bukti nanti ketika kita mulai menyimpulkan bahwa ada optimasi yang terjadi dalam algoritma kedua.

Iterasi melalui Sumpanggilan kasus pertama f(a)yang akan menambah dirinya sendiri f(b)lalu panggilan f(c)yang akan melakukan hal yang sama tetapi menambah f(d)sendiri untuk setiap 100000iterasi. Dalam kasus kedua, kita memiliki Sum1dan Sum2keduanya bertindak sama seolah-olah mereka memiliki fungsi yang sama dipanggil dua kali berturut-turut.

Dalam hal ini kita dapat memperlakukan Sum1dan Sum2sama seperti biasa di Summana Sumdalam kasus ini terlihat seperti ini: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }dan sekarang ini terlihat seperti optimasi di mana kita dapat menganggapnya sebagai fungsi yang sama.

Ringkasan dengan Analogi

Dengan apa yang telah kita lihat dalam kasus kedua hampir tampak seolah-olah ada optimasi karena keduanya untuk loop memiliki tanda tangan yang sama persis, tetapi ini bukan masalah sebenarnya. Masalahnya bukan pekerjaan yang sedang dilakukan oleh f(a), f(b), f(c), dan f(d). Dalam kedua kasus dan perbandingan antara keduanya, itu adalah perbedaan dalam jarak yang dijumlahkan oleh Penjumlahan dalam setiap kasus yang memberi Anda perbedaan dalam waktu eksekusi.

Pikirkan For Loopssebagai Summationsyang melakukan iterasi sebagai Bossyang memberi perintah kepada dua orang A& Bdan bahwa pekerjaan mereka adalah daging C& Dmasing-masing dan untuk mengambil beberapa paket dari mereka dan mengembalikannya. Dalam analogi ini, perulangan dan penjumlahan for loop atau penjumlahan kondisi sendiri sebenarnya tidak mewakili Boss. Apa yang sebenarnya mewakili Bossbukan dari algoritma matematika aktual secara langsung tetapi dari konsep aktual Scopedan Code Blockdalam rutin atau subrutin, metode, fungsi, unit terjemahan, dll. Algoritma pertama memiliki 1 ruang lingkup di mana algoritma 2 memiliki 2 cakupan berturut-turut.

Dalam kasus pertama pada setiap slip panggilan, Bosspergi ke Adan memberikan pesanan dan Apergi untuk mengambil B'spaket kemudian Bosspergi ke Cdan memberikan perintah untuk melakukan hal yang sama dan menerima paket dari Dpada setiap iterasi.

Dalam kasus kedua, Bosspekerjaan langsung dengan Apergi dan mengambil B'spaket sampai semua paket diterima. Kemudian Bossbekerja dengan Cmelakukan hal yang sama untuk mendapatkan semua D'spaket.

Karena kita bekerja dengan pointer 8-byte dan berurusan dengan alokasi heap mari kita pertimbangkan masalah berikut. Katakanlah Boss100 kaki dari Adan A500 kaki dari C. Kita tidak perlu khawatir tentang seberapa jauh dari Bossawalnya Ckarena urutan eksekusi. Dalam kedua kasus, Bossawalnya perjalanan dari Apertama lalu ke B. Analogi ini bukan untuk mengatakan bahwa jarak ini tepat; itu hanya skenario kasus uji yang berguna untuk menunjukkan cara kerja algoritma.

Dalam banyak kasus ketika melakukan alokasi tumpukan dan bekerja dengan cache dan file halaman, jarak antara lokasi alamat ini mungkin tidak banyak berbeda atau mereka dapat bervariasi secara signifikan tergantung pada sifat tipe data dan ukuran array.

Kasus Uji:

Kasus Pertama: Pada iterasi pertamaBossharus awalnya berjalan 100 kaki untuk memberikan slip pesanan keAdanApergi dan melakukan hal-nya, tetapi kemudianBossharus melakukan perjalanan 500 kaki untukCmemberinya slip pesanannya. Kemudian pada iterasi berikutnya dan setiap iterasi lainnya setelahBossharus bolak-balik 500 kaki antara keduanya.

Kasus Kedua: TheBossharus melakukan perjalanan 100 kaki pada iterasi pertamaA, tetapi setelah itu, dia sudah ada di sana dan hanya menunggu untukAkembali sampai semua slip terisi. KemudianBossharus menempuh jarak 500 kaki pada iterasi pertamaCkarenaCberjarak 500 kaki dariA. Karena iniBoss( Summation, For Loop )dipanggil tepat setelah bekerja denganAdia maka hanya menunggu di sana seperti yang dia lakukan denganAsampai semuaC'sslip pesanan selesai.

Perbedaan Jarak Yang Dijalani

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;    

Perbandingan Nilai Sewenang-wenang

Kita dapat dengan mudah melihat bahwa 600 jauh lebih sedikit dari 10 juta. Sekarang, ini tidak tepat, karena kita tidak tahu perbedaan sebenarnya dalam jarak antara alamat RAM atau dari mana Cache atau File Halaman setiap panggilan pada setiap iterasi akan disebabkan oleh banyak variabel tak terlihat lainnya. Ini hanya penilaian situasi yang harus diperhatikan dan dilihat dari skenario terburuk.

Dari angka-angka ini hampir akan tampak seolah-olah Algoritma One harus lebih 99%lambat dari Algoritma Dua; Namun, ini hanya Boss'ssebagian atau tanggung jawab algoritma dan tidak memperhitungkan pekerja yang sebenarnya A, B, C, & Ddan apa yang harus mereka lakukan pada setiap iterasi dari Loop. Jadi pekerjaan bos hanya menyumbang sekitar 15 - 40% dari total pekerjaan yang dilakukan. Sebagian besar pekerjaan yang dilakukan melalui pekerja memiliki dampak yang sedikit lebih besar untuk menjaga rasio perbedaan kecepatan menjadi sekitar 50-70%

Pengamatan: - Perbedaan antara kedua algoritma

Dalam situasi ini, itu adalah struktur dari proses pekerjaan yang dilakukan. Ini menunjukkan bahwa Kasus 2 lebih efisien dari optimasi parsial memiliki pernyataan fungsi dan definisi yang sama di mana hanya variabel yang berbeda berdasarkan nama dan jarak yang ditempuh.

Kami juga melihat bahwa jarak total yang ditempuh dalam Kasus 1 jauh lebih jauh daripada dalam Kasus 2 dan kami dapat mempertimbangkan jarak yang ditempuh Faktor Waktu kami antara kedua algoritma. Kasus 1 memiliki banyak pekerjaan yang harus dilakukan daripada Kasus 2 .

Ini dapat diamati dari bukti ASMinstruksi yang ditunjukkan dalam kedua kasus. Bersamaan dengan apa yang telah dinyatakan tentang kasus-kasus ini, ini tidak memperhitungkan fakta bahwa dalam Kasus 1 bos harus menunggu keduanya A& Cuntuk kembali sebelum dia dapat kembali Alagi untuk setiap iterasi. Ini juga tidak memperhitungkan fakta bahwa jika Aatau Bmembutuhkan waktu yang sangat lama maka Bosspekerja dan pekerja lainnya menganggur menunggu untuk dieksekusi.

Dalam Kasus 2 satu-satunya yang menganggur adalah Bosssampai pekerja kembali. Jadi, ini pun berdampak pada algoritma.

Pertanyaan yang Diubah OPs

EDIT: Pertanyaannya ternyata tidak relevan, karena perilaku sangat tergantung pada ukuran array (n) dan cache CPU. Jadi jika ada minat lebih lanjut, saya ulangi pertanyaannya:

Bisakah Anda memberikan beberapa wawasan yang mendalam tentang detail yang mengarah pada perilaku cache yang berbeda seperti yang diilustrasikan oleh lima wilayah pada grafik berikut?

Mungkin juga menarik untuk menunjukkan perbedaan antara arsitektur CPU / cache, dengan menyediakan grafik yang sama untuk CPU ini.

Mengenai Pertanyaan Ini

Seperti yang telah saya tunjukkan tanpa keraguan, ada masalah mendasar bahkan sebelum Hardware dan Software terlibat.

Sekarang untuk pengelolaan memori dan caching bersama dengan file halaman, dll. Yang semuanya bekerja bersama dalam satu set sistem terintegrasi antara yang berikut:

• The Architecture {Perangkat Keras, Firmware, beberapa Driver Tertanam, Kernel dan Set Instruksi ASM}.
• The OS{Sistem Manajemen File dan Memori, Driver dan Registry}.
• The Compiler {Unit Terjemahan dan Optimalisasi Kode Sumber}.
• Dan bahkan Source Codeitu sendiri dengan set (s) algoritma yang berbeda.

Kita sudah bisa melihat bahwa ada hambatan yang terjadi dalam algoritma pertama sebelum kita bahkan menerapkannya pada setiap mesin dengan sewenang-wenang setiap Architecture, OSdan Programmable Languagedibandingkan dengan algoritma kedua. Sudah ada masalah sebelum melibatkan intrinsik komputer modern.

Hasil Akhir

Namun; bukan untuk mengatakan bahwa pertanyaan-pertanyaan baru ini tidak penting karena mereka sendiri dan mereka memang memainkan peran. Mereka berdampak pada prosedur dan kinerja keseluruhan dan itu terbukti dengan berbagai grafik dan penilaian dari banyak orang yang telah memberikan jawaban dan komentar mereka.

Jika Anda memperhatikan analogi dari Bossdan dua pekerja A& Byang harus pergi dan mengambil paket dari C& Dmasing-masing dan mempertimbangkan notasi matematika dari dua algoritma yang dimaksud; Anda dapat melihat tanpa keterlibatan perangkat keras dan perangkat lunak komputer Case 2lebih 60%cepat dari Case 1.

Ketika Anda melihat grafik dan bagan setelah algoritma ini telah diterapkan pada beberapa kode sumber, dikompilasi, dioptimalkan, dan dieksekusi melalui OS untuk melakukan operasi mereka pada perangkat keras yang diberikan, Anda bahkan dapat melihat sedikit lebih banyak degradasi antara perbedaan. dalam algoritma ini.

Jika Datahimpunannya cukup kecil, mungkin pada awalnya tidak terlalu buruk. Namun, karena Case 1ini 60 - 70%lebih lambat daripada yang Case 2bisa kita lihat pada pertumbuhan fungsi ini dalam hal perbedaan dalam eksekusi waktu:

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)

Perkiraan ini adalah perbedaan rata-rata antara kedua loop ini baik secara algoritmik dan operasi mesin yang melibatkan optimasi perangkat lunak dan instruksi mesin.

Ketika kumpulan data tumbuh secara linear, demikian juga perbedaan waktu antara keduanya. Algoritma 1 memiliki lebih banyak pengambilan daripada algoritma 2 yang terbukti ketika Bossharus melakukan perjalanan bolak-balik jarak maksimum antara A& Cuntuk setiap iterasi setelah iterasi pertama sedangkan Algoritma 2 Bossharus melakukan perjalanan ke Asekali dan kemudian setelah dilakukan dengan Adia harus melakukan perjalanan jarak maksimum hanya satu kali ketika pergi dari Ake C.

Mencoba Bossmemfokuskan pada melakukan dua hal yang sama sekaligus dan menyulapnya bolak-balik alih-alih berfokus pada tugas yang sama secara berurutan akan membuatnya marah pada akhir hari karena ia harus bepergian dan bekerja dua kali lebih banyak. Karena itu, jangan kehilangan ruang lingkup situasi dengan membiarkan atasan Anda mengalami hambatan yang diinterpolasi karena pasangan dan anak-anak bos tidak akan menghargainya.

Amandemen: Prinsip Desain Rekayasa Perangkat Lunak

- Perbedaan antara Local Stackdan Heap Allocatedperhitungan dalam iteratif untuk loop dan perbedaan antara penggunaannya, efisiensi, dan efektivitasnya -

Algoritma matematika yang saya usulkan di atas terutama berlaku untuk loop yang melakukan operasi pada data yang dialokasikan pada heap.

• Operasi Stack Berturut-turut:
  • Jika loop melakukan operasi pada data secara lokal dalam satu blok kode atau cakupan yang ada di dalam stack frame itu masih akan berlaku, tetapi lokasi memori lebih dekat di mana mereka biasanya berurutan dan perbedaan jarak yang ditempuh atau waktu eksekusi hampir dapat diabaikan. Karena tidak ada alokasi yang dilakukan dalam heap, memori tidak tersebar, dan memori tidak diambil melalui ram. Memori biasanya berurutan dan relatif terhadap bingkai tumpukan dan penunjuk tumpukan.
  • Ketika operasi berturut-turut dilakukan pada stack, Prosesor modern akan menembolok nilai berulang dan alamat menjaga nilai-nilai ini dalam register cache lokal. Waktu operasi atau instruksi di sini sesuai urutan nano-detik.
• Operasi Alokasi Tumpukan Berturut-turut:
  • Ketika Anda mulai menerapkan alokasi tumpukan dan prosesor harus mengambil alamat memori pada panggilan berurutan, tergantung pada arsitektur CPU, Pengendali Bus, dan modul Ram waktu operasi atau eksekusi dapat sesuai urutan mikro untuk milidetik. Dibandingkan dengan operasi stack dalam cache, ini cukup lambat.
  • CPU harus mengambil alamat memori dari Ram dan biasanya apa pun di bus sistem lambat dibandingkan dengan jalur data internal atau bus data dalam CPU itu sendiri.

Jadi ketika Anda bekerja dengan data yang perlu di tumpukan dan Anda melintasi mereka dalam loop, itu lebih efisien untuk menjaga setiap set data dan algoritma yang sesuai dalam satu loop sendiri. Anda akan mendapatkan optimasi yang lebih baik dibandingkan dengan mencoba memfaktorkan loop berturut-turut dengan menempatkan beberapa operasi set data yang berbeda yang ada di tumpukan menjadi satu loop.

Tidak apa-apa untuk melakukan ini dengan data yang ada di stack karena mereka sering di-cache, tetapi tidak untuk data yang harus memiliki alamat memorinya ditanyai setiap iterasi.

Di sinilah Rekayasa Perangkat Lunak dan Desain Arsitektur Perangkat Lunak berperan. Ini adalah kemampuan untuk mengetahui bagaimana mengatur data Anda, mengetahui kapan harus menyimpan data Anda, mengetahui kapan harus mengalokasikan data Anda di heap, mengetahui bagaimana merancang dan mengimplementasikan algoritma Anda, dan mengetahui kapan dan di mana memanggilnya.

Anda mungkin memiliki algoritma yang sama yang berkaitan dengan kumpulan data yang sama, tetapi Anda mungkin ingin satu desain implementasi untuk varian stack-nya dan yang lain untuk varian heap-dialokasikan hanya karena masalah di atas yang dilihat dari O(n)kompleksitas algoritma ketika bekerja dengan heap.

Dari apa yang saya perhatikan selama bertahun-tahun banyak orang tidak mempertimbangkan fakta ini. Mereka akan cenderung merancang satu algoritma yang bekerja pada set data tertentu dan mereka akan menggunakannya terlepas dari set data yang di-cache secara lokal di stack atau jika dialokasikan pada heap.

Jika Anda menginginkan pengoptimalan yang benar, ya itu mungkin tampak seperti duplikasi kode, tetapi untuk menggeneralisasi akan lebih efisien untuk memiliki dua varian dari algoritma yang sama. Satu untuk operasi stack, dan lainnya untuk operasi heap yang dilakukan dalam loop berulang!

Berikut adalah contoh pseudo: Dua struct sederhana, satu algoritma.

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.

Inilah yang saya maksudkan dengan memiliki implementasi terpisah untuk varian stack versus varian heap. Algoritme itu sendiri tidak terlalu penting, itu adalah struktur pengulangan yang akan Anda gunakan.

Mungkin C ++ lama dan optimisasi. Di komputer saya, saya memperoleh kecepatan yang hampir sama:

Satu loop: 1,577 ms

Dua loop: 1,507 ms

Saya menjalankan Visual Studio 2015 pada prosesor E5-1620 3.5 GHz dengan RAM 16 GB.