Предыстория
Как-то раз у меня с коллегой завязался разговор по поводу улучшения инструментария для работы с битовыми флагами в перечислениях C++. На тот момент у нас уже была функция IsEnumFlagSet, принимающая на вход первым аргументом тестируемую переменную, вторым — набор флагов для проверки. Чем же она лучше старого доброго побитового И?
if (IsEnumFlagSet(state, flag))
{
}
// vs
if (state & flag)
{
}
На мой взгляд — читаемостью. Я довольно редко работаю с битовыми флагами и битовыми операциями вообще, поэтому при просмотре чужого кода намного легче воспринимать привычные имена функций, нежели загадочные & и |, которые сразу вызывают внутренний window.alert() c заголовком «Внимание! Тут, возможно, происходит какая-то магия».
if (state.Test(particularFlags)) {}Особенно читаемость ухудшается при операциях установки или снятия флагов. Сравните:
state |= flag; // если вы используете enum class, то нужно перегружать оператор |=
state &= ~flag;
//vs
RaiseEnumFlag(state, flag);
ClearEnumFlag(state, flag);
В процессе обсуждения также была высказана идея о создании функции
SetEnumFlag(state, flag, isSet): в зависимости от третьего аргумента, у state бы либо возводились флаги, либо снимались.Так как предполагалось, что этот аргумент передается в рантайме, то без оверхеда по сравнению с парой
RaiseEnumFlag/ClearEnumFlag, очевидно, не обойтись. Но ради академического интереса мне захотелось свести его к минимуму путем спуска в шахту к дьяволу микрооптимизаций.Реализация
1. Наивная реализация
Для начала введем наше перечисление (не будем использовать enum class для упрощения):
#include <limits>
#include <random>
enum Flags : uint32_t
{
One = 1u << 1,
Two = 1u << 2,
Three = 1u << 3,
OneOrThree = One | Three,
Max = 1u << 31,
All = std::numeric_limits<uint32_t>::max()
};И сама реализация:
void SetFlagBranched(Flags& x, Flags y, bool cond)
{
if (cond) {
x = Flags(x | y);
} else {
x = Flags(x & (~y));
}
}2. Микрооптимизация
Наивная реализация имеет очевидное ветвление, которое очень хотелось бы перенести в арифметику, что мы сейчас и попытаемся сделать.
Для начала нам нужно подобрать какое-то выражение, которое позволяет переходить из одного результата в другой на основе параметра. Например,
(x | y) & ¬p- При
p = 0возводим флаги:
(x | y) & ¬0 ? (x | y) & 1 ? x | y
- При
p = yфлаги снимаются:
(x | y) & ¬y ? (x & ¬y) | (y & ¬y) ? (x & ¬y) | 0 ? x & ¬y
Теперь нам нужно как-то «упаковать» в арифметику изменение значения параметра в зависимости от переменной
cond (помним — ветвления запрещены). Пусть изначально
p = y, и если cond истина, то пытаемся обнулить p, если нет, то оставляем все как есть.Напрямую с переменной
cond толком не поработать: при преобразовании в арифметический тип в случае true мы получим только одну единицу в младшем разряде, а нам в идеале нужно получить единицы во всех разрядах (UPD: всё-таки можно). По итогу, в голову не пришло ничего лучше решения с использованием побитовых сдвигов. Определим величину сдвига: мы не можем сразу сдвинуть все наши биты так, чтобы за одну операцию обнулить параметр
p, потому что стандарт требует, чтобы величина сдвига была меньше размера типа.Поэтому вычисляем максимальный размер сдвига, записываем предварительное выражение
constexpr auto shiftSize = sizeof(std::underlying_type_t<Flags>) * 8 - 1;
(x | y) & ~ ( y >> shiftSize * cond);
И отдельно обрабатываем младший бит результата выражения
y >> shiftSize * cond:(x | y) & ~ (( y >> shiftSize * cond) & ~cond);Упаковка ветвления произошла в
shiftSize * cond — в зависимости от false или true в cond, величина сдвига будет либо 0, либо 31 соответственно, и наш параметр будет либо равен y, либо 0.Что тут происходит при
shiftSize = 31: - При
cond = trueмы сдвигаем битыyна 31 вправо, вследствие чего самый старший битyстановится самым младшим, а все остальные обнуляются. У~condнаоборот, самый младший бит имеет значение 0, а все остальные — единица. Побитовое перемножение этих значений даст чистый 0. - При
cond = falseникакого сдвига не происходит,~condво всех разрядах имеет 1 и побитовое перемножение этих значений дастy.
Хочется заметить trade-off этого подхода, который не сразу бросается в глаза: без использования ветвлений мы вычисляем
x | y (то есть одну из веток наивного варианта) в любом случае, а дальше, за счет «лишних» арифметических операций, преобразуем ее в требуемый результат. И все это имеет смысл, если накладные расходы на дополнительную арифметику будут меньше, чем ветвление.Итак, финальное решение получилось следующим:
void SetFlagsBranchless(Flags& x, Flags y, bool cond)
{
constexpr auto shiftSize = sizeof(std::underlying_type_t<Flags>) * 8 - 1;
x = Flags((x | y) & ~(( y >> shiftSize * cond) & ~cond));
}(Размер сдвига корректнее считать через
std::numeric_limits::digits, см. комментарий)3. Сравнение
Реализовав решение без ветвления, я отправился на quick-bench.com, чтобы удостовериться в его преимуществе. Для разработки мы в первую очередь используем clang, поэтому я решил прогонять бенчмарки на нем (clang-9.0). Но тут меня ждал сюрприз…
И это с -O3. Без оптимизаций все еще хуже. Как так получилось? Кто виноват и что делать?
Командуем «отставить панику!» и идем разбираться на godbolt.org (quick-bench также предоставляет asm листинг, но godbolt в этом плане выглядит удобнее).
Далее будет идти речь только о уровне оптимизации -O3. Итак, какой же код нам сгенерировал clang для наивной реализации?
SetFlagBranched(Flags&, Flags, bool): # @SetFlagBranched(Flags&, Flags, bool)
mov eax, dword ptr [rdi]
mov ecx, esi
not ecx
and ecx, eax
or eax, esi
test edx, edx
cmove eax, ecx
mov dword ptr [rdi], eax
retНеплохо, правда? Clang тоже умеет в trade-off, и понимает, что вычислить обе ветки и использовать команду conditional move, которая не вовлекает в работу branch predictor, будет быстрее использования команд условных переходов (conditional jump).
Код branchless реализации:
SetFlag(Flags&, Flags, bool): # @SetFlag(Flags&, Flags, bool)
mov eax, dword ptr [rdi]
or eax, esi
test edx, edx
mov ecx, 31
cmove ecx, edx
shr esi, cl
not esi
or esi, edx
and esi, eax
mov dword ptr [rdi], esi
retПочти «branchless» — я, вроде бы, заказывал тут обычное умножение, а вы мне, батенька, conditional move принесли. Возможно, компилятор прав, и test + cmove в данном случае будет быстрее, чем imul, но я не настолько хорошо разбираюсь в ассемблере (знающие люди, подскажите, пожалуйста, в комментариях).
Интересно другое — по сути, для обоих реализаций после оптимизаций компилятор сгенерировал не совсем то, что мы просили, и в результате получилось нечто среднее: в обоих вариантах используется cmove, просто в branchless реализации у нас много дополнительной арифметики, которая и заваливает бенчмарк.
Clang восьмой версии и старше вообще использует настоящие условные переходы, «благодаря» которым «branchless» версия становится чуть ли не в полтора раза медленнее:
SetFlag(Flags&, Flags, bool): # @SetFlag(Flags&, Flags, bool)
mov eax, dword ptr [rdi]
or eax, esi
mov cl, 31
test edx, edx
jne .LBB0_2
xor ecx, ecx
.LBB0_2:
shr esi, cl
not esi
or esi, edx
and eax, esi
mov dword ptr [rdi], eax
retКакой вывод можно сделать? Помимо очевидного «не занимайтесь микрооптимизациями без надобности», разве что можно посоветовать всегда проверять результат работы в машинном коде — может оказаться так, что компилятор уже достаточно соптимизировал изначальный вариант, а ваши «гениальные» оптимизации ему будут непонятны, и назло вам он понатыкает условных переходов вместо умножений.
На этом месте можно было бы и закончить, если бы не одно «но». Код gcc для наивной реализации идентичен clang-овскому, а вот branchless версия..:
SetFlag(Flags&, Flags, bool):
movzx edx, dl
mov eax, esi
or eax, DWORD PTR [rdi]
mov ecx, edx
sal ecx, 5
sub ecx, edx
shr esi, cl
not esi
or esi, edx
and esi, eax
mov DWORD PTR [rdi], esi
retМое почтение разработчикам за столь изящный способ оптимизировать наше выражение, не используя ни
imul, ни cmove. Что тут происходит: bool переменная cond побитово сдвигается влево на 5 знаков (потому что тип нашего enum — uint32_t, его размер 32 бита, то есть 1000002), а затем из полученного результата вычитается она же. Таким образом, мы получаем 111112 = 3110 в случае cond = true, и 0 в противном. Надо ли говорить, что такой вариант быстрее наивного, даже с учетом его conditional move оптимизации?
Что ж, итог получился совсем странный — в зависимости от компилятора вариант без ветвлений может оказаться как быстрее, так и медленнее реализации с ветвлениями. Давайте попробуем помочь clang и преобразовать наше выражение по методу gcc (заодно упростим часть
~((y >> shiftSize * cond) & ~cond) по де Моргану — это делает и clang, и gcc):void SetFlagVerbose(Flags& x, Flags y, bool b)
{
constexpr auto shiftSize = sizeof(std::underlying_type_t<Flags>) + 1;
x = Flags( (x | y) & ( ~(y >> ((b << shiftSize) - b)) | b) );
}Такая подсказка имеет влияние только на trunk версию clang, где он действительно генерирует код аналогичный gcc (правда, в оригинальном «branchless» — все тот же test + сmove)
А что там у MSVC? В обоих версиях без ветвлений применяется честный imul (не знаю, насколько он быстрее/медленнее варианта clang/gcc — quick-bench не поддерживает этот компилятор), а в наивной версии появился conditional jump. Sad but true.
Итоги
Главным выводом, наверное, можно назвать то, что намерения программиста в высокоуровневом коде далеко не всегда отражаются в машинном коде — и это делает микрооптимизации бессмысленными без бенчмарков и просмотра листингов. Кроме того, результат микрооптимизаций может оказаться как лучше, так и хуже обычного варианта — все зависит от компилятора, что может представлять серьезную проблему, если проект кроссплатформенный.
Комментарии (56)
kunix
03.01.2020 18:02+2Сюда смотрели?
graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching
bool f; // conditional flag
unsigned int m; // the bit mask
unsigned int w; // the word to modify: if (f) w |= m; else w &= ~m;
w ^= (-f ^ w) & m;
// OR, for superscalar CPUs:
w = (w & ~m) | (-f & m);desiderium_07 Автор
04.01.2020 21:24Нет, я хотел сам получить выражение, поэтому нигде не искал. Эти варианты компактнее, спасибо, и вот почему: в статье я писал:
Напрямую с переменной cond толком не поработать: при преобразовании в арифметический тип в случае true мы получим только одну единицу в младшем разряде, а нам в идеале нужно получить единицы во всех разрядах.
Как оказалось, это не так — действительно,-condдает нам именно то, что нужно: приcond = falseэто даст те же нули, однако приcond = trueмы получим -1, то есть единицы во всех разрядах. Отталкиваясь от этого, видимо, можно и получить оба этих выражения.
Эти варианты еще хороши тем, что на всех компиляторах дают самый лучший результат (на MSVC asm аналогичен clang и gcc).
Clang 9.0 (последние два — варианты по ссылке):
gcc 9.2
kunix
04.01.2020 21:26Хех, я тоже хотел сам.
Но потом вспомнил, что я сегодня с похмелья, и полез на Bit Twiddling Hacks :)
Ryppka
04.01.2020 21:50(x | y) & ~0 ? (x | y) & 1 ? x | y
Минус перед единичкой не забыли? А то эквивалентность не выходит.desiderium_07 Автор
04.01.2020 00:41Нет, тут имеется в виду не С++ код, а логическое выражение, так что 1 это логическая единица. В этом случае '~' лучше поменять на '¬', да.
Nagg
04.01.2020 23:33clang вставляет cmove только если у него нет PGO (веса бранчей) если в бенчмарке все время будет выбираться одно из условий и только — то никакого cmove не будет вставлено.
qw1
03.01.2020 23:56+1Сама идея использовать
void SetFlag(Flags& x, Flags y, bool cond)
вместо идеоматичных
flags |= flag1; flags &= ~flag2;
плохая тем, что заставляет заранее пессимизировать код. Ведь `cond` в большинстве случаев константный — true или false, а компилятор не всегда сможет заинлайнить эту функцию (особенно, если используется не «наивный» вариант).desiderium_07 Автор
04.01.2020 00:38Так никто и не говорил об этом :) Эту функцию планировалось использовать в случае, если
condизвестно только в рантайме. Для приведенных выше строк предназначаются:RaiseEnumFlag(state, flag); ClearEnumFlag(state, flag);qw1
04.01.2020 09:58Программисты народ ленивый, особенно если их много в команде и каждый пишет свои вспомогательные ф-ции ))
Выучив SetFlag, они могут на нём и остановиться.
Не удивлюсь, если в C++ можно как-то намутить 3 варианта SetFlag, отдельные для константных значений true и false у последнего параметра, по аналогии с частичной специализацией шаблона. Тогда думать не надо, что использовать — всегда SetFlag.a-tk
04.01.2020 11:09Да легко!template<class T> constexpr FlagWrapper<T> Flags(T& value) { return value; } template<class T> class FlagWrapper { T& value; public: FlagWrapper(T& value) : value(value){} template<T flag> FlagWrapper& Set() { value |= flag; return *this; } FlagWrapper& Set(T flag) { value |= flag; return *this; } template<int flag> FlagWrapper& SetAt() { value |= T{1} << flag; return *this; } FlagWrapper& SetAt(int flag) { value |= T{1} << flag; return *this; } template<T flag> FlagWrapper& Clear() { value &=~ flag; return *this; } FlagWrapper& Clear(T flag) { value &=~ flag; return *this; } template<T flag> FlagWrapper& Toggle() { value ^= flag; return *this; } FlagWrapper& Toggle(T flag) { value ^= flag; return *this; } }qw1
04.01.2020 13:17Нет, это не то.
Надо чтобы
SetFlag(flags, bit, true); SetFlag(flags, bit, false); SetFlag(flags, bit, myboolean);
компилировались в вызовы трёх разных функций (оптимизированных, соответственно, под установку, сброс, или копирование бита).a-tk
04.01.2020 13:48Просто дайте возможность компилятору их заинлайнить и не вызывайте их по указателю.
qw1
04.01.2020 14:47А если алгоритмы принципиально разные, и фунция слишком большая, чтобы инлайнится?
Есть ли в C++ статическая диспетчирезация по значению параметра?a-tk
04.01.2020 15:351. Значит компилятор считает, что цена вызова ниже цены инлайнинга — так бывает.
2. template… — будет специализация. Если она используется в одном месте — значит скорее всего будет заинлайнена, если в нескольких и тяжёлая — см. п. 1.
2а. constexpr отчасти решает и эту проблему.
KanuTaH
04.01.2020 19:38+1Есть ли в C++ статическая диспетчирезация по значению параметра?
По значению прямо параметра функции, наверное, не получится пока, во всяком случае, я не знаю, как. Была у меня идея сделать это дело как-нибудь через шаблонные типы с частичной специализацией, на основе которых потом делаются перегруженные функции, и conversion constructor'ы в этих специализированных типах для прозрачного преобразования из bool в них, но не заработало это нормально.
Можно сделать просто через отдельные типы вместо одного bool на все случаи жизни и перегрузку (или шаблонизацию со SFINAE, по вкусу), что-то типа такого:
Заголовок спойлераnamespace Action { struct SetT {}; struct ClearT {}; constexpr SetT Set; constexpr ClearT Clear; struct Copy { explicit Copy(bool val) : m_val(val) {}; bool m_val; }; }; void SetFlag(int f, int b, Action::SetT) { [...] } void SetFlag(int f, int b, Action::ClearT) { [...] } void SetFlag(int f, int b, Action::Copy v) { [...] } int main() { [...] SetFlag(f, b, Action::Set); SetFlag(f, b, Action::Clear); SetFlag(f, b, Action::Copy {v}); [...] }
Yoooriii
04.01.2020 14:32+5По поводу:
Читаемость ухудшается при операциях установки или снятия флагов
state |= flag;
state &= ~flag;
//vs
RaiseEnumFlag(state, flag);
ClearEnumFlag(state, flag);
Я бы сказал это зависит от бэкграунда. Если вы занимаетесь программированием микроконтроллеров, то первый вариант выглядит естественно, а вот второй вызывает мягко говоря недоумение. Хотя для товарищей привыкших к языкам высокого уровня первый вариант просто нечитабелен, да и вообще пользоваться битовыми операциями в языках высокого уровня нынче некомильфо.
Иногда мне попадаются конструкции вида:
if (((bitmask & value) != 0) == false) {
/* условие (не)верно */
} else {
/* иначе */
}
Как к такому относиться, я не знаю, а вы?a-tk
04.01.2020 15:33А зачем
?) != 0) == false)VolCh
04.01.2020 15:56Явное лучше неявного?
a-tk
05.01.2020 11:21Напомнило…
if ((a == b).ToString().Length == "False".Length) ...
if ((a == b).ToString().Length == "True".Length) ...
TheCalligrapher
06.01.2020 19:36Нет.
Во-первых, в контекстах с выраженной булевской семаниткой, явное намного хуже неявного.
Во-вторых, почему результат предыдущего
!= 0— неявен, в результат== falseвдруг явен? Где логика?
И, самое главное, в третьих, если со скрежетом зубов еще можно пропустить
== true, то== false— это совершенно нечитаемо. Скрытая в== falseнеявная инверсия полностью убивает читаемость кода.a-tk
06.01.2020 20:21Тоже забавная вариация на тему:
switch (boolValue) { case false: // break; case true: // break; default: // break; }
mayorovp
04.01.2020 18:38+1Да и на языках высокого уровня первый вариант запросто может быть читаемее. Битовые операции — их же один раз выучил и помнишь, а вот у той же RaiseEnumFlag может быть аж 4 разных сигнатуры:
void RaiseEnumFlag(int& state, int flag); void RaiseEnumFlag(int flag, int& state); int RaiseEnumFlag(int state, int flag); int RaiseEnumFlag(int flag, int state);
deviant_9
04.01.2020 18:57+1constexpr auto shiftSize = sizeof(std::underlying_type_t<Flags>) * 8 - 1;
- Не 8, а CHAR_BIT.
- Всё равно будет неправильно, поскольку у целочисленного типа могут быть биты-заполнители (padding bits), которые здесь тоже подсчитаются.
Правильно (если тип беззнаковый, каким он в любом случае должен быть):
#include <limits> constexpr auto shiftSize = std::numeric_limits<std::underlying_type_t<Flags>>::digits - 1;
selrorener
05.01.2020 01:44Какой вывод можно сделать? Помимо очевидного «не занимайтесь микрооптимизациями без надобности»
Это не совсем верно. Хотя вы уже сами убедились в этом. clang очень слаб как компилятор. Делать какие-то выводы исходя из его результатов — не особо верно.
К тому же, ваш подход к измерениям так же не совсем верен. Эта функции не имеет смысла как не-инлайн. И даже по дефолту компилятор её почти всегда заинлайнит. А там результаты будут совершенно иные.
разве что можно посоветовать всегда проверять результат работы в машинном коде — может оказаться так, что компилятор уже достаточно соптимизировал изначальный вариант
Это дельный совет. Обратная связь это основа оптимизации.
а ваши «гениальные» оптимизации ему будут непонятны, и назло вам он понатыкает условных переходов вместо умножений.
Нет, просто у вас достаточно слабый компилятор. Я очень редко видел случаи, когда гцц мои "гениальные" оптимизации не понимал. Но опять же — тут нужно понимать компилятор. И оптимизировать исходя из результата.
Nagg
05.01.2020 01:57У меня хватает примеров когда гцц не мог в то, что умеет кланг/ллвм. Я бы не назвал его слабее гцц.
selrorener
05.01.2020 02:09У меня хватает примеров когда гцц не мог в то, что умеет кланг/ллвм. Я бы не назвал его слабее гцц.
Это всё, скорее всего, примеры, которые мало что значат. Просто было много статей в которых в шланг добавляли новую бесполезную эвристику, а после писал об этом. Причём сравнивали обычно с древними версиями гцц. Скорее всего, все ваши примеры — это оно самое.
Я же говорю о другом типе оптимизаций. А то, что выше — это просто примитивные реплейсы по эвристикам. Тут, очевидно, что будет множество примеров где в одном компиляторе есть какая-то эвристика, а в другом нет. Я это даже за оптимизации не считаю.
За оптимизации я считаю то, что мне сложно/невозможно сделать руками. Во всём этот шланг меня подводил. У него слабый flow-анализ. Допустим, он не в банальный кейс
f = [&]{++ptr;}; f(); *ptr = a; f(); *ptr = b;....
Да и бек у него под amd64 слабый. Рассказывают, что под arm сильный, но я не проверял. У гцц он намного сильнее.
Nagg
05.01.2020 04:00Вот из недавнего вам с флоу анализом: https://godbolt.org/z/gWgwj2
selrorener
05.01.2020 04:51Это не flow-анализ. Это очередной реплейс. К тому же пример специально подобран и вообще не состоятелен. Потому как gcc тупо ничего не сделает с кейсом T && T и все ифы там просто пыль в глаза.
Nagg
05.01.2020 11:32это flow-анализ. x && y — это не выражение, а два разных бейзик блока. и кейс вполне реальный. Про "реплейс" — это скорее про гцц, то как он реализует пипхол оптимизации на базе простого DSL (найти-заменить), в llvm же это все с кодом + он постоянно пытается деоптимизировать выражения в более сложные дабы найти возможности для CSE.
selrorener
05.01.2020 14:07это flow-анализ.
Нет.
x && y — это не выражениеИменно выражение. Блоки к теме отношения не имеют. гцц не просто не реплейсит
x && y— всё остальное он делает.
и кейс вполне реальный
Нет, кейс фейковый. Это явно видно. Взят случай, где гцц ничего не делает — выражение
x && y, далее придумывается какая-то лапша с ифами. И самое интересное — это работает. Вы продолжаете мне рассказывать про ифы, хотя они не при делах.
Про "реплейс" — это скорее про гцц, то как он реализует пипхол оптимизации на базе простого DSL (найти-заменить), в llvm же это все с кодом + он постоянно пытается деоптимизировать выражения в более сложные дабы найти возможности для CSE.
Никто не говорил, что в гцц нету реплейса. К тому же, я не знаю что мы обсуждаем. У меня есть конкретные реальные примеры( в том числе и в этом треде), а у вас есть специально подобранные кейсы с какой-то примитивной лапшой, которая никому ненужна.
У меня есть множество примеров того как clang ничего не может. Причём реальных. Причём таких, где он сливает в 2раза.
Я постоянно собираю код двумя компиляторами и у меня есть соответствующий опыт. clang генерирует почти всегда мусор за редкими исключениями.
Nagg
05.01.2020 14:33Именно выражение
Рекомендую почитать основы компиляторов перед тем как вступать в полемику.
У меня есть множество примеров того как clang ничего не може
Так поделитесь ими, ваш пример еще более бессмысленный чем мой (+ непонятно где именно там кланг не сработал). Мой реален, просто упрощен для годболта, а так я его достал из продакшена.
selrorener
05.01.2020 15:37Рекомендую почитать основы компиляторов перед тем как вступать в полемику.
На каком основании вы мне что-то рекомендуете? К тому же, почему вдруг стало игнорироваться всё остальное, где именно говорится о проблеме и том, что ваш пример не состоятелен? Зачем вы туда напихали ифов? Для чего? Если проблема не в ифах?
К тому же, абсолютно неважно как там какой-то компилятор трактует что-то в общем случае. В данном случае это выражение, чем и пользуется шланг выпиливая оттуда && реплейсом.
То, что с flow-анализом у гцц нету никаких проблем — https://godbolt.org/z/G5aAK9 — можно посмотреть так. Т.е. проблема именно в том, что гцц не реплейсит bool на 1|0 и && на & как это делает clang.
Так поделитесь ими, ваш пример еще более бессмысленный чем мой (+ непонятно где именно там кланг не сработал).
Почему вы игнорируете пример выше с установкой флагов? Мои пример это не код, на котором clang не сработал. Этот пример паттерна на котором он не сработал. Реальный пример слишком сложно перепастить на godbolt и ещё сделать так, что-бы он его собрал.
Мой реален, просто упрощен для годболта, а так я его достал из продакшена.
Вы не смогли даже правильную причину вывести и напихали непонятно зачем туда ифов. Как-то странно выглядит "реальная проблема". В ситуации с реальными проблемами сразу же ищется решение и ищется причина.
Nagg
05.01.2020 15:54В данном случае это выражение, чем и пользуется шланг выпиливая оттуда && реплейсом
"шланг" ничего не выпиливает — это просто фронтенд, он парсит С++ код в AST и эмитит промежуточный язык LLVM IR, который для данного случая выглядит как два отдельных выражения в разных бейсик блоках (для моего простого кода там их вообще 6) поэтому просто описать это как "ищи шаблон х && y и заменяй" не выйдет. Говорю это, т.к. сам пытался реализовывать такие оптимизации в C# JIT. Ещё раз повторю, пример вполне реален — выполняется два условия — возращаем одно значение, иначе — другое. Вот вам без вложенного ифа: https://godbolt.org/z/SMa2Zu (гцц ведет себя так, как будто я использовал __builtin_expect).
Реальный пример слишком сложно перепастить на godbolt и ещё сделать так, что-бы он его собрал.
Ну когда у вас будет пруф в виде годболт ссылки, я с удовольствием посмотрю, а пока это неаргументированный спор и раз вам лень его подкреплять хоть каким аругментом — мне тоже лень. Если у вас не получается сделать репро — то может быть не так уж и плохо всё у кланга?
selrorener
05.01.2020 16:41-1"шланг" ничего не выпиливает — это просто фронтенд, он парсит С++ код в AST и эмитит промежуточный язык LLVM IR
Очевидно, что под шлангом я имею ввиду компилятор полностью, включая llvm. К тому же llvm в текущем виде создан и живёт для шланга. И шланг часть llvm.
который для данного случая выглядит как два отдельных выражения в разных бейсик блоках (для моего простого кода там их вообще 6) поэтому просто описать это как "ищи шаблон х && y и заменяй" не выйдет.
Очевидно, что шаблон там будет не x && y, а другой. Но хорошо, пусть формально это можно назвать flow-анализом. Будем называть так.
Вот вам без вложенного ифа
Зачем мне это? Я сразу же сказал в чём там проблема и сказал, что будет так же и без вложенного ифа.
гцц ведет себя так, как будто я использовал __builtin_expect
Гцц ведёт себя так, потому что попросту никаких арифметических преобразований не производит в данном случае. К flow эта проблема отношения не имеет. Даже если там написать bool & bool — гцц не осилит. А вот если если заменить на uint8_t — всё работает. У llvm есть i1, скорее всего у гцц бул какой-то отдельный кейс, а не просто однобитное число. Но в данном случае это только часть проблемы.
Ну когда у вас будет пруф в виде годболт ссылки, я с удовольствием посмотрю, а пока это неаргументированный спор и раз вам лень его подкреплять хоть каким аругментом — мне тоже лень.
Опять же, у меня есть пруф — данная тема. Вы продолжаете его игнорировать. Я не обязан бежать на пруфом новым, если старый вам по какой-то причине неугоден. Не угоден — это дыры в вашей аргументации.
Если у вас не получается сделать репро — то может быть не так уж и плохо всё у кланга?
Всё плохо. Я не сохраняю примеры, потому как они мне не интересны. Я не часто спорю на эту тему. А любой реальный пример, если это не форфан прикрученные ифы к левой проблеме — сложно перепастить на godbolt.
Очевидно, что в таких примитивных двух строчках ничего нормально не проверить. Люди привыкли сравнивать херню, а не на реальных мегабайтах нагенереной лапши.
Nagg
05.01.2020 16:48+1К тому же llvm в текущем виде создан и живёт для шланга.
Нет, он был создан как промежуточный язык для любого ЯП.
Очевидно, что шаблон там будет не x && y, а другой
Нет, не очевидно.
у меня есть пруф — данная тема. Вы продолжаете его игнорировать.
Можете оформить ваш "пруф" как ссылку на годболте где будет сразу ВИДНА проблема? Если нет — это не пруф, а словоблудие. Которое мне, увы, надоело. Всего доброго.
У кланга действительно есть проблемы с флоу анализом и у меня есть пяток примеров, но раз вы ни одного не превели — то и я не буду.selrorener
05.01.2020 17:28-1Нет, он был создан как промежуточный язык для любого ЯП.
Нет. К тому же, я не говорил о том, чем он был создан. Я написал "в текущем виде", что-бы не ссылались на википедию те, кто за ним не следил.
Нет, не очевидно.
Очевидно. Точно так же, как очевидно то, что не имеют ввиду под шлангом только фронт. Абсолютно неважно в какую структуру преобразуется выражение — паттерн останется. К тому же, его можно узнать у шланга.
Это, кстати, та причина по которой я не разделяю llvm и шланг. Хоть llvm и даёт достаточно хайлевел api для генерации ir, но у фронта есть некая степень свободы. Которая может давать разницу и на которую может быть завязана оптимизация.
Можете оформить ваш "пруф" как ссылку на годболте где будет сразу ВИДНА проблема?
Ещё раз повторю. То, что вы пытаетесь выдать за пруф — пруфом не является. Это просто реплейс на x && y к которому вы форфан прикрутили ифы, не понимания что там и как происходит.
Которое мне, увы, надоело. Всего доброго.
Ещё раз, в теме уже есть пруф. Пока вы не ответите на него — других пруфов вам никто не даст. И игнор и попытка тянуть время — не сработает.
Хотя ладно. Мои примеры попросту не влезет в gotbolt. Но я поискал в истории — https://godbolt.org/z/nd2L72 — вот адаптировал пример на flow.
qw1
05.01.2020 17:00Мне кажется, тут clang перестарался.
Немного меняем пример, и у gcc скорее всего будет лучше latency, потому что в выходе clang больше инструкций и все они последовательно зависимы (т.е. выполнение не распараллеливается)
godbolt.org/z/mZgnr9
А вот здесь clang вообще на каком основании сделал безусловное чтение cond2? Переменная находится на другой странице, и эта страница может быть paged out. Это баг компилятора.
godbolt.org/z/Sssp7JNagg
05.01.2020 17:05Немного меняем пример, и у gcc скорее всего будет лучше latency, потому что у clang больше инструкций и все они зависимы (т.е. не распараллеливаются)
А вот это не факт, код кланга бранчлес, так что в зависимости от коллера может быть быстрее или медленее. Тем более с недавними патчами микрокода от Интел все джампы могут в любой момент солидно просесть. Попробуйте изменить свой пример добавив PGO профиль — кодген будет уже другим.
qw1
05.01.2020 17:10А вот это не факт, код кланга бранчлес
Я например слышал, что сейчас Intel рекомендует использовать бранчи вместо CMOVXX, потому что предиктор у них очень хороший, а CMOV перед выполнением всегда ждёт вычисления всех операндов.Nagg
05.01.2020 17:14CMOV в Skylake ускорили в два раза по летанси (и пропускной?) так что теперь он вроде всегда быстрее: https://raw.githubusercontent.com/xiadz/cmov/master/output/out-6700k.png (https://github.com/xiadz/cmov)
А джампы замедлили патчем (если джам/таргет пересекают случайно границу в 32 байта кода — то получают огромное пенальти)
qw1
05.01.2020 17:33Хотя, по вашей ссылке, в варианте CMOVCC код был короче, чем с JMPCC, и даже так в некоторых случаях они были равны. Здесь же (https://godbolt.org/z/mZgnr9) у clang всегда 7 инструкций до ret, а у gcc в лучшем случае 3, в худшем 6. То есть, не факт что clang быстрее.
selrorener
05.01.2020 17:39-2(и пропускной?)
Очевидно, что нет. Она и так была минимальной.
так что теперь он вроде всегда быстрее
Он итак был всегда быстрее, а бенчмарк этот — мусор. Он ничего не мериет. Он не учитывает засирание фронта мусором от джампов. Даже если сама логика не зависит от него, что крайне симнительно, то как минимум от этого зависит соседний поток при наличии SMT.
Точно так же, данный мусорный бенчмарк бенчит летенси, а если код упирается в летенси — это плохой код. Как минимум рядом с ним можно написать что-то ещё.
Т.е. бенчмарк замеряет только один сомнительный кейс, когда SMT нет, когда ещё какой-то логики рядом нет, когда логика сама по себе итеративна, т.е. упирается в летенси.
TheCalligrapher
06.01.2020 19:31constexpr auto shiftSize = sizeof(std::underlying_type_t<Flags>) * 8 - 1;
Что это за магическая константа 8?
(А, вижу, уже заметили.)
vital72
А использовать битовые поля, не?
desiderium_07 Автор
У нас «прокачанные» перечисления с интроспекцией и прочими плюшками, так что не.
IgorPie
Выводы в статье правильные. А читаемость можно подлатать макросами.
Кроме того, компиляторы сейчас очень умные и можно не жадничать в плане переменных в ущерб читаемости и разбивать строку вычислений на отдельные читаемые строки. (Наоборот, приходится еще volatile ставить, чтобы компилятор не наоптимизировал даже с -o0).
В стареньких DSP иногда все печально с переходами. Например jmp только дальше по программе, без шагов назад, поэтому там подобный подход необходим для выживания.
Antiproton
А можно глупый вопрос? Как в этих стареньких DSP реализовывались циклы и вызовы подпрограмм?
IgorPie
Вопрос скрывает в себе ответ: никак. Если работа идет со звуком ( или каким-то датчиком, например, вибрации), то 48000 раз в секунду запускается одна и та же программа длиной 128 (1024, 4096) команд и всё. На старте — читаются данные с АЦП, на выходе — отправляются в ЦАП (ну, или иные интерфейсы).
Переход — только вперед. «Обработка» «массивов» — аппаратный кольцевой буфер, где можно в начало кольца дописать данные. Для хранения мгновенных данных (состояний ручек управления, или фильтров) — регистры.
Регистр флагов показывает состояние аккумулятора. Но чаще всего, логика реализуется математикой как в статье.
selrorener
А что вы используете для прокачки перечислений?
desiderium_07 Автор
Макросы, куда же без них. Распространенный вариант — оборачивать определение перечисления в макрос, а вот тут используют __PRETTY_FUNCTION__ и __FUNCSIG__, чтобы вытащить имена перечислений, и даже оборачивать ничего не надо.
selrorener
Нет. Глянул и не смог понять как это могло бы работать. Уже думал, что я чего-то не знаю и вот оно открытие, но нет. Всё оказалось куда проще.
Расскажу как это работает, авось кому интересно будет.
База для реализации — это данный фокус. Смысл его заключается в том, что если мы передаём правильное значение енума, то он преобразуется в имя значения. Если нет — там остаётся каст.
Далее оно берёт и тупо перебирает какой-то диапазон значений, в поисках правильных. https://godbolt.org/z/8Q-EEf — как-то так.
Захардкодены туда -128...128 т.е. универсальность крайне сомнительна. Если значение выйдет за диапазон — оно никак про него не узнает. Опасно юзать такое. для чего-то шире uint8_t.