Algorytm sortowaniato pytanie staje się dwukrotnie szybszy (!) jeśli-fprofile-arcs jest włączone w gcc (4.7.2). Znacznie uproszczony kod C tego pytania (okazało się, że mogę zainicjować tablicę z wszystkimi zerami, dziwne zachowanie wydajności pozostaje, ale sprawia, że ​​rozumowanie jest znacznie prostsze):

#include <time.h>
#include <stdio.h>

#define ELEMENTS 100000

int main() {
  int a[ELEMENTS] = { 0 };
  clock_t start = clock();
  for (int i = 0; i < ELEMENTS; ++i) {
    int lowerElementIndex = i;
    for (int j = i+1; j < ELEMENTS; ++j) {
      if (a[j] < a[lowerElementIndex]) {
        lowerElementIndex = j;
      }
    }
    int tmp = a[i];
    a[i] = a[lowerElementIndex];
    a[lowerElementIndex] = tmp;
  } 
  clock_t end = clock();
  float timeExec = (float)(end - start) / CLOCKS_PER_SEC;
  printf("Time: %2.3f\n", timeExec);
  printf("ignore this line %d\n", a[ELEMENTS-1]);
}

Po długim czasie gry z flagami optymalizacji okazało się, że tak jest-ftree-vectorize również daje to dziwne zachowanie, więc możemy je przyjąć-fprofile-arcs bez dyskusji. Po profilowaniu za pomocąperf Znalazłem tojedyną istotną różnicą jest:

Szybka sprawagcc -std=c99 -O2 simp.c (działa w 3.1s)

    cmpl    %esi, %ecx
    jge .L3
    movl    %ecx, %esi
    movslq  %edx, %rdi
.L3:

Powolny przypadekgcc -std=c99 -O2 -ftree-vectorize simp.c (działa w 6.1s)

    cmpl    %ecx, %esi
    cmovl   %edx, %edi
    cmovl   %esi, %ecx

Jeśli chodzi o pierwszy fragment: Biorąc pod uwagę, że tablica zawiera tylko zera, zawsze przeskakujemy do.L3. To może bardzo skorzystać z przewidywania oddziałów.

Myślęcmovl instrukcje nie mogą korzystać z przewidywania oddziałów.

Pytania:

Czy wszystkie moje powyższe przypuszczenia są prawidłowe? Czy to sprawia, że ​​algorytm jest wolny?

Jeśli tak, jak mogę zapobiec wysyłaniu tej instrukcji przez gcc (inne niż trywialne-fno-tree-vectorization obejście oczywiście), ale nadal wykonujesz jak najwięcej optymalizacji?

Co to jest-ftree-vectorization? Dokumentacja jest dość niejasne, potrzebowałbym trochę więcej wyjaśnień, aby zrozumieć, co się dzieje.

Aktualizacja: Od momentu pojawienia się w komentarzach: Dziwne zachowanie wydajności w.r.t.-ftree-vectorize flaga pozostaje z losowymi danymi.Jak wskazuje YakkW celu dokonania selekcji trudno jest stworzyć zestaw danych, który spowodowałby wiele nieprawidłowości w branży.

Odkąd się pojawił: mam procesor Core i5.

Na podstawie komentarza Yakka, Stworzyłem test. Kod poniżej (online bez doładowania) oczywiście nie jest już algorytmem sortowania; Wyjąłem tylko wewnętrzną pętlę. Jego jedynym celem jest zbadanie wpływu przewidywania gałęzi:Pomijamyif oddział wfor pętla z prawdopodobieństwemp.

#include <algorithm>
#include <cstdio>
#include <random>
#include <boost/chrono.hpp>
using namespace std;
using namespace boost::chrono;
constexpr int ELEMENTS=1e+8; 
constexpr double p = 0.50;

int main() {
  printf("p = %.2f\n", p);
  int* a = new int[ELEMENTS];
  mt19937 mt(1759);
  bernoulli_distribution rnd(p);
  for (int i = 0 ; i < ELEMENTS; ++i){
    a[i] = rnd(mt)? i : -i;
  }
  auto start = high_resolution_clock::now();
  int lowerElementIndex = 0;
  for (int i=0; i<ELEMENTS; ++i) {
    if (a[i] < a[lowerElementIndex]) {
      lowerElementIndex = i;
    }
  } 
  auto finish = high_resolution_clock::now();
  printf("%ld  ms\n", duration_cast<milliseconds>(finish-start).count());
  printf("Ignore this line   %d\n", a[lowerElementIndex]);
  delete[] a;
}

Pętle zainteresowania:

Będzie to określane jakocmov

g++ -std=c++11 -O2 -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L30:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    movslq  %eax, %rdx
    cmovl   %rdx, %rbp
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L30

Będzie to określane jakonie cmov, the-fno-if-conversion flaga została wskazana przezTurix w swojej odpowiedzi.

g++ -std=c++11 -O2 -fno-if-conversion -lboost_chrono -lboost_system -lrt branch3.cpp

    xorl    %eax, %eax
.L29:
    movl    (%rbx,%rbp,4), %edx
    cmpl    %edx, (%rbx,%rax,4)
    jge .L28
    movslq  %eax, %rbp
.L28:
    addq    $1, %rax
    cmpq    $100000000, %rax
    jne .L29

Różnica obok siebie

cmpl    %edx, (%rbx,%rax,4) |     cmpl  %edx, (%rbx,%rax,4)
movslq  %eax, %rdx          |     jge   .L28
cmovl   %rdx, %rbp          |     movslq    %eax, %rbp
                            | .L28:

Czas wykonania jako funkcja parametru Bernoulliegop

Kod zcmov instrukcja jest absolutnie niewrażliwa nap. Kodbez cmov instrukcja jest zwycięzcą, jeślip<0.26 lub0.81<p i jest najwyżej 4,38x szybszy (p=1). Oczywiście, gorsza sytuacja dla predyktora gałęzi jest w okolicachp=0.5 gdzie kod jest 1,58x wolniejszy niż kod zcmov instrukcja.