Как выглядит безветвление, если в C ++ выглядит? - PullRequest
Новая
       10

Как выглядит безветвление, если в C ++ выглядит?

8 голосов
/ 26 мая 2011

Я понимаю, что у меня есть большой недостаток знаний в этой области (причудливый способ сказать, что я не знаю, Джек об этом).

Есть ли документация относительно того, как и когда их использовать

Ответы [ 3 ]

11 голосов
/ 26 мая 2011

Помимо всего кода без ветвей, основанного на твидлинге (который не охватывает все, например, FP), вы получите инструкции, специально предназначенные для создания кода без ветвей, это будет SETcc, FCMOVccи CMOVcc под x86, которые выполняют операции на основе флагов условий из сравнения.

будет действительно простой пример (да, пример настолько прост, что, вероятно, никогда не напишут что-то подобное, еготолько для демонстрации ясности): 

bool CheckZero(int x)
{
    if(x == 0)
       return true;

    return false;
    //OR we can use: return (x == 0) ? true : false; 
}

теперь простой компилятор x86 может скомпилировать его так: 

    MOV EAX,[ESP + 4]
    TEXT EAX,EAX
    JE _TRUE
    XOR EAX,EAX
    RETN 4

_TRUE:
    MOV EAX,1
    RETN 4

оптимизирующий компилятор x86 перенесет его в следующий код без ветвей(или аналогичный): 

MOV ECX,[ESP + 4]
XOR EAX,EAX
TEST ECX,ECX
SETE AL
RETN 4

Здесь можно найти немного более сложный пример .

Однако это то, что будет выполнять компилятор, а не какой-тоВы должны беспокоиться о себе (по крайней мере, не анализируя вывод вашего компилятора).но если код должен быть без ветвей без сбоев, C ++ не обеспечивает достаточного контроля для этого, поэтому вам нужно использовать (встроенную) сборку.

4 голосов
/ 26 мая 2011

http://hbfs.wordpress.com/2008/08/05/branchless-equivalents-of-simple-functions/

Я думаю (хотя я не знаю больше, чем то, что читаю на странице), это способ получить функциональность без ветвления (что имеет смысл на основе слов без ветвейесли ;)).Не знаю больше.

Спасибо, мистер Google.

1 голос
/ 22 октября 2017

Я написал симулятор троичной логики не так давно, и этот вопрос был для меня жизнеспособным, поскольку он напрямую влияет на скорость выполнения интерпретатора; От меня требовалось моделировать тонны и тонны троичных логических элементов как можно быстрее.

В двоично-троичной системе один трит упакован в два бита. Наиболее значимый бит означает отрицательный, а наименее значимый - положительный. Случай "11" не должен возникать, но он должен быть обработан должным образом и обозначен как 0.

Рассмотрим функцию inline int bct_decoder( unsigned bctData ), которая должна возвращать наш отформатированный трит как обычное целое число -1, 0 или 1; Как я заметил, есть 4 подхода: я назвал их «cond», «mod», «math» и «lut»; Давайте исследуем их

Первый основан на условных переходах jz | jnz и jl | jb, таким образом, cond. Его производительность не очень хорошая, потому что зависит от предсказателя ветвления. И что еще хуже - это меняется, потому что неизвестно, будет ли априори одна или две ветви. И вот пример: 

inline int bct_decoder_cond( unsigned bctData ) {
   unsigned lsB = bctData & 1;
   unsigned msB = bctData >> 1;
   return
       ( lsB == msB ) ? 0 : // most possible -> make zero fastest branch
       ( lsB > msB ) ? 1 : -1;
}

Это самая медленная версия, в худшем случае она может включать 2 ветви, и это то, где двоичная логика не работает. На моих 3770k он дает в среднем около 200 МИПС на случайных данных. (здесь и после - каждый тест является средним из 1000 попыток на случайно заполненном наборе данных 2 МБ)

Далее следует оператор по модулю, и его скорость находится где-то между первым и третьим, но определенно быстрее - 600 MIPS: 

inline int bct_decoder_mod( unsigned bctData ) {
    return ( int )( ( bctData + 1 ) % 3 ) - 1;
}

Следующим является безответственный подход, который включает только математику, то есть математику; он вообще не принимает инструкции перехода: 

inline int bct_decoder_math( unsigned bctData ) {
    return ( int )( bctData & 1 ) - ( int )( bctData >> 1 );
}

Это делает то, что должно, и ведет себя действительно замечательно. Для сравнения, оценка производительности составляет 1000 MIPS, и это в 5 раз быстрее, чем разветвленная версия. Возможно, разветвленная версия замедлена из-за отсутствия встроенной поддержки 2-битных подписанных int. Но в моем приложении это довольно хорошая версия сама по себе.

Если этого недостаточно, мы можем пойти дальше, имея что-то особенное. Следующий метод называется таблицей поиска: 

inline int bct_decoder_lut( unsigned bctData ) {
    static const int decoderLUT[] = { 0, 1, -1, 0 };
    return decoderLUT[ bctData & 0x3 ];
}

В моем случае один трит занимал только 2 бита, поэтому таблица lut составляла всего 2b * 4 = 8 байт и стоила попробовать. Он помещается в кэш и работает быстро со скоростью 1400-1600 MIPS, здесь моя точность измерений снижается. И это в 1,5 раза быстрее по сравнению с быстрым математическим подходом. Это потому, что у вас есть только заранее вычисленный результат и одна AND инструкция. К сожалению, кэши маленькие, и (если длина вашего индекса превышает несколько бит), вы просто не сможете его использовать.

Так что я думаю, что ответил на ваш вопрос о том, на что может быть похож разветвленный / безветвленный код. Ответ гораздо лучше и с подробными образцами, реальным применением и результатами измерений реальных характеристик.

...