Эффективное умножение / деление двух 128-битных целых чисел на x86 (без 64-битной)
Компилятор: MinGW / GCC
Проблемы: Код GPL/LGPL не допускается (GMP или любая другая библиотека bignum в этом отношении излишни для этой проблемы, поскольку у меня уже есть реализованный класс).
Я создал свой собственный большой целочисленный класс 128-битного размера (предназначенный для использования в игровом движке, но может быть обобщен для любого случая использования), и я считаю, что производительность текущих операций умножения и деления довольно ужасна (да, Я рассчитал их, см. Ниже), и я хотел бы улучшить (или изменить) алгоритмы, выполняющие низкоуровневое вычисление чисел.
Когда дело доходит до операторов умножения и деления, они невыносимо медленны по сравнению со всем остальным в классе.
Это приблизительные измерения относительно моего собственного компьютера:
Raw times as defined by QueryPerformanceFrequency:
1/60sec 31080833u
Addition: ~8u
Subtraction: ~8u
Multiplication: ~546u
Division: ~4760u (with maximum bit count)
Как вы можете видеть, просто умножение во много, много раз медленнее, чем сложение или вычитание. Деление примерно в 10 раз медленнее, чем умножение.
Я хотел бы повысить скорость работы этих двух операторов, поскольку в каждом кадре может выполняться очень большое количество вычислений (точечные произведения, различные методы обнаружения столкновений и т. Д.).
Структура (методы опущены) выглядит примерно так:
class uint128_t
{
public:
unsigned long int dw3, dw2, dw1, dw0;
//...
}
Умножение в настоящее время выполняется с использованием типичного метода длинного умножения (в сборке, чтобы я мог поймать EDX вывод), игнорируя слова, выходящие за пределы диапазона (то есть я делаю только 10 mullпо сравнению с 16).
Деление использует алгоритм сдвига-вычитания (скорость зависит от количества битов операндов). Однако, это не сделано в сборке. Я нашел, что это слишком сложно собрать, и решил позволить компилятору оптимизировать его.
В течение нескольких дней я работал с Google, просматривая страницы, описывающие алгоритмы, такие как умножение Карацубы, деление с высоким основанием и деление Ньютона-Рапсона, но математические символы находятся слишком далеко над моей головой. Я бы хотел использовать некоторые из этих продвинутых методов для ускорения моего кода, но сначала мне пришлось бы перевести "греческий" во что-то понятное.
Для тех, кто может посчитать мои усилия "преждевременной оптимизацией"; Я считаю этот код узким местом, потому что сами элементарные математические операции становятся медленными. Я могу игнорировать такие типы оптимизации в коде более высокого уровня, но этот код будет вызываться / использоваться достаточно, чтобы это имело значение.
Я хотел бы получить предложения о том, какой алгоритм мне следует использовать для улучшения умножения и деления (если возможно), и базовое (надеюсь, простое для понимания) объяснение того, как работает предложенный алгоритм, будет высоко оценено.
РЕДАКТИРОВАТЬ: Умножение Улучшения
Мне удалось улучшить операцию умножения, вставив код в оператор *=, и это кажется максимально быстрым.
Updated raw times:
1/60sec 31080833u
Addition: ~8u
Subtraction: ~8u
Multiplication: ~100u (lowest ~86u, highest around ~256u)
Division: ~4760u (with maximum bit count)
Вот некоторый простой код для изучения (обратите внимание, что мои имена типов на самом деле отличаются, это было отредактировано для простоты):
//File: "int128_t.h"
class int128_t
{
uint32_t dw3, dw2, dw1, dw0;
// Various constrctors, operators, etc...
int128_t& operator*=(const int128_t& rhs) __attribute__((always_inline))
{
int128_t Urhs(rhs);
uint32_t lhs_xor_mask = (int32_t(dw3) >> 31);
uint32_t rhs_xor_mask = (int32_t(Urhs.dw3) >> 31);
uint32_t result_xor_mask = (lhs_xor_mask ^ rhs_xor_mask);
dw0 ^= lhs_xor_mask;
dw1 ^= lhs_xor_mask;
dw2 ^= lhs_xor_mask;
dw3 ^= lhs_xor_mask;
Urhs.dw0 ^= rhs_xor_mask;
Urhs.dw1 ^= rhs_xor_mask;
Urhs.dw2 ^= rhs_xor_mask;
Urhs.dw3 ^= rhs_xor_mask;
*this += (lhs_xor_mask & 1);
Urhs += (rhs_xor_mask & 1);
struct mul128_t
{
int128_t dqw1, dqw0;
mul128_t(const int128_t& dqw1, const int128_t& dqw0): dqw1(dqw1), dqw0(dqw0){}
};
mul128_t data(Urhs,*this);
asm volatile(
"push %%ebp \n\
movl %%eax, %%ebp \n\
movl $0x00, %%ebx \n\
movl $0x00, %%ecx \n\
movl $0x00, %%esi \n\
movl $0x00, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%ebx \n\
adcl %%edx, %%ecx \n\
adcl $0x00, %%esi \n\
adcl $0x00, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%ecx \n\
adcl %%edx, %%esi \n\
adcl $0x00, %%edi \n\
movl 20(%%ebp), %%eax #Calc: (dw2*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 16(%%ebp), %%eax #Calc: (dw3*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%ecx \n\
adcl %%edx, %%esi \n\
adcl $0x00, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 20(%%ebp), %%eax #Calc: (dw2*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw2) \n\
mull 4(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw2) \n\
mull 4(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw3) \n\
mull (%%ebp) \n\
addl %%eax, %%edi \n\
pop %%ebp \n"
:"=b"(this->dw0),"=c"(this->dw1),"=S"(this->dw2),"=D"(this->dw3)
:"a"(&data):"%ebp");
dw0 ^= result_xor_mask;
dw1 ^= result_xor_mask;
dw2 ^= result_xor_mask;
dw3 ^= result_xor_mask;
return (*this += (result_xor_mask & 1));
}
};
Что касается деления, изучение кода довольно бессмысленно, так как мне нужно будет изменить математический алгоритм, чтобы увидеть какие-либо существенные преимущества. Единственный возможный выбор, по-видимому, - деление с высоким основанием, но мне еще предстоит выяснить (по моему мнению), как это будет работать.
2 ответа
Я бы не стал сильно беспокоиться о умножении. То, что вы делаете, кажется довольно эффективным. На самом деле я не следовал греческому в умножении Карацубы, но мне кажется, что он будет эффективнее только с гораздо большими числами, чем вы имеете дело.
Одно из предложений, которое у меня есть, - попытаться использовать наименьшие блоки встроенной сборки, а не кодировать свою логику в сборке. Вы можете написать функцию:
struct div_result { u_int x[2]; };
static inline void mul_add(int a, int b, struct div_result *res);
Функция будет реализована во встроенной сборке, и вы будете вызывать ее из кода C++. Он должен быть таким же эффективным, как чистая сборка, и намного проще для кода.
Насчет деления я не знаю. Большинство алгоритмов, которые я видел, говорят об асимптотической эффективности, что может означать, что они эффективны только для очень большого числа битов.
Правильно ли я понимаю ваши данные о том, что вы выполняете тест на машине с частотой 1,8 ГГц, и "u" в ваших временных параметрах - это такты процессора?
Если так, то 546 циклов для 10 32-битных MUL кажутся мне немного медленными. У меня есть свой собственный бренд bignums на Core2 Duo 2 ГГц, и MUL 128x128 = 256 бит работает примерно за 150 циклов (я делаю все 16 маленьких MUL), то есть примерно в 6 раз быстрее. Но это может быть просто более быстрый процессор.
Убедитесь, что вы развернули петли, чтобы сохранить эти накладные расходы. Сохраняйте регистрацию как можно меньше. Может быть, это поможет, если вы разместите здесь код ASM, чтобы мы могли его просмотреть.
Карацуба вам не поможет, так как он начинает действовать только после 20-40 32-битных слов.
Деление всегда намного дороже, чем умножение. Если вы делите на константу или на одно и то же значение много раз, это может помочь предварительно вычислить обратную величину и затем умножить ее.