Алгоритм сортировкиэтот вопрос становится в два раза быстрее (!), если-fprofile-arcs включен в gcc (4.7.2). Сильно упрощенный C-код этого вопроса (оказалось, что я могу инициализировать массив со всеми нулями, странное поведение производительности остается, но это значительно упрощает процесс рассуждения):

#include 
#include 

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

После долгой игры с флагами оптимизации выяснилось, что-ftree-vectorize также дает это странное поведение, чтобы мы могли взять-fprofile-arcs вне вопроса. После профилирования сperf Я обнаружил, чтоединственная существенная разница:

Быстрый случайgcc -std=c99 -O2 simp.c (работает в 3.1s)

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

Медленный случайgcc -std=c99 -O2 -ftree-vectorize simp.c (работает в 6.1с)

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

Что касается первого фрагмента: учитывая, что массив содержит только нули, мы всегда переходим к.L3, Это может очень выиграть от предсказания ветвления.

Я думаю,cmovl инструкции не могут извлечь выгоду из предсказания ветвления.

Вопросы:

Все мои предположения верны? Делает ли это алгоритм медленным?

Если да, как я могу помешать gcc выдать эту инструкцию (кроме тривиальной-fno-tree-vectorization Обходной путь, конечно), но все еще проводите как можно больше оптимизаций?

Что это ?-ftree-vectorizationДокументация довольно расплывчато, мне нужно немного больше объяснений, чтобы понять, чтопроисходит

Обновить: Так как это появилось в комментариях: странное поведение производительности w.r.t.-ftree-vectorize флаг остается со случайными данными.Как указывает Яккдля сортировки выбора на самом деле сложно создать набор данных, который привел бы ко многим ошибочным прогнозам ветвей.

Так как это также подошло: у меня есть процессор Core i5.

По мотивам ЯккакомментарийЯ создал тест. Код ниже (онлайн без повышения), конечно, больше не алгоритм сортировки; Я только вынул внутреннюю петлю. Его единственная цель состоит в том, чтобы изучить эффект предсказания ветвлений:Мы пропускаемif филиал вfor цикл с вероятностью.p

#include 
#include 
#include 
#include 
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