Oberon space
General Category => Общий раздел => Тема начата: Губанов Сергей Юрьевич от Май 02, 2012, 01:32:38 pm
-
Для измерения производительности разных компьютеров написал я однажды на C# простенькую програмку. Она сортирует массив целых чисел самым процессороёмким способом O(N^2).
i = 0;
while (i < n)
{
j = 0;
while (j < n)
{
if (a[j] < a[i])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
j++;
}
i++;
}
Но так как иногда я её запускал на компьютерах с Linux под Mono, а моновский JIT компилятор туповат на счёт оптимизации с проверкой индексов массивов, то я переписал сортировку в unsafe коде.
p = a;
while (p < e)
{
q = a;
while (q < e)
{
if (*q < *p)
{
int t = *p;
*p = *q;
*q = t;
}
q++;
}
p++;
}
Ансэйфный вариант работал быстрее сэйфного, что не вызывало у меня удивлений. Однако, потом я запустил эту программку на 64 разрядном компьютере и был очень удивлён тем, что сэйфный код вдруг стал работать на 20% быстрее ансэйфного :o
Об этом я писал как-то на Оберонкоре...
Сейчас я придумал что надо подкрутить в ансэйфном коде чтобы он ускорился. Вот код:
i = 0;
p = a;
while (i < n)
{
j = 0;
int* q = a;
while (j < n)
{
if (*q < *p)
{
int t = *p;
*p = *q;
*q = t;
}
j++;
q++;
}
i++;
p++;
}
он работает примерно на 20% быстрее сэйфного и, соответственно, примерно на 50% быстрее предыдущего ансэфного (несмотря на в два раза большее количество переменных).
a[ i ] распалось отдельно на индекс i и указатель p,
a[ j ] распалось отдельно на индекс j и указатель q.
-
Для измерения производительности разных компьютеров написал я однажды на C# простенькую програмку. Она сортирует массив целых чисел самым процессороёмким способом O(N^2).
Надо смотреть маш.код... Могу только отметить, что с точки зрения процессора обращение по индексу и обращение по указателю не могут отличаться на проценты. Вот в маш.коде типичное обращение по индексу:
mov edx,[i] ; помещаем индекс i в регистр edx
mov ecx,[j] ; помещаем индекс j в регистр ecx
mov edx,[edx*4] ; помещаем в регистр edx значение i-го элемента
cmp dword edx,[ecx*4] ; сравниваем значения i-го и j-го элементов
jae ... ; переход "по больше или равно"
а это обращение по указателям:
mov edx,[p] ; помещаем в регистр edx указатель p
mov ecx,[q] ; помещаем в регистр ecx указатель q
mov edx,[edx] ; помещаем в регистр edx значение с адреса p
cmp dword edx,[ecx] ; сравниваем значения с адресами p и q
jae ... ; переход по "больше или равно"
По времени исполнения операторы "mov edx,[edx*4]" и "mov edx,[edx]" практически не отличаются.
-
Студия выдаёт следующий код...
Медленный вариант:
i = 0;
00000109 mov dword ptr [rsp+30h],0
p = a;
00000164 mov rax,qword ptr [rbp]
00000168 mov qword ptr [rbp+10h],rax
0000016c jmp 00000000000001CC
{
q = a;
0000016e mov rax,qword ptr [rbp]
00000172 mov qword ptr [rbp+18h],rax
00000176 jmp 00000000000001B4
{
if (*q < *p)
00000178 mov rcx,qword ptr [rbp+18h]
0000017c mov ecx,dword ptr [rcx]
0000017e mov rax,qword ptr [rbp+10h]
00000182 mov eax,dword ptr [rax]
00000184 cmp ecx,eax
00000186 jge 00000000000001A6
{
int t = *p;
00000188 mov rax,qword ptr [rbp+10h]
0000018c mov eax,dword ptr [rax]
0000018e mov dword ptr [rbp+24h],eax
*p = *q;
00000191 mov rcx,qword ptr [rbp+18h]
00000195 mov ecx,dword ptr [rcx]
00000197 mov rax,qword ptr [rbp+10h]
0000019b mov dword ptr [rax],ecx
*q = t;
0000019d mov rcx,qword ptr [rbp+18h]
000001a1 mov eax,dword ptr [rbp+24h]
000001a4 mov dword ptr [rcx],eax
}
q++;
000001a6 mov rax,qword ptr [rbp+18h]
000001aa add rax,4
000001b0 mov qword ptr [rbp+18h],rax
while (q < e)
000001b4 mov rax,qword ptr [rbp+8]
000001b8 cmp qword ptr [rbp+18h],rax
000001bc jb 0000000000000178
}
p++;
000001be mov rax,qword ptr [rbp+10h]
000001c2 add rax,4
000001c8 mov qword ptr [rbp+10h],rax
while (p < e)
000001cc mov rax,qword ptr [rbp+8]
000001d0 cmp qword ptr [rbp+10h],rax
000001d4 jb 000000000000016E
}
На 50% более быстрый вариант:
p = a;
00000111 mov rax,qword ptr [rsp+28h]
00000116 mov qword ptr [rsp+38h],rax
0000011b jmp 00000000000001AA
{
j = 0;
00000120 mov dword ptr [rsp+34h],0
int* q = a;
00000128 mov rax,qword ptr [rsp+28h]
0000012d mov qword ptr [rsp+40h],rax
00000132 jmp 0000000000000185
{
if (*q < *p)
00000134 mov rcx,qword ptr [rsp+40h]
00000139 mov ecx,dword ptr [rcx]
0000013b mov rax,qword ptr [rsp+38h]
00000140 mov eax,dword ptr [rax]
00000142 cmp ecx,eax
00000144 jge 000000000000016A
{
int t = *p;
00000146 mov rax,qword ptr [rsp+38h]
0000014b mov eax,dword ptr [rax]
0000014d mov dword ptr [rsp+48h],eax
*p = *q;
00000151 mov rcx,qword ptr [rsp+40h]
00000156 mov ecx,dword ptr [rcx]
00000158 mov rax,qword ptr [rsp+38h]
0000015d mov dword ptr [rax],ecx
*q = t;
0000015f mov rcx,qword ptr [rsp+40h]
00000164 mov eax,dword ptr [rsp+48h]
00000168 mov dword ptr [rcx],eax
}
j++;
0000016a mov eax,dword ptr [rsp+34h]
0000016e add eax,1
00000171 mov dword ptr [rsp+34h],eax
q++;
00000175 mov rax,qword ptr [rsp+40h]
0000017a add rax,4
00000180 mov qword ptr [rsp+40h],rax
while (j < n)
00000185 cmp dword ptr [rsp+34h],0FFFFh
0000018d jl 0000000000000134
}
i++;
0000018f mov eax,dword ptr [rsp+30h]
00000193 add eax,1
00000196 mov dword ptr [rsp+30h],eax
p++;
0000019a mov rax,qword ptr [rsp+38h]
0000019f add rax,4
000001a5 mov qword ptr [rsp+38h],rax
while (i < n)
000001aa cmp dword ptr [rsp+30h],0FFFFh
000001b2 jl 0000000000000120
000001b8 mov qword ptr [rsp+28h],0
}
-
Видимо whille (i < n) и whille (j < n) против whille (p < e) и whille (q < e) выигрывают тем, что n - константа (n=0FFFFh), в то время как указатель e - переменная.
-
Видимо whille (i < n) и whille (j < n) против whille (p < e) и whille (q < e) выигрывают тем, что n - константа (n=0FFFFh), в то время как указатель e - переменная.
Это предположение легко проверить, сделайте переменную, в которую поместите данное значение и... сравните. Я пока не увидел в приведённом ранее коде каких-то значимых отличий. Странно, что такая большая разница.
-
В принципе удивляет такая вещь:
00000191 mov rcx,qword ptr [rbp+18h]
00000195 mov ecx,dword ptr [rcx]
00000197 mov rax,qword ptr [rbp+10h]
0000019b mov dword ptr [rax],ecx
0000019d mov rcx,qword ptr [rbp+18h]
000001a1 mov eax,dword ptr [rbp+24h]
000001a4 mov dword ptr [rcx],eax
... обратите внимание на адреса... Они вообще не выравниваются, что может сильно замедлить выборку следующей команды. Но это есть в обоих фрагментах кода... Странный какой-то компилятор...
-
И это тоже странно выглядит:
0000016a mov eax,dword ptr [rsp+34h]
0000016e add eax,1
00000171 mov dword ptr [rsp+34h],eax
00000175 mov rax,qword ptr [rsp+40h]
0000017a add rax,4
00000180 mov qword ptr [rsp+40h],rax
Каждые три команды заменяются на одну короткую:
inc eax
add qword ptr [rsp+40h],4
... но такой код опять же в каждом фрагменте, то есть не в этом причина различий, но компилятор удивляет.
-
Видимо whille (i < n) и whille (j < n) против whille (p < e) и whille (q < e) выигрывают тем, что n - константа (n=0FFFFh), в то время как указатель e - переменная.
Да, других отличий нет. Но давать столь большую разницу... это различие не должно, тем более, учитывая, что переменные в стеке выравнены правильно, и область локальных данных и параметров кэширована процессором. Использование индексов наряду с указателями даёт дополнительные операции присваивания и инкрементирования, что логике ухудшает вариант индексы+указатели.
Любопытно посмотреть на порождаемый код, если обмен производить с помощью xor, без использования временной целочисленной переменной... то есть вместо
int t = *p;
*p = *q;
*q = t;
написать что-то вроде этого:
*p = *p xor *q;
*q = *p xor *q;
*p = *p xor *q;
(на С# я не писал, и не знаю как там пишется XOR).
-
Это предположение легко проверить
Проверил. Да, всё дело оказалось в константности n!
Пишу const int n = 65535; и работает на 20% быстрее сэйфного кода.
А пишу просто int n = 65535; и работает на 20% медленнее сэйфного кода.
Между первым и вторым 50% разницы (1.20/0.80=1.50).
-
Странный какой-то компилятор...
Этот код я получил запустив программу из под Студии поставив брэкпоинт в исходнике. Известно, что при запуске из-под Студии программа (даже релизная) работает медленнее чем при автономном запуске. Машинный код генерируемый на лету автономным JIT компилятором я не знаю как получить.
-
Странный какой-то компилятор...
Этот код я получил запустив программу из под Студии поставив брэкпоинт в исходнике. Известно, что при запуске из-под Студии программа (даже релизная) работает медленнее чем при автономном запуске. Машинный код генерируемый на лету автономным JIT компилятором я не знаю как получить.
Понятно.
Меня XOR заинтересовал, как критерий оценки оптимизационных возможностей компилятора. Ну, да не важно...
Спасибо.
-
Попробовал XOR. Замедлилось на те же 50% (как будто других чисел нет). Одновременно XOR с неконстантным n тоже даёт те же 50% разницы (нет кумулятивного эффекта). Чего-то там суперскалярный процессор со спекулятивным вычислением значит делает параллельно (i7 2600K).
-
Попробовал XOR. Замедлилось на те же 50% (как будто других чисел нет). Одновременно XOR с неконстантным n тоже даёт те же 50% разницы (нет кумулятивного эффекта). Чего-то там суперскалярный процессор со спекулятивным вычислением значит делает параллельно (i7 2600K).
Значит создаётся неоптимизированный код (ожидаемо)... Зря, IMHO, ассемблер на помойку отнесли... красоты совсем не осталось... раньше в радость было посмотреть, как компиляторы старались, а сейчас... эх...
-
В ансэйфе писал потому, что хотел добиться примерно одинаковой скорости работы C# программы как под умным Микрософтовским рантаймом так и под туповатым Mono. Я же скорость процессоров хотел измерить. Сейчас попробовал запустить эту програмку под 32 разрядной Mono и обнаружил, что она там работает в пять с половиной раз медленнее (хотя компьютеры примерно одинаковые i7 2600K vs i7 950). То есть 64 разрядность архи важна.
-
В ансэйфе писал потому, что хотел добиться примерно одинаковой скорости работы C# программы как под умным Микрософтовским рантаймом так и под туповатым Mono. Я же скорость процессоров хотел измерить. Сейчас попробовал запустить эту програмку под 32 разрядной Mono и обнаружил, что она там работает в пять с половиной раз медленнее (хотя компьютеры примерно одинаковые i7 2600K vs i7 950). То есть 64 разрядность архи важна.
Не... в 5 раз... это видимо какая-то эмуляция работает...
-
Кстати, Сергей... мне не совсем понятна Ваша методика измерения скорости работы процессора...
Может было бы более правильно написать и откомпилировать код, а не полагаться на динамическую кодогенерацию. Тогда можно быть более уверенным, в том что меряется скорость процессора. Или есть ещё какие-то вводные?
-
Да была ещё привязка к тому, что мне интересно узнать не производительность процессора вообще, а как-то приближенно к производительности дотнетной платформы. Оказалось, что производительность процессоров варьируется гораздо менее серьёзно чем разница между Microsoft-товским 64 разрядным рантаймом и 32 разрядным Mono.
-
Да была ещё привязка к тому, что мне интересно узнать не производительность процессора вообще, а как-то приближенно к производительности дотнетной платформы. Оказалось, что производительность процессоров варьируется гораздо менее серьёзно чем разница между Microsoft-товским 64 разрядным рантаймом и 32 разрядным Mono.
Это было ожидаемо... Может быть не 5 раз, но в разы (не на проценты)...