Мотивация
Среди программистов, особенно тех, кто учился программировать где-то в конце 90-х, до сих пор живо стойкое убеждение, что алгоритм без ветвлений лучше, чем алгоритм с ветвлениями. Я нередко встречал чрезвычайную фанатичность в попытках реализовать ряд простых функций без ветвлений только из-за того, что программисту кажется, будто так будет эффективнее. Среди таких простых функций я особо выделил пока четыре: знак числа, абсолютное значение числа, минимум и максимум (в двух вариантах: для чисел со знаком и без знака). Если мой эксперимент окажется удачным, я возьмусь и за многие другие алгоритмы.
Правда, что без IF быстрее?
Нет, это неправда. Если быть более точным, то избавление от ветвлений может как дать прирост скорости, так и усугубить ситуацию в несколько раз. Всё зависит от конкретной машины, на которой данный код будет исполняться, и от компилятора. Приведу в качестве примера свой старый компьютер Core 2 Duo E8400 @3ГГц – на нём все предложенные функции работают быстрее в варианте с IF, когда данные подаются упорядоченно и ситуация может стать обратной при хаотичной подаче (подробности ниже). Компилятор у меня VC++ 2015, опция компиляции /Ox.
Давайте рассмотрим чуть подробнее те функции, что я предлагаю протестировать. Каждая из четырёх функций может быть написана полудюжиной вариантов, все из которых Вы можете изучить самостоятельно по ссылкам [1-7] в конце статьи. Все эти варианты я уже тестировал и выбрал для каждой функции два: классический и какой-либо без ветвлений (наилучший по моим измерениям). Если, опять же, мой эксперимент окажется удачным, я проведу похожее сравнение вообще всех известных мне вариантов [4-7].
Для начала я ввожу свои псевдонимы для типов данных и константу для сдвига:
typedef int32_t i32;
typedef uint32_t u32;
typedef int8_t sign_t;
const u32 SHIFT = 31;
Знак числа – sign
Классический вариант реализуется несложной схемой из условий:
sign_t sign0 (i32 a) {
if (a>0) return +1;
if (a<0) return -1;
return 0;
}
Наилучший вариант без ветвлений выглядит следующим образом:
sign_t sign1 (i32 a) {
return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
}
Да, здесь используется знаковый сдвиг и то тот факт, что отрицательные числа кодируются дополнительным кодом. Поэтому здесь мы имеем важное ограничение нашего эксперимента: у Вас на машине должен быть знаковый сдвиг и дополнительный код.
На моём процессоре разница между этими двумя функциями весьма заметна. Я прогнал их на всех возможных числах из рабочего диапазона и первая сработала за 2,87 секунды, а вторая только за 3,97 при упорядоченной подаче чисел и 13,02 vs 1,26 при хаотичной.
Абсолютное значение – abs
Здесь ситуация несколько лучше. Первая функция с IF, может выглядеть, например, вот так:
u32 abs0 (i32 a) {
if (a<0) return -a;
return a;
}
А без ветвления самый лучший (на мой взгляд) вариант имеет вид:
u32 abs1 (i32 a) {
const i32 b = a >> SHIFT;
return (a+b) ^ b;
}
Время работы первой 2,29, а второй — 2,33 при упорядоченной подаче и 12,01 vs 0,81 при хаотичной. Прошу обратить внимание: программист часто не знает, что компилятор может сам сделать код без ветвлений для abs, который будет по логике полностью совпадать со вторым вариантом [3]. Таким образом, если в программе есть IF, это не значит, что после компиляции ветвление останется. Мой компилятор генерирует код с ветвлением.
Минимум и максимум со знаком — mini и maxi
Кому-то может показаться, что классический вариант таких функции будет выглядеть вот так:
i32 mini0 (i32 a, i32 b) {
return a<b ? a:b;
}
i32 maxi0 (i32 a, i32 b) {
return a>b ? a:b;
}
На самом деле (и для меня это совершенно непонятно) вот такой вариант в полтора раза быстрее:
i32 mini0 (i32 a, i32 b) {
return a>b ? b:a;
}
i32 maxi0 (i32 a, i32 b) {
return a<b ? b:a;
}
Я обнаружил это, когда сравнивал разные варианты реализации, но конкретного ответа так и не нашёл. Когда смотрел ассемблерный листинг, то обнаружил, что разница только в порядке сравнения (a сравниваем с b, или наоборот). Подозреваю, что всё дело в микроархитектуре процессора. Аналогично, я замечал уже, что команда inc ecx работает значительно медленнее, чем lea eax, [eax+1], что тоже непонятно как можно объяснить, если не кривизной микроархитектуры.
Вариант без ветвлений для функций минимума и максимума в моём репертуаре только один (который корректно работает для всех возможных входных данных):
i32 mini1 (i32 a, i32 b) {
i32 d = a-b;
return a - (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}
i32 maxi1 (i32 a, i32 b) {
i32 d = a-b;
return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT));
}
Здесь разница колоссальная. Первая серия функций работает около 3,5 секунд, вторая – около 9 на последовательных данных и 2 секунды vs 6 секунд на хаотичных. Разница почти втрое в обоих случаях.
Дело в том, что в архитектуре x86 существует команда cmovl, которая как раз позволяет компилятору создать в первом случае код без ветвлений. Таким образом, получается, что на языке Си у нас ветвление есть, а реально его нет. Программист, который любой ценой хочет избавиться от ветвлений, не всегда знает, что компилятор может сделать это лучше него, если посчитает нужным.
Минимум и максимум без знака — minu и maxu
Классический вариант не меняется, кроме замены i32 на u32:
u32 minu0 (u32 a, u32 b) {
return a>b ? b:a;
}
u32 maxu0 (u32 a, u32 b) {
return a<b ? b:a;
}
Вариант без ветвлений будет основан на другой страшной формуле:
u32 minu1 (u32 a, u32 b) {
u32 d = a-b;
return a - (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
}
u32 maxu1 (u32 a, u32 b) {
u32 d = a-b;
return b + (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
}
Разница по скорости ещё больше: если первый вариант работает всё так же 3,5 секунд, то второй уже 9,5 на последовательных данных и примерно 2 секунды против 6 на хаотичных.
Суть и правила эксперимента
Я предлагаю читателям сами проверить на своих машинах то, каков будет результат сравнения. С этой целью была написана программа (GitHub) (с учётом замечаний meduzik и ivas, даю исправленную программу — тестируем обе. В одной данные подаются последовательно, во второй — хаотично). Её нужно скомпилировать и запустить. Работать она может долго, возможно, несколько минут, имейте терпение. Прошу обязательно отключить остальные ресурсоёмкие приложения на компьютере, когда запускаете эту программу.
Отработав, она выдаст в STDOUT таблицу (последовательная подача данных)
sign: 2.87 vs 3.97 abs: 2.29 vs 2.33 mini: 3.46 vs 8.93 maxi: 3.45 vs 9.10 minu: 3.45 vs 9.46 maxu: 3.45 vs 9.81
В первой колонке время работы функций с IF, а во второй – без ветвлений. В STDERR будет выведено число, не обращайте на него внимания, оно для правильного понимания компилятором циклов в программе.
Аналогичная таблица для хаотичной подачи:
sign: 13.02 vs 1.26 abs: 12.01 vs 0.81 mini: 1.89 vs 5.97 maxi: 1.93 vs 6.31 minu: 1.89 vs 6.44 maxu: 1.92 vs 6.70
Я прошу сделать следующее: вот эти таблички вместе с характеристиками своего процессора и названием компилятора (а также с опциями компиляции, если они имеют смысл) написать в качестве ответа к первому комментарию, который я сделаю. И других ответов именно к этому комментарию прошу не давать, чтобы не замусорить эксперимент.
Сразу хочу предупредить о возможных неудачах Вашего эксперимента, за которые я прошу меня простить, но я ничего не могу с этим поделать, как не старался.
- Программа не скомпилируется. Это возможно, так как не все компиляторы понимают std::chrono. Ещё, возможно, я где-то вышел за пределы Стандарта языка С++. Гарантирую только, что код компилируется в Visual C++ 2015 и GCC 4.8.1 (из MinGW) в OS Windows 7 (64). Компилировал я именно 32-битовый код. Я пытался спросить у грамотных людей на SO, как сделать программу лучше, но пока не получил ответа.
- У Вас на машине нет знакового сдвига или отрицательные числа имеют представление не в дополнительном коде — тогда все функции будут работать неправильно.
- Программа будет работать не так, как должна. Это возможно. Я впервые использую chrono и мог ошибиться. До этого всегда измерял время через утилиту runexe, а в этой программе мне нужен универсальный способ, который работал бы у большинства пользователей.
Итак, давайте вместе выясним, что в каких случаях лучше и на каком процессоре.
Список источников
- Hacker's Delight
- Bit Twiddling Hacks
- Optimized abs function
- Функция sign(x) — определение знака переменной
- Функция abs(x) — абсолютное значение числа
- Функции min(a,b) и max(a,b) для чисел со знаком
- Функции min(a,b) и max(a,b) для чисел без знака
Благодарности
Благодарю meduzik и ivas, за то, что напомнили мне про хаотичную подачу данных, о которой я случайно забыл.
Комментарии (144)
ToSHiC
15.04.2016 09:07+7Я как-то раз был на лекции от Интел по поводу устройства современного процессора, в контексте оптимизаций кода. Так вот, в процессорах, выпущенных в последние несколько лет, суперскалярность ого-го, может выполнять до 100 инструкций вперёд. Спекулятивно, конечно, часть из них придётся выкинуть потом. А ещё есть предсказатель переходов, в который закапывают много сил и творят чёрную магию.
В общем, все эти блоки внутри процессора чуть ли не умнее, чем компиляторы, а они точно умнее, большинство программистов. Лезть в дебри таких оптимизаций стоит только если явно есть хотспот.
Zealint
15.04.2016 09:11Вы правы, если говорить о настольных процессорах. Однако мне лично не очевидно, что будет на мобильных телефонах или видеокартах. Там как раз игра может стоить свеч. Суть эксперимента — проверить разные процессоры, у кого что есть. Ну и разные компиляторы между делом тоже.
semenyakinVS
15.04.2016 12:34Там как раз игра может стоить свеч
Ха, неплохой каламбур получился… Именно «игра» — в основном такие оптимизации нужны разве что для геймдева.Zealint
15.04.2016 12:37Да нет, я бы не сказал: ) В научных вычислениях, когда попадаются задачи, занимающие миллионы часов машинного времени, такое тоже может иметь смысл.
semenyakinVS
15.04.2016 13:04+1А зачем научные вычисления на мобильных телефонах делать… А, ой, и видеокартах. Не обратил внимание в начале, приношу свои извинения. Тогда да… На видеокартах, кстати, насколько я слышал, вообще все ветки исполняются одна за другой, а потом выбирается та, для которой условие прошло (подробнее, там когда про warp рассказывается говорится об этом).
Zealint
15.04.2016 13:12Это мне известно, вот и интересно, насколько результат будет другим. Вообще по-хорошему для видеокарты нужно делать тесты иначе, запускать там 1 поток и делать по нему выводу — плохая идея. Нужна другая система тестирования, учитывающая её особенность.
ToSHiC
15.04.2016 20:27Кстати, научные вычисления может быть полезно запускать на ARM процессорах с точки зрения экономии электроэнергии. Вместо 10 серверов x86 брать 100 на ARM, и это может оказаться дешевле/экономичнее с точки зрения электропотребления. Но это надо для каждой конкретной задачи рассматривать, экономии может и не получиться.
meduzik
15.04.2016 09:52+11Простите, но вы измеряете производительность сферического коня. На производительность алгоритмов с ветвлением огромное влияние оказывает branch prediction. У вас созданы идеальные для него условия: первые N/2 вызовов идут по одному пути, остальные — по другому. Подайте на вход случайную последовательность, и получите совершенно другие результаты.
Для примера: rextester.com/PDBX5718. Я оставил только sign. Случайностью входа управляет макрос RANDOM.
Данный вопрос хорошо освещен на StackOverflow: stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-arrayZealint
15.04.2016 09:58Спасибо за замечание. Если уж придираться полностью, то сам по себе способ — запускать подряд 232 раз функцию друг за другом — это тоже минус с точки зрения измерений, так как в реальных условиях всё может быть иначе.
Исправить ситуацию можно проще: после строки 28 добавить строку
a = 17*a+1;
Данные будут идти хаотично. Да, разница будет.
Zealint
15.04.2016 10:18Я исправил свою ошибку (в статье теперь ссылка на вторую программу). Хорошо, что Вы быстро появились: )
Данный момент я знал и в точности так делал в статье про подсчёт битов, но почему-то сейчас он вылетел из головы совсем. Спасибо.
byme
15.04.2016 10:09+2Просто посмотрев на исходний код я могу сказать, что ваши mini, maxi, minu, maxu проиграют в скорости. Поскольку это
i32 d = a - b;
return a - (d&(~(d ^ ((a^b)&(d^a))) >> SHIFT));
С его 8 операциями будет медленей чем один простой условный переход.
kosmos89
15.04.2016 13:33+2Ой, вот уж не факт. Все зависит от удачного предсказания перехода. Если не угадали — сброс конвейера. А это ой как дорого.
ivas
15.04.2016 10:09+5Ваш бенчмарк сильно зависит от работы предсказателя переходов. Попробуйте в качестве аргументов тестируемых функций передавать псевдослучайные числа вместо инкрементируемого числа и результаты будут немного другие.
Я использовал такой генератор:
inline unsigned int fastrand() {
return g_seed = (214013 * g_seed + 2531011);
}
Табличка:
Intel Core i7-3632QM @2.20GHz
Visual C++ 2015
Опции: /Ox
sign: 19.09 vs 5.79
abs: 16.64 vs 4.72
mini: 11.05 vs 12.95
maxi: 11.06 vs 13.18
minu: 10.97 vs 13.75
maxu: 11.07 vs 13.62
NickSin
15.04.2016 10:54Intel® Core(TM) i5-4258U CPU @ 2.40GHz
Apple LLVM version 7.3.0 (clang-703.0.29)
Опции: -std=gnu++11
Старая версия программы:
sign: 2.78 vs 3.21
abs: 3.79 vs 5.34
mini: 6.04 vs 14.08
maxi: 6.16 vs 13.99
minu: 6.26 vs 13.38
maxu: 5.87 vs 13.40
Новая версия программы:
sign: 33.67 vs 3.23
abs: 30.61 vs 3.75
mini: 31.84 vs 15.64
maxi: 32.54 vs 13.54
minu: 33.01 vs 13.91
maxu: 33.41 vs 14.28
TerraV
15.04.2016 10:54похоже термины profiling и bottleneck после этого исследования можно отправлять в историю.
Zealint
15.04.2016 10:56В статью были внесены изменения: добавлена вторая версия программы с хаотичной подачей данных. Такой подход несколько меняет ситуацию для sign и abs. Можно тестировать обе версии, потому что интересно теперь и то, в каких случаях разницы не будет.
atd
15.04.2016 11:36Тест рандомной версии на i7-3667U (mscv 2013, дефолтные настройки release):
sign: 13.71 vs 1.68
abs: 12.81 vs 0.29
mini: 1.11 vs 4.45
maxi: 1.06 vs 3.59
minu: 1.57 vs 4.16
maxu: 1.07 vs 4.28
2147483646
А теперь, внимание, снимем немного позора с min/max:
static i32 mini1(i32 x, i32 y) { return y ^ ((x ^ y) & -(x < y)); } static i32 maxi1(i32 x, i32 y) { return x ^ ((x ^ y) & -(x < y)); }
результат:
sign: 13.67 vs 1.66
abs: 13.15 vs 0.41
mini: 1.09 vs 2.90
maxi: 1.08 vs 1.89
Zealint
15.04.2016 11:39В последней версии min/max используются условия. Да, эта функция быстрее, и я даже об этом писал в одной своей статье, но по условиям эксперимента соревнуются именно функция с условием и функция БЕЗ него.
atd
15.04.2016 11:42+3операторы < и > не генерят бранчинга, посмотрите генерируемый асм
Zealint
15.04.2016 11:46Это я знаю, что в ряде случаев там будет линейный код. Но мы сейчас смотрим на код с позиции программиста, который не может знать, что сделает компилятор. Цель программиста — избавиться от условий, если он их видит (именно ТАК поступают те, кто фанатично избавляется от них — для них эта статья и написана). Более того, как я уже говорил, здесь просто пробный эксперимент, позже я, наверное, сделаю проверку всех существующих версий (они уже описаны в [4-7]).
atd
15.04.2016 11:51Простите, но условия — это ключевое слово if и оператор ?, так же условия содержатся в конструкциях for и while.
А > и < — просто бинарные операторы.
Любой программист, прочитавший хотя-бы книжку K&R об этом знает.atd
15.04.2016 11:55-1P.S.:
> в ряде случаев там будет линейный код
там во всех 100% случаев будет линейный код, на любых архитектурах, даже тех, которых пока нет, почитайте стандарт
Zealint
15.04.2016 11:55Вы всё равно не о том спорите. В ряде случаев конструкции < и > могут порождать ветвление (работать как условие). Я говорю о ситуации, когда программист, видя подобную конструкцию, считает, что здесь именно условие (он не знает, что именно сгенерирует компилятор). Бинарный оператор — это не гарантия отсутствия условного перехода, об этом знает любой, кто хоть раз оптимизировал программы. Верно?
atd
15.04.2016 11:59Нет, не верно, операторы < и > никогда не сгенерят бранч на x86, x86_64, IA64, ARM (включая thumb), ARM64.
Вообще, в погорячился про никогда. Например, на PIC micro этот оператор сгенерит бранч. Но там и операторы + и ? тоже нагенерят бранчей мама не балуй.
Если программист видит оператор < или > и думает про бранч, то он, простите, дебил.Zealint
15.04.2016 12:03Так лучше. И не надо считать подобных программистов дебилами, потому что в отличие от перечисленных архитектур, существует масса других.
Zealint
15.04.2016 12:23Ещё дополню: когда говорите «никогда», то следует подчеркнуть, что речь идёт о типах данных вроде int, что не превышают по разрядности разрядность кода и для которых существуют нужные инструкции в процессоре. Например, если взять Ваш код для min/max и подставить туда long long, вы увидите в листинге несколько условных переходов, хотя только что говорили, что их НИКОГДА не будет для архитектуры x86. Поэтому предлагаю не тыкать друг друга носом в Стандарт и в опыт реальной работы, а смотреть на вещи как есть. Есть не мало случаев, когда «бинарный оператор» даёт условный переход, и это не только у дебилов, у нормальных программистов тоже бывает.
atd
15.04.2016 13:01Если тип данных шире машинного, то и все ваши остальные конструкции будут усыпаны бранчами.
Что, операторов + ? и * тоже будем бояться как огня?
Вы придумали себе мнимого врага — компараторы, и с ним фанатично боретесь. Смешно жеZealint
15.04.2016 13:08Во-первых, Вы не правы, в этом нетрудно убедиться самостоятельно, просто скомпилировав мою версию min и max для long long — там не будет ни одного условного перехода. И не должно быть. Во-вторых, при чём тут умножение, сложение и вычитание? И там тоже не будет условных переходов, если тип данных шире регистра, в этом тоже можно легко убедиться. В-третьих, Вы считаете, что я придумал себе врага и с ним борюсь. Ошибаетесь, я как раз ни с кем не борюсь, а всего лишь предложил пробный эксперимент, по результатам которого сделаю другой. Моё мнение по поводу компараторов вы вообще нигде здесь не увидите. Вот видите, Вы уже начинаете сыпать домыслами, когда выяснилось, что Вы подходите к дискуссии по вопросу не с того краю.
SidMeier
15.04.2016 11:51-1semenyakinVS
15.04.2016 12:38Кстати, раз уже тема поднялась, задам вопрос — немного оффтоп… Вот часто когда говорят про компилятор, называют его clang — видел в постах. Но clang — это ведь только frontend, а backend у него llvm. Или я ошибаюсь?.. Ещё раз приношу свои извинения за оффтоп.
SidMeier
15.04.2016 12:47Просто традиция. Если подходить формально, то не clang, а clang++(также как не gcc а g++), но в большинстве случаев clang построен на базе llvm-backend, так что это просто опускают. Фактически llvm объединяет группу компиляторов с общим backend, а для обозначения конкретного используется имя frontend. И, ко всему прочему, есть llvm-gcc…
encyclopedist
15.04.2016 12:18+1Все кто постит тут результаты — не забывайте включать оптимизации (
-O3), иначе ваши результаты полностью бесполезны!
DistortNeo
15.04.2016 12:40С удовольствием бы проверил код интеловским компилятором, но вот незадача: MS в последнем апдейте VS его поломало. В любом случае, ветвление в современных процессорах — совсем не тот ужас, который был лет 25 назад.
До сих пор приходится это объяснять студентам, которые считают ветвление дорогой операцией, ломающей конвейер. При этом эти же студенты используют pow для возведения в квадрат и злоупотребляют делением.
DrSmile
15.04.2016 20:54Ветвление — это дорогая операция, ломающая конвейр в случае ошибки предсказания. Собственно, представленные в комментариях результаты тестов это наглядно демонстрируют. Однако, стоит понимать, что все современные процессоры имеют инструкцию условного копирования (cmove), поэтому в простых случаях использование оператора ?: к ветвлению не приводит.
А возведение в константную целочисленную степень, типа pow(x, 2), на современных компиляторах инлайнится в несколько умножений, поэтому ничего страшного в нем нет.DistortNeo
15.04.2016 22:08Ага, вот прямо сейчас посмотрел: компилятором VS инлайнится только возведение в степень 2.
Остальные варианты — pow(x, 1), pow(x, 3), pow(x, 2.0f) — через медленные вызовы возведения в степень.
В C# и того хуже: там всегда вызывается pow (проверял по времени выполнения, т.к. ассемблерный код при подключении отладчика становится другим).
sanblch
15.04.2016 12:40Intel® Core(TM) i5-3570 CPU @ 3.40GHz
Linux 3.19.0-56-generic x86_64 GNU/Linux
Ubuntu 15.10
gcc 5.2.1
g++ -O3 -std=c++14
Old:
sign: 4.84 vs 5.40
abs: 2.32 vs 2.44
mini: 3.17 vs 5.83
maxi: 3.07 vs 5.40
minu: 2.98 vs 5.40
maxu: 3.55 vs 5.30
New:
sign: 9.92 vs 3.03
abs: 9.56 vs 0.17
mini: 1.18 vs 1.09
maxi: 1.18 vs 1.38
minu: 10.31 vs 1.66
maxu: 1.28 vs 1.45
g++ -std=c++14
Old:
sign: 2.45 vs 2.28
abs: 1.43 vs 3.94
mini: 3.22 vs 11.44
maxi: 3.23 vs 11.20
minu: 3.26 vs 11.25
maxu: 3.36 vs 11.24
New:
sign: 21.10 vs 0.76
abs: 20.00 vs 2.12
mini: 22.27 vs 9.19
maxi: 22.19 vs 9.33
minu: 22.75 vs 9.38
maxu: 22.82 vs 9.46
P.S.: Мне пришлось заменить `chrono::duration_cast ` на `chrono::duration_cast `, чтобы получать неотрицательные значения времени
halyavin
15.04.2016 13:02+5В первую очередь нужно смотреть в дизассемблер. На x86 есть инструкция cmov (условное присваивание), предназначенная для избавления от простых ветвлений. Плюс есть SSE инструкции вычисляющие max/min для тех случаев, где цикл может быть векторизован. На ARM практически все инструкции могут быть условными, NEON (векторные инструкции на ARM) тоже поддерживает max и min. Так что у хорошего компилятора даже в коде с if'ами не будет полноценных ветвлений.
PS Для предотвращения оптимизации циклов, нужно использовать volatile. Так же советую посмотреть это видео про микробенчмарки: CppCon 2015: Chandler Carruth «Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!»Zealint
15.04.2016 13:11-1Я вообще-то написал про cmovXX, и сообщил, что компилятор может использовать данную конструкцию при необходимости. Да, у хорошего компилятора не будет ветвлений, но я веду речь про тех программистов, кто до сих пор этого не знает. С другой стороны, как выяснилось, при хаотичном потоке данных функции без ветвлений (sign, abs) на x86 чаще выигрывают.
volatile не вариант, он может в некоторых компиляторах заставить переменную оказаться в памяти и не применять к ней оптимизаций вообще, что порождает некоторые косвенные эффекты, которые нам не нужны.
Zealint
15.04.2016 15:15-3Видео, конечно, полезное для многих, спасибо за ссылку, но касательно моих интересов там нет ничего.
Вот представьте: мне нужна программа, которую любой пользователь может скомпилировать и запустить у себя, она выдаст время работы функций и всё. Не нужно, чтобы пользователь устанавливал бы себе дополнительные пакеты или делал какие-то дополнительные действия.
Далее, если говорить о честном тестировании функций, то тут вообще беда — даже хаотичное тестирование в цикле не сильно полезно (в малых циклах процессор может кэшировать сразу уже раскодированные команды при первом проходе, не раскодируя их затем при остальных), так как в реальных условиях, особенно когда нужная нам функция окружена некими другими командами, всё может быть совершенно иначе. Я ищу разные варианты решения этой проблемы, но пока не нахожу. Пока прихожу к выводу, что оптимизация программ в современных процессорах — это IT-аналог гадания на кофейной гуще. Хоть что делай — мы не знаем, что с этим сделает процессор, особенно если учесть, что ряд команд он преобразует во внутренние RISC команды которые (кстати) могут оказаться с ветвлениями (хотя исходные команды были без них). И вот об этих тонкостях работы микрокоманд хотелось бы узнавать из подобных видео. О том, насколько вообще честно мы можем измерить время работы функции, чтобы это было близко к реальным условиям.
summeroff
15.04.2016 13:12Kubuntu 15.10 x64
i7-4700MQ CPU @ 2.40GHz
gcc 5.2.1
# g++ -std=c++11 BranchFreeTimeoutNew.cpp -o test.elf
# ./test.elf
sign: 24.26 vs 2.54
abs: 24.49 vs 4.54
mini: 26.85 vs 12.34
maxi: 26.27 vs 12.45
minu: 32.05 vs 12.84
maxu: 31.15 vs 14.50
2147483646
# g++ -std=c++14 -O3 BranchFreeTimeoutNew.cpp -o test.elf
# ./test.elf
sign: 12.25 vs 1.09
abs: 11.18 vs 0.58
mini: 0.86 vs 1.21
maxi: 0.85 vs 1.11
minu: 11.87 vs 0.95
maxu: 0.89 vs 1.20
2147483646
encyclopedist
15.04.2016 13:23+4И ещё, для всех, если ещё не знаете — есть великолепный сервис gcc.godbolt.org, который позволяет быстро посмотреть на ассемлерный кот сгененированный разными компиляторами. Поддерживаются GCC, Clang и ICC разных версий и для разных архитектур.
mini0(int, int): cmpl %esi, %edi movl %esi, %eax cmovle %edi, %eax ret maxi0(int, int): cmpl %esi, %edi movl %esi, %eax cmovge %edi, %eax ret mini1(int, int): movl %edi, %eax movl %edi, %edx subl %esi, %eax xorl %edi, %esi xorl %eax, %edx andl %edx, %esi xorl %eax, %esi notl %esi sarl $31, %esi andl %eax, %esi movl %edi, %eax subl %esi, %eax ret maxi1(int, int): movl %edi, %edx movl %edi, %eax subl %esi, %edx xorl %esi, %eax xorl %edx, %edi andl %edi, %eax xorl %edx, %eax notl %eax sarl $31, %eax andl %edx, %eax addl %esi, %eax ret
Видно, что GCC сгенерировал cmov интсрукции, и в результате варинт с if не содержит условных переходов.
wizardsd
15.04.2016 15:57+4Со всеми этими оптимизациями ветвлений надо иметь ввиду, что во многих случаях эта оптимизация не бесплатна и процессор как-бы вычисляет обе веткие ветки одновременно, т.е. иногда вычислений становится больше. А когда вычислений больше надо учитывать наличие свободных исполнительных устройств, instruction latency, зависимости по данным и т.п.
Всё сводится к обычному The Third Rule of Code Optimization: Profile first
Shamov
15.04.2016 17:00-2Ветвление на современном процессоре стоит 0 тактов. В оптимистичном сценарии. Причём ничего не стоит не только сам if, но и условие внутри него. Это возможно благодаря так называемому предсказанию переходов. Но это название не более, чем маркетинговый трюк. Никакого предсказания в строгом смысле этого слова в процессоре не делается. Просто одновременно с вычислением условия на соседнем конвейере начинается выполнение той ветки, которая будет выполнена в случае true. Таким образом, к тому моменту, когда условие будет реально просчитано, первая ветка уже будет выполнена ровно на столько тактов, сколько потребовалось на вычисление условия. Конечно, если окажется, что условие равно false, то результаты выполнения первой ветки придётся отбросить и начать выполнять вторую ветку с самого начала. Но, во-первых, в компиляторе есть специальная оптимизация. Когда компилятор уверен в том, что наиболее вероятной веткой является else, он тупо переставляет ветки местами и инвертирует условие внутри if. Во-вторых, есть программист, который иногда лучше компилятора знает, какая ветка является более вероятной. Хороший программист всегда ставит наиболее вероятную ветку первой. На тот случай, если оптимизатор в компиляторе не сможет придти к однозначному выводу о необходимости оптимизации. В этом случае оптимизатор просто ничего не меняет и оставляет так, как было у программиста.
Zealint
15.04.2016 17:01+2На самом деле это неправда. Если бы стоимость была 0 тактов, то не было бы разницы между последовательным и хаотичным потоком данных.
Shamov
15.04.2016 17:16-1Эта разница объясняется иначе. Ветвление тут ни при чём. Это другая оптимизация, которая относится к циклам. Когда оптимизатор видит, что в коде есть цикл, в котором переменная монотонно возрастает/убывает, он переделывает код таким образом, чтобы эта переменная всегда была в регистре. И прямо в регистре он её инкрементит/декрементит, не перекладывая постоянно из регистра в память/кэш и обратно.
Zealint
15.04.2016 17:19Нет, дело не в этом. Когда данные подаются хаотично (по формуле), переменная также находится в регистре, я проверял (там же она пересчитывается). Более того, я всегда вычитаю время работы самого вычисления этих данных, оставляя чистое время работы самой функции.
Shamov
15.04.2016 17:50Не вижу, чтобы в программе измерялось время вычисления нового значения по формуле. Там измеряется только общее время работы всего цикла. Да это и невозможно сделать. На сам замер уйдёт несравнимо больше времени, чем на вычисление формулы.
Zealint
15.04.2016 17:57Я измеряю время работы пустого цикла, который генерирует входные данные, затем полного цикла, который вместе с генерацией данных вызывает функцию. В ассемблерном листинге я убедился, что генерация происходит в регистре. Затем я вычитаю время работы полного цикла и пустого — получаю почти чисто время работы функции. А мы наблюдаем, что разница между одной и другой версией колоссальна. Версия с ветвлением может работать в несколько десятков раз медленнее, чем без ветвлений при хаотичной подаче, когда как при последовательной подаче версия с ветвлением выигрывает. Это можно объяснить только тем, что ветвление играет роль в вычислениях, особенно когда предсказатель не может надёжно предсказывать.
Shamov
15.04.2016 18:40Это некорректно. Когда вы убираете из цикла вызов тестируемой функции, выполнение кода распределяется по конвейерам процессора совсем по-другому. Условие продолжения цикла (while (a != 0)) — это тоже ветвление. Процессор начинает выполнять следующую итерацию цикла ещё до того, как вычислит формулу, в надежде на то, что a действительно не будет равно нулю. В случае пустого цикла каждая следующая итерация цикла использует один дополнительный конвейер. Пока предыдущее значение a ещё не готово, на этом конвейере уже можно делать всё, что не зависит от a: 1) выбрать какие именно из блоков умножения и сложения будут использованы (и тех и других много); 2) загрузить в них обе константы (19993 и 1); 3) подготовить два временных места для размещения результатов умножения и сложения (внутренних для конвейера); 4) хрен знает что ещё (конвейер делает много такого, что не сразу приходит в голову). А когда в цикле есть ещё и функция, которая тоже зависит от a, то каждая следующая итерация задействует два дополнительных конвейера. Один делает всё то же самое, что и в случае пустого цикла, а второй параллельно начинает выполнять тестируемую функцию и делает всю возможную работу, которую можно сделать до того, как реально упрётся в отсутствие значения a, вычисленного на предыдущей итерации. Короче говоря, я хочу сказать, что замер на пустом цикле вообще никак не соотносится с замером на цикле с тестовой функцией.
Zealint
15.04.2016 18:46Мы сейчас разговариваем не о способе измерения времени, а о том, что по Вашим словам стоимость ветвления равна нулю. Это не так и это нетрудно показать. Тот факт, что я не вполне корректно измеряю время работы функции мне и так хорошо известен. Но других вариантов, увы, не вижу. Этот способ хотя бы как-то коррелирует со сложностью функции.
Shamov
15.04.2016 18:57Пока вам удалось показать это лишь с опорой на предположение о том, что будто бы вам удаётся измерять время работы функции в цикле отдельно от времени работы самой циклической конструкции. Это не так. Именно поэтому я и начал говорить о способе измерения времени. Я считаю, что измерить время работы настолько крохотных функций путём многократного их повторения в цикле на современном процессоре вообще невозможно. Тем более при использовании ключа -O3.
Zealint
15.04.2016 19:00Да сколько можно… я не говорю нигде про отдельное измерение. Я сказал, что получаю почти чистое время работы функции в этих конкретных условиях. Это время не является точным, но оно коррелирует с реальностью. С тем, как функция будет вести себя в практических приложениях. Вы же, невнимательно прочитав мой ответ, считаете, что я делаю абсолютно точные вычисления и спорите с этой выдумкой. Не надо так.
Shamov
15.04.2016 19:04Нигде не говорил подобного. Я отрицаю именно то, что вы на самом деле утверждаете. То, что замер не является точным, — понятно. Это само собой. Речь идёт о том, что он также не является ни чистым, ни почти чистым. Условия замера в случае «пустого» цикла и в случае цикла с функцией совершенно разные.
Zealint
15.04.2016 19:11Попробую на пальцах объяснить.
Есть функция f, а есть функция g. Есть цикл, внутрь которого мы встраиваем эти функции. С функцией f получаем время A, с функцией g получаем время B. Есть ещё время C, когда цикл почти пустой (там только генерация данных). Я вычисляю (A-C) и (B-C), называя это практически чистым временем работы функции. Я называют это этим словом, то есть даю название этим значениям (Вы можете называть их «грязным временем», суть это не поменяет). Эти значения разные, они показывают то, насколько одна функция быстрее или медленнее другой (можно даже не вычитать C, если угодно, но я хочу вычитать).
Вы понимаете? Я получаю два разных числа и на основе их соотношения делаю приблизительный вывод о скорости работы функций. Этот вывод коррелирует с реальностью. Я не говорю, что данные числа отражают реальность, я говорю, что если в этом эксперименте одна функция сильно быстрее другой, то в реальности будет ТО ЖЕ САМОЕ. Это понятно? Если нет, то что именно не так?Shamov
15.04.2016 21:33Зачем вы всё это мне объясняете? Это всё понятно из текста программы. Проблема в другом. Не в том, что я не понимаю, что вы хотите измерить, а в том, что вы реально измеряете не то, что хотите. Понимаете? Мысленная модель вашего эксперимента не соответствует тому, как это на самом деле выполняется в процессоре с предсказанием условных переходов. В вашей модели сама циклическая конструкция никак не влияет на вызываемую внутри функцию. Вы просто вычитаете время, затраченное на цикл, из общего времени. В действительности же при выполнении в цикле таких простейших функций конструкция цикла оказывается неразделимо переплетена с самой функцией. Когда вы убираете из цикла вызов функции, процесс выполнения самой циклической конструкции меняется очень существенно. Проще говоря, вы не можете вычислить (А-С). Когда вы измеряете A, в него в качестве составляющей входит время, которое вы обозначаете как С. А когда вы пытаетесь измерить это С отдельно (чтобы вычесть его из A), у вас реально измеряется время, которое даже не С-штрих… это просто другое время — D… оно никак не связано с тем С, которое входит в А. Возможно, какая-то связь между C и D есть, но скорее всего даже разработчики процессоров не сразу скажут, какая именно и есть ли связь вообще.
Zealint
16.04.2016 09:29-1Нет, Вы по-прежнему меня не понимаете, приписывая мне своё видение эксперимента. Будет ли Вам лучше, если я скажу, что мне нужны числа A и B? А зачем они нужны — я в тексте статьи не говорил. Число C я вычитаю для более удобного определения соотношения (считайте это погрешностью). По поводу наличия или отсутствия связи между этими величинами и реальностью я имею своё мнение, основанное на моём опыте. При этом заметьте, я не спорю, что эти числа никакого отношения к реальному времени работы функции не имеют, я утверждаю лишь, что есть чёткая корреляция.
Shamov
16.04.2016 10:22А я, основываясь на своём опыте, считаю, что такая корреляция могла бы быть лишь в том случае, если бы в процессоре не было бы оптимизации ветвлений через предсказание переходов. При этом мой опыт больше и лучше вашего. Я занимаюсь программированием только на С++ более 15 лет. А до этого писал на чистом С и ассемблере. Так что вы совершенно напрасно придаёте такое значение своему опыту в нашем с вами разговоре. По сравнению с моим он незначителен (считайте его погрешностью).
Zealint
16.04.2016 10:30Ну началось: ) Сейчас будем выяснять, кто круче по числу лет. Наверное, Вы из тех людей, кто путает количество и качество.
Внимательно слушаю ответ на мой вопрос ниже.Shamov
16.04.2016 10:39Выяснять ничего не будем. Понятно, что я круче и по числу лет и по качеству опыта. Но заметьте, не я начал делать упор на свой опыт, пытаясь что-то обосновать. Это вы начали. Я про опыт заговорил лишь для того, чтобы напомнить вам, что опыт есть не только у вас.
Zealint
16.04.2016 13:11Вы не правы. Я сказал про свой опыт ТОЛЬКО для того чтобы показать, что в нём (в моём опыте) присутствует корреляция между моими сферическими в вакууме экспериментами и тем, как результаты опыта ложатся на реальные задачи. А Вы приняли это на свой счёт, будто бы я пытаюсь соревноваться. Нет, этого, увы, не будет: )
Shamov
16.04.2016 13:29Возможно, я что-то неправильно понял. Мне показалось, что вы каким-то образом обосновываете свою правоту ссылкой на опыт. Это выглядело как заход с козырей. Естественно, я был вынужден ответить тоже козырем. Любой подобный разговор чем-то похож на преферанс, где отвечать нужно той же мастью. А из козырей у меня, к сожалению, есть только старшие карты — туз и король.
Zealint
16.04.2016 13:36Нет, простите, если я, быть может, выбрал не тот оборот речи, однако когда я сказал «опыт», то это было (и мне показалось, я написал ясно), в контексте того, что мой опыт таких экспериментов даёт нужный результат в реальных расчётах. Обычно в научных, потому как оптимизацией бытовых программ я не занимаюсь. Это было сказано против Вашего тезиса о том, что будто бы мои эксперименты не имеют смысла. Хотя я-то знаю, что имеют.
Zealint
15.04.2016 19:31На всякий случай, вынужден пояснить один философский момент из нашей жизни. В нашей жизни многие вещи определяются косвенно, так как напрямую их определить нельзя вообще никак. Так, например, учёные не могут разглядеть и замерить свойства квантовых частиц, но определяют их физику по косвенным признакам, в результате соударения их друг об друга. Получаемая физиками модель отвечает на ряд вопросов, важных для физиков. Далее, в реальных условиях человек не бегает по беговой дорожке в соответствующей одежде, однако если взять двух людей на беговой дорожке и двух людей, бегущих за троллейбусом, то и там, и там оба покажут качественно одинаковый результат (тот прибежит первым, кто лучше к этому подготовлен). В мире всё так, эксперимент есть эксперимент, и если я говорю, что мне нужны эти данные и я знаю, что с ними делать, значит на то у меня есть основания, диктуемые опытом. А кому кажется, что тут нет ВООБЩЕ никакой связи — ну значит это его мнение, пусть кажется дальше. Любой факт может иметь значение для того, кто в теме. Кто не в теме, тому это может ничего не говорить. Вот на этом можно и остановить разговор.
aml
15.04.2016 21:18Он вас не слушает. Я хотел большой коммент написать про измерение сферического коня в вакууме. Но вы уже это разжевали так, что по-моему больше даже вопросов быть не может.
Zealint
16.04.2016 09:30Вряд ли Вам это помогло бы, потому что я как раз знаю, что делаю. Не уверен, что мне необходимо это пояснять кому-либо. Или Вы считаете иначе?
Zealint
15.04.2016 18:54Ещё Вы неверно поняли смысл пустого цикла (посмотрите всё-таки программу и мой комментарий выше внимательнее). Пустым я назвал цикл, в котором есть вычисление потока данных. То есть формула там тоже присутствует.
Shamov
15.04.2016 18:59Это я понял. И из моего предыдущего комментария видно, что я это понял. Я назвал цикл пустым только потому, что соответствующий этому циклу тайминг у вас сохраняется в переменную empty.
Zealint
15.04.2016 19:01В таком случае нет смысла мне сообщать, что я что-то делаю неправильно. Я же назвал условия эксперимента. Вы же спорите с тем, как Вы представляете себе этот эксперимент, а не я.
encyclopedist
15.04.2016 18:17+3Там есть предсказание. Читайте документацию. Есть специальные таблицы, которые сохраняют историю переходов в зависимости от адреса, и на основе истории делают предсказание.
Shamov
15.04.2016 18:45Тогда измерять тем более бессмысленно. Чтобы измерения имели смысл, нужно знать логику работы с этими таблицами и учитывать её.
Zealint
15.04.2016 19:03Смысл есть всегда. В данном случае мы пытаемся отыскать разницу по времени работы функций по отношению друг к другу. Наши измерения показывают эту разницу и в ней есть смысл. Или Вы хотите утверждать, что если, скажем, в наших экспериментах одна функция быстрее другой в 10 раз, то в реальных программах со случайным потоком данных может статься наоборот?
Shamov
15.04.2016 19:06-1Нет, они показывают не эту разницу, а какие-то неслучайные числа, которые не имеют отношения к умозрительной модели вашего эксперимента.
Zealint
15.04.2016 19:14Это ещё нужно доказать, что не имеют отношения. Подобные голословные заключения здесь мало полезны.
Shamov
15.04.2016 21:39К сожалению, всё ровно наоборот. Традиционно доказывать нужно именно соответствие модели эксперименту. Не наоборот.
Zealint
16.04.2016 09:32Ничего подобного, я же не приводил никакой модели и не называл целей эксперимента. Цель и модель приписали мне Вы, и с ней же спорите. Если я даже попрошу Вас назвать мою умозрительную модель — Вы не сможете этого сделать. Попробуйте, если не верите.
Shamov
16.04.2016 10:09+1То, что вы не привели никакой модели эксперимента, — это не оправдание, а скорее отягчающее обстоятельство. Должны были привести, если считаете, что эта модель не следует однозначно из текста программы. Эксперимент, который не имеет никакой модели, не имеет и смысла.
На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.Zealint
16.04.2016 10:29Ответьте, пожалуйста, на простой вопрос.
Вот цикл, который выполняется 20 секунд:
u32 i = 0, s = 0; do { i = 19993*i + 1; s += sign0 ((i32)i); } while (i!=0);
Вот цикл, который выполняется 10 секунд:
u32 i = 0, s = 0; do { i = 11*i + 1; s += sign0 ((i32)i); } while (i!=0);
(Функции в цикле одинаковые — которые с IF из статьи).
Вопрос такой: почему время работы разное, если принять во внимание Ваше утверждение о том, что ветвление работает 0 тактов? Мой компилятор выдаёт абсолютно идентичные листинги программ, разница только в константе, которая кладётся в регистр. В первом случае 19993, во втором — 11.
По поводу эксперимента… Вы продолжаете заниматься приписыванием мне какой-то своей модели поведения. У меня есть цели и задачи эксперимента (а Вы сказали, что нет), я знаю, чего я хочу добиться, но я не обязан об этом сообщать. Если Вы не понимаете моих целей, то это НЕ значит, что моя методика обязана совпадать с Вашим представлением о таковой. Верно?
Далее, по поводу ветвления цикла. Мне не нужно учитывать предсказание выхода из него, оно не влияет на то, что мне нужно. Подставляя разные функции в программу, предсказание выхода из цикла я существенно не меняю.
Я внимательно слушаю Ваш ответ на простой вопрос.Shamov
16.04.2016 11:16-1Константа разная, поэтому и время работы разное. Операция умножения выполняется за разное время, которое зависит от операндов.
К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.
Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.Zealint
16.04.2016 13:16Обождите. Я никак в толк не возьму: что именно я не понимаю? Вы можете сформулировать конкретный тезис? Чётко и одним предложением.
Можно ли узнать, как размер константы связан со скоростью вычисления? Константы какого размера будут давать одинаковое время умножения, если второй операнд всегда 32 бита?Shamov
16.04.2016 13:45-1Одним предложением это вряд ли можно сформулировать. Важен не размер константы, а количество значащих разрядов, а иногда и конкретное значение. Например, умножение на 11 можно сделать вообще без умножения. В десятичной системе это часто можно сделать в уме: добавить справа ноль, умножив таким образом на 10, и прибавить к результату операнд. Для двоичной системы тоже несложно придумать алгоритм без умножения: добавить к операнду три нуля, прибавить операнд с двумя добавленными нулями и вычесть операнд. Если я смог придумать такой алгоритм за 10 секунд, то разработчики процессора скорее всего тоже додумались до такой оптимизации за много лет работы и встроили её в блок, выполняющий умножение.
Zealint
16.04.2016 13:48Хорошо, я признаю, что здесь облажался. Сейчас проверил с константой 257, стало работать одинаково. Но эта константа довольно большая для моих целей, поэтому мой тест не показывает ни положительного, ни отрицательного результата. Зато данный результат показывает эксперимент в моём комментарии ниже.
Zealint
16.04.2016 13:46Я продолжил свой эксперимент: загнал в массив упорядоченный набор чисел и запустил цикл с функцией sign0 (которая с IF), получил почти 16 секунд. Затем взял массив из тех же, но неупорядоченых чисел, получил 20 секунд. Затем повторил эксперимент с функцией sing1 (без IF), время работы в обоих случаях одинаково (16,8 сек). Вывод: ветвление вносит дополнительные затраты на работу программы, когда предсказатель не может надёжно предсказывать, то есть ветвление — это не 0 тактов.
Shamov
16.04.2016 14:05-1Но я и не говорил, что оно всегда 0 тактов. Мой первый коммент состоял не только из первого предложения. Фактически, уже со второго предложения начинается объяснение, почему иногда может быть не 0. Естественно, если вы будете специально запутывать предсказатель, то не 0 тактов будет чаще. Но в реальных программах входные данные, как правило, не запутаны. И значит стоимость ветвления в среднем близка к нулю. И обычно можно не беспокоиться о том, что у тебя в программе есть лишний IF, который можно было бы убрать, придумав какой-нибудь изощрённый алгоритм.
Zealint
16.04.2016 14:17-1К сожалению, в моей реальности это не так, иначе я вряд ли бы занимался подобными экспериментами. В одних случаях ветвление работает быстрее, в других без него быстрее. На видеокартах так вообще часто приходится делать уйму работы, чтобы вместо одно IF была сотня строк, но зато более быстрых. В таком случае, я не понял суть вашей претензии. Из двух алгоритмов я выбираю тот, который на моих сферических в вакууме тестах работает быстрее — и этот выбор я делаю на разных компьютерах с помощью сообщества, которое эти тесты запускает.
Shamov
16.04.2016 14:59+1Суть в том, что а) эксперимент здесь не нужен; б) эксперимент смоделирован неверно.
Не нужен он потому, что выводы, которые вы делаете, как бы, из эксперимента можно сделать, исходя лишь из понимания того, как работает процессор. Т.е. на основе одной лишь теории. Вообще без практического эксперимента. Разумеется, процессоры оптимизированы под типовой сценарий, который выполняется в большинстве программ. В таком типовом сценарии IF почти всегда стоит 0. Если же у вас особая специфика и условные переходы в вашей программе непредсказуемы, то, разумеется, вашей программе эти оптимизации ничем не помогают.
А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.Zealint
16.04.2016 15:05-2Так… ну вот, как я и говорил, Вы совершенно неверно понимаете мою мотивацию. Чтобы говорить о верности или неверности эксперимента, нужно знать мои цели. Вы их не знаете (а я их и не говорил). Далее, Вы серьезно думаете, что в какой-то программе sign, abs или минимум с максимумом будут узким местом, чтобы с ними так возиться? Вряд ли. Вообще эти функции — это последнее, что меня интересовало бы в сложной программе, где они как капля в море. Меня интересует в этом эксперименте другое, совсем другое… и я ещё даже не решил, писать статью с объяснением или нет.
Shamov
16.04.2016 15:17+1Ну, на это я даже не знаю, что сказать. Эксперимент совершенно точно выглядит как эксперимент по исследованию ветвлений. Понятно, что на примере каких-то конкретных функций, и что сами эти функции не имеют значения. Но предметом исследование определённо является само ветвление и его влияние на тайминг. Если это на самом деле не так, и реальная цель вашего эксперимента состоит, например, в исследовании того, сколько человек поведутся на призыв и начнут запускать бессмысленный и некорректный бенчмарк на своих машинах, то тогда у меня нет возражений по существу. Если эксперимент был социальным, то он действительно удался.
Zealint
16.04.2016 15:23-1Чушь несёте. Одна из косвенных целей — сравнить два алгоритма. В одном из них есть IF (в программе), в другом — нет. При этом меня совершенно не интересует, как именно будет работать (и будет ли он вообще после компиляции) условный переход. Теперь ясно? Суть: есть сферический в вакууме цикл проверки двух РАЗНЫХ (абсолютно разных) функций, мне нужно узнать время работы этих циклов минус время работы цикла, который я назвал пустым (даже если разность будет отрицательной). Зачем мне это нужно — этого я нигде не говорил. Далее, не нужно пытаться делать выводы только на основе того, как с Ваших позиций выглядит эксперимент. Очень может оказаться, что Вы многого не знаете, чтобы залезать в чужую голову и делать вид, что Вы там что-то понимаете. Я так и не понял, вашу претензию. Видимо, её нет, а Вы хотели просто что-то сказать, но не знали, что. Ещё раз: условные переходы в скомпилированном коде меня НЕ интересуют. Не интересует меня и то, как долго или быстро работает IF, где бы он ни был.
Shamov
16.04.2016 15:29Ну, тогда просто согласимся на том, что обычно условный переход ничего не стоит и париться на счёт него не нужно.
А о чём в действительности был ваш эксперимент, вы расскажете в другой раз. И лучше кому-нибудь другому. Я уже устал от того, что вы мне постоянно пересказываете суть вашего эксперимента разными словами, каждый раз делая акцент на том, что я его неправильно понял, хотя каждый следующий пересказ лишь укрепляет мою уверенность в том, что я правильно понял суть с первого раза.
Zealint
16.04.2016 15:14-2Далее, если продолжить указывать Вам на логические ошибки, то можно это сделать со многих сторон. Вот одна из них: я сказал Вам, что меня интересует время работы моего цикла при вызове одной и другой функции. Вы же мне говорите, что я исследую работу IF, хотя эти два момента не связаны напрямую. Сколько уже можно приписывать мне СВОИ представления о том, что Я делаю, а не Вы?
Shamov
16.04.2016 15:23+1Добро пожаловать в реальность! В будущем все люди, с которыми вы будете иметь дело, только тем и будут заниматься, что приписывать вам те мысли и цели, которые, как они думают, у вас есть. Телепатов, к сожалению, нет. Но это не мешает людям думать, что они точно знают мысли других. Вам придётся как-то научиться жить с этим. И не факт, что сможете. У многих гиков это не получается и со временем они начинают не любить окружающих за то, что их никто не понимает.
Zealint
16.04.2016 15:28-1С чего Вы решили, что знаете, с какими людьми я буду иметь дело в будущем? Более того, класс людей, которые любят соваться в том, в чём не разобрались достаточно хорошо, очень велик и меня это не удивляет. Меня удивляет Ваша упорная настойчивость повторять мне одну и ту же мысль, которую я понял с первого раза и против которой чётко и ясно указал контраргумент, а затем повторил его 10 раз. Вот здесь в комментарии это последний раз. И то, я сделал одолжение, что так настойчиво объяснял свою позицию. Если и сейчас не понятно, то мне теперь это безразлично. Разговор окончен: )
Shamov
16.04.2016 15:35+1Я говорю о людях вообще. Мне не нужно знать, с какими конкретно людьми вы будете иметь дело, чтобы предсказать, какие у вас будут с ними проблемы. У всех людей есть одно общее свойство — они не телепаты. Мой прогноз основан только на этом свойстве людей.
DistortNeo
16.04.2016 17:38+1Касательно операции умножения — есть такой документик:
http://www.agner.org/optimize/instruction_tables.pdf
В современных процессорах операция умножения выполняется за константное количество тактов. А вот время выполнения деления пока что довольно долгое и зависит от значений операндов.Shamov
16.04.2016 18:07-1Поздно. Он уже проверил. И у него получились разные результаты при разных значениях операндов.
ivas
16.04.2016 21:17+3Время работы этих циклов отличается ровно в 2 раза, потому что тело цикла с константой 19993 исполнится 4294967296 раз, а с константой 11 — 2147483648 раз.
gena_glot
15.04.2016 23:22Нужно понимать что вот под капотом глубоко где-то так (вариант 2) и будет, по крайней нормальный Math-compiler именно так и сделает, но это будет работать быстрее, потому что там решили общую задачу и написали 100.000 тестов. В принципе, поэтому либы и пишутся.
Классический вариант реализуется несложной схемой из условий:
Вот такие штуки превращаются
sign_t sign0 (i32 a) {
if (a>0) return +1;
if (a<0) return -1;
return 0;
}
В вот такие штуки:
sign_t sign1 (i32 a) {
return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
}
POPSuL
22.04.2016 14:22А у меня как-то так получилось…
Intel(R) Core(TM) i3-3120M CPU @ 2.50GHz
Ubuntu 16.10 x64
GCC 5.3.1
Linux xx 4.4.0-18-generic #34-Ubuntu SMP Wed Apr 6 14:01:02 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux
Линейно:
g++ -std=gnu++11 -O0sign: 6.23 vs 5.54
abs: 4.52 vs 8.28
mini: 7.12 vs 19.71
maxi: 7.28 vs 19.04
minu: 7.12 vs 18.99
maxu: 7.12 vs 18.93
2147483646
Zealint
Ответом к этому комментарию я прошу давать только таблицу времени работы.
Укажите также процессор и компилятор с опциями. Используйте тэг «pre».
Zealint
mwambanatanga
Intel Core 2 Duo E7300 @ 2.66GHz
GCC 4.8.4
Опции: -std=gnu++11
sign: 4.52 vs 6.46
abs: 5.33 vs 12.79
mini: 11.02 vs 28.10
maxi: 11.01 vs 27.45
minu: 8.99 vs 27.38
maxu: 9.17 vs 27.46
2147483646
encyclopedist
Вы точно с оптимизацией скомпилировали? -O3 например?
mwambanatanga
Никак нет. Здесь точно без оптимизации. Ниже по ветке я запостил результаты для обновлённого (хаотического) теста с -O3 и без.
S0mnium
Intel(R) Core(TM) i5-3450 CPU @ 3.10GHz
g++ -std=gnu++11 BranchFreeTimeout.cpp
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
sign: 4.64 vs 3.84
abs: 2.88 vs 5.78
mini: 5.01 vs 14.40
maxi: 5.08 vs 14.55
minu: 5.07 vs 14.10
maxu: 5.09 vs 13.63
mwambanatanga
coldwind
Zealint
Прошу простить мой косяк!
Сделал в тексте апдейт программы: я совсем забыл, что нужно подавать на вход хаотичные данные, о чём мне справедливо указали ниже. Вот правильная версия программы.
Тех, кто уже принял участие, прошу перетестировать. Далее можно, кстати, обе программы тестировать — интересно же.
kshvakov
g++ -std=gnu++11 (gcc version 4.8.4)
Intel® Core(TM) i7-2600 CPU @ 3.40GHz
sign: 4.49 vs 5.82
abs: 5.12 vs 6.15
mini: 6.30 vs 15.02
maxi: 5.92 vs 14.99
minu: 6.13 vs 14.88
maxu: 6.38 vs 15.30
Intel® Xeon® CPU E5-2620 0 @ 2.00GHz
sign: 7.08 vs 9.13
abs: 6.32 vs 9.53
mini: 9.59 vs 22.66
maxi: 9.25 vs 22.94
minu: 9.76 vs 22.87
maxu: 9.94 vs 23.15
clang++ -std=gnu++11 (clang version 3.4)
Intel® Core(TM) i7-2600 CPU @ 3.40GHz
sign: 3.42 vs 4.11
abs: 3.26 vs 4.90
mini: 5.55 vs 11.98
maxi: 6.27 vs 12.00
minu: 5.65 vs 12.46
maxu: 5.55 vs 12.38
Intel® Xeon® CPU E5-2620 0 @ 2.00GHz
sign: 5.64 vs 6.74
abs: 5.57 vs 8.05
mini: 8.39 vs 18.64
maxi: 9.48 vs 18.66
minu: 8.92 vs 19.50
maxu: 8.92 vs 19.33
YuriKrugloff
Intel Core2 Duo E7300 2.66GHz
gcc (i686-posix-dwarf-rev1, Built by MinGW-W64 project) 5.2.0
Опции: -std=c++11 -s
sign: 25.29 vs 4.18
abs: 23.76 vs 13.42
mini: 31.17 vs 28.49
maxi: 30.17 vs 28.64
minu: 28.41 vs 29.11
maxu: 29.73 vs 29.00
2147483646
prefrontalCortex
Zealint
Intel Core 2 Duo E8400 @3.00GHz
Visual C++ 2015
Опции: /Ox
Последовательно
Хаотично
SidMeier
SidMeier
mwambanatanga
AoD314
MaksymGabielkov
Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2GHz
gcc version 4.9.2 (Raspbian 4.9.2-10)
options: -std=gnu++11
BranchFreeTimeout.cpp
sign: 66.21 vs 89.49
abs: 62.63 vs 78.74
mini: 71.58 vs 125.39
maxi: 71.58 vs 125.32
minu: 68.00 vs 128.90
maxu: 68.00 vs 128.90
2147483646
BranchFreeTimeoutNew.cpp
sign: 85.91 vs 93.07
abs: 81.43 vs 82.33
mini: 91.29 vs 128.90
maxi: 91.29 vs 128.90
minu: 87.70 vs 132.48
maxu: 87.70 vs 132.49
2147483646
MaksymGabielkov
mwambanatanga
win32asm
botanic@botfang:~$ cat /proc/cpuinfo | grep -wm1 Intel
model name: Intel® Core(TM) i7-4810MQ CPU @ 2.80GHz
опции везде -std=c++11 -O3 -lstdc++
botanic@botfang:~/source/other/fastest_algorithm$ clang -v
Debian clang version 3.5.0-10 (tags/RELEASE_350/final) (based on LLVM 3.5.0)
…
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
sign: -0.00 vs -0.00
abs: -0.00 vs -0.00
mini: -0.00 vs -0.00
maxi: -0.00 vs -0.00
minu: -0.00 vs -0.00
maxu: -0.00 vs -0.00
2147483648
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeoutNew
sign: 9.63 vs 0.69
abs: 0.50 vs 0.25
mini: 1.03 vs 2.10
maxi: 0.98 vs 2.27
minu: 1.14 vs 2.16
maxu: 0.87 vs 2.25
2147483646
botanic@botfang:~/source/other/fastest_algorithm$ gcc -v
…
gcc version 4.9.2 (Debian 4.9.2-10)
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
sign: 3.61 vs 1.90
abs: 1.16 vs 1.23
mini: 1.64 vs 2.91
maxi: 1.64 vs 2.32
minu: 1.86 vs 1.14
maxu: 1.62 vs 1.94
2147483646
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeoutNew
sign: 9.85 vs 0.72
abs: 9.77 vs 0.37
mini: 0.60 vs 0.98
maxi: 0.60 vs 0.99
minu: 11.09 vs 1.02
maxu: 0.62 vs 1.03
2147483646
вне программы кланг с -O1 (-O2 тоже был неверно понят):
botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
sign: 7.38 vs 5.86
abs: 4.74 vs 5.82
mini: 5.83 vs 7.06
maxi: 5.84 vs 6.41
minu: 5.82 vs 8.18
maxu: 5.89 vs 6.99
2147483646
qabal
Intel® Core(TM) i7 CPU 950 @3.07GHz 3.06GHz
Windows 7 32
g++ -std=c++11
sign: 6.18 vs 8.08
abs: 7.43 vs 12.77
mini: 11.19 vs 26.56
maxi: 11.30 vs 26.67
minu: 13.91 vs 23.85
maxu: 13.91 vs 24.64
kalterfive
Железо: Intel® Pentium® CPU N3530 @ 2.16GHz;
Компилятор: GCC 5.3.0;
Командная строка:
g++ -o3 -std=gnu++11.Линейно:
Хаотично:
ComradeAndrew
ComradeAndrew
То же самое для чуть более нового интела:
edb
Intel® Core(TM) i3-4130 CPU @ 3.40GHz
g++ -std=gnu++11 BranchFreeTimeoutNew.cpp
sign: 23.61 vs 1.75
abs: 22.11 vs 3.52
mini: 24.28 vs 10.84
maxi: 24.51 vs 10.83
minu: 23.90 vs 10.87
maxu: 23.80 vs 10.79
2147483646
grechnik
Для разнообразия, на AMD:
Но, надо отметить, определение empty в последовательной версии некорректно: что gcc, что clang успешно сворачивают цикл с empty в константу. gcc, кстати, в неправильную константу: https://godbolt.org/g/wibi2q.
Zealint
Вот же незадача. Даже не знаю, что делать. Volatile мне не подходит, она тупит в некоторых компиляторах, подобные пустые циклы, оказалось, тоже не подходят. Я подумаю…
Vladusch
Intel Xeon E5620
Visual C++ 2015
Опции: /Ox /arch:SSE2
Release Win32:
sign: 18.47 vs 4.68
abs: 15.53 vs 1.47
mini: 2.96 vs 8.32
maxi: 2.99 vs 7.92
minu: 3.06 vs 8.35
maxu: 2.94 vs 8.41
2147483646
Release x64:
sign: 18.56 vs 4.71
abs: 15.83 vs 1.68
mini: 3.08 vs 7.81
maxi: 3.02 vs 7.78
minu: 3.03 vs 8.32
maxu: 3.31 vs 7.61
2147483646
wolphin
AMD FX(tm)-4300 @ 3.80GHz
gcc version 4.8.4
g++ -std=c++11 -O2 BranchFreeTimeoutNew.cpp
sign: 11.89 vs 2.16
abs: 12.05 vs 0.00
mini: -0.05 vs 2.15
maxi: -0.08 vs 1.66
minu: 12.77 vs 2.23
maxu: 0.00 vs 1.74
2147483646
vioblex
Intel Core i7 @ 2.2 GHz (Mac)
g++ -std=c++11 BranchFreeTimeoutNew.cpp
sign: 27.91 vs 2.95
abs: 28.03 vs 4.16
mini: 32.46 vs 12.13
maxi: 32.33 vs 12.04
minu: 31.42 vs 12.93
maxu: 30.78 vs 12.90
2147483646
YuriKrugloff
xaizek
Intel® Core(TM) i7-4790 CPU @ 3.60GHz
gcc version 5.3.0 (GCC)
-std=c++11 -O3 -march=native
последовательно:
хаотично:
Zealint
Никак не могу понять, почему у нескольких людей уже такие тормоза на minu с IF? Очень резко выбивается из общей картины.
xaizek
Исходный вариант (
return a>b ? b:a;):Модифицированный вариант (
return b>a ? a:b;):Причуда компилятора (может если
%eaxявляется операндом не с той стороны, то шаблон для генерацииcmovне срабатывает; хотя скорее тут что-то посложнее).magicxor
У меня вообще отрицательные значения.
Хаотичная версия:
AMD A10-4600M APU with Radeon(tm) HD Graphics, 2300 МГц
Visual C++ 2015
Опции: /Ox
sign: 16.48 vs 0.76
abs: 15.21 vs -0.36
mini: -0.34 vs 5.09
maxi: -1.09 vs 4.94
minu: -0.39 vs 4.98
maxu: -1.18 vs 5.18
Zealint
Да, это входило в мои цели тоже — мне нужно было определить, будут ли у кого-то отрицательные значения, т. к. это свидетельствует о необходимости пересмотреть методологию расчётов.
4144
Для AMD такое вроде нормально, по крайней мере раньше был такой баг, исправлялось настройкой таймера в системе.
Попробуйте запустить ping 127.0.0.1 или адрес другого компьютера в локальной сети и посмотрите время ответа. Если получите отрицательное, это баг процессора.
Botanegg
Intel® Core(TM) i5-4670K CPU @ 3.40GHz
gcc (GCC) 5.3.0
Опции: -std=c++11 -O3 -DNDEBUG
Последовательно
sign: 4.64 vs 3.02
abs: 2.27 vs 2.35
mini: 2.34 vs 5.10
maxi: 2.34 vs 4.64
minu: 2.33 vs 4.54
maxu: 2.72 vs 4.47
Хаотично
sign: 10.26 vs 0.68
abs: 9.34 vs 0.33
mini: 0.55 vs 0.88
maxi: 0.55 vs 0.85
minu: 10.08 vs 0.72
maxu: 0.55 vs 0.93
Randl
Новая версия
Intel Core i7 5500U @ 2.4GHz
mingw-w64 x86_64-5.3.0-posix-seh-rt_v4-rev0
Без оптимизаций:
С оптимизациями (-fno-exceptions -fno-rtti -std=c++14 -O3 -fstrict-aliasing -flto -fomit-frame-pointer -march=native -floop-interchange -ftree-loop-distribution -floop-strip-mine -floop-block -ftree-vectorize):
А если включить еще и -ffast-math -funroll-loops, то получается фигня