Оптимизация времени выполнения программы на С++ (убираем условные переходы)

При оптимизации времени выполнения алгоритма, использующего LDPC декодер, профайлер привел к функции, вычисляющей следующее значение:
image
где a и b — целые числа. Количество вызовов шло на миллионы, а реализация ее была достаточно проста и бесхитростна:

int LLR(int a, int b)
{
  if (a>0) 
    return (b>0) ? __min(a,b) : -__min(a,-b);
  else
    return  (b>0) ? -__min(-a,b) :  __min(-a,-b);
}


Функция состоит, по сути, из трех последовательных операций сравнения. Это дает (с учетом оптимизации компилятора) два (если числа разных знаков) или три (если одного) условных перехода для получения результата. Вспомнив о потенциальных проблемах конвеера при большом количестве условных переходов, было решено уменьшить их количество или даже избавиться от них. Для оценки быстродействия был написан небольшой
тестовый проект
#include <Windows.h>

static inline int LLR(int a, int b)
{
	if (a>0) 
		return (b>0) ? __min(a,b) : -__min(a,-b);
	else
		return (b>0) ? -__min(-a,b) : __min(-a,-b);
}

int _tmain(int argc, _TCHAR* argv[])
{
	SetPriorityClass(GetCurrentProcess(),REALTIME_PRIORITY_CLASS);
	SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_TIME_CRITICAL);
	srand(0);
	int x(0);
	__int64 t1,t2;	
	QueryPerformanceCounter((LARGE_INTEGER*)&t1);
	for (size_t i=0;i<MAXUINT>>4;i++)
	{
		int a = rand() - RAND_MAX / 2;
		int b = rand() - RAND_MAX / 2;
/*		x += LLR(a,b);*/
	}
	QueryPerformanceCounter((LARGE_INTEGER*)&t2);
	t2 -= t1;
	QueryPerformanceFrequency((LARGE_INTEGER*)&t1);
	_tprintf_s(_T("%f"),t2/(t1*1.));
	return 0;
}


Сборка производилась в MSVS 2008 в конфигурации Release (настройки по умолчанию) для платформы x86.

Для начала, закомментируем вызов расчетной функции чтобы оценить время выполнения цикла с генерацией случайных чисел (к сожалению, вызов QueryPerformanceCounter() сам по себе довольно медленный и приводит к значительному искажению результата если его делать внутри цикла). Запускаем проект несколько раз, чтобы убедится в повторяемости результата. На машине с процессором Intel Core i7-3770 c частотой 3.4 ГГц время выполнения составляет в среднем 9.2 секунды. Если раскомментировать вызов расчетной функции, пересобрать проект и повторить эксперимент — получаем примерно 11.5 секунд. Прирост времени выполнения налицо, с ним и будем бороться.

Попробуем избавиться от условных операторов. Для начала выясним знак произведения a и b. Вычислять его в лоб некорректно из-за возможного переполнения. Так как нам важен только знак (то есть значение бита знакового разряда целого числа), то уместно воспользоваться операцией xor для определения знака произведения a и b. Далее, сдвинем результат a xor b вправо на 31 бит (оставляя только знаковый разряд) и получим 0 в случае неотрицательного числа и 1 в случае отрицательного. Умножим это значение на два, вычтем из единицы и получим -1 для отрицательного числа и 1 для неотрицательного:
int sign = 1-2*((unsigned)a^b)>>31);
Теперь рассчитаем модули a и b. Аналогичным методом определяем знаковые коэффициенты a и b и умножаем на них:
int c;
c = 1-2*(((unsigned)a)>>31);
a *= c;

c = 1-2*(((unsigned)b)>>31);
b *= c;
Перейдем к расчету минимума. Поскольку a и b уже имеют неотрицательные значения, рассчитать минимум можно, ориентируясь на знак их разности:
int numbers[2], min;	
numbers[0] = b;
numbers[1] = a;

a -= b;
c = (unsigned(a))>>31;

min = numbers[c];
Соберем все вместе и получим
следующую функцию
static inline int LLR_2(int a, int b)
{
	int sign, numbers[2];
	sign = 1-2*(((unsigned)a^b)>>31);
	a *=  1-2*(((unsigned)a)>>31);
	b *= 1-2*(((unsigned)b)>>31);
	numbers[0] = b;
	numbers[1] = a;
	a -= b;
	return sign*numbers[((unsigned)a)>>31];
}


Заменим вызов LLR() на LLR_2() и посмотрим, что получилось. В ассемблерном коде теперь ни одного условного перехода, зато появились три инструкции целочисленного умножения imul (умножение на 2 компилятор сам заменяет на сдвиг). Прогнав тестовую программу, получаем следующий результат — время выполнения составляет 9.4 секунды! Итого, сравнивая времена «нетто» (2.1 и 0.2 секунды соответственно) для двух вариантов расчета искомого значения, получаем десятикратное* увеличение скорости выполнения требуемой операции.

Попробуем пойти еще немного дальше. Целочисленное умножение необходимо только для перемены знака числа, которую можно выполнить напрямую. В частности, вычисление модуля числа a можно реализовать следующим образом:
unsigned int mask[] = {0,(unsigned)-1};
unsigned int constant[] = {0, 1};
int c = ((unsigned)a)>>31;
a = a^mask[c]+constant[c];
И наконец, заменим сдвиг вправо на 31 бит единичным циклическим сдвигом влево с помощью функции _rotl(). Забегая вперед отметим, что компилятор преобразует ее вызов напрямую в инструкцию rol без использования call. Соберем все вместе еще раз и получим
третий вариант
static unsigned int mask[] = {0,(unsigned)-1};
static unsigned int constant[] = {0, 1};

static inline int LLR_3(int a, int b)
{
	int sign,c, numbers[2];
	sign = (_rotl(a^b,1) & 1);
	c = ((_rotl(a,1) & 1));
	a = (a^mask[c])+constant[c];

	c = ((_rotl(b,1) & 1));
	b = (b^mask[c])+constant[c];

	numbers[0] = b;
	numbers[1] = a;

	c = ((_rotl(a-b,1) & 1));

	return (numbers[c]^mask[sign])+constant[sign];
}


Заменяем вызов LLR()_2 на LLR_3() и видим, что значимого прироста это не дает (время выполнения составляет примерно те же 9.4 секунды с небольшой разницей в третьем знаке в меньшую сторону). Получается, что imul на современных процессорах выполняется довольно быстро!

Вернемся к алгоритму, с которого все началось. Описанной оптимизацией только лишь одной функции удалось сократить время обработки единичного блока данных со 160 до 140 секунд (при выполнении на i7), что составляет более 10% и является весьма неплохим результатом. На очереди еще несколько похожих функций…

Ну и напоследок предлагаю вариант реализации функции определения максимума двух целых 32-разряздных чисел. Написан он был уже чисто из академического любопытства. Желающие могут не спешить заглядывать под спойлер и попробовать реализовать подобное сами. Вариант без условных переходов работает примерно втрое быстрей стандартного макроса __max() (при выполнении на i7). Удачи в оптимизации ваших программ!
Скрытый текст
static inline int max(int a, int b)
{
	int numbers[2][2];
	numbers[0][0] = b;
	numbers[0][1] = a;
	numbers[1][0] = a;
	numbers[1][1] = b;
	int sign_a = (unsigned)a>>31;
	int sign_b = (unsigned)b>>31;
	int sign_ab = (unsigned)(a^b)>>31;
	int abs_a = (1-2*sign_a)*a;
	int abs_b = (1-2*sign_b)*b;
	int sign_a_b = (unsigned)(abs_a-abs_b)>>31;

	int c0 = sign_ab;
	int c1 = ((1^(sign_a_b)^(sign_a | sign_b)) & (1^c0)) | (sign_ab & sign_a);

	int result = numbers[c0][c1];
	return result;
}



*UPD. В комментариях пользователь shodan привел пример, в котором rand() убран из подсчета времени, а чтение данных производится из заранее сформированного массива. В этом случае прирост производительности приблизительно трехкратный. По-видимому, это связано с более эффективной работой конвеера при чтении данных из массива.
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 60

    +3
    int x,y,r;
    r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
      0
      хм, забыл про абс
      mask = v >> sizeof(int) * CHAR_BIT — 1;
      r = (v + mask) ^ mask;
        +1
        (с) graphics.stanford.edu/~seander/bithacks.html
          0
          вот это -(x < y) — можете прояснить?
            0
            уже не надо, спасибо :)
              0
              посмотрите на ссылку, которую я выше написал, там объяснено
                0
                ссылка интересная, мне ее уже подсказали
              0
              А вот эта операция не содержит ли условного перехода внутри: -(x < y)?
                0
                Нет, но считается, что true == 1, а false == 0
                  0
                  Перехода нет. Есть лишь вычисление выражения (x<y) что есть sub x, y результат которого уходит дальше.
                    +1
                    В современных процессорах есть команда SETL, которая записывает в регистр результат «меньше?» последнего сравнения (в виде 0 или 1). Без такой команды обойтись без переходов было бы очень сложно.
                      +1
                      Можно, например: ((x — y) >> 31) & 1.
                        +1
                        Нельзя. Если x=2e9, y=-2e9, то результат будет неправильным. В этом-то и основная проблема.
                  +11
                  А потом этот код разбирать какому-нибудь программисту. Не завидую ему.
                    +6
                    Если снабдить минимальными комментариями — разберется. Да и сам факт разбора кода декодера означает преодоление некоторого входного порога, «какой-нибудь» программист туда просто не полезет
                      +19
                      Главное — добавить в начало строчку // return sign(a*b) * min(abs(a), abs(b))
                        +5
                        Как раз именно та ситуация, когда нужны комментарии. При наличии их и тестов нет никаких проблем.
                          +4
                          >Не завидую ему.

                          Ссылку на эту статью в комменты — и я наоборот ему завидую.
                          • UFO just landed and posted this here
                            0
                            Спасибо, интересно и несложно. Хотя у atrydg действительно компактнее вышло.
                            Никак не мог распарсить
                            (unsigned)-1
                            Решил спросить что это такое и дошло.
                            Про пару опечаток в личку отписал.
                              0
                              Да, согласен, что можно не использовать вспомогательные массивы и в целом более компактно. Но согласитесь, что использование конструкции -(x < y) — это требует очень высокой стадии просветления
                              0
                              Здесь условных переходов точно нет. Сравнений тоже (предполагается, что ни 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;
                              
                                +5
                                А потом кто-то запустит это на 64 битной машине.
                                  0
                                  Если компилятор мощный, то может наблюдаться прирост производительности в разы.
                                    0
                                    По идее, все будет хорошо, потому что int на 64х битной машине точно также равен четырем байтам.
                                      +6
                                      Совсем нет.

                                      По стандарту не задается размер int, есть только рекомендация делать его равным машинному слову. на 64 битах машинное слово будет равно 64 битам, и размер int, скорее всего будет зависеть от настроек компилятора. Компиляторов много разных, поэтому с каким нибудь может получиться, что int имеет размер 64 бита. Попробовал добиться этого от GCC, но там для x86 и x86_64 размер int всегда равен 32 битам.
                                        0
                                        int вообще-то в языке, а не на машине.
                                        А уж что там за компилятор и как он его переделает — другое дело.
                                        0
                                        Если просто запустит — ничего не произойдет.
                                        Если именно пересобрать под 64х битную платформу — то зависит от компилятора. В случае MSVS тоже ничего не произойдет.
                                        +5
                                        Попробовал собрать и повторить.
                                        И ускорение не в 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

                                        Что я делаю не так??
                                          0
                                          Вы уверены, что в целях оптимизации компилятор не объединил три цикла в один? У меня сейчас нет возможности запустить ваш пример, как появится — проверю и отпишусь.
                                            0
                                            Лучше на ты. Да, уверен. В дебажном билде результаты расчетов такие же, в дизасме наглядно видать 3 цикла и честные вызовы функций.

                                            Ну и эта, пример не мой ;) практически чистый cut/paste плюс пачка незначащих правок типа замены tprintf на printf. И одна значащая, вынос rand() за цикл с целью мерить именно оптимизируемую функцию, а не воздух.
                                              0
                                              Результат вычислений (x), естественно должен быть одинаков во всех трех случаях вне зависимости от debug/release. Спасибо, что обратил внимание, в LLR_2() и в LLR_3() вкрались опечатки. в LLR_2() это отсутствующая скобка (((unsigned)a^b)>>31), в LLR_3() не хватает скобок при операторе ^ и a вместо b там, где рассчитывается модуль а.

                                              Насчет увеличения времени… В твоем примере (с вынесенном рандом) у меня функция с условными переходами работает быстрее чем остальные. По-видимому оба массива полностью поместились в стеке и и предсказание переходов дало свои плоды. Я увеличил размер массива до 1Мб, после чего LLR опять стала самой медленной. Но разница во времени выполнения — 3.5 раза а не 10.
                                                0
                                                Скопировал из статьи заново, результаты начали сходиться. С любым размером блока ускорение есть, однако ни разу не 10 раз. Вот например с блоком 16 мб выходит около 2.1 раз.

                                                gist.github.com/anonymous/5604401
                                                  0
                                                  Я сделал дополнение к посту. Вероятно, все упирается в конкретную последовательность инструкций, а вызов rand() сильно «сбивает» конвеер.
                                          0
                                          int a,b,min;
                                          ...
                                          min = a - (a-b) * ( ((a-b) >> 31) + 1 );
                                          
                                            0
                                            Либо даже вот так:
                                            min = b + (b-a)*((a-b) >> 31);
                                            

                                            На одно сложение меньше.
                                              0
                                              min = b - ((b-a) & ((a-b) >> 31));
                                              

                                              А так от умножения избавились. Извините за столько комментариев — на ходу сочинял.
                                                0
                                                Работает только когда нет переполнения при вычитании. Например, при a,b>=0.
                                                  0
                                                  a,b — модули, так что тут все корректно
                                                    0
                                                    С отрицательными числами работает.
                                              +7
                                              Только вот надо сказать, что декодер, работающий по такой приближенной формуле, довольно сильно проигрывает по вероятности ошибки «настоящей» формуле. Настоящая формула выглядит так:

                                              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). Вот тут битовые ухищрения у меня работали медленнее, чем условные переходы.

                                                0
                                                Полностью согласен, я несколько упростил специально для того, чтобы акцентировать внимание на условных переходах. естественно далее там есть табулированный логарифм экспоненты.
                                                  0
                                                  Если N — степень двойки то на ARM например есть инструкция ssat, предполагаю на x86 что-нибудь похожее должно быть. А еще есть инструкции для saturating арифметики (qadd/qsub на ARM + аналоги для NEON). В SSE наверное тоже есть, не приходилось под x86 писать. Saturating-арифметика довольно часто используется в DSP и использование специальных инструкций дает прирост скорости в разы, по сравнению с условными переходами.
                                                  0
                                                  Каким компилятором собирали? VC++?
                                                  Для дальнейшего исследования можно попробовать посмотреть с vTune'е что происходит и где тормоза.
                                                    0
                                                    Странно, что до нынешнего времени компиляторы не научились распознавать и оптимизировать канонические реализации max и sign
                                                      +1
                                                      И где здесь C++? :)
                                                        +3
                                                        Начиная с Пентиум Про есть команда условного перемещения — 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];
                                                            }
                                                        
                                                          0
                                                          А, получается вот как можно добиться cmov от компилятора. Мы пробовали использовать асмовую вставку с ним, действительно не особенно выигрывает по сравнению с условным переходом.
                                                            0
                                                            Удивительно, единственная выкладка на ассемблере в посте про низкоуровневую оптимизацию. И то, не в посте а в комментарии.
                                                              +1
                                                              Я мог бы выложить соответствующие ассемблерные листинги, но намеренно не стал загромождать пост, т.к. в приведенных примерах трансляция в общем-то однозначная. Мне казалось, что небольших комментариев (про imul, rol и т.п.) будет достаточно.
                                                              0
                                                              Пока нет, но не очень понятно, что вы хотите ей сказать?
                                                                0
                                                                там отлично разжевано про предсказание ветвлений и про возможность отказа от условных переходов
                                                                  0
                                                                  в общем, очень по теме поста ссылка
                                                                0
                                                                А собственно какой из алгоритмов LDPC декодера был реализован?
                                                                  0
                                                                  Ответ комментом ниже, промахнулся
                                                                  0
                                                                  Реализация взята отсюда (с некоторыми оптимизациями, в т.ч. описанной в топике), длины блоков 16200 или 64800 бит
                                                                    0
                                                                    Ну вы не с того краю заходите ИМХО. Belief propagation (BP) алгоритм самый медленный. Все равно что сортировку пузырьком оптимизировать.
                                                                      0
                                                                      А что можете посоветовать?
                                                                        0
                                                                        Все зависит от постановки задачи, а об этом вы ни-ни. Откуда у вас вообще LDPС вылезло, что вы делаете?
                                                                        Ну и конечно самый общий ответ на ваш вопрос тут ieeexplore.ieee.org

                                                                  Only users with full accounts can post comments. Log in, please.