Триумфальное возвращение Ломуто

[ikle]

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. Ну это так, заметки на полях, для реальных данных нужно тестировать на реальных примерах.

[beeruser]

GCC6? Такое давно в cmov преобразуется.
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

Что характерно, попытка выпендритьсяпоказать владение битовыми трюками приводит к менее эффективному коду на ARM.

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

[ikle]

GCC6?

Промышленная разработка часто использует определённые фиксированные версии инструментов разработки по ряду причин. Так, у меня и 4.6, 4.7, 4.9 есть.

Но в данной случае это просто Debian 9.

Такое давно в cmov преобразуется.

Да, на это указали в комментариях к оригинальной статье и получили другие цифры, нежели автор.

[Enjection]

C++20 — знаковые инты теперь официально two's-complement насколько я помню

[Ogi]

А в D целые представляются всегда как дополнение до двух?

Уолтер не видит смысла поддерживать что-то другое.

[knstqq]

А как это работает не в абстрактном случае сортировки на одном ядре, а в случае, ширина памяти будет иметь значение? Например, 16 параллельно запущенных сортировок разных массивов на 16 ядрах.