Почему векторизация дерева делает этот алгоритм сортировки в 2 раза медленнее?
Алгоритм сортировкиэтот вопрос становится в два раза быстрее (!), если-fprofile-arcs
включен в 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.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 <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
Это будет упоминаться какнет смов,-fno-if-conversion
флаг был отмеченТурикс в своем ответе.
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,38 раза быстрее (p=1
). Конечно, худшая ситуация для предсказателя отрасли находится на уровнеp=0.5
где код в 1,58 раза медленнее, чем код сcmov
инструкция.