Хотел озвучить ситуацию, с которой столкнулся и послушать людей поумнее меня на тему того - как быть?
Я пользуюсь C# для написания простого процедурного кода, что-то посчитать, что-то проверить из алгоритмов. Глубоко C# не изучаю, так как мне это неинтересно совсем, пользуюсь им исключительно как молотком чтобы забить саморез - жёстко, абсолютно говнокодисто и с подрывом пятых точек некоторых кодер-наци. Но при этом я знаю, что у любого компилятора могут быть как фиксированные так и настраиваемые оптимизации - ну там переменную в регистр запихать или вместо вызова инлайн код использовать. В общем это понятно и оно есть и к C# у меня отношение как к весьма современному и технологичному продукту и тут мы подбираемся к проблеме, с которой я столкнулся.
Изучая статью я, как и привык, делал замеры времени выполнения кода, причём весьма простым и тривиальным Stopwatch. Если необходимо, то я делаю например 100 проходов и замеряю среднее время, но как правило 2-3 запусков достаточно чтобы определить порядок изменения скорости.
Вот код:
static long NotDicSearch(byte[] text, byte[] pat)
{
int s = 0;
int compares = 0, jumps = 0, m = pat.Length, n = text.Length, matches = 0, m_1 = m - 1;
byte[] rights = new byte[256];
for (int i = 0; i < 256; i++)
rights[i] = 0;
for (int i = 0; i < m; i++)
rights[pat[i]] = 1;
int[] bpos = new int[m + 1];
int[] shift = new int[m + 1];
for (int i = 0; i < m + 1; i++) shift[i] = 0;
suffix(shift, bpos, pat, m);
shifts(shift, bpos, pat, m);
Stopwatch sw = new Stopwatch();
sw.Restart();
//------------------------------------------------------------------------------
while (s <= n - m)
{
int j = m - 1;
while (j >= 0 && text[s + j] == pat[j])
j--;
compares += m - j;
if (j < 0)
{
matches++;
s += m;
}
else
{
if (rights[text[s + j]] == 1) s += shift[j + 1];
else s += j + 1;
}
jumps++;
}
//------------------------------------------------------------------------------
sw.Stop();
return sw.ElapsedMilliseconds;
}
static void suffix(int[] shift, int[] bpos, byte[] pat, int m)
{
// m is the length of pattern
int i = m, j = m + 1;
bpos[i] = j;
while (i > 0)
{
while (j <= m && pat[i - 1] != pat[j - 1])
{
if (shift[j] == 0) shift[j] = j - i;
j = bpos[j];
}
i--; j--;
bpos[i] = j;
}
}
static void shifts(int[] shift, int[] bpos, byte[] pat, int m)
{
int i, j = bpos[0];
for (i = 0; i <= m; i++)
{
if (shift[i] == 0) shift[i] = j;
if (i == j) j = bpos[j];
}
}Так я провожу вызов:
byte[] text = File.ReadAllBytes("c:\text.txt");
byte[] pat = File.ReadAllBytes("c:\pattern.txt");
long mid = 0;
int i = 0;
for (i = 0; i < 100; i++)
{
long r = NotDicSearch(text, pat);
mid = i == 0 ? r : (mid + r) / 2;
}
Console.WriteLine("NaiveStrFind: {0} ms / {1}", mid, i);Файл размером в 833Мб (выжимка слов из файла enwik9), а паттерн слово "schemata".
Ну и собственно из-за чего сыр-бор - изменение положения строки
int s = 0;на первую в процедуре (на полном листинге выше как раз в этой позиции) или на позицию перед while
int s = 0;
while (s <= n - m)меняет скорость работы основного цикла на 7,5% (объявление сразу перед while быстрее) и вопрос - почему оптимизации, такие очевидные как например итератор основного цикла в регистре ЦПУ (если это и происходит с s) зависят от положения строки инициализации переменной в процедуре? И второй очевидный вопрос - сколько таких "приколов" есть еще, чтобы уже знать и выбирать сообразно потребности?
Проверялось на:
Microsoft Visual Studio Community 2022 Версия 17.2.4
VisualStudio.17.Release/17.2.4+32602.215
Microsoft .NET Framework Версия 4.8.04161
Комментарии (15)
baldr
16.06.2022 09:15+11Добро пожаловать на StackOverflow. Спасибо что задали ваш вопрос. Было очень интересно прочитать вашу статью.
BellaLugoshi Автор
16.06.2022 09:57-21Статья, в том числе, является протестной формой тысячам хламостатей заполонивших Хабр. Ресурс превратился в выгребную яму, с чем я всех и поздравляю. Ну и чтобы не писать абы-что, я задал конкретный вопрос, на который пока не нашел ответ. SO - англоязычный ресурс и мне малоинтересен и не совсем ясно почему формат моей статьи вдруг не соответствует формату современного Хабра - я каждый день вижу кто и что сюда пишет.
baldr
16.06.2022 10:05+15В таком случае мне странно как такому постоянному посетителю нужно объяснять очевидные (на мой взгляд) вещи.
Для тех, кто не умеет писать на английском есть Хабр Q&A (бывший Тостер), есть StackOverflow на русском, и еще какие-то форумы по C#, наверное.
Когда вы разберетесь - вы можете вернуться сюда и написать статью с разбором и объяснением.
Если каждый будет тут спрашивать свои вопросы или просить написать курсовик - ну это уже скатится непонятно к чему.
Voland69
16.06.2022 10:18+4не совсем ясно почему формат моей статьи вдруг не соответствует формату современного Хабра
Потому что есть Toster, предназначенный как раз для вопросов, ответов и бурных обсуждений. Статья на Хабре предполагает некий разбор ситуации (к примеру приведите IL листинг обоих вариантов, проанализируйте, сделайте выводы, и уже будет предмет обсуждения). А пока это выглядит так "вот у меня тут что то случилось, сам не понял что, разберитесь и расскажите" - а это ИМХО совсем не формат статьи на Хабре.
DistortNeo
16.06.2022 10:21+3Автор, бросьте бяку.
Попробуйте .NET 6.0, там очень сильно оптимизировали JIT-компилятор.
AndreyDmitriev
16.06.2022 10:25+1Что помешало просто спуститься на уровень ниже и посмотреть во что оно там компиляется?
Hrodvitnir
16.06.2022 11:14Глубоко C# не изучаю, так как мне это неинтересно совсем, пользуюсь им исключительно как молотком чтобы забить саморез - жёстко, абсолютно говнокодисто и с подрывом пятых точек некоторых кодер-наци.
Так может кодер-наци вовсе не наци, если вы начали с такой вводной?
OrangeDays
16.06.2022 11:22+5Подтверждаю, проявляется для x64 и x86.
Листинг 1. s в начале фукнции.
//------------------------------------------------------------------------------ while (s <= n - m) 00007FFD973A0AFC mov eax,dword ptr [rsp+54h] 00007FFD973A0B00 mov r8d,eax 00007FFD973A0B03 sub r8d,r12d 00007FFD973A0B06 test r8d,r8d 00007FFD973A0B09 jl App.Program.NotDicSearch(Byte[], Byte[])+027Bh (07FFD973A0BFBh) 00007FFD973A0B0F lea ecx,[r12-1] { int j = m - 1; 00007FFD973A0B14 mov r9d,ecx 00007FFD973A0B17 jmp App.Program.NotDicSearch(Byte[], Byte[])+01B0h (07FFD973A0B30h) 00007FFD973A0B19 mov rax,qword ptr [rsp+40h] 00007FFD973A0B1E jmp App.Program.NotDicSearch(Byte[], Byte[])+068h (07FFD973A09E8h) 00007FFD973A0B23 mov qword ptr [rsp+40h],rax 00007FFD973A0B28 jmp App.Program.NotDicSearch(Byte[], Byte[])+094h (07FFD973A0A14h) j--; 00007FFD973A0B2D dec r9d while (j >= 0 && text[s + j] == pat[j]) 00007FFD973A0B30 test r9d,r9d 00007FFD973A0B33 jl App.Program.NotDicSearch(Byte[], Byte[])+01DEh (07FFD973A0B5Eh) 00007FFD973A0B35 lea r10d,[rbx+r9] 00007FFD973A0B39 cmp r10d,r13d 00007FFD973A0B3C jae App.Program.NotDicSearch(Byte[], Byte[])+02BEh (07FFD973A0C3Eh) 00007FFD973A0B42 movsxd r10,r10d 00007FFD973A0B45 movzx r10d,byte ptr [rsi+r10+10h] 00007FFD973A0B4B cmp r9d,r15d 00007FFD973A0B4E jae App.Program.NotDicSearch(Byte[], Byte[])+02BEh (07FFD973A0C3Eh) 00007FFD973A0B54 movsxd r11,r9d 00007FFD973A0B57 cmp r10b,byte ptr [rdi+r11+10h] 00007FFD973A0B5C je App.Program.NotDicSearch(Byte[], Byte[])+01ADh (07FFD973A0B2Dh) compares += m - j; 00007FFD973A0B5E mov r10d,r12d 00007FFD973A0B61 sub r10d,r9d 00007FFD973A0B64 add ebp,r10d if (j < 0) 00007FFD973A0B67 test r9d,r9d 00007FFD973A0B6A jge App.Program.NotDicSearch(Byte[], Byte[])+01FEh (07FFD973A0B7Eh) { matches++; 00007FFD973A0B6C mov r11d,dword ptr [rsp+50h] 00007FFD973A0B71 inc r11d 00007FFD973A0B74 mov dword ptr [rsp+50h],r11d s += m; 00007FFD973A0B79 add ebx,r12d 00007FFD973A0B7C jmp App.Program.NotDicSearch(Byte[], Byte[])+026Fh (07FFD973A0BEFh) 00007FFD973A0B7E mov qword ptr [rsp+28h],rdx } else { if (rights[text[s + j]] == 1) s += shift[j + 1]; 00007FFD973A0B83 lea r10d,[rbx+r9] 00007FFD973A0B87 cmp r10d,r13d 00007FFD973A0B8A jae App.Program.NotDicSearch(Byte[], Byte[])+02BEh (07FFD973A0C3Eh) 00007FFD973A0B90 movsxd r11,r10d 00007FFD973A0B93 movzx r11d,byte ptr [rsi+r11+10h] 00007FFD973A0B99 cmp r11d,100h 00007FFD973A0BA0 jae App.Program.NotDicSearch(Byte[], Byte[])+02BEh (07FFD973A0C3Eh) 00007FFD973A0BA6 movsxd r11,r11d 00007FFD973A0BA9 mov rdx,qword ptr [rsp+40h] 00007FFD973A0BAE cmp byte ptr [rdx+r11+10h],1 00007FFD973A0BB4 jne App.Program.NotDicSearch(Byte[], Byte[])+0261h (07FFD973A0BE1h) if (rights[text[s + j]] == 1) s += shift[j + 1]; 00007FFD973A0BB6 lea r10d,[r9+1] 00007FFD973A0BBA mov rax,qword ptr [rsp+30h] 00007FFD973A0BBF mov r9d,dword ptr [rax+8] 00007FFD973A0BC3 cmp r10d,r9d 00007FFD973A0BC6 jae App.Program.NotDicSearch(Byte[], Byte[])+02BEh (07FFD973A0C3Eh) 00007FFD973A0BC8 movsxd r9,r10d 00007FFD973A0BCB add ebx,dword ptr [rax+r9*4+10h] 00007FFD973A0BD0 mov qword ptr [rsp+30h],rax 00007FFD973A0BD5 mov qword ptr [rsp+40h],rdx 00007FFD973A0BDA mov rdx,qword ptr [rsp+28h] 00007FFD973A0BDF jmp App.Program.NotDicSearch(Byte[], Byte[])+026Fh (07FFD973A0BEFh) else s += j + 1; 00007FFD973A0BE1 lea ebx,[r10+1] 00007FFD973A0BE5 mov qword ptr [rsp+40h],rdx 00007FFD973A0BEA mov rdx,qword ptr [rsp+28h] } jumps++; 00007FFD973A0BEF inc r14d //------------------------------------------------------------------------------ while (s <= n - m) 00007FFD973A0BF2 cmp r8d,ebx 00007FFD973A0BF5 jge App.Program.NotDicSearch(Byte[], Byte[])+0194h (07FFD973A0B14h) }Листинг 2. s перед циклом:
//------------------------------------------------------------------------------ int s = 0; 00007FFD97390AF4 xor eax,eax while (s <= n - m) 00007FFD97390AF6 mov r8d,r13d 00007FFD97390AF9 sub r8d,r15d 00007FFD97390AFC test r8d,r8d 00007FFD97390AFF jl App.Program.NotDicSearch(Byte[], Byte[])+0260h (07FFD97390BE0h) 00007FFD97390B05 lea ecx,[r15-1] { int j = m - 1; 00007FFD97390B09 mov r9d,ecx 00007FFD97390B0C jmp App.Program.NotDicSearch(Byte[], Byte[])+01A5h (07FFD97390B25h) 00007FFD97390B0E mov rax,qword ptr [rsp+48h] 00007FFD97390B13 jmp App.Program.NotDicSearch(Byte[], Byte[])+061h (07FFD973909E1h) 00007FFD97390B18 mov qword ptr [rsp+48h],rax 00007FFD97390B1D jmp App.Program.NotDicSearch(Byte[], Byte[])+08Dh (07FFD97390A0Dh) j--; 00007FFD97390B22 dec r9d while (j >= 0 && text[s + j] == pat[j]) 00007FFD97390B25 test r9d,r9d 00007FFD97390B28 jl App.Program.NotDicSearch(Byte[], Byte[])+01D3h (07FFD97390B53h) 00007FFD97390B2A lea r10d,[rax+r9] 00007FFD97390B2E cmp r10d,r12d 00007FFD97390B31 jae App.Program.NotDicSearch(Byte[], Byte[])+02A3h (07FFD97390C23h) 00007FFD97390B37 movsxd r10,r10d 00007FFD97390B3A movzx r10d,byte ptr [rsi+r10+10h] 00007FFD97390B40 cmp r9d,r14d 00007FFD97390B43 jae App.Program.NotDicSearch(Byte[], Byte[])+02A3h (07FFD97390C23h) 00007FFD97390B49 movsxd r11,r9d 00007FFD97390B4C cmp r10b,byte ptr [rdi+r11+10h] 00007FFD97390B51 je App.Program.NotDicSearch(Byte[], Byte[])+01A2h (07FFD97390B22h) compares += m - j; 00007FFD97390B53 mov r10d,r15d 00007FFD97390B56 sub r10d,r9d 00007FFD97390B59 add ebx,r10d if (j < 0) 00007FFD97390B5C test r9d,r9d 00007FFD97390B5F jge App.Program.NotDicSearch(Byte[], Byte[])+01F3h (07FFD97390B73h) { matches++; 00007FFD97390B61 mov r13d,dword ptr [rsp+54h] 00007FFD97390B66 inc r13d 00007FFD97390B69 mov dword ptr [rsp+54h],r13d s += m; 00007FFD97390B6E add eax,r15d 00007FFD97390B71 jmp App.Program.NotDicSearch(Byte[], Byte[])+0255h (07FFD97390BD5h) } else { if (rights[text[s + j]] == 1) s += shift[j + 1]; 00007FFD97390B73 lea r10d,[rax+r9] 00007FFD97390B77 cmp r10d,r12d 00007FFD97390B7A jae App.Program.NotDicSearch(Byte[], Byte[])+02A3h (07FFD97390C23h) 00007FFD97390B80 movsxd r11,r10d 00007FFD97390B83 movzx r11d,byte ptr [rsi+r11+10h] 00007FFD97390B89 cmp r11d,100h 00007FFD97390B90 jae App.Program.NotDicSearch(Byte[], Byte[])+02A3h (07FFD97390C23h) 00007FFD97390B96 movsxd r11,r11d 00007FFD97390B99 mov r13,qword ptr [rsp+48h] 00007FFD97390B9E cmp byte ptr [r13+r11+10h],1 00007FFD97390BA4 jne App.Program.NotDicSearch(Byte[], Byte[])+024Ch (07FFD97390BCCh) if (rights[text[s + j]] == 1) s += shift[j + 1]; 00007FFD97390BA6 lea r10d,[r9+1] 00007FFD97390BAA mov r9,qword ptr [rsp+38h] 00007FFD97390BAF mov r11d,dword ptr [r9+8] 00007FFD97390BB3 cmp r10d,r11d 00007FFD97390BB6 jae App.Program.NotDicSearch(Byte[], Byte[])+02A3h (07FFD97390C23h) 00007FFD97390BB8 movsxd r10,r10d 00007FFD97390BBB add eax,dword ptr [r9+r10*4+10h] 00007FFD97390BC0 mov qword ptr [rsp+38h],r9 00007FFD97390BC5 mov qword ptr [rsp+48h],r13 00007FFD97390BCA jmp App.Program.NotDicSearch(Byte[], Byte[])+0255h (07FFD97390BD5h) else s += j + 1; 00007FFD97390BCC lea eax,[r10+1] 00007FFD97390BD0 mov qword ptr [rsp+48h],r13 } jumps++; 00007FFD97390BD5 inc ebp while (s <= n - m) 00007FFD97390BD7 cmp r8d,eax 00007FFD97390BDA jge App.Program.NotDicSearch(Byte[], Byte[])+0189h (07FFD97390B09h) }В листинге 1 дополнительные инструкции в сроках 47, 73, 78.
P.S. в х86 также присутсвует "лишняя" инструкция только в одном в месте, примерно соответсвующем строке 73 листинга 1.
Voland69
16.06.2022 11:48Судя по дополнительным инструкциям в первом варианте происходит перемещение значения регистра в адрес памяти и обратно, что видимо и вызывает замедление. Предположу, что последующие объявления int переменных "вытеснили" s из доступных регистров в первом варианте.
Sornyak_Rstt
17.06.2022 08:24Скорее всего дело в месте данной переменной в стеке; тк int это значимый тип данных, и значение хранится в стеке, и если я не ошибаюсь, то данные попадают в стек по принципу LIFO (последним вошел - первым вышел), соответственно прочие значимые типы данных находятся поверх s, что «затрудняет» повторное использование “s”. (Возможно, я ошибаюсь)
BellaLugoshi Автор
17.06.2022 11:17-3Поскольку доброта и понимание на этом ресурсе на первом месте - я не могу писать чаще раза в сутки. Многим, накидавшим мне в карму советую перечитать Хабраэтикет.
Поэтому ответы скомпонованы в один блок:
Для тех, кто не умеет писать на английском есть Хабр Q&A (бывший Тостер), есть StackOverflow на русском
Я умею писать на английском. Хабр Q/A и SO на русском - это аудитория в 20 просмотров, а так как тема весьма важная и в каком-то смысле титаническая, то о ней не просто трубить нужно, а можно сказать с мигалками и сиренами. Тут я получил охват в 2700 человек и я думаю он будет еще больше.
Когда вы разберетесь - вы можете вернуться сюда и написать статью с разбором и объяснением.
Разберусь в чём? Для меня ошибка в работе C# очевидна, я её озвучил, для меня неочевидны пути решения этой проблемы (как часто бывает даже на таком уровне продуктов - решение никто не будет делать, как в сказке - и так сойдёт).
Статью с разбором чего? Весь материал - уже законченная информация, я не могу за майкрософт решить делать что-то с C# или не делать.
Если каждый будет тут спрашивать свои вопросы или просить написать курсовик - ну это уже скатится непонятно к чему.
Ну вообще-то это адская фигня, а не вопрос для курсовика. Если вас устраивает такой уровень работы компилятора/транслятора, то вам и флаг в руки, а я проблему считаю критически важной.
предназначенный как раз для вопросов, ответов и бурных обсуждений.
Я вижу достаточно статей с подобным содержанием которые одобрительно встречают читатели, а значит не в формате дело.
Статья на Хабре предполагает некий разбор ситуации (к примеру приведите IL листинг обоих вариантов, проанализируйте, сделайте выводы, и уже будет предмет обсуждения)
А я могу прочитать в каких-то правилах эти рекомендации, чтобы понимать - это действительно формат ресурса или ваша выдумка? (я знаю что это ваша выдумка, но всё же)
А пока это выглядит так "вот у меня тут что то случилось, сам не понял что, разберитесь и расскажите" - а это ИМХО совсем не формат статьи на Хабре.
Я обозначил проблему в крупном ЯП, о которой не смог найти ничего. Понял я проблему ровно настолько, чтобы её распознать и суметь описать.
Могу ошибаться, но похоже на то, что S вы закопали глубоко в стек.
Я ничего не могу закопать в стек.
Автор, бросьте бяку.Попробуйте .NET 6.0, там очень сильно оптимизировали JIT-компилятор.
Уже тестировал сильно ранее для другого кода, но специально для вас сделал это еще раз - производительность кода NET 6 на 25% медленнее для наивного алгоритма и на 13% медленнее для КМП реализации (на картинке вывод результата для КМП второй строкой тоже надписан как NaiveStrFind, не запутайтесь)
Что помешало просто спуститься на уровень ниже и посмотреть во что оно там компиляется?
Ничего, просто это не имеет практической пользы, так как вопрос совсем в другом.
Так может кодер-наци вовсе не наци, если вы начали с такой вводной?
Когда человек не вопрос читает, а ковыряется в том как например именованы переменные, то это кодер-наци. Я отклонил несколько таких комментариев, но вы же понимаете что даже если я об этом написал - ничего не помешает им написать всякой ерунды.
Подтверждаю, проявляется для x64 и x86.
Спасибо за подтверждение, но сам листинг не имеет смысла, так как проблема ясна и без него, вопрос как раз в том - как эту проблему решить.
Судя по дополнительным инструкциям в первом варианте происходит перемещение значения регистра в адрес памяти и обратно, что видимо и вызывает замедление. Предположу, что последующие объявления int переменных "вытеснили" s из доступных регистров в первом варианте.
Скорее всего дело в месте данной переменной в стеке; тк int это значимый тип данных, и значение хранится в стеке, и если я не ошибаюсь, то данные попадают в стек по принципу LIFO (последним вошел - первым вышел), соответственно прочие значимые типы данных находятся поверх s, что «затрудняет» повторное использование “s”. (Возможно, я ошибаюсь)
Это всё здорово, но никак нас не приближает к ответу на заданный вопрос.
baldr
17.06.2022 11:49+1Уже не первый раз я вижу как ваша убежденность в своей правоте натыкается на бездушную стену непонимания среди остальных посетителей.
Я вижу достаточно статей с подобным содержанием которые одобрительно встречают читатели, а значит не в формате дело.
Уже, казалось бы, статья в глубоком минусе и -16 к карме только за этот пост должны что-то вам подсказать, но вам важно (важно же?) получить ответ на самый важный в мире вопрос и поэтому надо его опубликовать в виде статьи. По-моему не так уж много людей считают это таким "титаническим".
Вы хотите чтобы за вас нашли решение бесплатно и объяснили вам - все-таки вам на SO.
Вы хотите чтобы "критически важную" проблему решили - вам в багтрекер Microsoft.
BellaLugoshi Автор
18.06.2022 12:07Уже не первый раз я вижу как ваша убежденность в своей правоте натыкается на бездушную стену непонимания среди остальных посетителей
Это привилегия некоторых хабов, например предпоследнюю статью когда убрал с C# хаба она ушла в плюс. Токсичное сообщество.
По-моему не так уж много людей считают это таким "титаническим"
25% производительности в трубу а всем пофигу - и почему я не удивлён.
Вы хотите чтобы за вас нашли решение бесплатно и объяснили вам - все-таки вам на SO
Если вы заметили, то решение я уже нашёл, вопросы касаются немного других вещей.
Вы хотите чтобы "критически важную" проблему решили - вам в багтрекер Microsoft
Вот сегодня вышло несколько статей, которые, если следовать вашей логике, нужно отправлять или в личные блоги или в твиттеры или в маны, но почему-то они вышли в виде статей и собирают плюсики, правда на других хабах. Значит буду избегать токсичную аудиторию и проблемы не будет.
Не знаю на счёт вашего случая, но перед измерением времени работы лучше принудительно вызывать сборщик мусора
Нет, сборщик мусора никак не влияет на ситуацию.
Sandman_dn
17.06.2022 17:12Не знаю на счёт вашего случая, но перед измерением времени работы лучше принудительно вызывать сборщик мусора:
GC.Collect(); GC.WaitForPendingFinalizers();
OrangeDays
Подтверждаю, проявляется для x64 и x86.
Листинг 1. s в начале фукнции.
Листинг 2. s перед циклом:
В листинге 1 дополнительные инструкции в сроках 47, 73, 78.
P.S. в х86 также присутсвует "лишняя" инструкция только в одном в месте, примерно соответсвующем строке 73 листинга 1.