Скоростной бинарный поиск

[POP]

Кто как ищет бинарные данные в памяти?

Допустим есть условие: в 300mb памяти найти с десяток разных значений.

Я делаю так: тупо для каждого значения, которое нужно найти, цикл побайтный с нуля и до конца блока памяти, и с каждого адреса делаю сверку функцией CompareMem. То есть для десяти значений нужно 10 раз эти 300mb побайтно пробежать, что влечет за собой добротный такой зависончик секунд на 20 на мощном компе. Страшно представить, что будет на обычных офиcных PC.

[--Ins--]

Смотря что и где искать. В общем случае рецепта нет. Но в частных возможно составления по данным некоторого кеша и поиска уже в нем

[Pavia]

POP
Бинарный поиск это поиск дехотомией. Пару микросекунд.

Цитата POP @ 11.06.12, 10:33

То есть для десяти значений нужно 10 раз эти 300mb побайтно пробежать

Пробегайте один раз.

Цитата POP @ 11.06.12, 10:33

что влечет за собой добротный такой зависончик секунд на 20 на

А это у вас ошибка в коде.

[POP]

Pavia

Цитата Pavia @ 11.06.12, 11:43

Пробегайте один раз.

Дык, от перемены мест умножаемых результат не меняется. Какая разница, 10 раз пробежать сверяя каждый байт с одним значением или пробежать один раз, но каждый байт сверять 10 раз? Разницы никакой.

Цитата Pavia @ 11.06.12, 11:43

А это у вас ошибка в коде.

Дело не в Application.ProcessMessages, а в затрачиваемом времени. Все равно долго ждать.

Цитата Pavia @ 11.06.12, 11:43

Бинарный поиск это поиск дехотомией. Пару микросекунд.

Это вы о чем?

[MBo]

>Это вы о чем?
О том, что название темы вводит в заблуждение. Бинарный (двоичный) поиск - известный алгоритм поиска на сортированных данных, к данной задаче отношения не имеет.

Добавлено 11.06.12, 12:40
А по теме - какого типа данные нужно искать?

[POP]

MBo

А я имею ввиду от слова "бинари", то есть обычный блок памяти, байты, в котором нужно искать любую последовательность байт.

[MBo]

Если нужно искать последовательности байт, то нужно обратить внимание на алгоритмы поиска в строках - подыскать такой, который позволяет искать сразу много образцов в тексте - например, Ахо-Корасик или Рабин-Карп это умеют.

Сообщение отредактировано: MBo - 11.06.12, 13:35

[Pavia]

POP

Цитата POP @ 11.06.12, 12:34

Дык, от перемены мест умножаемых результат не меняется.

Это ты зря сказал. Это в математике не меняется. А в программирование ещё как. Но сейчас не об этом.

Цитата POP @ 11.06.12, 12:34

Какая разница, 10 раз пробежать сверяя каждый байт с одним значением или пробежать один раз, но каждый байт сверять 10 раз?

В первом случае кэш не оптимально используется.

Цитата POP @ 11.06.12, 12:34

А это у вас ошибка в коде.
Дело не в Application.ProcessMessages, а в затрачиваемом времени. Все равно долго ждать.

У меня поиск подстроки в строке выдает на одной машине 250Мбайт/с на другой 500МБайт/с
Т.е 300 мб за 10 проходов должен отрабатывать 6-12, а у вас в 2 раза больше.

Цитата POP @ 11.06.12, 13:10

А я имею ввиду от слова "бинари", то есть обычный блок памяти, байты, в котором нужно искать любую последовательность байт.

Наконец то задачу услышали. Это называется поиск подстрок в строке.

[--Ins--]

Еще раз отмечу: если задача позволяет, то самый лучший выигрыш производительности даст построение некоторого промежуточного индекса или кеша и поиск уже в нем. Так например работают многие поисковые системы в интернете - поиск ведется не в страницах текста, а сначала из содержимого страниц составляется индексная база, в которой данные упорядочены удобным для поиска образом, а потом поиск ведется уже в индексной базе. Такой подход оправдан, если операция поиска осуществляется значительно чаще, чем изменение данных, в которых ищем

Сообщение отредактировано: --Ins-- - 11.06.12, 13:51

[leo]

Цитата Pavia @ 11.06.12, 13:36

В первом случае кэш не оптимально используется

В общем случае это, конечно, так, но при тупом побайтовом сравнении разницы практически может и не быть, т.к. скорость чтения современной памяти в пересчете к частоте процессора составляет не менее 1 байта за такт, а для тупой побайтовой проверки без разворота цикла и прочих ухищрений требуется не менее 2-3 тактов на 1 байт, а с учетом условных переходов при "ложном обнаружении" и того больше. Поэтому чтобы проявился эффект от кэширования, нужно еще и саму скорость сравнений повысить, например, использовать известную фишку с поиском нуля в 4-байтных словах (используемую при поиске длины строки в strlen)
Ну или если речь идет о поиске не слишком коротких строк, то можно использовать алгоритмы быстрого поиска а ля Бойер-Мур, но только не по всему файлу за раз, а блоками размером с кэш первого уровня

Сообщение отредактировано: leo - 11.06.12, 14:39

[Pavia]

leo
И вообще я тему поиска подстроки очень хорошо проработал.

Частота памяти RAM около 100Мгц с этой частотой к неё идут запросы. Уже очень давно и практически не растёт. Растёт частота отдачи данных. Но она практически неважна. Так как в первом случае у тебя будет 10*N запросов. А во втором N запросов.

Эффект кэша будет заметен при любом раскладе. Что-бы его не заметить надо очень сильно постараться.

Цитата

т.к. скорость чтения современной памяти в пересчете к частоте процессора составляет не менее 1 байта за такт

Чтение из кэша первого уровня составляет 3 такта. Читать мы можем по 1,2,4,8 байт. Заставить компилятор использовать оптимальную конструкцию чтения не просто. Тут только ассемблер поможет, но на переходах 2 такта потратите. За такт 0.5 байта не больше. Так что больше 1000-1500 МБайт/с не получить.

Цитата

например, использовать известную фишку с поиском нуля

Эта фишка не работает если несколько разных байт. Да и другие тоже плохо работают. Я нашел только две фишки которые работают.
Первая, вылизанная программа. Когда мы читаем из кэша 4 байта в регистр и далее из регистра выбираем по байту и использовать этот байт для поиска в таблице. Таблица это реализация автомата. Но проблема построения таблицы чтобы она хорошо помещалась в кэш вопрос открытый.


Вторая фишка сравнивать не байт, а два байта за раз. В среднем хорошо работает. Правда если надо найти несколько подстрок, то быстрее будет автомат.

[POP]

Pavia

Цитата Pavia @ 11.06.12, 13:36

У меня поиск подстроки в строке выдает на одной машине 250Мбайт/с на другой 500МБайт/с
Т.е 300 мб за 10 проходов должен отрабатывать 6-12, а у вас в 2 раза больше.

Вообщем сделал замеры:

Файл 277mb, загружен весь в память, замеры производил на третью попытку (чтобы в кеше все было), 22 параметра искал (в среднем длина каждого 5 байт), проц AMD 4x 955 3,2 ГГц. = 49 секунд.

Причем в каждом из 22-x циклов, каждую 1024 итерацию я делаю ProcessMessages, дабы форма не зависала. Никаких ASM вставок или подобных оптимизаций нет конечно.

Сделайте у себя замеры тоже, если материал под рукой.

[Pavia]

Цитата POP @ 11.06.12, 15:44

каждую 1024 итерацию я делаю ProcessMessages

Надо через 1 миллионов, а лучше через 10 миллионов.

t=15,21 с; speed=455,00 МБайт/с C2D 2.2ГГц И дело тут не в процессоре, а в частоте памяти.

procedure TForm1.Button1Click(Sender: TObject);
Var
 s:String;
 t1,t2:Integer;
 sub:array [0..21] of String;
 I,J:Integer;
begin
SetLength(s,300*1024*1024);
for i:=1 to 300*1024*1024 do
 s[i]:=Char(Random(255));
 
for i:=0 to Length(sub)-1 do
 begin
 SetLength(Sub[i],5);
 for j:=1 to 5 do
  begin
  sub[i][j]:=Char(Random(255));
  end;
 end;
t1:=GetTickCount;
for i:=0 to Length(sub)-1 do
 Memo1.Lines.Add(IntToStr(Pos(sub[i],s)));
t2:=GetTickCount;
Memo1.Lines.Add('******');
Memo1.Lines.Add(Format('t=%f с; speed=%f МБайт/с',[(t2-t1)/1000,Length(sub)*(Length(s)/1000)/(t2-t1)]));
end;

[POP]

Pavia

У меня в таком варианте выдает: t=4,27 с; speed=1622,27 МБайт/с

а вот если переделать цикл под CompareMem вот так:

t1:=GetTickCount;
for i:=0 to Length(sub)-1 do
begin
 for j:= 1 to Length(s)-5 do
 begin
  if CompareMem(@s[j], @sub[i], 5) then
   Beep();
 end;
end;
t2:=GetTickCount;

То выдает близкий к моему результат:

t=55,16 с; speed=125,47 МБайт/с


Может функцию Pos можно как-то под бинарный (binary) поиск приспособить, почему она такая быстрая?

[Pavia]

POP
Вам лучше сделать алгоритм Ахо-Корасик.

[POP]

Цитата Pavia @ 11.06.12, 17:15

Вам лучше сделать алгоритм Ахо-Корасик.

А зачем изобретать велосипед, если Pos работает в 10 раз быстрее CompareMem, может из нее алгоритм позаимствовать?

Добавлено 11.06.12, 17:24
Точно!

Фунция Pos работает так: cначала ищется первый символ, а потом с позиции этого символа по длину субстроки, сравниваются остальные.

Надо переделать алго.

[leo]

Pavia
Удивительные вещи говоришь. С одной стороны, реальную скорость чтения памяти занижаешь, приводя ничего не значащие "100МГц" и необоснованно списывая как "практически неважную" скорость отдачи данных, хотя по всем тестам на современных компах реальная скорость чтения памяти большими блоками, по величине Мб/с как правило превышает частоту CPU в МГц. А с другой стороны и скорость кэша занижаешь, приводя некие "3 такта", хотя на самом деле это латентность единичного доступа, а в циклах рулит не латентность, а проп.способность, которая составляет 1 или даже 0.5 такта (2 чтения за 1 такт).
Может ты тему поиска подстроки и "хорошо проработал", но мы тоже не лыком шиты, и на васме было предостаточно задачек по оптимизации побайтового поиска с конретными цифрами, из которых видно, что на примитивных бесхитростных алгосах тормозит именно проц, и только при различных ухищрениях\векторизациях наступает упор по скорости чтения памяти.

Цитата Pavia @ 11.06.12, 15:42

Эта фишка не работает если несколько разных байт

Причем тут один или несколько. Я говорю с точки зрения использования кэша. Пока скорость самой обработки не превышает скорости чтения из ОЗУ (и тем более из кэша), то переход к блочной обработке данных мало, что даст (грубо говоря за время обработки данные по любому успевают подкачиваться из ОЗУ, поэтому особо не важно находятся ли они в кэше или в ОЗУ). А если проверять одновременно не одну строку, а все в одном цикле (на основе автомата или еще чего), то и подавно не имеет смыла говорить о блочности обработки.
Поэтому нужно различать 2 подхода: либо 1) мы пытаемся все впихнуть в один проход и строим какой-то автомат, который в итоге должен обеспечить более высокую скорость, чем отдельные сравнения, либо 2) пытаемся увеличить скорость поиска одной строки настолько, чтобы она была заметно выше скорости чтения ОЗУ, и тогда юзаем блочную обработку - первая строка обрабатываетяс "медленно" при чтении из ОЗУ, а последующие "быстро" из кэша.

[POP]

Pavia

Ура!

Резко сократил время поиска добавив всего одну строку:

t1:=GetTickCount;
for i:=0 to Length(sub)-1 do
begin
 for j:= 1 to Length(s)-5 do
 begin
  if s[j] = sub[i][1] then
   if CompareMem(@s[j], @sub[i], 5) then
    Beep();
 end;
end;
t2:=GetTickCount;

То есть теперь CompareMem вызывается только если первый байт сходится. Время такое:

t=22,48 с; speed=307,80 МБайт/с


PS.
Наверное придется вообще от CompareMem отказаться, самому делать.

Сообщение отредактировано: POP - 11.06.12, 17:37

[leo]

Цитата POP @ 11.06.12, 17:17

А зачем изобретать велосипед, если Pos работает в 10 раз быстрее CompareMem, может из нее алгоритм позаимствовать?

А ты значит, с ходу CompareMem запускал, вместо того чтобы сначала хотя бы 1-й символ "ручками" сравнить?!
PS: Ага, уже "исправился" - молодец!

PS: Не знаю, как на "современных" дельфях, а в D7 и ранее Pos реализована на команде процессора rep scasb, которая отличается простотой реализации, но отнюдь не скоростью, и согласно всем мануалам на обычных циклах (лучше ес-но развернутых) можно получить лучшие результаты

Сообщение отредактировано: leo - 11.06.12, 17:39

[Pavia]

leo
Нука разверни мне цикл. А я посмотрю.

[leo]

Цитата Pavia @ 11.06.12, 17:40

Нука разверни мне цикл. А я посмотрю

Ты имеешь в виду на паскале (т.к. с асмом то проблем нет)?
Сейчас не могу - нужно срочно переместиться "во времени и пространстве"

[POP]

Цитата leo @ 11.06.12, 17:38

А ты значит, с ходу CompareMem запускал, вместо того чтобы сначала хотя бы 1-й символ "ручками" сравнить?!

Исходники этой функции на асме, тут я пас. Но меня возмущает другое: почему эта функция САМА первый байт не сверяет, почему я заместо нее сам вручную должен это делать? Она что, сразу всю байты Length пытается сравнить, невзирая на то, что предыдущие не сошлись?

22 секунды - это все еще очень далеко до ~5 сек функции Pos.

Сообщение отредактировано: POP - 11.06.12, 17:51

[Pavia]

Цитата leo @ 11.06.12, 17:47

Ты имеешь в виду на паскале (т.к. с асмом то проблем нет)?

Основной цикл из POS, где идет поиск одного символа. На асаме если вам так проще. Так что бы прирост был.

Добавлено 11.06.12, 17:53

Цитата POP @ 11.06.12, 17:50

Исходники этой функции на асме, тут я пас. Но меня возмущает другое: почему эта функция САМА первый байт не сверяет, почему я заместо нее сам вручную должен это делать? Она что, сразу всю байты Length пытается сравнить, невзирая на то, что предыдущие не сошлись?

Просто CompareMem вызывает Length что бы узнать длину строк и делает ещё несколько проверок на nil. Это и съедает скорость.

[leo]

Цитата POP @ 11.06.12, 17:50

Но меня возмущает другое: почему эта функция САМА первый байт не сверяет, почему я заместо нее сам вручную должен это делать?

Цитата Pavia @ 11.06.12, 17:51

Просто CompareMem вызывает Length что бы узнать длину строк и делает ещё несколько проверок на nil. Это и съедает скорость.

Просто: 1) сам вызов функции (команды call+ret) съедает намного больше времени чем непосредственное сравнение двух байт, 2) конвенция о вызовах функций заставляет делать дополнительные (в данном случае лишние) действия - вызывающий код должен позаботиться о сохранении самых популярных регистров eax,ecx,edx и впихнуть в них параметры функции, ну и 3) сама функция прежде чем что-то делать должна произвести элементарные проверки валидности переданных ей параметров

Сообщение отредактировано: leo - 11.06.12, 18:58

[leo]

Цитата Pavia @ 11.06.12, 17:51

Основной цикл из POS, где идет поиск одного символа. На асаме если вам так проще. Так что бы прирост был

По сравнению с Pos даже простой разворот типа:

while (p[0] <> c) and (p[1] <> c) and (p[2] <> c) and (p[3] <> c) and (i <= L) do
begin
  inc(p,4);
  inc(i,4);
end;

дает выигрыш по скорости.
Но трик с обработкой двордов лучше тем, что можно проверять совпадение сразу двух байт и таким образом уменьшить вероятность ложных захватом и связанных с эти потерь на условные переходы и т.п.
Модифицированный код #13 от Pavia:

procedure TForm1.Button1Click(Sender: TObject);
{$DEFINE UseDwTrick} //!!! <-- закомментировать для проверки Pos
Var
  s:AnsiString;
  t1,t2:Integer;
  sub:array [0..21] of AnsiString;
  I,J,L:integer;
{$IFDEF UseDwTrick}
  ss:AnsiString;
  Ls,k:Integer;
  dw1,dw2,mask1,mask2:longword;
  p,pp:pAnsiChar;
  c:AnsiChar;
{$ENDIF}
begin
  L:=300*1024*1024;
  SetLength(s,L);
  for i:=1 to L do
    s[i]:=Char(Random(255));
 
  for i:=0 to Length(sub)-1 do
  begin
    SetLength(Sub[i],5);
    for j:=1 to 5 do
     sub[i][j]:=Char(Random(255));
  end;
  //(+) для контроля копируем строку sub[0] в конец s
  Move(sub[0][1],s[L-10],Length(sub[0]));
 
  t1:=GetTickCount;
  for i:=0 to Length(sub)-1 do
  begin
{$IFDEF UseDwTrick} //поиск совпадений двух симолов при чтении 4-байт
    ss:=sub[i];
    mask1:=Ord(ss[1]); //1-й искомый символ
    mask1:=mask1 + mask1 shl 8 + mask1 shl 16 + mask1 shl 24; //маска для xor
    c:=ss[2];          //2-й искомый символ
    mask2:=Ord(c);
    mask2:=mask2 + mask2 shl 8 + mask2 shl 16 + mask2 shl 24; //маска для xor
    Ls:=Length(sub[0]);
    L:=Length(s)-Ls+1; //ограничиваем длину поиска
    p:=pointer(s);
    j:=0;
    repeat
      //1) поиск совпадения первых двух символов
      repeat
        dw1:=pLongword(p)^;          //читаем дворд
        //маска с 1-м симв. + сдвинутая маска со 2-м
        dw1:=(dw1 xor mask1) or ((dw1 xor mask2) shr 8);
        inc(p,4);
        inc(j,4);
        //нуль в одном из трех первых байтах dw1 означают совпадение двух символов
        //а нуль в старшем байте - совпадение только первого символа
        //используем изв.прием для проверки наличия хотя бы одного 0-байта в дворде
        dw2:=((dw1+$7EFEFEFF) xor not dw1) and $81010100;
      until (dw2 <> 0) or (j > L);
      //если не нашли и конец строки
      if dw2 = 0 then
      begin
        j:=0;   //строка не найдена
        Break;
      end;
      //2) проверка совпадения строки на одной из 4-х позиций
      if p[0] <> c then //добавляем проверку 2-го символа для старшего байта
        dw1:=dw1 or $F000000;
      pp:=p-5;
      repeat //проверяем совпадения
        k:=3; //проверка с 3-го символа
        if dw1 and $FF = 0 then //если есть совпадение первых 2-х
          while (k <= Ls) and (ss[k] = pp[k]) do
            inc(k);
        dw1:=dw1 shr 8;
        inc(pp);
      until (pp > p-2) or (k > Ls);
      //3) если найдено совпадение
      if k > Ls then
      begin
        j:=pp-pAnsiChar(s)+1; //позиция подстроки в s
        Break;
      end;
    until false; //j > L;
    Memo1.Lines.Add(IntToStr(j));
{$ELSE}
    Memo1.Lines.Add(IntToStr(Pos(sub[i],s)));
{$ENDIF}
  end;
 
  t2:=GetTickCount;
  Memo1.Lines.Add('******');
  Memo1.Lines.Add(Format('t=%.3f с; speed=%f МБайт/с',[(t2-t1)/1000,Length(sub)*(Length(s)/1000)/(t2-t1)]));
end;

Выигрыш, конечно, существенно зависит от проца, например, на древнем PentiumD получается почти в 2 раза (90%), а на современном i5 только 35%. С другой стороны попытка использовать блочную обработку для задействования кэша приводит к мизерному выигрышу в несколько процентов, что говорит о том, что все же основным тормозом по прежнему остается именно CPU, а не скорость подгрузки данных из памяти

[POP]

Люди, не могу приблизится по скорости к функции Pos.

Предполагая, что в ней используется обычный brute force, сделал свою функцию но приспособленную для работы с массивом байт, а не строк. Все исходники и примеры в интернете, все сделано для строк.
Но почему-то скорость чудовищно низкая:

function TForm1.MyPosBruteForce(P1, P2: Pointer; BufLen, PatternLen: cardinal): cardinal;
var
i, j: cardinal;
 
begin
 Result:= 0;
 if PatternLen > BufLen then Exit;
 
 for i:= 0 to (BufLen-PatternLen) do
  for j:= 0 to PatternLen-1 do
   if PByte(DWORD(P2)+j)^ <> PByte(DWORD(P1)+i+j)^ then Break
   else
    if j = BufLen then
    begin
     Result:= i;
     Exit;
    end;
end;
 
 
 
 
procedure TForm1.Button1Click(Sender: TObject);
var
s:String;
t1,t2:Integer;
sub:array [0..21] of String;
I,J:Integer;
 
begin
SetLength(s,300*1024*1024);
for i:=1 to 300*1024*1024 do
 s[i]:=Char(Random(255));
 
for i:=0 to Length(sub)-1 do
begin
SetLength(Sub[i],5);
for j:=1 to 5 do
 begin
  sub[i][j]:=Char(Random(255));
 end;
end;
 
t1:=GetTickCount;
for i:=0 to Length(sub)-1 do
begin
 //if Pos(sub[i],s) <> 0 then Beep();
 if MyPosBruteForce(@s[1], @sub[i][1], Length(s), 5) <> 0 then Beep();
end;
t2:=GetTickCount;
RichEdit1.Lines.Add('******');
RichEdit1.Lines.Add(Format('t=%f с; speed=%f МБайт/с',[(t2-t1)/1000,Length(sub)*(Length(s)/1000)/(t2-t1)]));
end;

Вот объясните мне, почему, если закоментировать вызов моей функции и раскоментировать Pos, то скорость возрастает сразу в 6 раз? Вызовов каких-то функции замедляющих работу нет.

Сообщение отредактировано: POP - 12.06.12, 11:46

[leo]

Цитата POP @ 12.06.12, 11:44

сделал свою функцию но приспособленную для работы с массивом байт, а не строк

AnsiString и Pos и раньше можно было с равным успехом использовать и для хранения\поиска байтов, а в последних версиях дельфей для этих целей появилась RawString.

var
  s,sub:AnsiString;
  i:integer;
begin
  SetString(s,P1,BufLen); //!!! на копию может памяти не хватить, поэтому лучше сразу грузить в s
  SetString(sub,P2,PatternLen);
  i:=Pos(sub,s);
end;

Добавлено 12.06.12, 12:25

Цитата POP @ 12.06.12, 11:44

Но почему-то скорость чудовищно низкая:

Потому, что опять тупишь и проверяешь всю подстроку, а нужны раздельные циклы поиска первого символа и только если есть совпадение, то второй цикл проверки остатков подстроки. Первый цикл должен быть максимально быстрым, поэтому никакие излишества в нем не допустимы

Добавлено 12.06.12, 13:03
Вот пример реализации через pAnsiChar, можно заменить на pByte, если он допускает индексаю, или объявить pByteArray большого размера

function MyPos(P1,P2:pointer;BufLen,PatternLen:integer):integer;
var
  p,pp:pAnsiChar;
  c:AnsiChar;
  i,j:integer;
begin
  BufLen:=BufLen-PatternLen+1;
  p:=P1;
  pp:=P2;
  c:=pp[0];
  i:=0;
  while i < BufLen do //общий внешний цикл
  begin
    //"быстрый" цикл поиска первого символа
    while (i < BufLen) and (p[i] <> c) do
      inc(i);
    if p[i] <> c then //достигли конца строки
      Break;
    j:=1; //проверяем остатки строки
    while (j < PatternLen) and (pp[j] = p[i+j]) do
      inc(j);
    if j >= PatternLen then //если все совпало, то нашли
    begin
      Result:=i+1; //+1 если индексация с 1 как в Pos
      Exit;
    end;
    inc(i);
  end;
  Result:=0;
end;

[POP]

Цитата leo @ 12.06.12, 12:05

Потому, что опять тупишь и проверяешь всю подстроку, а нужны раздельные циклы поиска первого символа и только если есть совпадение, то второй цикл проверки остатков подстроки.

Ну и где ты в моем исходнике это все увидел? Как раз два цикла, сверяется только первый байт (указатель PByte), а не вся подстрока. Код был взять из bruteforce примера - http://www.rsdn.ru/article/alg/textsearch.xml и адаптирован под работу с указателями.

[leo]

Цитата POP @ 12.06.12, 15:12

Ну и где ты в моем исходнике это все увидел? Как раз два цикла, сверяется только первый байт

Я увидел, а ты - нет. Я тебе толкую о НЕЗАВИСИМЫХ циклах, а у тебя они ВЛОЖЕННЫЕ. Поэтому у меня скорость выше или по кр.мере не ниже чем Pos, а у тебя "почему-то скорость чудовищно низкая" и если "раскоментировать Pos, скорость возрастает сразу в 6 раз". Видимо ты умнее, или "не от мира сего", в том смысле, что видишь то, что другие не видят, и наоборот

Добавлено 12.06.12, 16:15
Ладно, если отбросить эмоции, то могу предложить пару вариантов.
Первый экпериментальный (может сам поймешь, что к чему): вынеси проверку if PByte(... за пределы второго цикла, и сразу получишь увеличение скорости

for i:= 0 to (BufLen-PatternLen) do
 if PByte(DWORD(P1)+i)^ = PByte(P2)^ then //!!! <---
   for j:= 1 to PatternLen-1 do
     if PByte(DWORD(P2)+j)^ <> PByte(DWORD(P1)+i+j)^ then
       Break
     else
       ...

Второй, теоретико-логический. Судя по твоим данным из #12 и #14 ф-я Pos дает скорость поиска ~1.6Гб/с при частоте проца 3.2ГГц, т.е.один байт обрабатывается в среднем за 2 такта процессора. С учетом того, что современные процы могут обрабатывать независимые команды по несколько штук за такт, это должно быть не более 4-5 команд процессора (переходы jXX можно не учитывать). Вот теперь возьми и сравни в отладчике в окне CPU, сколько шагов по F8 занимает цикл поиска первого символа в моем варианте MyPos, и сколько в твоем (или чьем-то там) MyPosBruteForce. Остается только все это умножить на 300млн. байт и все становится ясным и понятным

Резюме: простой независимый цикл компилятор может соптимизировать, разместив все переменные в регистрах, так, что он не будет отличаться по скорости от встроенной команды rep scasb (или даже окажется быстрее). А в сложных конструкциях с вложенными циклами возникают те же проблемы, что и с вызовом функций - нехватка регистров с необходимостью излишних чтений и записей в память, плюс накладные расходы на инициализацию цикла или вызов функции, плюс бестолковые действия на первой итерации типа ...+j при j=0 - раз ты знаешь, что для первого символа j=0, то делай эту проверку отдельно без всякого j, а то ядреные "мужики то не знают" и тупо выполняют два бестолковых сложения с нулем, а это считай уже 2 такта процессора, за которые Pos в среднем все тело цикла выполняет

Сообщение отредактировано: leo - 12.06.12, 16:54

[POP]

Цитата leo @ 12.06.12, 15:41

а то ядреные "мужики то не знают" и тупо выполняют два бестолковых сложения с нулем, а это считай уже 2 такта процессора, за которые Pos в среднем все тело цикла выполняет

Намек понял, покопаю свои исходники.. потестю..

PS.
Ситуация с алгоритмикой поиска строки в подстроке напомнила мне старые-добрые вирусные (в позновательном смысле) DOS времена, когда оптимизировали все и вся на асме.. высчитывали такты. Оказывается, что теперь вся коллективная мощь мысли програмеров переместилась с вылизывания самого маленького TSR вируса в 80 байт на потактовую оптимизацию циклов поиска подстроки в строке

Те кто вылизывал колекционные вирусы, теперь вылизывают алгоритмы поиска сигнатур в своих антивирусах.

Жуть

[Pavia]

POP
Вам всётаки лучше автомат сделать у него сложность O1(n) не зависит от числа шаблонов. Против текущего O2(n*m).
Автомат работает по медленее чем поиск примерно в 2 раза O1~2*O2

Антивирусы писали ещё и двацать лет назад. Видел я один отчёт/журнальчик 1989г.

leo
Так-как мой код на работе, то проверить смог сегодня.

Цитата leo @ 12.06.12, 10:20

Сообщ. #25 от Вчера, 13:20

Цитата leo @ 12.06.12, 10:20

PentiumD получается почти в 2 раза (90%), а на современном i5 только 35%.

Я вчера засомнивался в вашем коде. Так как на моей машине c2d он дал прирост только 11%. Сейчас сравил свой код с вашим. На домашнем вечером проверю.
i5
POS 1050
MyPOS 1200
YouPOS 1400

c2d
POS 500
MyPOS 750
YouPOS 1000

А вчера почему-то работало медленно.

С кэшем я погарячился. При линейном доступе память хорошо отрабатывает, а у POS такой случай.

Цитата

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

Вызов функции и возврат из неё CALL и ret это безусловный переход и тут процесор очень хорошо оптимизирует. Конечно не всегда и не совсем он справляется. Да и поддерживать такой бордак труднее.

Я выделяю код поиска 1 символа(4 сисволов) в отдельную процедуру. Он не так часто вызывается поэтому производительность не страдает.

function MyPosDWord(const d:DWord; Len:Integer; s:PChar):Integer;
var i:Integer;
 p:PChar;
begin
Result:=-1;
i:=Len;
p:=s;
repeat
 begin
 if PDWord(@p[0])^=d then
   begin
   Result:=DWord(p)-DWord(s);
   exit;
   end;
 Dec(i);
 Inc(p);
 end;
until i=0;
end;

Сообщение отредактировано: Pavia - 13.06.12, 17:37

[OpenGL]

Ну нафлудили Автор, тебе надо использовать алгоритм Ахо-Корасик. Вот тут можешь взять реализацию на С++. Будет заметно быстрее, особенно если надо искать длинные строки.

[leo]

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

[POP]

leo
Вынос поиска первого байта за пределы второго цикла дает прирост в два раза, соответственно отставание от Pos сокращается в два раза, с ~30 секунд до ~15. Но, извините, Pos работает за 5 секунд. Твой пример с ~PAnsiChar дает те же 15 секунд. Это никуда не годится (в сравнении с Pos).

Есть подозрение, что без ASM большего результата для bruteforce трудно добится, я прав?

Цитата Pavia @ 13.06.12, 06:12

Вам всётаки лучше автомат сделать у него сложность O1(n) не зависит от числа шаблонов.

У вас он уже реализован? Как скорость по сравнению c Pos на вашем же примере в 300mb?

Цитата OpenGL @ 13.06.12, 06:20

Автор, тебе надо использовать алгоритм Ахо-Корасик. Вот тут можешь взять реализацию на С++

А на Delphi есть?

[POP]

Также реализовал упрощенный алгоритм Boyer-Moore (взятый с http://www.rsdn.ru/article/alg/textsearch.xml), который как утверждается является наиболее быстрым из неспециализированных универсальных алгоритмов, адаптировал его под работу с массивом байт:

function TForm1.MyPosBoyerMoore(P1, P2: Pointer; BufLen, PatternLen: cardinal): cardinal;
var
BMT: TBMTable;
Pos, lp, i: cardinal;
 
begin
 for i:= 0 to 255 do
  BMT[i]:= PatternLen;
 for i:= PatternLen-1 downto 0 do
  if BMT[PByte(DWORD(P2)+i)^] = PatternLen then
   BMT[PByte(DWORD(P2)+i)^]:= PatternLen - i + 1;
 
 lp:= PatternLen-1;
 Pos:= PatternLen-1;
 while Pos < BufLen-1 do
  if PByte(DWORD(P2)+lp)^ <> PByte(DWORD(P1)+Pos)^ then
   Pos:= Pos + BMT[PByte(DWORD(P1)+Pos)^]
  else
   for i:= lp - 1 downto 0 do
    if PByte(DWORD(P2)+i)^ <> PByte(DWORD(P1)+Pos-lp+i)^ then
    begin
     Inc(Pos);
     Break;
    end
    else
    if i = 1 then
    begin
     Result:= Pos - lp + 1;
     Exit;
    end;
 Result:= 0;
end;

За 100% безошибочность кода пока не ручаюсь, ибо цель пока стоит в замере времени, но суть вот в чем, этот код дает прирост еще примерно в 1,5 раза от моих последних достижений, с ~15 до 9 секунд. Но это все еще далеко до ~4,77 секунд функции Pos.

Вот и спрашивается, а нафига мудрить с этими алгоритмами для не узкоспециализированных задач в своем софте, если можно попытаться сделать фунцию Pos на асме (дабы достичь ее скоростей) для поиcка в маасиве байт?

Загружать файл сразу в String не подходит. Нужна Pos для массива байт.

Всяческая помощь, для реализации Pos на асме, приветствуется.

[OpenGL]

Цитата POP @ 13.06.12, 11:29

Вот и спрашивается, а нафига мудрить с этими алгоритмами для не узкоспециализированных задач в своем софте, если можно попытаться сделать фунцию Pos на асме (дабы достичь ее скоростей) для поиcка в маасиве байт?

Уже же было сказано. Сложность с pos O(n * k + s), где k - количество строк, s - их суммарная длина, n - длина строки, в которой производится поиск. С Ахо-Корасик сложность будет O(n + s), поэтому с ростом k даже неоптимально написанный Ахо-Корасик станет лучше идеально вылизанного pos.

[POP]

Цитата OpenGL @ 13.06.12, 11:59

поэтому с ростом k даже неоптимально написанный Ахо-Корасик станет лучше идеально вылизанного pos.

Дак поделись Ахо-Корасиком для Delphi.

[OpenGL]

Цитата POP @ 13.06.12, 12:01

Дак поделись Ахо-Корасиком для Delphi.

На Дельфи нет. Да и переписать его несложно.

Цитата POP @ 13.06.12, 12:01

Ахо-Корасиком

Фамилия Маргарет Корасик не склоняется

[Filka]

POP
На Pascal-е: http://ilyaraz.fatal.ru/src/ahokor.html

Сообщение отредактировано: Filka - 13.06.12, 12:51

[POP]

Вот прикол, оптимизации дают эффект. Ниже рабочий варинат упрощенного Boyer-Moore:

function TForm1.MyPosBoyerMoore(P1, P2: Pointer; BufLen, PatternLen: cardinal): cardinal;    // Упрощенный Booyer-Moore
var
BMT: array [0..255] of integer;
Pos, lp, i: cardinal;
 
begin
 Result:= 0;
 if (PatternLen > BufLen) then Exit;
 
 for i:= 0 to 255 do
  BMT[i]:= PatternLen;
 for i:= PatternLen downto 1 do
  BMT[PByte(DWORD(P2)+i-1)^]:= PatternLen - i;
 
 Pos:= PatternLen-1;
 lp:= PatternLen-1;
 while Pos < BufLen do
  if PByte(DWORD(P2)+lp)^ <> PByte(DWORD(P1)+Pos)^ then
   Pos:= Pos + BMT[PByte(DWORD(P1)+Pos)^]
  else
   for i:= lp - 1 downto 0 do
    if PByte(DWORD(P2)+i)^ <> PByte(DWORD(P1)+Pos-lp+i)^ then
    begin
     Inc(Pos);
     Break;
    end
    else
    if i = 0 then
    begin
     Result:= Pos - lp + 1;  // Дает смещение+1 в массиве байт, отнимать 1 надо от результата. 0 - если ничего не найдено.
     Exit;
    end;
end;

В таком варианте имеем ~8,35 секунд и Warning компилятора об использования signed and unsigned типов (integer в таблице смещений и cardinal в циклах). Меняем в таблице integer на cardinal, получаем прирост до ~7,38 секунд, то есть целая секунда. Зачем в массиве 4-х байтовые integer, если можно воткнуть однобайтовый Byte? Воткнул - получил ~6,50.

Жизнь налаживается, скоро подойду к результату Pos

Цитата Filka @ 13.06.12, 12:50

На Pascal-е: http://ilyaraz.fatal.ru/src/ahokor.html

Посмотрю.

[Filka]

Цитата POP @ 13.06.12, 11:29

Всяческая помощь, для реализации Pos на асме, приветствуется.

В system.pas на асме она и написана (только называется она там _Pos)...

Сообщение отредактировано: Filka - 13.06.12, 14:40

[POP]

Люди, нашел описание какого-то быстрого алгоритма, но без названия, кто-нибудь знает, что это за алгоритм - http://programmersforum.ru/showthread.php?t=196864

Цитата Filka @ 13.06.12, 14:38

В system.pas на асме она и написана (только называется она там _Pos)...

Не понимаю для чего она используется, но как и обычная Pos они для строк написаны, а не для массива байт.

[leo]

Цитата Pavia @ 13.06.12, 06:12

Вызов функции и возврат из неё CALL и ret это безусловный переход и тут процесор очень хорошо оптимизирует

Речь не о переходах, которые действительно прогнозируется и ничего не стоят, а в латентности самих операций call и ret, связанных с push\pop и их косвенном влиянием на последующие операции с памятью

Цитата POP @ 13.06.12, 10:06

Твой пример с ~PAnsiChar дает те же 15 секунд. Это никуда не годится (в сравнении с Pos).

Я еще приводил "супер"-пример в #25, который работает быстрее Pos...

Сообщение отредактировано: leo - 13.06.12, 17:47

[POP]

Цитата leo @ 13.06.12, 17:46

Я еще приводил "супер"-пример в #25, который работает быстрее Pos...

А у меня он дает слабину в пол секунды по сравнению с Pos.

Делаю свой вариант Pos на асме, как сделаю, отпишусь с результатом.

[leo]

Цитата POP @ 13.06.12, 19:55

А у меня он дает слабину в пол секунды по сравнению с Pos

Кстати, у меня на AMD он и вовсе тупит и работает существенно хуже Pos. Тут конечно дельфийский компилер всю малину портит, генеря ужасно неоптимизированный код, ну и сами AMD на таком коде сильно тупят по сравнению с интеловскими камнями.

Ну тогда придется на асме "поразвлечься"
Во-первых, вот тебе вариант дельфийского Pos, подправленного для произвольных байт\строк (взято из LStrPos D7):

function Pos_D7(S, Sub:pointer; SLen, SubLen:integer):integer; register;
asm //           eax edx          ecx    stack
        TEST    EDX,EDX
        JE      @@noWork
 
        TEST    EAX,EAX
        JE      @@stringEmpty
 
        PUSH    EBX
        PUSH    ESI
        PUSH    EDI
        MOV     ESI,EDX                         { Point ESI to substr           }
        MOV     EDI,EAX                         { Point EDI to s                }
        PUSH    EDI                             { remember s position to calculate index        }
        MOV     EDX,SubLen                      { EDX = Length(substr)          }
        DEC     EDX                             { EDX = Length(substr) - 1              }
        JS      @@fail                          { < 0 ? return 0                        }
        MOV     AL,[ESI]                        { AL = first char of substr             }
        INC     ESI                             { Point ESI to 2'nd char of substr      }
        SUB     ECX,EDX                         { #positions in s to look at    }
                                                { = Length(s) - Length(substr) + 1      }
        JLE     @@fail
@@loop:
        REPNE   SCASB
        JNE     @@fail
        MOV     EBX,ECX                         { save outer loop counter               }
        PUSH    ESI                             { save outer loop substr pointer        }
        PUSH    EDI                             { save outer loop s pointer             }
 
        MOV     ECX,EDX
        REPE    CMPSB
        POP     EDI                             { restore outer loop s pointer  }
        POP     ESI                             { restore outer loop substr pointer     }
        JE      @@found
        MOV     ECX,EBX                         { restore outer loop counter    }
        JMP     @@loop
 
@@fail:
        POP     EDX                             { get rid of saved s pointer    }
        XOR     EAX,EAX
        JMP     @@exit
 
@@stringEmpty:
        XOR     EAX,EAX
        JMP     @@noWork
 
@@found:
        POP     EDX                             { restore pointer to first char of s    }
        MOV     EAX,EDI                         { EDI points of char after match        }
        SUB     EAX,EDX                         { the difference is the correct index   }
@@exit:
        POP     EDI
        POP     ESI
        POP     EBX
@@noWork:
end;

Ну и для сравнения, "навороченный" вариант с поиском первого байта двордами:

function SuperPos(S, Sub:pointer; SLen, SubLen:integer):integer;register;
//               eax edx          ecx   stack
var
  p0,p4:pointer;
  mask,Len:Longword;
asm
   push ebx
   push edi
   push esi
   sub ecx,SubLen //i = SLen-SubLen
   jl @@fail      //if i < 0 goto @@fail
   sub SubLen,1   //SubLen:=SubLen-1
   inc ecx        //i = SLen-SubLen+1
   mov p0, eax    //p0:=S для вычисления позиции в сл.успеха
   mov Len,ecx    //Len:=i
   and ecx,-4     //i:=Len, округленное вниз до 4-х
   mov edi,eax    //edi==p:=S
   mov esi,edx    //esi:=Sub
   //создание xor-маски для 1-го символа Sub
   movzx eax,byte[edx]
   mov edx,$01010101
   mul edx
   mov mask, eax
   mov ebx,eax   //ebx - маска
  {nop  //фишки для выравнивания адреса метки @@loop1 на 16 байт
   nop
   nop }
@@loop1: //repeat - цикл поиска первого символа
   mov eax,[edi] //eax = pDword(p)^
@@rembytes:
   add edi,4     //inc(p,4)
   xor eax,ebx   //xor с маской -> совпадающие байты становятся = 0
   //трик для поиска хоть одного 0-байта в дворде
   lea edx,[eax+$7EFEFEFF]
   not eax
   xor eax,edx
   and eax,$81010100
   jnz @@found  //есть 0-байт - нашли совпадение
   sub ecx,4    //dec(i,4);
   jle @@endLoop1
   //повтор для уменьшения тормоза совершаемого перехода jg @@loop1
   mov eax,[edi]
   add edi,4
   xor eax,ebx
   lea edx,[eax+$7EFEFEFF]
   not eax
   xor eax,edx
   and eax,$81010100
   jnz @@found
   sub ecx,4
   jg @@loop1
 
@@endLoop1:
   //тут eax = 0
   jl @@end    //i < 0 только после @@rembytes, выход с Result:=0
@@checkLen:
   mov ecx,Len //проверка наличия доп.байт, не кратных 4-м
   and ecx,3   //i:=Len and 3;
   jz @@end    //=0 - выход с Result:=0
@@1: //читаем побайтно в eax
   movzx edx,byte[edi+ecx-1] //ecx=3,2,1 -> edi+2,edi+1,edi
   shl eax,8
   or eax,edx
   dec ecx
   jnz @@1
   jmp @@rembytes //еще один проход через @@loop1
 
@@found: //здесь edi = p = p'+4, где p' - ук-ль на прочитанный дворд
   mov p4,edi  //p4:=p
   sar eax,1   //АРИФМ.сдвиг с сохр.знака: $81010100 -> $C0808080
 
@@loop2: //цикл по совпадениям
   add edi,1     //pp:=p+1,p+2,... = p'+5,p'+6, ...
   shr eax,8
   jc @@checkSub //есть совпадение байта
   jnz @@loop2   //если есть еще совпадения
   //больше нет совпадений == "ложная тревога"
   mov edi,p4    //восстанавливаем ткущий ук-ль edi=p=p'+4
   mov ebx,mask  //восстанавливаем маску
@@fail:
   xor eax,eax   //Result:=0
   sub ecx,4     //dec(i,4)
   jg @@loop1    //> 0 - возврат к поиску первого байта
   jz @@checkLen //= 0 - на контроль оставшихся байт
   jmp @@end     //< 0 - на выход
 
@@checkSub:     //проверка совпадения с подстрокой
   xor ebx,ebx   //j:=0 - счетчик длины подстроки 1..SubLen-1
@@loop3:
   add ebx,1          //inc(j)
   mov dl,[edi+ebx-5] //p'[j]
   cmp dl,[esi+ebx]   //if p'[j] <> sub[j]
   jne @@loop2
   cmp ebx,SubLen     //until j >= SubLen;
   jl @@loop3
   //нашли подстроку
   sub edi,p0         //Result:=pp-p0-4
   lea eax,[edi-4]
 
@@end:
   pop esi
   pop edi
   pop ebx
end;

Сообщение отредактировано: leo - 14.06.12, 17:04

[leo]

Сравнительные цифирьки по методике #13 c заменой Pos(..) на
Pos_D7(pointer(s),pointer(sub[i]),Length(s),Length(sub[i])) и т.п.

Процессор:     PentiumD     i5-2410M    Athlon 64 X2  Phenom II X2
Частота,МГц     3000       2700-2900       2400          3000
Скорость,Мб/с              (tyrbo bust)
   Pos_D7:        628         1167           978          1322
   SuperPos:     1825         2843          1511          2283
Время,с
   Pos_D7:      11.02         5.92          7.08          5.24
   SuperPos:     3.79         2.43          4.58          3.03
 
Разница,раз     2.91         2.43          1.54          1.73

Сообщение отредактировано: leo - 15.06.12, 09:59

[POP]

Практика показала, что если на постоянной основе на асме не пишешь, то лучше туда даже с мелочевкой не лезть. Все равно ничего хорошего не выйдет, заколебался отлавливать AccessViolations.


leo
У меня твоя первая ф-я дает около ~4,9 секунд. Вторая оптимизированная функция дает ~4,28, то есть практически тот же самый результат что и у стандартной Pos.

На данный момент я терзаюсь в сомнениях, что использовать у себя в софте как универсальный неспециализированный поисковик: c одной стороны все кричат (Факи), что брутефорс это начальный уровень и нужно юзать один из специальных поисковых алгоритмов (Boyer-Moore, Аха-корасик), с другой стороны эти алгоритмы сливают обычному Pos на асме. У меня написанный на Delphi упрощенный Boyer-Moore дает 6,5 секунд по сравнению 4,28 Pos на асме.

Что скажешь, leo, может этот алгоритм гепотетически более универсален и может дать выигрышь в будущем на каком-нибудь хитром бинарничке, по сравнению с брутефорсе?

Я склоняюсь воткнуть твой оптимизированный вариант брутефорсе (dword) да и закрыть вопрос.

[Dimonka]

POP
Тебе не нужны никакие алгоритмы, пока ты ищешь только одну подстроку символов. Алгоритмы потребуются для поиска сразу нескольких строк одновременно.

[POP]

Цитата Dimonka @ 17.06.12, 17:22

Алгоритмы потребуются для поиска сразу нескольких строк одновременно.

Я ищу ~20 подстрок и делаю соответственно двадцать проходов по бинарнику.

[leo]

Цитата POP @ 16.06.12, 19:09

У меня твоя первая ф-я дает около ~4,9 секунд. Вторая оптимизированная функция дает ~4,28, то есть практически тот же самый результат что и у стандартной Pos

Что ты заладил "у меня, у меня"? Тебе нужен "универсальный неспециализированный поисковик" или заточенный под твой конкретный проц?! Я тебе цифирьки привел для разных камней, и они достаточно хорошо отражают "теоретические закономерности". В частности можно на 100% утверждать, что на всех интеловских камнях (и в настоящем, и в будущем) SuperPos будет давать значительный выигрыш по сравнению с Pos, реализованной на командах rep scasb и rep cmpsb. А все модели AMD на "запредельном" коде типа SuperPos могут тормозить и в настоящем, и в будущем, если AMD в конце концов не откажется от нескольких своих принципиальных архитектурных фишек, за которые ее давно критикуют. В частности двойной разворот основного цикла в SuperPos 100% рулит на интеловских камнях, а на AMD как "бог на душу положит" в зависимости от адреса начала цикла и возможных конфликтов портов при параллельном исполнении команд первой и второй части цикла (в AMD команды принудительно распределяются по 3-м портам в порядке их следования в программе, что может приводить к конфликту - невозможности одновременного исполнения двух независимых команд, попавших в один порт, хотя два других порта в данном такте м.б.свободными - у интела такого нет, т.к.любая простая ALU- команда м.б. направлена в любой свободный порт). К тому же и в NetBurst (Pentium4) и во всех Core рулит кэширование микрокоманд (небольших) циклов, что устраняет зависимость от выравнивания адреса начала цикла и связанную с этим возможную потерю одного-двух тактов для неблагоприятных ситуаций. Резюме: чтобы код типа SuperPos работал гарантированно быстро на AMD, его нужно специально "затачивать" под AMD с подбором выравнивания цикла и возможными перестановками команд для исключения конфликта портов. Но в дельфи нет возможности принудительно задавать выравнивание, поэтому если даже его подобрать вставкой команд типа nop (как показано в #45) для конкретной проги, то оно не будет универсальным и может "уехать не в ту степь" при любых изменениях в проге

Добавлено 18.06.12, 07:51
PS: У меня "в загашнике" где-то должен быть еще более быстрый вариант поиска двух байт на MMX (методом "вилки"), который и на AMD д.б. гарантированно быстрее rep scasb

Добавлено 18.06.12, 08:27
Что касается специализированных алгоритмов, то при одновременном поиске ~15-20 подстрок и более можно точно не мудрить и использовать алгоритм Ахо-Корасик, который к тому же является наиболее "тупым" в плане устойчивости и независимости как от длины подстрок, так и вероятностей распределения символов и потерь времени на ложные захваты. Мы тут с подачи Pavia экспериментируем на чисто случайных последовательностях байт, хотя в реальных и "бинарничках", и тем более в текстовиках, есть определенные корреляции и вероятности появляения определенных байтов. Поэтому можно нарваться на ситуацию, когда или первый символ подстроки для вариаций Pos, или последний символ для вариаций Бойер-Мур'а окажется "супер-популярным", что будет приводить к частым ложным срабатываниям основного цикла и заметному ухудшению скорости поиска. А алгос Ахо-Корасик всегда крутится внутри своего заранее заданного автомата без всяких условных переходов и соотв-но не зависит от вероятностей появления символов. Но зато он является и самым медленным в плане времени обработки одного байта, поэтому для малого числа строк может проигрывать обычному Pos. Причем опять же на AMD этот алгос будет давать несколько худшие рез-ты, чем на интеловских камнях, из-за принципиальной фишки AMD под названием AGI (Address Generation Interlock), из-за которой чтение следующего байта входной строки будет тормозиться чтением состояния автомата для пред.символа\байта

Добавлено 18.06.12, 08:34
PS: Основная идея алгоса Бойер-Мура с перескоками по shift_table в принципе может быть "прикручена" и к поиску по SuperPos. Вот только для этого длины подстрок в 5 символов явно маловато и доп.затраты на переходы по shift_table могут просто не окупиться при скачках максимум на 4 позиции (опять же особенно на AMD с его AGI).

Сообщение отредактировано: leo - 18.06.12, 08:34