Mengapa penjumlahan yang dikelompokkan lebih lambat dengan grup yang disortir daripada grup yang tidak disortir?

27

Saya memiliki 2 kolom bilangan bulat terbatas tab, yang pertama adalah bilangan bulat acak, yang kedua adalah bilangan bulat yang mengidentifikasi grup, yang dapat dihasilkan oleh program ini. ( generate_groups.cc)

#include <cstdlib>
#include <iostream>
#include <ctime>

int main(int argc, char* argv[]) {
  int num_values = atoi(argv[1]);
  int num_groups = atoi(argv[2]);

  int group_size = num_values / num_groups;
  int group = -1;

  std::srand(42);

  for (int i = 0; i < num_values; ++i) {
    if (i % group_size == 0) {
      ++group;
    }
    std::cout << std::rand() << '\t' << group << '\n';
  }

  return 0;
}

Saya kemudian menggunakan program kedua ( sum_groups.cc) untuk menghitung jumlah per grup.

#include <iostream>
#include <chrono>
#include <vector>

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[p_g[i]] += p_x[i];
  }
}

int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums;

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group > n_groups) {
      n_groups = group;
    }
  }
  sums.resize(n_groups);

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  for (int i = 0; i < 10; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sums.data());
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << std::endl;

  return 0;
}

Jika saya kemudian menjalankan program-program ini pada dataset dengan ukuran tertentu, dan kemudian mengacak urutan baris dari dataset yang sama, data yang dikocok menghitung jumlah ~ 2x atau lebih cepat dari data yang dipesan.

g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006

Saya berharap data asli yang diurutkan berdasarkan kelompok memiliki lokalitas data yang lebih baik dan lebih cepat, tetapi saya mengamati perilaku yang berlawanan. Saya bertanya-tanya apakah ada yang bisa membuat hipotesis alasannya?

c++ performance Jim
sumber
1
Saya tidak tahu, tetapi Anda menulis ke elemen di luar kisaran jumlah vektor - jika Anda melakukan hal yang normal dan meneruskan referensi ke vektor alih-alih petunjuk ke elemen data, dan kemudian digunakan .at()atau mode debug operator[]yang tidak dibatasi memeriksa Anda akan melihat.
Shawn
Sudahkah Anda memverifikasi bahwa file "groups2" memiliki semua data Anda di dalamnya, dan itu semua sedang dibaca dan diproses? Apakah mungkin ada karakter EOF di tengah suatu tempat?
1201ProgramAlarm
2
Program ini memiliki perilaku yang tidak terdefinisi karena Anda tidak pernah mengubah ukuran sum. Alih-alih sums.reserve(n_groups);Anda harus menelepon sums.resize(n_groups);- itulah yang mengisyaratkan @Shawn.
Eugene
1
Perhatikan (lihat misalnya di sini atau di sini ) bahwa vektor pasangan, alih-alih dua vektor (nilai dan grup), berperilaku seperti yang diharapkan.
Bob__
1
Anda mengurutkan data berdasarkan nilainya, kan? Tapi kemudian itu juga memilah kelompok, dan itu berdampak pada tekanan p_out[p_g[i]] += p_x[i];. Mungkin dalam urutan acak asli, grup sebenarnya menunjukkan pengelompokan yang baik sehubungan dengan akses ke p_outarray. Mengurutkan nilai-nilai mungkin menyebabkan pola akses indeks-kelompok yang buruk p_out.
Kaz

Jawaban:

33

Pengaturan / membuatnya lambat

Pertama-tama, program berjalan dalam waktu yang hampir bersamaan terlepas dari:

sumspeed$ time ./sum_groups < groups_shuffled 
11558358

real    0m0.705s
user    0m0.692s
sys 0m0.013s

sumspeed$ time ./sum_groups < groups_sorted
24986825

real    0m0.722s
user    0m0.711s
sys 0m0.012s

Sebagian besar waktu dihabiskan di loop input. Tapi karena kita tertarik pada grouped_sum(), mari abaikan itu.

Mengubah loop tolok ukur dari 10 menjadi 1000 iterasi, grouped_sum()mulai mendominasi waktu berjalan:

sumspeed$ time ./sum_groups < groups_shuffled 
1131838420

real    0m1.828s
user    0m1.811s
sys 0m0.016s

sumspeed$ time ./sum_groups < groups_sorted
2494032110

real    0m3.189s
user    0m3.169s
sys 0m0.016s

perf diff

Sekarang kita dapat menggunakan perfuntuk menemukan tempat terpanas di program kami.

sumspeed$ perf record ./sum_groups < groups_shuffled
1166805982
[ perf record: Woken up 1 times to write data ]
[kernel.kallsyms] with build id 3a2171019937a2070663f3b6419330223bd64e96 not found, continuing without symbols
Warning:
Processed 4636 samples and lost 6.95% samples!

[ perf record: Captured and wrote 0.176 MB perf.data (4314 samples) ]

sumspeed$ perf record ./sum_groups < groups_sorted
2571547832
[ perf record: Woken up 2 times to write data ]
[kernel.kallsyms] with build id 3a2171019937a2070663f3b6419330223bd64e96 not found, continuing without symbols
[ perf record: Captured and wrote 0.420 MB perf.data (10775 samples) ]

Dan perbedaan di antara mereka:

sumspeed$ perf diff
[...]
# Event 'cycles:uppp'
#
# Baseline  Delta Abs  Shared Object        Symbol                                                                  
# ........  .........  ...................  ........................................................................
#
    57.99%    +26.33%  sum_groups           [.] main
    12.10%     -7.41%  libc-2.23.so         [.] _IO_getc
     9.82%     -6.40%  libstdc++.so.6.0.21  [.] std::num_get<char, std::istreambuf_iterator<char, std::char_traits<c
     6.45%     -4.00%  libc-2.23.so         [.] _IO_ungetc
     2.40%     -1.32%  libc-2.23.so         [.] _IO_sputbackc
     1.65%     -1.21%  libstdc++.so.6.0.21  [.] 0x00000000000dc4a4
     1.57%     -1.20%  libc-2.23.so         [.] _IO_fflush
     1.71%     -1.07%  libstdc++.so.6.0.21  [.] std::istream::sentry::sentry
     1.22%     -0.77%  libstdc++.so.6.0.21  [.] std::istream::operator>>
     0.79%     -0.47%  libstdc++.so.6.0.21  [.] __gnu_cxx::stdio_sync_filebuf<char, std::char_traits<char> >::uflow
[...]

Lebih banyak waktu main(), yang mungkin telah grouped_sum()disimpulkan. Bagus, terima kasih banyak, perf.

perf annotate

Apakah ada perbedaan di mana waktu dihabiskan di dalam main() ?

Dikocok:

sumspeed$ perf annotate -i perf.data.old
[...]
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
       │180:   xor    %eax,%eax
       │       test   %rdi,%rdi
       │     ↓ je     1a4
       │       nop
       │         p_out[p_g[i]] += p_x[i];
  6,88 │190:   movslq (%r9,%rax,4),%rdx
 58,54 │       mov    (%r8,%rax,4),%esi
       │     #include <chrono>
       │     #include <vector>
       │
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
  3,86 │       add    $0x1,%rax
       │         p_out[p_g[i]] += p_x[i];
 29,61 │       add    %esi,(%rcx,%rdx,4)
[...]

Diurutkan:

sumspeed$ perf annotate -i perf.data
[...]
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
       │180:   xor    %eax,%eax
       │       test   %rdi,%rdi
       │     ↓ je     1a4
       │       nop
       │         p_out[p_g[i]] += p_x[i];
  1,00 │190:   movslq (%r9,%rax,4),%rdx
 55,12 │       mov    (%r8,%rax,4),%esi
       │     #include <chrono>
       │     #include <vector>
       │
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
  0,07 │       add    $0x1,%rax
       │         p_out[p_g[i]] += p_x[i];
 43,28 │       add    %esi,(%rcx,%rdx,4)
[...]

Tidak, itu dua instruksi yang sama mendominasi. Jadi mereka membutuhkan waktu lama dalam kedua kasus, tetapi bahkan lebih buruk ketika data diurutkan.

stat perf

Baik. Tetapi kita harus menjalankannya dalam jumlah yang sama, jadi setiap instruksi harus menjadi lebih lambat karena alasan tertentu Mari kita lihat apa yang perf statdikatakan.

sumspeed$ perf stat ./sum_groups < groups_shuffled 
1138880176

 Performance counter stats for './sum_groups':

       1826,232278      task-clock (msec)         #    0,999 CPUs utilized          
                72      context-switches          #    0,039 K/sec                  
                 1      cpu-migrations            #    0,001 K/sec                  
             4 076      page-faults               #    0,002 M/sec                  
     5 403 949 695      cycles                    #    2,959 GHz                    
       930 473 671      stalled-cycles-frontend   #   17,22% frontend cycles idle   
     9 827 685 690      instructions              #    1,82  insn per cycle         
                                                  #    0,09  stalled cycles per insn
     2 086 725 079      branches                  # 1142,639 M/sec                  
         2 069 655      branch-misses             #    0,10% of all branches        

       1,828334373 seconds time elapsed

sumspeed$ perf stat ./sum_groups < groups_sorted
2496546045

 Performance counter stats for './sum_groups':

       3186,100661      task-clock (msec)         #    1,000 CPUs utilized          
                 5      context-switches          #    0,002 K/sec                  
                 0      cpu-migrations            #    0,000 K/sec                  
             4 079      page-faults               #    0,001 M/sec                  
     9 424 565 623      cycles                    #    2,958 GHz                    
     4 955 937 177      stalled-cycles-frontend   #   52,59% frontend cycles idle   
     9 829 009 511      instructions              #    1,04  insn per cycle         
                                                  #    0,50  stalled cycles per insn
     2 086 942 109      branches                  #  655,014 M/sec                  
         2 078 204      branch-misses             #    0,10% of all branches        

       3,186768174 seconds time elapsed

Hanya satu hal yang menonjol: mandek-siklus-frontend .

Oke, pipa instruksi mandek. Di frontend. Tepat apa artinya mungkin bervariasi antara microarchictectures.

Tapi saya punya dugaan. Jika Anda murah hati, Anda mungkin menyebutnya hipotesa.

Hipotesa

Dengan mengurutkan input, Anda meningkatkan lokalitas penulisan. Bahkan, mereka akan sangat lokal; hampir semua penambahan yang Anda lakukan akan menulis ke lokasi yang sama dengan yang sebelumnya.

Itu bagus untuk cache, tetapi tidak bagus untuk pipa. Anda memperkenalkan dependensi data, mencegah agar instruksi tambahan berikutnya tidak dilanjutkan sampai penambahan sebelumnya selesai (atau sebaliknya membuat hasilnya tersedia untuk instruksi selanjutnya )

Itu masalahmu.

Kupikir.

Memperbaikinya

Beberapa vektor penjumlahan

Sebenarnya, mari kita coba sesuatu. Bagaimana jika kita menggunakan beberapa vektor penjumlahan, beralih di antara mereka untuk setiap penambahan, dan kemudian menyimpulkannya di bagian akhir? Harganya sedikit lokalitas, tetapi harus menghapus dependensi data.

(kodenya tidak cantik; jangan menilai saya, internet !!)

#include <iostream>
#include <chrono>
#include <vector>

#ifndef NSUMS
#define NSUMS (4) // must be power of 2 (for masking to work)
#endif

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int** p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[i & (NSUMS-1)][p_g[i]] += p_x[i];
  }
}

int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums[NSUMS];

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group >= n_groups) {
      n_groups = group+1;
    }
  }
  for (int i=0; i<NSUMS; ++i) {
    sums[i].resize(n_groups);
  }

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  int* sumdata[NSUMS];
  for (int i = 0; i < NSUMS; ++i) {
    sumdata[i] = sums[i].data();
  }
  for (int i = 0; i < 1000; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sumdata);
  }
  for (int i = 1; i < NSUMS; ++i) {
    for (int j = 0; j < n_groups; ++j) {
      sumdata[0][j] += sumdata[i][j];
    }
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << " with NSUMS=" << NSUMS << std::endl;

  return 0;
}

(oh, dan saya juga memperbaiki perhitungan n_groups; tidak aktif satu per satu.)

Hasil

Setelah mengkonfigurasi makefile saya untuk memberikan -DNSUMS=...argumen kepada kompiler, saya bisa melakukan ini:

sumspeed$ for n in 1 2 4 8 128; do make -s clean && make -s NSUMS=$n && (perf stat ./sum_groups < groups_shuffled && perf stat ./sum_groups < groups_sorted)  2>&1 | egrep '^[0-9]|frontend'; done
1134557008 with NSUMS=1
       924 611 882      stalled-cycles-frontend   #   17,13% frontend cycles idle   
2513696351 with NSUMS=1
     4 998 203 130      stalled-cycles-frontend   #   52,79% frontend cycles idle   
1116188582 with NSUMS=2
       899 339 154      stalled-cycles-frontend   #   16,83% frontend cycles idle   
1365673326 with NSUMS=2
     1 845 914 269      stalled-cycles-frontend   #   29,97% frontend cycles idle   
1127172852 with NSUMS=4
       902 964 410      stalled-cycles-frontend   #   16,79% frontend cycles idle   
1171849032 with NSUMS=4
     1 007 807 580      stalled-cycles-frontend   #   18,29% frontend cycles idle   
1118732934 with NSUMS=8
       881 371 176      stalled-cycles-frontend   #   16,46% frontend cycles idle   
1129842892 with NSUMS=8
       905 473 182      stalled-cycles-frontend   #   16,80% frontend cycles idle   
1497803734 with NSUMS=128
     1 982 652 954      stalled-cycles-frontend   #   30,63% frontend cycles idle   
1180742299 with NSUMS=128
     1 075 507 514      stalled-cycles-frontend   #   19,39% frontend cycles idle

Jumlah vektor penjumlahan yang optimal mungkin akan tergantung pada kedalaman pipa CPU Anda. CPU ultrabook berusia 7 tahun saya mungkin dapat memaksimalkan pipa dengan vektor yang lebih sedikit daripada yang dibutuhkan CPU desktop mewah.

Jelas, lebih banyak belum tentu lebih baik; ketika saya menjadi gila dengan 128 vektor penjumlahan, kami mulai menderita lebih banyak dari kesalahan cache - sebagaimana dibuktikan oleh input yang diacak menjadi lebih lambat dari yang diurutkan, seperti yang Anda harapkan sebelumnya. Kami telah datang lingkaran penuh! :)

Jumlah per grup dalam daftar

(ini ditambahkan dalam edit)

Agh, kutu buku dikecam ! Jika Anda tahu input Anda akan diurutkan dan mencari kinerja yang lebih banyak lagi, penulisan ulang fungsi berikut (tanpa tambahan jumlah array) bahkan lebih cepat, setidaknya di komputer saya.

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
  int i = n-1;
  while (i >= 0) {
    int g = p_g[i];
    int gsum = 0;
    do {
      gsum += p_x[i--];
    } while (i >= 0 && p_g[i] == g);
    p_out[g] += gsum;
  }
}

Trik yang satu ini adalah memungkinkan kompiler menyimpan gsumvariabel, jumlah grup, dalam register. Saya menduga (tetapi mungkin sangat salah) bahwa ini lebih cepat karena loop umpan balik dalam pipa bisa lebih pendek di sini, dan / atau lebih sedikit memori yang diakses. Prediktor cabang yang baik akan membuat pemeriksaan ekstra untuk kesetaraan grup menjadi murah.

Hasil

Mengerikan untuk input yang diacak ...

sumspeed$ time ./sum_groups < groups_shuffled
2236354315

real    0m2.932s
user    0m2.923s
sys 0m0.009s

... tetapi sekitar 40% lebih cepat daripada solusi "banyak jumlah" saya untuk input yang diurutkan.

sumspeed$ time ./sum_groups < groups_sorted
809694018

real    0m1.501s
user    0m1.496s
sys 0m0.005s

Banyak grup kecil akan lebih lambat daripada yang besar, jadi apakah ini implementasi yang lebih cepat atau tidak akan sangat tergantung pada data Anda di sini. Dan, seperti biasa, pada model CPU Anda.

Beberapa vektor penjumlahan, dengan offset alih-alih bit masking

Sopel menyarankan empat tambahan yang tidak gulungan sebagai alternatif dari pendekatan masking bit saya. Saya telah mengimplementasikan versi umum dari saran mereka, yang dapat menangani hal yang berbeda NSUMS. Saya mengandalkan kompiler membuka gulungan lingkaran dalam untuk kita (yang memang, setidaknya untuk NSUMS=4).

#include <iostream>
#include <chrono>
#include <vector>

#ifndef NSUMS
#define NSUMS (4) // must be power of 2 (for masking to work)
#endif

#ifndef INNER
#define INNER (0)
#endif
#if INNER
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int** p_out) {
  size_t i = 0;
  int quadend = n & ~(NSUMS-1);
  for (; i < quadend; i += NSUMS) {
    for (int k=0; k<NSUMS; ++k) {
      p_out[k][p_g[i+k]] += p_x[i+k];
    }
  }
  for (; i < n; ++i) {
    p_out[0][p_g[i]] += p_x[i];
  }
}
#else
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int** p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[i & (NSUMS-1)][p_g[i]] += p_x[i];
  }
}
#endif


int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums[NSUMS];

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group >= n_groups) {
      n_groups = group+1;
    }
  }
  for (int i=0; i<NSUMS; ++i) {
    sums[i].resize(n_groups);
  }

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  int* sumdata[NSUMS];
  for (int i = 0; i < NSUMS; ++i) {
    sumdata[i] = sums[i].data();
  }
  for (int i = 0; i < 1000; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sumdata);
  }
  for (int i = 1; i < NSUMS; ++i) {
    for (int j = 0; j < n_groups; ++j) {
      sumdata[0][j] += sumdata[i][j];
    }
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << " with NSUMS=" << NSUMS << ", INNER=" << INNER << std::endl;

  return 0;
}

Hasil

Waktu untuk mengukur. Perhatikan bahwa karena saya bekerja di / tmp kemarin, saya tidak memiliki data input yang sama persis. Oleh karena itu, hasil ini tidak dapat dibandingkan secara langsung dengan yang sebelumnya (tetapi mungkin cukup dekat).

sumspeed$ for n in 2 4 8 16; do for inner in 0 1; do make -s clean && make -s NSUMS=$n INNER=$inner && (perf stat ./sum_groups < groups_shuffled && perf stat ./sum_groups < groups_sorted)  2>&1 | egrep '^[0-9]|frontend'; done; done1130558787 with NSUMS=2, INNER=0
       915 158 411      stalled-cycles-frontend   #   16,96% frontend cycles idle   
1351420957 with NSUMS=2, INNER=0
     1 589 408 901      stalled-cycles-frontend   #   26,21% frontend cycles idle   
840071512 with NSUMS=2, INNER=1
     1 053 982 259      stalled-cycles-frontend   #   23,26% frontend cycles idle   
1391591981 with NSUMS=2, INNER=1
     2 830 348 854      stalled-cycles-frontend   #   45,35% frontend cycles idle   
1110302654 with NSUMS=4, INNER=0
       890 869 892      stalled-cycles-frontend   #   16,68% frontend cycles idle   
1145175062 with NSUMS=4, INNER=0
       948 879 882      stalled-cycles-frontend   #   17,40% frontend cycles idle   
822954895 with NSUMS=4, INNER=1
     1 253 110 503      stalled-cycles-frontend   #   28,01% frontend cycles idle   
929548505 with NSUMS=4, INNER=1
     1 422 753 793      stalled-cycles-frontend   #   30,32% frontend cycles idle   
1128735412 with NSUMS=8, INNER=0
       921 158 397      stalled-cycles-frontend   #   17,13% frontend cycles idle   
1120606464 with NSUMS=8, INNER=0
       891 960 711      stalled-cycles-frontend   #   16,59% frontend cycles idle   
800789776 with NSUMS=8, INNER=1
     1 204 516 303      stalled-cycles-frontend   #   27,25% frontend cycles idle   
805223528 with NSUMS=8, INNER=1
     1 222 383 317      stalled-cycles-frontend   #   27,52% frontend cycles idle   
1121644613 with NSUMS=16, INNER=0
       886 781 824      stalled-cycles-frontend   #   16,54% frontend cycles idle   
1108977946 with NSUMS=16, INNER=0
       860 600 975      stalled-cycles-frontend   #   16,13% frontend cycles idle   
911365998 with NSUMS=16, INNER=1
     1 494 671 476      stalled-cycles-frontend   #   31,54% frontend cycles idle   
898729229 with NSUMS=16, INNER=1
     1 474 745 548      stalled-cycles-frontend   #   31,24% frontend cycles idle

Yup, loop dalam NSUMS=8adalah yang tercepat di komputer saya. Dibandingkan dengan pendekatan "gsum lokal" saya, itu juga memiliki manfaat tambahan untuk tidak menjadi buruk bagi input yang dikocok.

Menarik untuk dicatat: NSUMS=16menjadi lebih buruk daripada NSUMS=8. Ini bisa jadi karena kita mulai melihat lebih banyak cache yang hilang, atau karena kita tidak memiliki cukup register untuk membuka gulungan lingkaran dalam dengan benar.

Snild Dolkow
sumber
5
Ini sangat menyenangkan. :)
Snild Dolkow
3
Itu luar biasa! Tidak tahu perf.
Tanveer Badar
1
Saya ingin tahu apakah dalam pendekatan pertama Anda membuka gulungan 4x secara manual dengan 4 akumulator berbeda akan menghasilkan kinerja yang lebih baik. Sesuatu seperti godbolt.org/z/S-PhFm
Sopel
Terima kasih untuk sarannya. Ya, itu meningkatkan kinerja, dan saya telah menambahkannya ke jawabannya.
Snild Dolkow
Terima kasih! Saya telah mempertimbangkan sesuatu seperti ini mungkin kemungkinan tetapi tidak tahu bagaimana cara menentukannya, terima kasih atas jawaban terperinci Anda!
Jim
3

Inilah sebabnya mengapa kelompok yang disortir lebih lambat daripada kelompok yang tidak disentuh;

Pertama di sini adalah kode rakitan untuk menjumlahkan loop:

008512C3  mov         ecx,dword ptr [eax+ebx]
008512C6  lea         eax,[eax+4]
008512C9  lea         edx,[esi+ecx*4] // &sums[groups[i]]
008512CC  mov         ecx,dword ptr [eax-4] // values[i]
008512CF  add         dword ptr [edx],ecx // sums[groups[i]]+=values[i]
008512D1  sub         edi,1
008512D4  jne         main+163h (08512C3h)

Mari kita lihat instruksi add yang merupakan alasan utama untuk masalah ini;

008512CF  add         dword ptr [edx],ecx // sums[groups[i]]+=values[i]

Saat prosesor terlebih dahulu menjalankan instruksi ini, prosesor akan mengeluarkan memori read (load) request ke alamat di edx kemudian menambahkan nilai ecx kemudian mengeluarkan write (store) request untuk alamat yang sama.

ada fitur dalam memori pemanggil prosesor menyusun ulang

Untuk memungkinkan optimalisasi kinerja pelaksanaan instruksi, arsitektur IA-32 memungkinkan penyimpangan dari model Strongordering yang disebut pemesanan prosesor di Pentium 4, Intel Xeon, dan prosesor keluarga P6. Variasi pengaturan prosesor ini (disebut model pemesanan memori) memungkinkan operasi peningkatan kinerja seperti memungkinkan pembacaan untuk melanjutkan penulisan buffered. Tujuan dari salah satu variasi ini adalah untuk meningkatkan kecepatan eksekusi instruksi, sambil mempertahankan koherensi memori, bahkan dalam sistem multi-prosesor.

dan ada aturannya

Membaca dapat disusun ulang dengan penulisan yang lebih lama ke lokasi yang berbeda tetapi tidak dengan penulisan yang lebih tua ke lokasi yang sama.

Jadi jika iterasi berikutnya mencapai instruksi tambah sebelum permintaan tulis selesai, ia tidak akan menunggu jika alamat edx berbeda dari nilai sebelumnya dan mengeluarkan permintaan baca dan memesan ulang atas permintaan menulis yang lebih lama dan instruksi tambahkan berlanjut. tetapi jika alamatnya sama, instruksi add akan menunggu sampai penulisan lama selesai.

Perhatikan bahwa loop pendek dan prosesor dapat menjalankannya lebih cepat daripada pengontrol memori menyelesaikan permintaan tulis ke memori.

jadi untuk grup yang diurutkan Anda akan membaca dan menulis dari alamat yang sama berkali-kali secara berurutan sehingga akan kehilangan peningkatan kinerja menggunakan memori yang dipesan ulang; sementara itu jika grup acak digunakan maka setiap iterasi akan memiliki alamat yang mungkin berbeda sehingga pembacaan tidak akan menunggu lebih lama tulis dan disusun ulang sebelum itu; tambah instruksi tidak akan menunggu yang sebelumnya pergi.

Ahmed Anter
sumber