Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[44.192.247.185] |
|
Сообщ.
#1
,
|
|
|
Вот простое задание дали: нужно из массива из N элементов, найти такие с четным индексом, чтобы делились на числа 3 и 5 без остатка. Нужно реализовать данное решение на C++ и на ассемблере(вставки в C++ код). Проблема в том что код на ассемблере выполняется немного медленнее.
Вот код #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
,
|
|
|
В общем видимо компилятор неплохо оптимизирует код. Так как нужны парные индексы решил переписать код (прибавлять индекс +2, вместо +1) + еще проверка на четность занимает время.
__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++ код решил тоже поменять, чтобы было соответствие 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 получился немного больше чем два раза. |
Сообщ.
#3
,
|
|
|
Вообще, код на C++ и должен быть ощутимо быстрее, т.к. нормальный компилятор делит (и получает остаток от деления) на константу через умножение, ибо деление – довольно медленная операция.
Например: https://godbolt.org/z/u-WwzH Добавлено Пора бы уж вшить в процессоры константы для быстрого деления хотя бы на степени двойки и числа, скажем, до 256 |
Сообщ.
#4
,
|
|
|
Чуть-чуть оптимизировал:
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 } } |
Сообщ.
#5
,
|
|
|
Парни!
Куча кода, даже с надписью "слегка оптимизированного" - это почти прекрасно... Но предлагаю сделать что-то более осязаемое - запилить на одной платформе что-то типа бейнчмарка (на основе шаблона замера времени). В реализации шаблона предусмотреть 500-1000 итераций основного действия, дабы исключить (по возможности) влияние внешних факторов на тестируемой платформе. И только потом заценить, кто чего и как сумел оптимизировать. Без этого это - мув туда, мув сюда, джамп обратно Резюме Берем все одинаковые входные статические данные, обрабатываем, получаем время. Пример-заготовка Предлагаю для замеров использовать шаблон (составляйте сами) на основе копипасты, которую я сохранил в посте на своем форуме. Просто и стандартно по отношению к Цэ++ |
Сообщ.
#6
,
|
|
|
Разве теория не гласит, что в данном случае MMX-код должен всех победить? Или на него (на эти инструкции) давно подзабили и... в проигрыше, короче?!
|
Сообщ.
#7
,
|
|
|
Цитата Славян @ Разве теория не гласит, что в данном случае MMX-код должен всех победить? В каком месте? После него еще столько спецификаций было запилено. |
Сообщ.
#8
,
|
|
|
Славян, а это нужно вообще? Для данного случая? И кому?
Добавлено Цитата JoeUser @ Тут микро- и наносекунды нужны, даже для тысяч итераций. Предлагаю для замеров использовать шаблон (составляйте сами) на основе копипасты, которую я сохранил в посте на своем форуме. |
Сообщ.
#9
,
|
|
|
Цитата Jin X @ Тут микро- и наносекунды нужны, даже для тысяч итераций. Так я и говорю - давайте по стопицот милёнов! |
Сообщ.
#10
,
|
|
|
Что-то я не понял, JoeUser, что ты предлагаешь. Куда что пихать, куда выкладывать, как сравнивать...
Цитата Славян @ В MMX нет деления. Есть умножение, но только 16-битное, с получением отдельно старших или младших половин 32-битного произведения, и нет остатка от деления. Разве теория не гласит, что в данном случае MMX-код должен всех победить? |
Сообщ.
#11
,
|
|
|
Цитата Qraizer @ Что-то я не понял, JoeUser, что ты предлагаешь. Предлагаю запиливать, к примеру, на ideone.com, с учетом одинаковых входных данных. Делать по 10000 итераций, и по общему времени сравнивать с "конкурентами". |
Сообщ.
#12
,
|
|
|
Цитата Qraizer @ Надо думать, что под MMX подразумевается SSE/AVX, хотя там история, по сути, та же (для целых чисел). Есть умножение DWORD-ов с получением QWORD-результата (pmuldq). Учитывая, что нужно брать только чётные элементы, это можно заюзать. Вопрос только в том: нужен ли этот баян козе? В MMX нет деления. Есть умножение, но только 16-битное, с получением отдельно старших или младших половин 32-битного произведения, и нет остатка от деления. |