Алгоритм сортировки этот вопрос становится в два раза быстрее (!), если включен в gcc (4.7.2). Сильно упрощенный C-код этого вопроса (оказалось, что я могу инициализировать массив со всеми нулями, странное поведение производительности остается, но это делает рассуждение намного проще):
#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]);
}
После долгой игры с флагами оптимизации оказалось, что -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.1s)
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 <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;
}
Интересующие петли:
Это будет обозначаться как cmov
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
Это будет обозначаться как no cmov, флаг -fno-if-conversion был указан Turix в его ответе.
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
Разница бок о бок
cmpl %edx, (%rbx,%rax,4) | cmpl %edx, (%rbx,%rax,4)
movslq %eax, %rdx | jge .L28
cmovl %rdx, %rbp | movslq %eax, %rbp
| .L28:
Время выполнения как функция параметра Бернулли p
Код с инструкцией cmov абсолютно нечувствителен к p. Код без инструкции cmov является победителем, если p<0.26 или 0.81<p и не более 4.38x быстрее (p=1). Конечно, худшая ситуация для предсказателя ветвления составляет около p=0.5, где код на 1.58x медленнее, чем код с инструкцией cmov.
