Zastąpienie 32-bitowego licznika pętli 64-bitowym wprowadza szalone odchylenia wydajności

Zakodowałem odpowiedni program C do eksperymentu i mogę potwierdzić to dziwne zachowanie. Co więcej, gcc uważa 64-bitową liczbę całkowitą (która i tak powinna być size_t...) być lepszym, ponieważ użycie uint_fast32_t powoduje, że gcc używa 64-bitowego uint.

Trochę pofatygowałem się z montażem:
Po prostu weź 32-bitową wersję, Zamień wszystkie 32-bitowe instrukcje/rejestry na 64-bitową wersję w wewnętrznej pętli popcount programu. Uwaga: kod jest tak jak szybka jak wersja 32-bitowa!

Jest to oczywiście hack, ponieważ rozmiar zmiennej nie jest tak naprawdę 64-bitowy, ponieważ inne części programu nadal używają wersji 32-bitowej, ale tak długo, jak wewnętrzna pętla popcount dominuje nad wydajnością, jest to dobry początek.

Następnie skopiowałem kod wewnętrznej pętli z 32-bitowej wersji programu, zhakowałem go do 64-bitowej, majstrowałem z rejestrami, aby zastąpić wewnętrzną pętlę wersji 64-bitowej. Ten kod działa również jako szybki jak wersja 32-bitowa.

Mój wniosek jest taki, że jest to złe planowanie instrukcji przez kompilator, a nie rzeczywista zaleta szybkości / opóźnienia instrukcji 32-bitowych.

(Zastrzeżenie: zhakowałem montaż, mogłem coś zepsuć nie zauważając. Nie sądzę.)

To nie jest odpowiedź, ale trudno ją odczytać, jeśli umieszczę wyniki w komentarzu.

Otrzymuję te wyniki z Mac Pro (Westmere 6-rdzenie Xeon 3,33 GHz). Skompilowałem go za pomocą clang -O3 -msse4 -lstdc++ a.cpp -o a (- O2 uzyskać ten sam wynik).

Clang with uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

Clang with uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

Próbowałem też:

1. Odwróć kolejność testu, wynik jest taki sam, więc wyklucza współczynnik bufora.
2. mieć for twierdzenie odwrotne: for (uint64_t i=size/8;i>0;i-=4). Daje to ten sam wynik i dowodzi, że kompilacja jest wystarczająco inteligentna, aby nie dzielić rozmiaru przez 8 każdej iteracji (zgodnie z oczekiwaniami).

Oto moje Dzikie przypuszczenie:

Współczynnik prędkości składa się z trzech części:

• Code cache: uint64_t wersja ma większy rozmiar kodu, ale nie ma to wpływu na mój procesor Xeon. To sprawia, że wersja 64-bitowa jest wolniejsza.

• Użyte instrukcje. Uwaga nie tylko liczba pętli, ale bufor jest dostępny z 32-bitowym i 64-bitowy indeks dwóch wersji. Dostęp do wskaźnika z przesunięciem 64-bitowym wymaga dedykowanego rejestru i adresowania 64-bitowego, podczas gdy możesz użyć natychmiastowego przesunięcia 32-bitowego. Może to sprawić, że wersja 32-bitowa będzie szybsza.

• Instrukcje są emitowane tylko na kompilacji 64-bitowej (czyli prefetch). To sprawia, że 64-bit jest szybszy.

Te trzy czynniki razem pasują do obserwowanych pozornie sprzecznych wyników.

Nie mogę dać mi wiarygodnej odpowiedzi, ale podać przegląd prawdopodobnej przyczyny. to odniesienie pokazuje dość wyraźnie, że dla instrukcji w ciele pętli istnieje stosunek 3:1 między opóźnieniem a przepustowością. Pokazuje również efekty wielokrotnej wysyłki. Ponieważ w nowoczesnych procesorach x86 istnieją (dawać-lub-brać) trzy jednostki całkowite, generalnie możliwe jest wysłanie trzech instrukcji na cykl.

Więc między szczytowym rurociągiem a wielokrotnym wysyłaniem wydajność i awaria tych mechanizmów, mamy czynnik sześciu w wydajności. Powszechnie wiadomo, że złożoność zestawu instrukcji x86 sprawia, że dość łatwo dochodzi do dziwacznego pęknięcia. Powyższy dokument ma świetny przykład:

[1]}Wydajność Pentium 4 dla 64-bitowych prawych zmian jest naprawdę słaba. 64-bitowy lewy shift, jak również wszystkie 32-bitowe zmiany mają akceptowalną wydajność. Wygląda na to, że ścieżka danych z górnych 32 bitów do dolnych 32 bitów ALU nie jest dobrze zaprojektowane.

Osobiście natknąłem się na dziwny przypadek, w którym gorąca pętla działała znacznie wolniej na konkretnym rdzeniu czterordzeniowego układu (AMD, jeśli dobrze pamiętam). W rzeczywistości uzyskaliśmy lepszą wydajność na mapie-zmniejszyliśmy obliczenia, wyłączając rdzeń.

Tutaj domyślam się twierdzenia o jednostkach całkowitych: że popcnt, licznik pętli i obliczenia adresów mogą ledwo działać z pełną prędkością z 32-bitowym licznikiem szerokości, ale licznik 64-bitowy powoduje niezgodność i potoki stragany. Ponieważ w sumie jest tylko około 12 cykli, potencjalnie 4 cykle z wieloma wysyłkami, Na wykonanie korpusu pętli, pojedyncze stoisko może rozsądnie wpłynąć na czas pracy przez współczynnik 2.

Zmiana wywołana przez użycie zmiennej statycznej, która, jak zgaduję, powoduje drobną zmianę kolejności instrukcji, jest kolejną wskazówką, że 32-bitowy kod jest w pewnym punkcie krytycznym dla twierdzenia.

Próbowałem tego z Visual Studio 2013 Express, używając wskaźnika zamiast indeksu, co nieco przyspieszyło proces. Podejrzewam, że to dlatego, że adresowanie jest offset + register, zamiast offset + register + (register

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

Kod zestawu: r10 = bfrptr, r15 = bfrend, rsi = count, rdi = buffer , R13 = k:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main

Próbowałeś przejść do GCC?

Otrzymuję następujące wyniki z tymi dodatkowymi optymalizacjami:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

Próbowałeś przesunąć krok redukcji poza pętlę? W tej chwili masz zależność od danych, która naprawdę nie jest potrzebna.

Try:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

Masz też dziwne aliasing, który nie jestem pewien, czy jest zgodny ze ścisłymi zasadami aliasingu.

TL;DR: zamiast tego użyj __builtin wewnętrznych.

Udało mi się zrobić gcc 4.8.4 (a nawet 4.7.3 na gcc.godbolt.org) wygenerować optymalny kod za pomocą __builtin_popcountll, który używa tej samej instrukcji asemblera, ale nie ma tego fałszywego błędu zależności.

Nie jestem w 100% pewien mojego kodu porównawczego, ale objdump wyjście wydaje się dzielić moje poglądy. Używam innych tricków (++i vs i++) aby kompilator rozwijał pętlę dla mnie bez instrukcji movl (dziwne zachowanie, muszę powiedz).

Wyniki:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

Kod porównawczy:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

Opcje kompilacji:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

Wersja GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Wersja jądra Linuksa:

3.19.0-58-generic

Informacje o procesorze:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management: