Удивительное затормаживание и ускорение unsafe кода C# 64bit

[Губанов Сергей Юрьевич]

Для измерения производительности разных компьютеров написал я однажды на 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% быстрее ансэйфного

Об этом я писал как-то на Оберонкоре...

Сейчас я придумал что надо подкрутить в ансэйфном коде чтобы он ускорился. Вот код:

Код: [Выделить]

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.

[alexus]

Для измерения производительности разных компьютеров написал я однажды на 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 - переменная.

[alexus]

Видимо whille (i < n) и whille (j < n) против whille (p < e) и whille (q < e) выигрывают тем, что n - константа (n=0FFFFh), в то время как указатель e - переменная.

Это предположение легко проверить, сделайте переменную, в которую поместите данное значение и... сравните. Я пока не увидел в приведённом ранее коде каких-то значимых отличий. Странно, что такая большая разница.

[alexus]

В принципе удивляет такая вещь:

Код: [Выделить]

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
... обратите внимание на адреса... Они вообще не выравниваются, что может сильно замедлить выборку следующей команды. Но это есть в обоих фрагментах кода... Странный какой-то компилятор...

[alexus]

И это тоже странно выглядит:

Код: [Выделить]

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
... но такой код опять же в каждом фрагменте, то есть не в этом причина различий, но компилятор удивляет.

[alexus]

Видимо 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 компилятором я не знаю как получить.

[alexus]

Странный какой-то компилятор...

Этот код я получил запустив программу из под Студии поставив брэкпоинт в исходнике. Известно, что при запуске из-под Студии программа (даже релизная) работает медленнее чем при автономном запуске. Машинный код генерируемый на лету автономным JIT компилятором я не знаю как получить.

Понятно.
Меня XOR заинтересовал, как критерий оценки оптимизационных возможностей компилятора. Ну, да не важно...
Спасибо.

[Губанов Сергей Юрьевич]

Попробовал XOR. Замедлилось на те же 50% (как будто других чисел нет). Одновременно XOR с неконстантным n тоже даёт те же 50% разницы (нет кумулятивного эффекта). Чего-то там суперскалярный процессор со спекулятивным вычислением значит делает параллельно (i7 2600K).

[alexus]

Попробовал XOR. Замедлилось на те же 50% (как будто других чисел нет). Одновременно XOR с неконстантным n тоже даёт те же 50% разницы (нет кумулятивного эффекта). Чего-то там суперскалярный процессор со спекулятивным вычислением значит делает параллельно (i7 2600K).

Значит создаётся неоптимизированный код (ожидаемо)... Зря, IMHO, ассемблер на помойку отнесли... красоты совсем не осталось... раньше в радость было посмотреть, как компиляторы старались, а сейчас... эх...

[Губанов Сергей Юрьевич]

В ансэйфе писал потому, что хотел добиться примерно одинаковой скорости работы C# программы как под умным Микрософтовским рантаймом так и под туповатым Mono. Я же скорость процессоров хотел измерить. Сейчас попробовал запустить эту програмку под 32 разрядной Mono и обнаружил, что она там работает в пять с половиной раз медленнее (хотя компьютеры примерно одинаковые i7 2600K vs i7 950). То есть 64 разрядность архи важна.

[alexus]

В ансэйфе писал потому, что хотел добиться примерно одинаковой скорости работы C# программы как под умным Микрософтовским рантаймом так и под туповатым Mono. Я же скорость процессоров хотел измерить. Сейчас попробовал запустить эту програмку под 32 разрядной Mono и обнаружил, что она там работает в пять с половиной раз медленнее (хотя компьютеры примерно одинаковые i7 2600K vs i7 950). То есть 64 разрядность архи важна.

Не... в 5 раз... это видимо какая-то эмуляция работает...