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

[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