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

[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 байт на потактовую оптимизацию циклов поиска подстроки в строке

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

Жуть