С Новым годом! Опишу классический сюжет — оптимизацию длинной арифметики в C++ при помощи ассемблерных вставок. Однако, на Хабре его еще не было, поэтому после некоторых колебаний решил запостить сюда, вы уж простите, если сами когда-то писали то же самое и продвинулись дальше меня :-)
Пусть в классе BigInt, представляющем длинное целое, объявлены поля void *words — массов слов, int wc — количество слов в массиве (длина слова в байтах задается на этапе компиляции). Тогда реализация сложения на чистом C++ может быть такой:
...
typedef unsigned int uInt;
typedef unsigned long long int uLong;
#define MAX_uInt ((uInt)(-1))
#define MUL ((uLong)MAX_uInt) // MUL: Max_uInt in Unsigned Long
int BigInt::WS = sizeof(uInt);
BigInt & BigInt::operator+=(const BigInt &rhs)
{
... // увеличить приемник, если необходимо
uLong carry = 0;
for ( uInt *th = (uInt*)words, *oz = (uInt*)rhs.words,
*limit = oz + rhs.wc, *thl = th + wc;
oz < limit || carry && th < thl;
oz++, th++)
{
uLong t = carry + *th;
t += oz < limit ? *oz : 0;
if (t > MUL)
{
carry = 1;
t &= MUL;
}
else carry = 0;
*th = (uInt)t;
}
if (carry) {
... //увеличить приемник на одно слово
}
return *this;
}
Видно, что Си не очень подходит для решения нашей задачи: нельзя складывать сразу по 8 байт, потому что не остается места для единственного бита переполнения.
Будем считать, сколько тактов процессор тратит на сложение каждых 4 байтов из массива слов длинного целого. Примерно так:
struct timespec t1, t2;
BigInt *a = ..., *b = ...; // длина в байтах - 400
clock_gettime(CLOCK_MONOTONIC_RAW, &t1);
for (int j = 0; j < 10000000; j++) {
*a += *b;
*a -= *b;
}
clock_gettime(CLOCK_MONOTONIC_RAW, &t2);
printf(...); // пошаманить с t1 и t2
Вот прогресс по ключам оптимизации GCC:
-O1 | -O2 | -O3 |
7 | 6 | 6 |
Перепишем тело метода сложения с использованием ассемблерной вставки:
// uInt это int ИЛИ long long int
BigInt & BigInt::operator+=(const BigInt &rhs)
{
... // увеличить приемник, если необходимо
uInt *th = (uInt*)words, *oz = (uInt*)rhs.words;
asm goto (
"clc\n"
"l1:\t"
"mov\t(%[oz]), %[ax]\n\t"
"adc\t%[ax], (%[th])\n\t"
"lahf\n\t"
"add\t%[ws], %[th]\n\t"
"add\t%[ws], %[oz]\n\t"
"sahf\n\t"
"loop\tl1\n\t"
"jnc\t%l[nocarry]\n"
:
: [th] "r" (th), [oz] "r" (oz),
[ws] "I" (sizeof(uInt)), [ax] "a" ((uInt)0), "c" (wc)
:
: nocarry
);
... //увеличить приемник на одно слово
nocarry: return *this;
}
В дальнейшем сразу буду писать результат компиляции (для uInt ≡ long long int):
...
clc
lo: mov (%rbx), %rax
adc %rax, (%rdx)
lahf
add $8, %rdx
add $8, %rbx
sahf
loop lo
jnc nocarry
...
Вкратце о том, что тут происходит: в регистрах bx и dx лежат указатели на текущее слово, adc — очень удобная инструкция, которая складывает источник, приемник и флаг переполнения, то что нужно! lahf и sahf сохраняют и загружают базовые флаги — эти инструкции нужны, потому что add сбрасывает флаг переполнения. loop итерирует столько раз, сколько лежит в регистре cx.
Это именно то (честно), что я сначала написал. Данный вариант выполняется за 7 тактов в обоих вариантах, соответственно за 3,5 такта на каждые четыре байта в «длинном варианте». GCC пока на высоте, но получившийся ассемблер еще оптимизировать и оптимизировать.
.
Дурные слухи ходят вокруг инструкции loop. Надо попробовать без нее, тем более, что это почти ничего не стоит:
...
clc
lo: mov (%rbx), %rax
adc %rax, (%rdx)
lahf
add $8, %rdx
add $8, %rbx
sahf
dec %rcx
jnz lo
jnc nocarry
...
Результат — 5 (2,5) тактов! Никогда не используйте loop — он экономит строчку, зато тратит целых 2 жирных такта на каждой итерации.
.
Хотелось бы разобраться с увеличением указателей — нет ли способа не задевать CF (carry flag — флаг «переноса», переполнения)? К счастью, есть — инструкция lea вычисляет ссылку на память и кладет ее в регистр-приемник, не трогая флаги. Вот как можно использовать ее для инкремента указателей:
...
clc
lo: mov (%rbx), %rax
adc %rax, (%rdx)
lea 8(%rdx), %rdx
lea 8(%rbx), %rbx
dec %rcx
jnz lo
jnc nocarry
...
По сути
lea 8(%rdx), %rdxделает то же самое, что и
add $8, %rdx— прибавляет к регистру размер слова.
На этот вариант процессор тратит 2 такта (то есть 1 такт на 4 байта). Признаться, сам не ожидал, что lahf/sahf занимают так много времени.
.
Что же делать дальше? SSE, к сожалению, тут не помощники: пока используется 64-битная архитектура, несуществующая инструкция padc xmm, xmm генерировала бы по сути тот же поток микроинструкций, что и последовательность из двух обычных сложений, распараллелить сложение с переполнением нельзя. Точно, значит надо и написать два сложения подряд, развернуть ассемблерный цикл. Золотой прием оптимизации.
// WS = 16
...
clc
lo: mov (%rbx), %rax
adc %rax, (%rdx)
mov 8(%rbx), %rax
adc %rax, 8(%rdx)
lea 16(%rbx), %rbx
lea 16(%rdx), %rdx
dec %rcx
jnz lo
jnc nocarry
...
Теперь одна итерация выполняется за 3 такта, что соответствует 0.75 такта на 4 байта.
Ура! GCC -O2 сделан в 8 раз! Дальше думать некогда! Еще раз всех с наступающим!