На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Перед отправкой сообщения внимательно прочтите правила раздела!!!
1. Запрещается обсуждать написание вирусов, троянов и других вредоносных программ!
2. Помните, что у нас есть FAQ раздела Assembler и Полезные ссылки. Посмотрите, возможно, там уже имеется решение вашего вопроса.

3. Настоятельно рекомендуем обратить особое внимание на правила форума, которые нарушаются чаще всего:
  3.1. Заголовок темы должен кратко отражать её суть. Темы с заголовками типа "Срочно помогите!" или "Ассемблер" будут отправляться в Корзину для мусора.
  3.2. Исходники программ обязательно выделяйте тегами [code]...[/code] (одиночные инструкции можно не выделять).
  3.3. Нежелательно поднимать старые темы (не обновлявшиеся более года) без веской на то причины.

Не забывайте также про главные Правила форума!

Добро пожаловать и приятного вам общения!!! ;)
 
Модераторы: Jin X, Qraizer
  
> Проблема с быстродействием
    Вот простое задание дали: нужно из массива из N элементов, найти такие с четным индексом, чтобы делились на числа 3 и 5 без остатка. Нужно реализовать данное решение на C++ и на ассемблере(вставки в C++ код). Проблема в том что код на ассемблере выполняется немного медленнее.
    Вот код
    ExpandedWrap disabled
      #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;
      }
      В общем видимо компилятор неплохо оптимизирует код. Так как нужны парные индексы решил переписать код (прибавлять индекс +2, вместо +1) + еще проверка на четность занимает время.
      ExpandedWrap disabled
            __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++ код решил тоже поменять, чтобы было соответствие
      ExpandedWrap disabled
            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 получился немного больше чем два раза.
        Вообще, код на C++ и должен быть ощутимо быстрее, т.к. нормальный компилятор делит (и получает остаток от деления) на константу через умножение, ибо деление – довольно медленная операция.
        Например: https://godbolt.org/z/u-WwzH

        Добавлено
        Пора бы уж вшить в процессоры константы для быстрого деления хотя бы на степени двойки и числа, скажем, до 256 :)
          Чуть-чуть оптимизировал:
          ExpandedWrap disabled
            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
                    }
            }
          Сообщение отредактировано: Qraizer -
            Парни!

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

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

            Резюме

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

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

            Предлагаю для замеров использовать шаблон (составляйте сами) на основе копипасты, которую я сохранил в посте на своем форуме.
            Просто и стандартно по отношению к Цэ++ :)
              Разве теория не гласит, что в данном случае MMX-код должен всех победить? Или на него (на эти инструкции) давно подзабили и... в проигрыше, короче?!
                Цитата Славян @
                Разве теория не гласит, что в данном случае MMX-код должен всех победить?

                В каком месте? После него еще столько спецификаций было запилено.
                  Славян, а это нужно вообще? Для данного случая? И кому?

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

                    Так я и говорю - давайте по стопицот милёнов!
                      Что-то я не понял, JoeUser, что ты предлагаешь. Куда что пихать, куда выкладывать, как сравнивать...
                      Цитата Славян @
                      Разве теория не гласит, что в данном случае MMX-код должен всех победить?
                      В MMX нет деления. Есть умножение, но только 16-битное, с получением отдельно старших или младших половин 32-битного произведения, и нет остатка от деления.
                        Цитата Qraizer @
                        Что-то я не понял, JoeUser, что ты предлагаешь.

                        Предлагаю запиливать, к примеру, на ideone.com, с учетом одинаковых входных данных.
                        Делать по 10000 итераций, и по общему времени сравнивать с "конкурентами".
                          Цитата Qraizer @
                          В MMX нет деления. Есть умножение, но только 16-битное, с получением отдельно старших или младших половин 32-битного произведения, и нет остатка от деления.
                          Надо думать, что под MMX подразумевается SSE/AVX, хотя там история, по сути, та же (для целых чисел). Есть умножение DWORD-ов с получением QWORD-результата (pmuldq). Учитывая, что нужно брать только чётные элементы, это можно заюзать. Вопрос только в том: нужен ли этот баян козе?
                          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                          0 пользователей:


                          Рейтинг@Mail.ru
                          [ Script execution time: 0,0373 ]   [ 15 queries used ]   [ Generated: 28.03.24, 19:40 GMT ]