Компилятор: 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;
//...
}
Умножение в настоящее время выполняется с использованием типичного метода long-умножения (в сборке, чтобы я мог перехватить вывод EDX), игнорируя слова, выходящие за пределы диапазона ( то есть я делаю только 10 mull по сравнению с 16).
Деление использует алгоритм shift-subtract (скорость зависит от количества битов операндов). Однако, это не сделано в сборке. Я нашел, что это слишком сложно собрать, и решил позволить компилятору оптимизировать его.
У меня 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));
}
};
Что касается деления, изучение кода довольно бессмысленно, поскольку мне нужно будет изменить математический алгоритм, чтобы увидеть какие-либо существенные преимущества. Единственный возможный выбор, по-видимому, - деление с высоким основанием, но мне еще предстоит сгладить (на мой взгляд) только , как это будет работать.