Комментарии 6
auto smaller = -int(x < pivot);
А в D целые представляются всегда как дополнение до двух? Вот в Си — точно нет, в Си++ — скорее всего так же. То есть такая конструкция на Си будет точно непереносима. Точнее, ограниченно переносима (валидна для большинства современных архитектур).
Можно предложить другое решение:
(x < y) * zРешение более переносимо. Посмотрим на то, что GCC 6 генерирует, исходный код:
int f (int x, int y, int z)
{
return (x < y) * z;
}
int g (int x, int y, int z)
{
return -(x < y) & z;
}Результирующий код:
f: xorl %eax, %eax
cmpl %esi, %edi
setl %al
imull %edx, %eax
ret
g: xorl %eax, %eax
cmpl %esi, %edi
setl %al
negl %eax
andl %edx, %eax
ret— В варианте с умножением ещё и операций меньше, в том числе меньше стадий при суперскалярном выполнении.
Вариант с умножением, тем не менее, может оказаться заметно медленнее на старых архитектурах и некоторых современных микроконтроллерах с экстремально низким потреблением. Впрочем, даже для последовательного умножения ранний выход использовался уже давно. С ранним выходом решения становятся либо одинаковыми по времени, ли с умножением чуть медленнее (на такт — два).
Для современных же архитектур с параллельным умножителем, получаем либо равенство, либо преимущество варианта с умножением. (Это в добавок к лучшей переносимости.)
P.S. Ну это так, заметки на полях, для реальных данных нужно тестировать на реальных примерах.
Clang 10 генерит одинаковые последовательности инструкций на х86 (и для тернарного оператора в том числе)
gcc.godbolt.org/z/4Mvov7
f(int, int, int):
xor eax, eax
cmp edi, esi
cmovl eax, edx
retНа ARM будет ещё короче.
f(int, int, int):
cmp w0, w1
csel w0, w2, wzr, lt
retЧто характерно, попытка
g(int, int, int):
cmp w0, w1
csetm w0, lt
and w0, w0, w2
retВариант с умножением, тем не менее, может оказаться заметно медленнее на старых архитектурах и некоторых современных микроконтроллерах
На последних микроархитектурах Интел, латентность IMUL r32,r/m32 — 3 такта.
Можно ознакомиться тут: uops.info/table.html
А вот для микроконтроллера Cortex-M4, например, MUL Rd, Rn, Rm занимает всего 1 такт.
www.engr.colostate.edu/ECE251/Labs/AppendixB.pdf
GCC6?
Промышленная разработка часто использует определённые фиксированные версии инструментов разработки по ряду причин. Так, у меня и 4.6, 4.7, 4.9 есть.
Но в данной случае это просто Debian 9.
Такое давно в cmov преобразуется.
Да, на это указали в комментариях к оригинальной статье и получили другие цифры, нежели автор.
А в D целые представляются всегда как дополнение до двух?
Уолтер не видит смысла поддерживать что-то другое.
Триумфальное возвращение Ломуто