Comments 60
int x,y,r;
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
хм, забыл про абс
mask = v >> sizeof(int) * CHAR_BIT — 1;
r = (v + mask) ^ mask;
mask = v >> sizeof(int) * CHAR_BIT — 1;
r = (v + mask) ^ mask;
(с) graphics.stanford.edu/~seander/bithacks.html
вот это -(x < y) — можете прояснить?
А вот эта операция не содержит ли условного перехода внутри: -(x < y)?
Нет, но считается, что true == 1, а false == 0
Перехода нет. Есть лишь вычисление выражения (x<y) что есть sub x, y результат которого уходит дальше.
В современных процессорах есть команда SETL, которая записывает в регистр результат «меньше?» последнего сравнения (в виде 0 или 1). Без такой команды обойтись без переходов было бы очень сложно.
А потом этот код разбирать какому-нибудь программисту. Не завидую ему.
Если снабдить минимальными комментариями — разберется. Да и сам факт разбора кода декодера означает преодоление некоторого входного порога, «какой-нибудь» программист туда просто не полезет
Главное — добавить в начало строчку // return sign(a*b) * min(abs(a), abs(b))
Как раз именно та ситуация, когда нужны комментарии. При наличии их и тестов нет никаких проблем.
>Не завидую ему.
Ссылку на эту статью в комменты — и я наоборот ему завидую.
Ссылку на эту статью в комменты — и я наоборот ему завидую.
UFO just landed and posted this here
Спасибо, интересно и несложно. Хотя у atrydg действительно компактнее вышло.
Никак не мог распарсить
Про пару опечаток в личку отписал.
Никак не мог распарсить
(unsigned)-1Решил спросить что это такое и дошло.
Про пару опечаток в личку отписал.
Здесь условных переходов точно нет. Сравнений тоже (предполагается, что ни a, ни b не равны -2^31)
int sa=a>>31, sb=b>>31;
int sres=sa^sb;
a=(a^sa)-sa; b=(b^sb)-sb;
int d=a-b;
d&=(d>>31);
return ((b+d)^sres)-sres;
А потом кто-то запустит это на 64 битной машине.
Если компилятор мощный, то может наблюдаться прирост производительности в разы.
По идее, все будет хорошо, потому что int на 64х битной машине точно также равен четырем байтам.
Совсем нет.
По стандарту не задается размер int, есть только рекомендация делать его равным машинному слову. на 64 битах машинное слово будет равно 64 битам, и размер int, скорее всего будет зависеть от настроек компилятора. Компиляторов много разных, поэтому с каким нибудь может получиться, что int имеет размер 64 бита. Попробовал добиться этого от GCC, но там для x86 и x86_64 размер int всегда равен 32 битам.
По стандарту не задается размер int, есть только рекомендация делать его равным машинному слову. на 64 битах машинное слово будет равно 64 битам, и размер int, скорее всего будет зависеть от настроек компилятора. Компиляторов много разных, поэтому с каким нибудь может получиться, что int имеет размер 64 бита. Попробовал добиться этого от GCC, но там для x86 и x86_64 размер int всегда равен 32 битам.
int вообще-то в языке, а не на машине.
А уж что там за компилятор и как он его переделает — другое дело.
А уж что там за компилятор и как он его переделает — другое дело.
Если просто запустит — ничего не произойдет.
Если именно пересобрать под 64х битную платформу — то зависит от компилятора. В случае MSVS тоже ничего не произойдет.
Если именно пересобрать под 64х битную платформу — то зависит от компилятора. В случае MSVS тоже ничего не произойдет.
Попробовал собрать и повторить.
И ускорение не в 10 раз, и… тупо не сходятся результаты расчетов.
C:\Temp\hey>1
0.954874 sec, x=-1132049649
0.381489 sec, x=-1903287257
0.452164 sec, x=971761649
gist.github.com/anonymous/5601991
Что я делаю не так??
И ускорение не в 10 раз, и… тупо не сходятся результаты расчетов.
C:\Temp\hey>1
0.954874 sec, x=-1132049649
0.381489 sec, x=-1903287257
0.452164 sec, x=971761649
gist.github.com/anonymous/5601991
Что я делаю не так??
Вы уверены, что в целях оптимизации компилятор не объединил три цикла в один? У меня сейчас нет возможности запустить ваш пример, как появится — проверю и отпишусь.
Лучше на ты. Да, уверен. В дебажном билде результаты расчетов такие же, в дизасме наглядно видать 3 цикла и честные вызовы функций.
Ну и эта, пример не мой ;) практически чистый cut/paste плюс пачка незначащих правок типа замены tprintf на printf. И одна значащая, вынос rand() за цикл с целью мерить именно оптимизируемую функцию, а не воздух.
Ну и эта, пример не мой ;) практически чистый cut/paste плюс пачка незначащих правок типа замены tprintf на printf. И одна значащая, вынос rand() за цикл с целью мерить именно оптимизируемую функцию, а не воздух.
Результат вычислений (x), естественно должен быть одинаков во всех трех случаях вне зависимости от debug/release. Спасибо, что обратил внимание, в LLR_2() и в LLR_3() вкрались опечатки. в LLR_2() это отсутствующая скобка (((unsigned)a^b)>>31), в LLR_3() не хватает скобок при операторе ^ и a вместо b там, где рассчитывается модуль а.
Насчет увеличения времени… В твоем примере (с вынесенном рандом) у меня функция с условными переходами работает быстрее чем остальные. По-видимому оба массива полностью поместились в стеке и и предсказание переходов дало свои плоды. Я увеличил размер массива до 1Мб, после чего LLR опять стала самой медленной. Но разница во времени выполнения — 3.5 раза а не 10.
Насчет увеличения времени… В твоем примере (с вынесенном рандом) у меня функция с условными переходами работает быстрее чем остальные. По-видимому оба массива полностью поместились в стеке и и предсказание переходов дало свои плоды. Я увеличил размер массива до 1Мб, после чего LLR опять стала самой медленной. Но разница во времени выполнения — 3.5 раза а не 10.
Скопировал из статьи заново, результаты начали сходиться. С любым размером блока ускорение есть, однако ни разу не 10 раз. Вот например с блоком 16 мб выходит около 2.1 раз.
gist.github.com/anonymous/5604401
gist.github.com/anonymous/5604401
Я сделал дополнение к посту. Вероятно, все упирается в конкретную последовательность инструкций, а вызов rand() сильно «сбивает» конвеер.
int a,b,min;
...
min = a - (a-b) * ( ((a-b) >> 31) + 1 );
Только вот надо сказать, что декодер, работающий по такой приближенной формуле, довольно сильно проигрывает по вероятности ошибки «настоящей» формуле. Настоящая формула выглядит так:
где a и b — настоящие LLR (т.е., не квантованные в int). К сожалению, в таком виде формула очень медленная и численно неустойчивая. Поэтому умные люди придумали эквивалентную ей формулу:
Как видно, здесь все упирается в вычисление функции
Интереснее, как оптимизировать другую половину алгоритма (на variable nodes). Там приходится «обрезать» получающиеся суммы, чтобы они не выходили за пределы некоторого интервала [-N, N], т.е. примерно так: x = max(min(a, N), -N). Вот тут битовые ухищрения у меня работали медленнее, чем условные переходы.
x = 2 * atanh(tanh(a/2) * tanh(b/2)),
где a и b — настоящие LLR (т.е., не квантованные в int). К сожалению, в таком виде формула очень медленная и численно неустойчивая. Поэтому умные люди придумали эквивалентную ей формулу:
x = max(a + b, 0) + log(1 + exp(-abs(a + b)))
- max(a, b) - log(1 + exp(-abs(a - b)))
Как видно, здесь все упирается в вычисление функции
log(1 + exp(-abs(t))) для разных значений t. Для нее приходится делать lookup table. Работает это дело относительно медленно — уже не так важно, как вы там вычисляете максимум.Интереснее, как оптимизировать другую половину алгоритма (на variable nodes). Там приходится «обрезать» получающиеся суммы, чтобы они не выходили за пределы некоторого интервала [-N, N], т.е. примерно так: x = max(min(a, N), -N). Вот тут битовые ухищрения у меня работали медленнее, чем условные переходы.
Полностью согласен, я несколько упростил специально для того, чтобы акцентировать внимание на условных переходах. естественно далее там есть табулированный логарифм экспоненты.
Если N — степень двойки то на ARM например есть инструкция ssat, предполагаю на x86 что-нибудь похожее должно быть. А еще есть инструкции для saturating арифметики (qadd/qsub на ARM + аналоги для NEON). В SSE наверное тоже есть, не приходилось под x86 писать. Saturating-арифметика довольно часто используется в DSP и использование специальных инструкций дает прирост скорости в разы, по сравнению с условными переходами.
Каким компилятором собирали? VC++?
Для дальнейшего исследования можно попробовать посмотреть с vTune'е что происходит и где тормоза.
Для дальнейшего исследования можно попробовать посмотреть с vTune'е что происходит и где тормоза.
Странно, что до нынешнего времени компиляторы не научились распознавать и оптимизировать канонические реализации max и sign
И где здесь C++? :)
Начиная с Пентиум Про есть команда условного перемещения — cmov.
если компилятор тупит и не хочет её генерировать для конструкций вида
a=a<b?a:b;
то можно ему
Сгенерируется красивый код без ветвлений:
Но он не сильно быстрее вашего варианта (cmov довольно медленно выполняется).
если компилятор тупит и не хочет её генерировать для конструкций вида
a=a<b?a:b;
то можно ему
подсказать:
static inline int f4(int a, int b)
{
int _a=-a;
_a=_a<0?a:_a;
int _b=-b;
_b=_b<0?b:_b;
_a=_a<_b?_a:_b;
int _c=-_a;
_c=(a^b)<0?_c:_a;
return _c;
}
Сгенерируется красивый код без ветвлений:
примерно такой
//eax==a, edx==b
mov ebx, eax
neg ebx
cmovs ebx, eax
mov ecx, edx
neg ecx
cmovs ecx, edx
cmp ebx, edx
cmovg ebx, edx
mov edx, ebx
neg edx
xor eax, ebx
cmovs ebx, edx
//ebx <- ответ
Но он не сильно быстрее вашего варианта (cmov довольно медленно выполняется).
А вот этот заметно быстрее
static inline int f5(int a, int b)
{
int s,_a,_b,n[2];
_a=(a>>31)&0xFFFFFFFE;
_b=(b>>31)&0xFFFFFFFE;
s=(_a^_b)+1;
a*=(_a)+1;
b*=(_b)+1;
n[0]=b;
n[1]=a;
return s*n[a<b];
}
А, получается вот как можно добиться cmov от компилятора. Мы пробовали использовать асмовую вставку с ним, действительно не особенно выигрывает по сравнению с условным переходом.
Удивительно, единственная выкладка на ассемблере в посте про низкоуровневую оптимизацию. И то, не в посте а в комментарии.
А собственно какой из алгоритмов LDPC декодера был реализован?
Реализация взята отсюда (с некоторыми оптимизациями, в т.ч. описанной в топике), длины блоков 16200 или 64800 бит
Ну вы не с того краю заходите ИМХО. Belief propagation (BP) алгоритм самый медленный. Все равно что сортировку пузырьком оптимизировать.
А что можете посоветовать?
Все зависит от постановки задачи, а об этом вы ни-ни. Откуда у вас вообще LDPС вылезло, что вы делаете?
Ну и конечно самый общий ответ на ваш вопрос тут ieeexplore.ieee.org
Ну и конечно самый общий ответ на ваш вопрос тут ieeexplore.ieee.org
Sign up to leave a comment.
Оптимизация времени выполнения программы на С++ (убираем условные переходы)