2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение01.10.2018, 20:10 


14/01/11
2916
Dmitriy40 в сообщении #1343055 писал(а):
Код:
Cmp3: xor EDX,EDX ;0156 0/0.25xor 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


Пришло на ум, что, если бы в исходном сообщении неравенства были нестрогими, можно было бы попробовать такой вариант:
Код:
Cmp3:   xor     EDX,EDX
        xor     EAX,EAX
        cmp     N0, ECX
        adc    EAX,0
        ...
        cmp     N10,ECX 
        adc     EAX,0 
        ret

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


20/08/14
11061
Россия, Москва
Sender в сообщении #1343076 писал(а):
Пришло на ум, что, если бы в исходном сообщении неравенства были нестрогими, можно было бы попробовать такой вариант:
Константы поправить не проблема (если N0>0).
Команды
Код:
cmp im32,r32
не существует, так сравнить регистр можно лишь с памятью, что впрочем так же быстро и занимает 10 тактов вместо 9.3 для setcc (реальное измерение даёт 12с).
Можно попробовать ускорить накапливая две или даже три суммы в разных регистрах и складывая их лишь в конце, но это улучшает лишь до 9.0 тактов (реально - 11с).
Можно после сравнения вдвигать перенос в регистр и потом однократно popcnt, но такие сдвиги страшно медленные и общий итог 12 тактов (реально аж 33с).
Похоже ни один из вариантов смысла не имеет, разница между 15с и даже 11с не слишком существенна.

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


14/01/11
2916
Dmitriy40 в сообщении #1343088 писал(а):
Команды
Код:
cmp im32,r32

не существует

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

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


20/08/14
11061
Россия, Москва
Sender
Для многих компиляторов (ассемблеров) можно и без указания размера, он определяется по имени регистра. Вот когда память и непосредственный операнд, то да, размер необходим.

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


28/07/17

317
Изначально вопрос был по ускорению кода Си. А ассемблерная вставка ускорит ли такой код? То есть, выполнится она быстрее, но накладные расходы на заполнение регистров, на стек?

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение02.10.2018, 12:52 
Аватара пользователя


14/11/12
1338
Россия, Нижний Новгород
Dmitriy40 в сообщении #1343055 писал(а):
Код:
        vpcmpgtd        ymm1,ymm1,ymm0  ;15     1/0.5
        vpcmpgtd        ymm2,ymm1,ymm0  ;15     1/0.5
Если не ошибаюсь во второй строчке вроде должно быть так:
Код:
vpcmpgtd ymm2,ymm2,ymm0

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


20/08/14
11061
Россия, Москва
SergeyGubanov
Да, разумеется, это опечатка. Перепроверил, скорость от неё никак не изменяется.
Честно говоря я ни одну из функций на правильность вычислений не проверял (может там даже условие не совсем исходное), меня интересовала лишь приблизительная оценка скорости. Да, не слишком корректно, но для оценки тенденции почему бы нет. А при реальном применении "допилить по месту". :-)

FomaNeverov в сообщении #1343161 писал(а):
То есть, выполнится она быстрее, но накладные расходы на заполнение регистров, на стек?
Выше я приводил и результаты реальных измерений, именно в виде вызова функции, там и стек, и регистры, и всё прочее (по стандартному соглашению о вызовах для x64). Полный код не стал приводить лишь чтобы не захламлять смысл (тем более что кое-что добавляет сам ассемблер и в исходном коде этого не видно (хотя в бинарнике я разумеется смотрел что там реально), например пролог и эпилог функций).

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


12/07/07
4438
На всякий случай. Под win64 приведенные Вами функции почти листовые (leaf ): из несвободно модифицируемых регистров они изменяют только rbx; см., например, Overview of x64 Calling Conventions. Если вместо rbx взять свободно модифицируемый регистр, то пролог и эпилог будут не нужны. Компиляторы [с языков] высокого уровня могут дополнительно накладывать ограничения на свободно модифицируемые регистры, но в любом случае [свободно модифицируемых] регистров будет достаточно, чтобы приведенные вами функции остались листовыми.
Редактирование: добавлено "с языков" и "свободно модифицируемых".

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


20/08/14
11061
Россия, Москва
Повторю, я не ставил перед собой цели написать законченный модуль, лишь сравнить подручными средствами скорости выполнения разных кусочков кода. И сюда процитировал лишь непосредственно тестирующую часть.
Функции сравнений RBX не портят, а портить RDX имеют право, как и ymm0-ymm5. Из тестовой же функции я привёл лишь критичную для проверки скорости часть и эта часть тоже соблюдает соглашение. Сохранить RBX (и ymm при желании) я могу и вне процитированного цикла тестирования так как ничего лишнего в нём не вызывается.
Так что функции CmpX соглашению о вызовах следуют, а остальное (тестовое окружение) никакому соглашению следовать совершенно не обязано.

Заставить ассемблер не добавлять пролог и эпилог в виде команд
Код:
push RBP
mov  RBP,RSP
;sub RSP,0x20 - эта команда реально не добавляется так как другие процедуры не вызываются и стековый кадр без надобности
...
leave
в функции CmpX не то чтобы трудно, но зачем, их наличие как раз приближает тест к реальности и позволяет пользоваться макросами invoke и stdcall для вызова функций. В теоретическом анализе (руками и IACA) разумеется это (и команды call+ret) не учитывалось как неизменяемая от функции к функции часть.

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


12/07/07
4438
Да, я недосмотрел, действительно только "окружение". Тогда для меня эпилог и пролог совсем неожиданно. Ну, в приличных системах все мелкие и критические по скорости функции стараются делать листовыми. Это тут оффтопик, конечно.

На самом деле, realeugene описал идею ясно. А дальше от компилятора зависит: может сам компилятор всё оптимально сделает (если на высоком уровне код разумно записать), или можно в текст макросы вставить с intrinsics, или только asm функции доступны, или вообще отдельно скомпилировать и прилинковать функции нужно будет. Ну и детали лист / не лист тогда и обсуждать, если надо.

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С
Сообщение04.10.2018, 16:13 
Аватара пользователя


14/11/12
1338
Россия, Нижний Новгород
Спасибо всем кто ответил.

Попробовал следующий вариант с использованием AVX512:

Используется синтаксис C
static inline unsigned int f_avx512(unsigned int n)
{
    __m512i a = _mm512_set1_epi32(n);
    __m512i b = _mm512_set_epi32(N0, N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, -1, -1, -1, -1, -1);
    return 16 - _popcnt32(_mm512_mask2int(_mm512_cmplt_epu32_mask(a, b))); // k = (a < b) ? 1 : 0
}
 

Оказалось, эта процедура работает в десять раз быстрее исходной:

$ icc -O3 -xSKYLAKE-AVX512 -o test test.c
$ ./test
begin functional test...
functional test passed
run performance test...
ticks (empty ) 2.297993
ticks (branch) 9.502484
ticks (avx512) 3.013675
gain 10.066612


Тест:
код: [ скачать ] [ спрятать ]
Используется синтаксис C
#include <immintrin.h>
#include <stdint.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N0 100000000
#define N1 123456789
#define N2 234567891
#define N3 345678912
#define N4 456789123
#define N5 567891234
#define N6 678912345
#define N7 789123456
#define N8 891234567
#define N9 912345678
#define N10 999999999

static uint64_t random_seed;

static inline uint32_t next_random()
{
    random_seed = random_seed * 7305322493271191329ull + 2938793273570587247ull;
    return (random_seed >> 24);
}

static inline unsigned int f_empty(unsigned int n)
{
    return n;
}

static inline unsigned int f_branch(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;
}

static inline unsigned int f_avx512(unsigned int n)
{
    __m512i a = _mm512_set1_epi32(n);
    __m512i b = _mm512_set_epi32(N0, N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, -1, -1, -1, -1, -1);
    return 16 - _popcnt32(_mm512_mask2int(_mm512_cmplt_epu32_mask(a, b))); // k = (a < b) ? 1 : 0
}

int main(int argc, char* argv[])
{
    const uint64_t N = 1000000000;
    uint64_t n, dummy, t0, t1, t2;

    printf("begin functional test...\n");
    for (n = 0; n < N; n++) {
        unsigned int r1 = f_branch(n);
        unsigned int r2 = f_avx512(n);
        if (r1 != r2) {
            printf("functional test failed!!!\n");
            printf("f_branch(%" PRIu64 ")=%d f_avx512(%" PRIu64 ")=%d\n", n, r1, n, r2);
            return -1;
        }
    }
    printf("functional test passed\n");
    printf("run performance test...\n");

    dummy = 0;

    random_seed = 42;
    t0 = _rdtsc();
    for (n = 0; n < N; n++) {
        dummy += f_empty(next_random());
    }
    t0 = _rdtsc() - t0;

    random_seed = 42;
    t1 = _rdtsc();
    for (n = 0; n < N; n++) {
        dummy += f_branch(next_random());
    }
    t1 = _rdtsc() - t1;

    random_seed = 42;
    t2 = _rdtsc();
    for (n = 0; n < N; n++) {
        dummy += f_avx512(next_random());
    }
    t2 = _rdtsc() - t2;

    printf("ticks (empty ) %f\n", (double)t0 / (double)N);
    printf("ticks (branch) %f\n", (double)t1 / (double)N);
    printf("ticks (avx512) %f\n", (double)t2 / (double)N);
    printf("gain           %f\n", (double)(t1 - t0) / (double)(t2 - t0));
    printf("dummy %" PRIu64 "\n", dummy);

    return 0;
}
 

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С [asm, AVX512]
Сообщение28.09.2020, 07:57 


28/09/20
1
Есть у меня набросок кода для бинарного поиска. Мощная штука для поиска значений в таблице.

// Функция возвращает наименьший индекс k, такой что x<=Arr[k]; или k=Arr.size(), если x больше всех x[k].
// Т.е. это индекс, куда можно было бы вставить x, чтобы не нарушить сортировку.

int Search(const double &x, const std::vector<double> &Arr)
{
int i=0, j=Arr.size(), k; // i, j - границы поиска (j - последний индекс +1)
while((k=(i+j)>>1)<j)
if(x<=Arr[k])
j=k;
else
i=k+1;
return k;
}

Здесь неравенство в условии можно поменять на строгое. Соотв. функции в библиотеке <algorithm> называются lower_bound и upper_bound.

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С [asm, AVX512]
Сообщение28.09.2020, 10:41 
Заслуженный участник


12/07/07
4438
Данная тема посвящена поиску в таблице с малым числом значений (см. начальное сообщение), а не вообще бинарному поиску. В этом случае AVX позволяет написать быструю функцию.

В разделе «Низкоуровневое программирование» обсуждается программирование на уровне ассемблера, программирование GPU, написание драйверов. Программирование на ЯВУ общего назначения обсуждается в разделе «Программирование», см. тему «!!=ВАЖНО=!! Правила выбора раздела для размещения новой темы».

Aenigma, что Вы хотите обсудить/рассказать/спросить?

 Профиль  
                  
 
 Re: Помогите ускорить ещё одну функцию на С [asm, AVX512]
Сообщение28.09.2020, 11:58 
Заслуженный участник


20/08/14
11061
Россия, Москва
Aenigma
Смотрите здесь свою "мощную штуку": Двоичный поиск.

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

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



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

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


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

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