какая процедура proc1 или proc2 выполняется быстрее и почему
char M[4000*4100];
int proc1()
{
int i,j,c;
c=0;
for (j=0;j<4000;j++)for(i=0;i<4000;i++) c=c+M[i*4096 + j];
return c;
}
int proc2()
{
int i,j,c;
c=0;
for (j=0;j<4000;j++)for(i=0;i<4000;i++) c=c+M[i*4097 + j];
return c;
}
proc1 наверное, ведь умножение на 4096 заменится на сдвиг на 12 бит.
Хотя после оптимизации обе будут выполняться одинаково. Оптимизированные версии выглядят так
char M[4000*4100];
int proc1()
{
int i,j,c;
c=0;
for (j=0;j<4000;j++)for(i=0;i<16384000;i+=4096) c=c+M[i + j];
return c;
}
int proc2()
{
int i,j,c;
c=0;
for (j=0;j<4000;j++)for(i=0;i<16388000;i+=4097) c=c+M[i + j];
return c;
}
Видимо первая. Могу предположить что умножение на 4096 быстрее, чем на 4097, т.к. что бы умножить на 4096 достаточно сдвинуть биты влево на 12 позиций (2^12 = 4096).
Здравствуйте, korzhik, Вы писали:
W>>какая процедура proc1 или proc2 выполняется быстрее и почему
K>proc2 быстрее
кстати, я не пошутил
у меня на компе proc2 выполняется в 1.5 раза быстрее чем proc1.
Как такое может быть и почему???!!!
Протестируйте пожалуйста у себя:
#include <boost/progress.hpp>
char M[4000*4100];
int proc1()
{
boost::progress_timer t;
int c = 0;
for (int j = 0; j < 4000; ++j)
for (int i = 0; i < 4000; ++i)
c = c + M[i*4096 + j];
return c;
}
int proc2()
{
boost::progress_timer t;
int c = 0;
for (int j = 0; j < 4000; ++j)
for (int i = 0; i < 4000; ++i)
c = c + M[i*4097 + j];
return c;
}
int main()
{
proc1();
proc2();
}
Здравствуйте, icWasya, Вы писали:
W>Здравствуйте, Вы писали: >>>proc2 выполняется в 1.5 раза быстрее чем proc1 >>>Более того, тормоза возникают и на других числах, кратных 512...
W>а тормоза происходят не на умножении , а собственно на выборке из массива!
У меня недавно тоже такая проблема возникла. Я множил матрицы. Матрицы 1024х1024 прога множила 90 секунд, а у моего друга — 20. Было обидно. Я использовал линейный массив и вручную вычислял индексы, а он массив массивов. Оказалось, что дело было как раз в загадочном числе 1024 (кратно 512). На других числах я даже, кажется, его рулил.
unsigned int n; //1024
type *A, *B, *C;
type **Ai, **Bi, **Ci;
void mult(int stroke) {
for (unsigned __int32 i = 0; i < n; i++) {
for (unsigned __int32 j = 0; j < n; j++)
Ci[stroke][i] += Ai[stroke][j] * Bi[j][i];
// C[stroke * n + i] += A[stroke * n + j] * B[j * n + i];
}
}
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Кодт, Вы писали:
К>>Более того, тормоза возникают и на других числах, кратных 512...
A>Что-то я не понимаю почему так
Все очень просто
Число 4096 — магическое в архитектуре PC (пентиум и выше), т.к весит 12 бит. а память в кэше первого уровня имеет 12 битную адресацию, т.е 2 блока памяти находящиеся по адресу, имеющему одинаковый остаток от деления на 4096 будут иметь один адрес,(но с этим адресом аасоциируется не одна а несколько линий) и несмотря на то что имеется несколько линий для одного адреса, по коду видно, что 4000 раз подняд идет работа с одним адресом . После 4-5 циклов все линии заполнятся, и при следующем чтении, ПРОЦЕССОРУ необходимо будет прочитать всю линию в 16 байт для продолжения работы(он по другому не умеет). далее идет ещё более труба, но она в обоих кусках кода. Как некаторые не знают, число 4096 — магическое. Именно по этому адресу выравниваются данные во кэше второго уровня. И обмен с памятью происходит именно по страницам. следовательно, мы не скоро, а очень скоро придем к тому, что у нас кончится кэш и второго уровня, но к данному случаю это не относися.
З.Ы. этот код пример как НЕ НАДО ПИСАТЬ ПРОГРАММЫ
Re: Тест скорости
От:
Аноним
Дата:
28.12.04 13:53
Оценка:
Здравствуйте, icWasya, Вы писали:
W>какая процедура proc1 или proc2 выполняется быстрее и почему W>
W>char M[4000*4100];
W>int proc1()
W>{
W> int i,j,c;
W> c=0;
W> for (j=0;j<4000;j++)for(i=0;i<4000;i++) c=c+M[i*4096 + j];
W> return c;
W>}
W>int proc2()
W>{
W> int i,j,c;
W> c=0;
W> for (j=0;j<4000;j++)for(i=0;i<4000;i++) c=c+M[i*4097 + j];
W> return c;
W>}
W>
Здравствуйте, Аноним, Вы писали:
А>Все очень просто А>Число 4096 — магическое в архитектуре PC (пентиум и выше) А>З.Ы. этот код пример как НЕ НАДО ПИСАТЬ ПРОГРАММЫ
Так ведь выходит, что наоборот, надо писать именно как пр.2, ибо второй вариант работает у меня примерно вдвое скорее.
Я смотрел что там компилятор скомпилировал — так там он в обоих случаях поставил сложение, только
в первом случае с 4096, а во втором — 4097...
; 1275 : for (j=0;j<4000;j++)for(i=0;i<4000;i++) c=c+M[i*4096 + j];
xor esi, esi
$L58372:
lea ecx, DWORD PTR ?M@@3PADA[esi]
mov edx, 4000 ; 00000fa0H
$L58375:
movsx edi, BYTE PTR [ecx]
add eax, edi
add ecx, 4096 ; 00001000H
dec edx
jne SHORT $L58375
inc esi
cmp esi, 4000 ; 00000fa0H
jl SHORT $L58372
Перекуём баги на фичи!
, а собственно на выборке из массива! 
