Помогите ускорить ещё одну функцию на С [asm, AVX512]

[SergeyGubanov]

В духе темы topic129871.html у меня тоже есть вопрос.

Не знает ли кто-нибудь можно ли (и как) ускорить следующую функцию:

Используется синтаксис C

static inline unsigned int f (unsigned int n)
{
    if (n < N0) { return 0; }
    if (n < N1) { return 1; }
    if (n < N2) { return 2; }
    if (n < N3) { return 3; }
    if (n < N4) { return 4; }
    if (n < N5) { return 5; }
    if (n < N6) { return 6; }
    if (n < N7) { return 7; }
    if (n < N8) { return 8; }
    if (n < N9) { return 9; }
    if (n < N10) { return 10; }
    return 11;
}
 

Здесь N0 .. N10 - 32-битные константы известные при компиляции.

Значения n обычно в рабочих наборах распределены неоднородно, какие-то значения встречаются часто, а какие-то редко, но вид распределения на момент компиляции программы не известен. Хотелось бы чтобы даже в худшем случае она работала неплохо.

Можно использовать AVX512 если это вдруг чем-то поможет.

[warlock66613]

Я бы попробовал для начала перейти от линейного поиска к бинарному.

Используется синтаксис C

static inline unsigned int f (unsigned int n)
{
    if (n < N5) {
        if (n < N2) {
            if (n < N1) {
                if (n < N0)
                    return 0;
                else
                    return 1;
            } else {
                return 2;
            }
        } else {
            if (n < N4) {
                if (n < N3)
                    return 3;
                else
                    return 4;
            } else {
                return 5;
            }
        }
    } else {
        if (n < N8) {
            if (n < N7) {
                if (n < N6)
                    return 6;
                else
                    return 7;
            } else {
                return 8;
            }
        } else {
            if (n < N10) {
                if (n < N9)
                    return 9;
                else
                    return 10;
            } else {
                return 11;
            }
        }
    }
}
 

[Yodine]

Может разности чисел найти? Длины диапазонов и т.д.
Попробовать сконструировать хеш--функцию.
https://en.wikipedia.org/wiki/Perfect_hash_function

[Munin]

SergeyGubanov в сообщении #1342950 писал(а):

Здесь N0 .. N10 - 32-битные константы известные при компиляции.

Каким по счёту байтом они друг друга отличаются?

Стандартный максимально простой способ сделать быстрый выбор - это таблица, например, из 256 значений, и выбор по индексу в этой таблице.

[realeugene]

Диапазон чисел полные 32 разряда без знака? И эта функция вызывается внутри цикла с коротким телом?

Цель тут может быть - минимизировать количество непредсказанных переходов. Я с AVX512 не работал, но, да, кажется есть команда сравнения 32-разрядных целых без знака в виде вектора. Тогда схема может быть такой: размножаете тестируемую величину в вектор, сравниваете с заранее подготовленным вектором констант, находите позицию старшего ненулевого бита в результате (была команда). Как то так.

Функция _mm512_mask_cmp_epu32_mask
Можно и без маски, конечно, если добить вектор констант UINT_MAX.

[upgrade]

SergeyGubanov

Ошибки будут:
если $n<N10$ и $n<N0$, причем $N10 > N0$ то функция завершится не добравшись до $N10$

[realeugene]

upgrade в сообщении #1342973 писал(а):

Ошибки будут:

Вы какое именно утверждение комментируете?

[Sender]

Если совсем без переходов, можно так, например:

Используется синтаксис C

return (n>=N0)+(n>=N1)+(n>=N2)+(n>=N3)+(n>=N4)+(n>=N5)+(n>=N6)+(n>=N7)+(n>=N8)+(n>=N9)+(n>=N10);

[upgrade]

realeugene в сообщении #1342976 писал(а):

upgrade в сообщении #1342973 писал(а):

Ошибки будут:

Вы какое именно утверждение комментируете?

Стартовое.

[realeugene]

upgrade в сообщении #1342978 писал(а):

Стартовое.

Тогда вы не поняли стартовый код. Добавлю, что монотонность констант в этой задаче, очевидно, подразумевается.

[upgrade]

realeugene
В таком случае скорее всего не ускорить никак.
Ифы достаточно быстро работают, например в таком коде:

Sender в сообщении #1342977 писал(а):

Если совсем без переходов, можно так, например:

Используется синтаксис C

return (n>=N0)+(n>=N1)+(n>=N2)+(n>=N3)+(n>=N4)+(n>=N5)+(n>=N6)+(n>=N7)+(n>=N8)+(n>=N9)+(n>=N10);

Тоже ифы (в скобках), только они проверяются по всему массиву значений, а в стартовом посте работа функции завершается как только находит первое TRUE, а остальные не проверяет (тут могу ошибаться, т.к. си не знаю).

[Sender]

upgrade в сообщении #1342980 писал(а):

Тоже ифы (в скобках), только они проверяются по всему массиву значений

В худшем случае всё равно все проверяются. При включённой оптимизации в моём варианте переходов нет, только условные установки байт. Не уверен, правда, что это сильно поможет.

[Geen]

Sender в сообщении #1342977 писал(а):

Если совсем без переходов, можно так, например:

Используется синтаксис C

return (n>=N0)+(n>=N1)+(n>=N2)+(n>=N3)+(n>=N4)+(n>=N5)+(n>=N6)+(n>=N7)+(n>=N8)+(n>=N9)+(n>=N10);

Только "истина" это $-1$...

[realeugene]

Geen в сообщении #1342996 писал(а):

Только "истина" это $-1$...

Нет.

[Dmitriy40]

Проверил несколько вариантов (Haswell, Win7x64), посчитал latency в тактах (и сравнил с IACA): с условными переходами, с условными пересылками cmovcc, с суммированием условий setcc, с AVX2 (в AVX512 код будет проще). Табличный вариант проверять поленился.

(Исходный код)

Cmp1:   mov     EAX,0           ;0156   1/0.25
        cmp     ECX,N0          ;0156   1/0.25
        jb      .exit           ;06     1-0.5/
        mov     EAX,1           ;0156   1/0.25
        cmp     ECX,N1          ;0156   1/0.25
        jb      .exit           ;06     1-0.5/
        ...
        mov     EAX,10          ;0156   1/0.25
        cmp     ECX,N10         ;0156   1/0.25
        jb      .exit           ;06     1-0.5/
        mov     EAX,11          ;0156   1/0.25
.exit:  ret

Cmp2:   mov     EAX,11          ;0156   1/0.25
        mov     EDX,10          ;0156   1/0.25
        cmp     ECX,N10         ;0156   1/0.25
        cmovb   EAX,EDX         ;0156*2 2/0.5
        mov     EDX,9           ;0156   1/0.25
        cmp     ECX,N9          ;0156   1/0.25
        cmovb   EAX,EDX         ;0156*2 2/0.5
        ...
        mov     EDX,0           ;0156   1/0.25
        cmp     ECX,N0          ;0156   1/0.25
        cmovb   EAX,EDX         ;0156*2 2/0.5
        ret

Cmp3:   xor     EDX,EDX         ;0156   0/0.25
        xor     EAX,EAX         ;0156   0/0.25
        cmp     ECX,N0          ;0156   1/0.25
        setge   AL              ;06     1/0.5
        cmp     ECX,N1          ;0156   1/0.25
        setge   DL              ;06     1/0.5
        add     AL,DL           ;0156   1/0.25
        ...
        cmp     ECX,N10         ;0156   1/0.25
        setge   DL              ;06     1/0.5
        add     AL,DL           ;0156   1/0.25
        ret

Cmp4:   vmovdqu         ymm1,[const]    ;23     3/0.5
        vmovdqu         ymm2,[const+32] ;23     3/0.5
        vmovd           xmm0,ECX        ;5      1/1
        vpbroadcastd    ymm0,xmm0       ;5      3/1
        vpcmpgtd        ymm1,ymm1,ymm0  ;15     1/0.5
        vpcmpgtd        ymm2,ymm1,ymm0  ;15     1/0.5
        vmovmskps       EAX,ymm1        ;0      2/1
        vmovmskps       EDX,ymm2        ;0      2/1
        or              EAX,0x0800      ;0156   1/0.25
        shl             EDX,8           ;06     1/0.5
        or              EAX,EDX         ;0156   1/0.25
        bsf             EAX,EAX         ;1      3/1
        ret
const:  dd      N0,N1,N2,N3,N4,N5,N6,N7
        dd      N8,N9,N10,0,0,0,0,0

Самым быстрым оказался вариант с условными переходами, он выдаёт значение через 6 тактов (если ни один переход не выполнится, а выполниться может максимум один) т.к. он хорошо параллелится по всем 4-м портам. Остальные варианты занимают 13-15 тактов.

Реальное измерение в таком цикле

        mov     EBX,-1
.cycl:  mov     ECX,EBX
        ror     ECX,3           ;Для перемешивания, нивелирует предсказание переходов
        call    CmpX
        mov     [result],EAX    ;Добавим зависимость от результата
        sub     EBX,1
        jnz     .cycl

показывает результаты: 13s, 17s, 15s, 8s. Тестировались 11 равномерно распределённых в 2^32 порогов N0-N11.
Как видно даже один выполняемый переход резко всё портит для первого варианта. Отказ от перемешивания командой ror времена практически не меняет (что тоже непонятно для первого варианта, ведь тогда практически все переходы предсказываются верно).
На удивление прекрасно отрабатывает AVX2 вариант, причина мне не совсем понятна, возможно влияет разворот цикла в очереди микрокоманд и её длины хватает чтобы AVX инструкции успевали параллелиться - throughput для тел процедур составляет 5.7, 11.8, 9.3, 3.0 такта соответственно, что и может объяснять аномально высокую скорость AVX кода.

Но в итоге максимальное реальное ускорение по сравнению с кодом на условных переходах составило всего полтора раза (ну или два раза если констант будет 15-16 штук). Считаю оно того не стоит.