Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > Assembler > Проблема с быстродействием


Автор: mylok 24.11.19, 20:27
Вот простое задание дали: нужно из массива из N элементов, найти такие с четным индексом, чтобы делились на числа 3 и 5 без остатка. Нужно реализовать данное решение на C++ и на ассемблере(вставки в C++ код). Проблема в том что код на ассемблере выполняется немного медленнее.
Вот код
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #include <iostream>
    #include <ctime>
    #include <iomanip>
    using namespace std;
     
    const int N = 10000000;
    int int_array[N];
     
    int res_N = 0;
    int res_int_array[N];
     
    void init_array(){
        srand(time(0));
        for(int i=0;i<N;i++){
            int_array[i] = rand()%136 + 15;
        }
    }
     
    void print_array(){
        if(N>100) return;
        for(int i=0;i<N;i++){
            cout<<int_array[i]<<" ";
        }
    }
    //Код C++
    void find_values(int* arr){
        res_N = 0;
     
        for(int i=0; i<N; i++){
            if(i%2!=0){
                continue;
            }
            if(arr[i]%3 == 0 && arr[i]%5 == 0){
                res_int_array[res_N] =  arr[i];
                res_N++;
            }
        }
    }
    //аналогичный код asm
    void find_values_asm(int* arr){
     
        res_N = 0;
        __asm{
        
            xor eax,eax
            xor esi,esi
            xor edi,edi
            mov ecx,N
            mov esi, arr
        l_begin:
     
            xor edx,edx
            mov eax,ecx
            mov ebx,2
            div ebx
            cmp edx,0
            jnz l_next
     
            mov ebx, [esi]
            mov ax,bx
            mov bl,3
            div bl
            cmp ah,0
     
            jnz l_next
     
            mov ebx, [esi]
            mov ax,bx
            mov bl,5
            div bl
            cmp ah,0
            jnz l_next
     
            mov ebx, [esi]
            mov [res_int_array+edi],ebx
            inc res_N
            add edi,4  
     
        l_next:
     
            add esi,4  
            loop l_begin
        }
    }
     
    void print_res_array(int *res_array, int sizeN){
        if(N>100) {
            cout<<"Result N = "<<sizeN<<endl;
            return;
        }
        for(int i=0;i<sizeN;i++){
            cout<<res_array[i]<<" ";
        }
    }
     
    int main(int argc, char** argv) {
        
        cout<<setprecision(15);
        init_array();
        print_array();
        cout<<endl<<endl;
     
        int m;
        do
        {
            cout<<"1. C++ \n";
            cout<<"2. Asm \n";
            cout<<"3. Exit\n";
            cout<<": ";
            cin>>m;
            system("cls");
            clock_t tStart, tEnd;
            switch(m)
            {
                case 1:
                    tStart = clock();
                    find_values(int_array);
                    tEnd = clock();
                    cout<<"Time "<<double(tEnd - tStart) / double(CLOCKS_PER_SEC)<<endl;
                    cout<<endl;
                    print_res_array(res_int_array, res_N);
                    break;
                case 2:
                    tStart = clock();
                    find_values_asm(int_array);
                    tEnd = clock();
                    cout<<"Time "<<double(tEnd - tStart) / double(CLOCKS_PER_SEC)<<endl;
                    cout<<endl;
                    print_res_array(res_int_array, res_N);
                    break;
                    
            }
            cout<<endl;
        }while(m<3);
     
        return 0;
    }

Автор: mylok 24.11.19, 23:54
В общем видимо компилятор неплохо оптимизирует код. Так как нужны парные индексы решил переписать код (прибавлять индекс +2, вместо +1) + еще проверка на четность занимает время.
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
        __asm{
        
            xor eax,eax
            xor esi,esi
            xor edi,edi
            mov ecx,N
            mov esi, arr
        l_begin:
     
            mov ebx, [esi]
            mov ax,bx
            mov bl,3
            div bl
            cmp ah,0
            jnz l_next
     
            mov ebx, [esi]
            mov ax,bx
            mov bl,5
            div bl
            cmp ah,0
            jnz l_next
     
            mov ebx, [esi]
            mov [res_int_array+edi],ebx
            inc res_N
            add edi,4  
     
        l_next:
     
            add esi,8
            sub ecx,2
            cmp ecx,0
            jnz l_begin
        }

C++ код решил тоже поменять, чтобы было соответствие
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
        for(int i=0; i<N; i+=2){
            if(arr[i]%3 == 0 && arr[i]%5 == 0){
                res_int_array[res_N] =  arr[i];
                res_N++;
            }
     
        }


Выигрыш по времени asm получился немного больше чем два раза.

Автор: Jin X 25.11.19, 07:38
Вообще, код на C++ и должен быть ощутимо быстрее, т.к. нормальный компилятор делит (и получает остаток от деления) на константу через умножение, ибо деление – довольно медленная операция.
Например: https://godbolt.org/z/u-WwzH

Добавлено
Пора бы уж вшить в процессоры константы для быстрого деления хотя бы на степени двойки и числа, скажем, до 256 :)

Автор: Qraizer 25.11.19, 12:39
Чуть-чуть оптимизировал:
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    void find_values_asm(int* arr)
    {
        __asm{
                    push ebp
                    xor  ebx, ebx
                    lea  esi, [ebx+3]
                    lea  edi, [ebx+5]
                    mov  edx, [N]
                    mov  ecx, [arr]
                    lea  edx, [edx*4+ecx]
                    push edx
            l_begin:
     
                    mov  eax, [ecx]
                    mov  ebp, eax
                    cdq
                    div  esi
                    test edx, edx
                    jnz  l_next
     
                    mov  eax,ebp
                    div  edi
                    test edx, edx
                    jnz  l_next
     
                    mov  [res_int_array+ebx*4],ebp
                    inc  ebx
     
            l_next:
     
                    lea  ecx, [ecx+2*4]
                    cmp  ecx, [esp]
                    jb   l_begin
                    pop  eax
                    pop  ebp
            }
    }

Автор: JoeUser 25.11.19, 15:33
Парни!

Куча кода, даже с надписью "слегка оптимизированного" - это почти прекрасно...
Но предлагаю сделать что-то более осязаемое - запилить на одной платформе
что-то типа бейнчмарка (на основе шаблона замера времени). В реализации шаблона
предусмотреть 500-1000 итераций основного действия, дабы исключить (по возможности)
влияние внешних факторов на тестируемой платформе.

И только потом заценить, кто чего и как сумел оптимизировать. Без этого это - мув туда,
мув сюда, джамп обратно :)

Резюме

Берем все одинаковые входные статические данные, обрабатываем, получаем время.

Пример-заготовка

Предлагаю для замеров использовать шаблон (составляйте сами) на основе копипасты, которую я сохранил в посте на своем форуме.
Просто и стандартно по отношению к Цэ++ :)

Автор: Славян 25.11.19, 16:23
Разве теория не гласит, что в данном случае MMX-код должен всех победить? Или на него (на эти инструкции) давно подзабили и... в проигрыше, короче?!

Автор: JoeUser 25.11.19, 17:31
Цитата Славян @
Разве теория не гласит, что в данном случае MMX-код должен всех победить?

В каком месте? После него еще столько спецификаций было запилено.

Автор: Jin X 25.11.19, 18:13
Славян, а это нужно вообще? Для данного случая? И кому?

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

Автор: JoeUser 25.11.19, 20:00
Цитата Jin X @
Тут микро- и наносекунды нужны, даже для тысяч итераций.

Так я и говорю - давайте по стопицот милёнов!

Автор: Qraizer 26.11.19, 12:04
Что-то я не понял, JoeUser, что ты предлагаешь. Куда что пихать, куда выкладывать, как сравнивать...
Цитата Славян @
Разве теория не гласит, что в данном случае MMX-код должен всех победить?
В MMX нет деления. Есть умножение, но только 16-битное, с получением отдельно старших или младших половин 32-битного произведения, и нет остатка от деления.

Автор: JoeUser 26.11.19, 13:14
Цитата Qraizer @
Что-то я не понял, JoeUser, что ты предлагаешь.

Предлагаю запиливать, к примеру, на ideone.com, с учетом одинаковых входных данных.
Делать по 10000 итераций, и по общему времени сравнивать с "конкурентами".

Автор: Jin X 29.11.19, 08:01
Цитата Qraizer @
В MMX нет деления. Есть умножение, но только 16-битное, с получением отдельно старших или младших половин 32-битного произведения, и нет остатка от деления.
Надо думать, что под MMX подразумевается SSE/AVX, хотя там история, по сути, та же (для целых чисел). Есть умножение DWORD-ов с получением QWORD-результата (pmuldq). Учитывая, что нужно брать только чётные элементы, это можно заюзать. Вопрос только в том: нужен ли этот баян козе?

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)