Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Хотел озвучить ситуацию, с которой столкнулся и послушать людей поумнее меня на тему того - как быть?
Я пользуюсь 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