2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 09:51 
Аватара пользователя


14/11/12
1304
Россия, Нижний Новгород
В духе темы 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 если это вдруг чем-то поможет.

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 10:40 
Заслуженный участник
Аватара пользователя


02/08/11
5668
Я бы попробовал для начала перейти от линейного поиска к бинарному.
код: [ скачать ] [ спрятать ]
Используется синтаксис 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;
            }
        }
    }
}
 

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 10:48 


12/08/14

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

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 11:34 
Заслуженный участник
Аватара пользователя


30/01/06
70617
SergeyGubanov в сообщении #1342950 писал(а):
Здесь N0 .. N10 - 32-битные константы известные при компиляции.

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

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

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 12:23 


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

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

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

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 12:45 


07/08/14
3168
SergeyGubanov

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

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 12:48 


27/08/16
5558
upgrade в сообщении #1342973 писал(а):
Ошибки будут:
Вы какое именно утверждение комментируете?

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 12:49 


14/01/11
2124
Если совсем без переходов, можно так, например:
Используется синтаксис C
return (n>=N0)+(n>=N1)+(n>=N2)+(n>=N3)+(n>=N4)+(n>=N5)+(n>=N6)+(n>=N7)+(n>=N8)+(n>=N9)+(n>=N10);

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 12:50 


07/08/14
3168
realeugene в сообщении #1342976 писал(а):
upgrade в сообщении #1342973 писал(а):
Ошибки будут:
Вы какое именно утверждение комментируете?

Стартовое.

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 12:54 


27/08/16
5558
upgrade в сообщении #1342978 писал(а):
Стартовое.
Тогда вы не поняли стартовый код. Добавлю, что монотонность констант в этой задаче, очевидно, подразумевается.

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 13:01 


07/08/14
3168
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, а остальные не проверяет (тут могу ошибаться, т.к. си не знаю).

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 13:04 


14/01/11
2124
upgrade в сообщении #1342980 писал(а):
Тоже ифы (в скобках), только они проверяются по всему массиву значений

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

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 14:28 
Заслуженный участник
Аватара пользователя


01/09/13
2413
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$...

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 14:29 


27/08/16
5558
Geen в сообщении #1342996 писал(а):
Только "истина" это $-1$...
Нет.

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 19:02 
Заслуженный участник


20/08/14
5829
Россия, Москва
Проверил несколько вариантов (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 штук). Считаю оно того не стоит.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group