Да, есть способ рассчитать максимум или минимум двух double с без каких-либо ветвей. Код C ++ для этого выглядит следующим образом:
#include <algorithm>
double FindMinimum(double a, double b)
{
return std::min(a, b);
}
double FindMaximum(double a, double b)
{
return std::max(a, b);
}
Бьюсь об заклад, вы видели это раньше. Если вы не верите, что это без веток, проверьте разборку :
FindMinimum(double, double):
minsd xmm1, xmm0
movapd xmm0, xmm1
ret
FindMaximum(double, double):
maxsd xmm1, xmm0
movapd xmm0, xmm1
ret
Это то, что вы получаете от всех популярных компиляторов, ориентированных на x86. Используется набор инструкций SSE2, в частности инструкции minsd / maxsd, которые без разветвлений оценивают минимальное / максимальное значение двух значений с плавающей запятой двойной точности.
Все 64-битные процессоры x86 поддерживают SSE2 ; это требуется расширениями AMD64. Даже большинство процессоров x86 без 64-битной поддержки поддерживают SSE2. Он был выпущен в 2000 году. Вам пришлось бы пройти долгий путь, чтобы найти процессор, который не поддерживает SSE2. Но что если ты это сделал? Ну, даже там, вы получаете код без ответвлений на большинстве популярных компиляторов :
FindMinimum(double, double):
fld QWORD PTR [esp + 12]
fld QWORD PTR [esp + 4]
fucomi st(1)
fcmovnbe st(0), st(1)
fstp st(1)
ret
FindMaximum(double, double):
fld QWORD PTR [esp + 4]
fld QWORD PTR [esp + 12]
fucomi st(1)
fxch st(1)
fcmovnbe st(0), st(1)
fstp st(1)
ret
Инструкция fucomi выполняет сравнение, устанавливает флаги, а затем инструкция fcmovnbe выполняет условное перемещение на основе значения этих флагов. Все это полностью без ветвей и основано на инструкциях, введенных для ISA x86 с Pentium Pro еще в 1995 году, поддерживаемых на всех чипах x86 начиная с Pentium II.
Единственный компилятор, который не будет генерировать здесь код без ответвлений, - это MSVC, поскольку не использует команду FCMOVxx . Вместо этого вы получите:
double FindMinimum(double, double) PROC
fld QWORD PTR [a]
fld QWORD PTR [b]
fcom st(1) ; compare "b" to "a"
fnstsw ax ; transfer FPU status word to AX register
test ah, 5 ; check C0 and C2 flags
jp Alt
fstp st(1) ; return "b"
ret
Alt:
fstp st(0) ; return "a"
ret
double FindMinimum(double, double) ENDP
double FindMaximum(double, double) PROC
fld QWORD PTR [b]
fld QWORD PTR [a]
fcom st(1) ; compare "b" to "a"
fnstsw ax ; transfer FPU status word to AX register
test ah, 5 ; check C0 and C2 flags
jp Alt
fstp st(0) ; return "b"
ret
Alt:
fstp st(1) ; return "a"
ret
double FindMaximum(double, double) ENDP
Обратите внимание на инструкцию ветвления JP (переход, если установлен бит четности). Команда FCOM используется для сравнения, которое является частью базового набора команд x87 FPU. К сожалению, это устанавливает флаги в слове состояния FPU, поэтому для разветвления этих флагов их необходимо извлечь. В этом и заключается цель инструкции FNSTSW, в которой слово состояния x87 FPU сохраняется в регистре общего назначения AX (его также можно сохранить в памяти, но & hellip; почему?). Затем код TEST устанавливает соответствующий бит и соответственно разветвляется, чтобы обеспечить возвращение правильного значения. В дополнение к ветви, поиск слова состояния FPU также будет относительно медленным. Вот почему Pentium Pro представил инструкции FCOM.
Тем не менее, маловероятно , что вы могли бы улучшить скорость любого из этого кода, используя операции сдвига битов для определения мин / макс. Есть две основные причины:
Единственным компилятором, генерирующим неэффективный код, является MSVC, и нет хорошего способа заставить его генерировать нужные вам инструкции. Несмотря на то, что встроенная сборка поддерживается в MSVC для 32-разрядных целей x86, - это дурацкое поручение при поиске улучшений производительности . Я также процитирую себя:
Встроенная сборка нарушает работу оптимизатора довольно значительными способами, поэтому, если вы не пишете значительный ряд кода во встроенной сборке, маловероятно, что будет существенный прирост производительности. Кроме того, встроенный синтаксис Microsoft чрезвычайно ограничен. Он меняет гибкость на простоту во многом. В частности, нет способа указать значения input , поэтому вы застряли, загружая ввод из памяти в регистр, и вызывающая сторона вынуждена подготовить ввод из регистра в память. Это создает феномен, который я люблю называть «целой лотерейкой» или, для краткости, «медленный код». Вы не переходите на встроенную сборку в тех случаях, когда допустим медленный код. Таким образом, всегда предпочтительнее (по крайней мере, в MSVC) выяснить, как писать исходный код на C / C ++, который убеждает компилятор выдавать нужный объектный код. Даже если вы можете приблизить к идеальному выводу, это все же значительно лучше, чем штраф, который вы платите за использование встроенной сборки.
Чтобы получить доступ к необработанным битам значения с плавающей запятой, вам необходимо выполнить переход домена, с плавающей запятой на целое, а затем обратно к плавающей запятой. Это медленно, , особенно без SSE2, потому что единственный способ получить значение из FPU x87 в целочисленные регистры общего назначения в ALU - это косвенно через память.
Если вы все равно захотите использовать эту стратегию - скажем, для ее сравнения - вы можете воспользоваться тем, что значения с плавающей запятой лексикографически упорядочены в терминах их представлений IEEE 754 , за исключением знак бит. Итак, поскольку вы предполагаете, что оба значения положительны:
FindMinimumOfTwoPositiveDoubles(double a, double b):
mov rax, QWORD PTR [a]
mov rdx, QWORD PTR [b]
sub rax, rdx ; subtract bitwise representation of the two values
shr rax, 63 ; isolate the sign bit to see if the result was negative
ret
FindMaximumOfTwoPositiveDoubles(double a, double b):
mov rax, QWORD PTR [b] ; \ reverse order of parameters
mov rdx, QWORD PTR [a] ; / for the SUB operation
sub rax, rdx
shr rax, 63
ret
Или, чтобы избежать встроенной сборки:
bool FindMinimumOfTwoPositiveDoubles(double a, double b)
{
static_assert(sizeof(a) == sizeof(uint64_t),
"A double must be the same size as a uint64_t for this bit manipulation to work.");
const uint64_t aBits = *(reinterpret_cast<uint64_t*>(&a));
const uint64_t bBits = *(reinterpret_cast<uint64_t*>(&b));
return ((aBits - bBits) >> ((sizeof(uint64_t) * CHAR_BIT) - 1));
}
bool FindMaximumOfTwoPositiveDoubles(double a, double b)
{
static_assert(sizeof(a) == sizeof(uint64_t),
"A double must be the same size as a uint64_t for this bit manipulation to work.");
const uint64_t aBits = *(reinterpret_cast<uint64_t*>(&a));
const uint64_t bBits = *(reinterpret_cast<uint64_t*>(&b));
return ((bBits - aBits) >> ((sizeof(uint64_t) * CHAR_BIT) - 1));
}
Обратите внимание, что в этой реализации есть серьезных предостережений. В частности, он сломается, если два значения с плавающей точкой имеют разные знаки или оба значения будут отрицательными. Если оба значения отрицательны, код можно изменить, чтобы перевернуть их знаки, выполнить сравнение и затем вернуть противоположное значение. Для обработки случая, когда два значения имеют разные знаки, можно добавить код для проверки бита знака.
// ...
// Enforce two's-complement lexicographic ordering.
if (aBits < 0)
{
aBits = ((1 << ((sizeof(uint64_t) * CHAR_BIT) - 1)) - aBits);
}
if (bBits < 0)
{
bBits = ((1 << ((sizeof(uint64_t) * CHAR_BIT) - 1)) - bBits);
}
// ...
Работа с отрицательным нулем также будет проблемой. IEEE 754 говорит, что +0,0 равно & минус; 0,0, поэтому ваша функция сравнения должна будет решить, хочет ли она обрабатывать эти значения как разные, или добавить специальный код в процедуры сравнения, который гарантирует, что отрицательный и положительный ноль будут рассматриваться как эквивалентные.
Добавление всего этого специального кода , безусловно, снизит производительность до такой степени, что мы достигнем уровня безумного сравнения с плавающей запятой и, скорее всего, окажутся медленнее.