Поиск в бинарном файле

← →
Sha © (2004-09-30 09:24) [120]

> Defunct

Попробуй написать аналог Борландовской Pos на базе своей функции и померяйся с вот этим:

//(c) John O"Harrow
function PosJOH_MMX(const SubStr : AnsiString; const Str : AnsiString) : Integer;
asm
test eax, eax
jz @NotFoundExit {Exit if SurStr = ""}
test edx, edx
jz @NotFound {Exit if Str = ""}
mov ecx, [edx-4] {Length(Str)}
cmp [eax-4], 1 {Length SubStr = 1?}
je @SingleChar {Yes - Exit via CharPos}
jl @NotFound {Exit if Length(SubStr) < 1}
sub ecx, [eax-4] {Subtract Length(SubStr), -ve handled by
CharPos}
add ecx, 1 {Number of Chars to Check for 1st Char}
push esi {Save Registers}
push edi
push ebx
push ebp
mov esi, eax {Start Address of SubStr}
mov edi, ecx {Initial Remainder Count}
mov eax, [eax] {AL = 1st Char of SubStr}
mov ebp, edx {Start Address of Str}
mov ebx, eax {Maintain 1st Search Char in BL}
@StrLoop:
mov eax, ebx {AL = 1st char of SubStr}
mov ecx, edi {Remaining Length}
push edx {Save Start Position}
call @CharPos {Search for 1st Character}
pop edx {Restore Start Position}
test eax, eax {Result = 0?}
jz @StrExit {Exit if 1st Character Not Found}
mov ecx, [esi-4] {Length SubStr}
add edx, eax {Update Start Position for Next Loop}
sub edi, eax {Update Remaining Length for Next Loop}
sub ecx, 1 {Remaining Characters to Compare}
@StrCheck:
mov al, [edx+ecx-1] {Compare Next Char of SubStr and Str}
cmp al, [esi+ecx]
jne @StrLoop {Different - Return to First Character Search}
sub ecx, 1
jnz @StrCheck {Check each Remaining Character}
mov eax, edx {All Characters Matched - Calculate Result}
sub eax, ebp
@StrExit:
pop ebp {Restore Registers}
pop ebx
pop edi
pop esi
ret
@NotFound:
xor eax, eax {Return 0}
@NotFoundExit:
ret
@SingleChar:
mov al, [eax] {Search Character}
@CharPos:
CMP ECX, 8
JG @@NotSmall
@@Small:
or ecx, ecx
jle @@NotFound {Exit if Length <= 0}
CMP AL, [EDX]
JZ @Found1
DEC ECX
JZ @@NotFound
CMP AL, [EDX+1]
JZ @Found2
DEC ECX
JZ @@NotFound
CMP AL, [EDX+2]
JZ @Found3
DEC ECX
JZ @@NotFound
CMP AL, [EDX+3]
JZ @Found4
DEC ECX
JZ @@NotFound
CMP AL, [EDX+4]
JZ @Found5
DEC ECX
JZ @@NotFound
CMP AL, [EDX+5]
JZ @Found6
DEC ECX
JZ @@NotFound
CMP AL, [EDX+6]
JZ @Found7
DEC ECX
JZ @@NotFound
CMP AL, [EDX+7]
JZ @Found8
@@NotFound:
XOR EAX, EAX
RET
@Found1:
MOV EAX, 1
RET
@Found2:
MOV EAX, 2
RET
@Found3:
MOV EAX, 3
RET
@Found4:
MOV EAX, 4
RET
@Found5:
MOV EAX, 5
RET
@Found6:
MOV EAX, 6
RET
@Found7:
MOV EAX, 7
RET
@Found8:
MOV EAX, 8
RET

@@NotSmall: {Length(Str) > 8}
MOV AH, AL
ADD EDX, ECX
MOVD MM0, EAX
PUNPCKLWD MM0, MM0
PUNPCKLDQ MM0, MM0
PUSH ECX {Save Length}
NEG ECX
@@First8:
MOVQ MM1, [EDX+ECX]
ADD ECX, 8
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched {Exit on Match at any Position}
CMP ECX, -8 {Check if Next Loop would pass String End}
JGE @@Last8
@@Align: {Align to Previous 8 Byte Boundary}
LEA EAX, [EDX+ECX]
AND EAX, 7 {EAX -> 0 or 4}
SUB ECX, EAX
@@Loop:
MOVQ MM1, [EDX+ECX]
ADD ECX, 8
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched {Exit on Match at any Position}
CMP ECX, -8 {Check if Next Loop would pass String End}
{$IFNDEF NoUnroll}
JGE @@Last8
MOVQ MM1, [EDX+ECX]
ADD ECX, 8
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched {Exit on Match at any Position}
CMP ECX, -8 {Check if Next Loop would pass String End}
{$ENDIF}
JL @@Loop
@@Last8:
MOVQ MM1, [EDX-8] {Position for Last 8 Used Characters}
POP EDX {Original Length}
PCMPEQB MM1, MM0 {Compare All 8 Bytes}
PACKSSWB MM1, MM1 {Pack Result into 4 Bytes}
MOVD EAX, MM1
TEST EAX, EAX
JNZ @@Matched2 {Exit on Match at any Position}
EMMS
RET {Finished - Not Found}
@@Matched: {Set Result from 1st Match in EDX}
POP EDX {Original Length}
ADD EDX, ECX
@@Matched2:
EMMS
SUB EDX, 8 {Adjust for Extra ADD ECX,8 in Loop}
TEST AL, AL
JNZ @@MatchDone {Match at Position 1 or 2}
TEST AH, AH
JNZ @@Match1 {Match at Position 3 or 4}
SHR EAX, 16
TEST AL, AL
JNZ @@Match2 {Match at Position 5 or 6}
SHR EAX, 8
ADD EDX, 6
JMP @@MatchDone
@@Match2:
ADD EDX, 4
JMP @@MatchDone
@@Match1:
SHR EAX, 8 {AL <- AH}
ADD EDX, 2
@@MatchDone:
XOR EAX, 2
AND EAX, 3 {EAX <- 1 or 2}
ADD EAX, EDX

end;

← →
Игорь Шевченко © (2004-09-30 10:18) [121]

Defunct © (29.09.04 18:14) [117]

В процитированном

← →
Romkin © (2004-09-30 10:31) [122]

Sha © (30.09.04 09:24) [120] Бррр...
Может, так достаточно? http://delphibase.endimus.ru/?action=viewfunc&topic=strsearch&id=10271
Интересно, и насколько отстает?

← →
Sha © (2004-09-30 16:44) [123]

Romkin © (30.09.04 10:31) [122]

Вот и мне интересно, насколько Defunct отстанет.
Думаю, в среднем по разным длинам, отстанет прилично.

А в 2 слишним раза перекрыть RTL можно и на Паскале:
function PosShaPas(const SubStr: AnsiString; const Str: AnsiString): Integer; var len, lenSub: integer; ch: char; p, pSub, pStart, pEnd: pchar; label Ret, Ret0, Ret1, Next0, Next1; begin; p:=pointer(Str); pSub:=pointer(SubStr); //if you need pure Pascal uncomment this paragraph //and comment out the next 3 paragraphs { len:=length(Str); lenSub:=length(SubStr); pEnd:=p+len; pStart:=p; pEnd:=pEnd-lenSub; if (len<=0) or (lenSub<=0) or (p>pEnd) then begin; Result:=0; exit; end; } if (p=nil) or (pSub=nil) then begin; Result:=0; exit; end; len:=pinteger(p-4)^; lenSub:=pinteger(pSub-4)^; if (len<lenSub) or (lenSub<=0) then begin; Result:=0; exit; end; pEnd:=p+len; pStart:=p; pEnd:=pEnd-lenSub; ch:=pSub[0]; if lenSub=1 then begin; repeat; if ch=p[0] then goto Ret0; if ch=p[1] then goto Ret1; p:=p+2; until p>pEnd; Result:=0; exit; end; repeat; if ch=p[0] then begin; len:=lensub; repeat; if psub[len-1]<>p[len-1] then goto Next0; if psub[len-2]<>p[len-2] then goto Next0; len:=len-2; until len<2; goto Ret0; Next0:end; if ch=p[1] then begin; len:=lensub; repeat; if psub[len-1]<>p[len] then goto Next1; if psub[len-2]<>p[len-1] then goto Next1; len:=len-2; until len<2; goto Ret1; Next1:end; p:=p+2; until p>pEnd; Result:=0; exit; Ret1: inc(pEnd); p:=p+2; if p<=pEnd then goto Ret; Result:=0; exit; Ret0: inc(p); Ret: Result:=p-pStart; end;

← →
Defunct © (2004-09-30 21:05) [124]

Sha © (30.09.04 09:24) [120]

Пока не не адаптировал фукнкцию к Ansi String, но к приведенной вами функции - Respect.

строка SubString = "Test Stringx" - 12 симоволов.
5.978/ 4.153 / 3.900 ([120]/[123]/[112]).

строка SubString = "Test String" - 11 симоволов.
6.278/ 4.753 / 4.085 ([120]/[123]/[112]).

Но это и понятно, там рассмотрены почти все частные случаи.
Попробую и своего зверька [112] привести к нормальному виду.

To Sha: За счет чего достигается такое быстродействие в [123]?

← →
GuAV © (2004-09-30 21:20) [125]

У меня быстрее [120], [123] немного медленнее.
на коротком файле (autoecex.bat) быстрее всего [112].

Celeron 2000, win9x.

не ММХ - ф-ция ваще в пролёте.

← →
Defunct © (2004-09-30 21:37) [126]

Defunct © (30.09.04 21:05) [124]
опечатка:

строка SubString = "Test Stringx" - 12 симоволов.
5.978/ 4.153 / 3.900 ([112]/[120]/[123]).

строка SubString = "Test String" - 11 симоволов.
6.278/ 4.753 / 4.085 ([112]/[120]/[123]).

← →
Sha © (2004-09-30 22:22) [127]

> Defunct © (30.09.04 21:05) [124]
> За счет чего достигается такое быстродействие в [123]?

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

Так что дело тут, как видишь, совсем не в выборе языка :)

← →
Defunct © (2004-09-30 22:24) [128]

С вот таким вот изменением, скорость [112] сравнялась с [120]

@@Scan: {$ifdef MMX} MovD MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) // PCMPGTD MM7, MM5 // make a dword mask // PUNPCKHWD MM7, MM7 // mix 2 dwords into a qword MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound // yes - 1st char of the constant was found Add EDi,4 // correct index Sub ECx,4 // and buffer size Jns @@Scan // continue scan if buffer not empty Jmp @@Exit_False // otherwise - leave with no result @@CharFound: MovD EAx, MM4 // restore EAx (1st and last chars of the constant) {$endif} Repne ScasB {$ifndef MMX} JNE @@Exit_False // no 1st char of the constant found = exit_false {$endif}

Я даже не думал, что MovQ работает настолько медленней чем 2 MovD
[123] действительно получается в пролете.

строка SubString = "Test String" - 11 симоволов.
4.078/4.085/4.753 ([112 с указанным изменением]/[120]/[123])

Просмотренный буфер - 2.5Gb (читался порциями по 1Mb, файл 25Mb, 100 раз подряд).

← →
Defunct © (2004-09-30 22:26) [129]

> а также маленькой хитрости - изменения направления сравнения.

О, стоит применить к [112] ;)

← →
Sha © (2004-09-30 22:27) [130]

> Defunct © (30.09.04 22:24) [128]

Дай полный код своего аналога Pos. Я его завтра потестирую.

← →
GuAV © (2004-09-30 22:40) [131]

> Пока не не адаптировал фукнкцию к Ansi String

для своих тестов я так сделал:

Function DefunctMMX(const Constant: string; const Buffer: string): Integer; Assembler; Asm Push EDi Push ESi Push EBx Push EBp // a fix to make this fcn Pos compatible MOV ECX, [EDX-4] // should not affect perfomance much Push ECx // store total buffer size for later calculation pos

← →
Defunct © (2004-09-30 23:22) [132]

> Дай полный код своего аналога Pos. Я его завтра потестирую.

unit Search; interface {$define MMX} Function ConstantPos(const Constant, Buffer: string): Integer; implementation Function ConstantPos(const Constant, Buffer: string): Integer; Assembler; Asm Push EDi Push ESi Push EBx Push EBp MOV ESI, EAX // ESi pointer to constant Mov EDi, EDx // EDi pointer to buffer Mov ECx, [EDi-4] Push ECx // store total buffer size for later calculation pos Mov EBX, [ESI-4] Dec EBX Mov Al, [ESi] // Store first char of the constant in AL {$ifdef MMX} Mov Ah, Al // Spreading char to 32bit register Push Ax Push Ax Pop EAx MovD MM6, EAx PSLLQ MM6,MM6 // Spreading char to mmx register MovD MM6, EAx PXOR MM5,MM5 // Z mask for later calculations {$endif} Mov Ah, [ESi+EBx] // Store last char of the constant in AH Dec EBx // EBx - length of the constant w/o 1st and last chars Mov EDx,ECx // EDx - Stored residual buffer size Inc ESi Mov EBp, ESi // EBp - stored pointer to 2nd char of constant {$ifdef MMX} MovD MM4, EAx // store EAx in MM buffer {$endif} @@Scan: {$ifdef MMX} MovQ MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) PCMPEQD MM7, MM5 // make a dword mask PCMPEQD MM7, MM5 // invert dword mask PSLLQ MM7,16 // mix 2 dwords into a qword MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound // yes - 1st char of the constant was found Add EDi,8 // correct index Sub ECx,8 // and buffer size Jns @@Scan // continue scan if buffer not empty Jmp @@Exit_False // otherwise - leave with no result @@CharFound: MovD EAx, MM4 // restore EAx (1st and last chars of the constant) {$endif} Repne ScasB {$ifndef MMX} JNE @@Exit_False // no 1st char of the constant found = exit_false {$endif} Mov EDx, ECx // store new residual buffer size Cmp EDx, EBx // constant still can be settled in buffer Ja @@CheckLastChar // no - exit with false result @@Exit_False: Pop EAx Xor EAx,EAx // False = (0), check delphi help for more info Dec EAx Jmp @@Leave_Proc @@CheckLastChar: // as proposed in Boyer-Mur alhorithm Cmp Ah, [EDi+EBx] // check found substring with last char of the constant Jnz @@Scan // not match - continue searching @@CompareWholeString: Mov ECx, Ebx // ECx - constant chars amount shr ECx, 2 // ECx - constant chars amount div 4 jz @@SkipDTest Repe CmpsD Jnz @@SkipBTest @@SkipDTest: Mov ECx, Ebx and ECx, 3 jz @@Constant_Exists // two least significant bits // of amount are zero so the Constant matches Repe CmpsB Jz @@Constant_Exists @@SkipBTest: Mov ESi, EBp // restore pointer to 2nd char of constant Add EDx, ECx Sub EDx, EBx // correct residual buffer size Mov ECx, EDx // restore residual buffer size to ECx Jnz @@Scan @@Constant_Exists: Pop EAx Sub EAx, EDx @@Leave_Proc: {$ifdef MMX} EMMS // finish mmx operations {$endif} Pop EBp Pop EBx Pop ESi Pop EDi End; end.

← →
Defunct © (2004-09-30 23:46) [133]

Вот более достоверные результаты (просмотр 25Gb):

[132] - 42.230 сек
[120] - 38.800 сек
[123] - 46.831 сек

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

2 Sha, если вашу функцию сделать в MMX исполнении, она поидее побъет всех ;) т.к. [132] без MMX - 65.453

← →
Sha © (2004-09-30 23:53) [134]

> Defunct

1. Функция не является полным аналогом Pos.
Не будет работать для пустых строк, т.к. за длиной строки полезет по адресу (0-4)=FFFFFFFC.

2. Не корректно замерять скорость Pos на файлах или на буфере длиной 2Gb. Погрешности за счет дисковых очень велики и не предсказуемы.

← →
GuAV © (2004-09-30 23:58) [135]

Sha © (30.09.04 23:53) [134]
Какие размеры для замера предлагаете?
имхо 0, 128 байт, 1 кБ и 1 МБ.

← →
Sha © (2004-10-01 00:12) [136]

> Defunct

3. Оригинальная Pos из RTL в случае неуспеха возвращает 0, твоя -1:
@@Exit_False: Pop EAx Xor EAx,EAx // False = (0), check delphi help for more info Dec EAx Jmp @@Leave_Proc

4. Оригинальная Pos никогда не тестирует символы, идущие за терминатором. Твоя тестирует, что теоретически может вызвать AV.

← →
Sha © (2004-10-01 00:16) [137]

> GuAV © (30.09.04 23:58) [135]
> Какие размеры для замера предлагаете?

Предлагаю использовать неплохой (хотя и не без нереканий) вариант
http://dennishomepage.gugs-cats.dk/PosBV45.zip

← →
Sha © (2004-10-01 00:38) [138]

> Defunct

5. Похоже, твоя функция иногда будет выдавать неверный результат (следствие пункта 4):
ConstantPos(#0,"Мы находим даже терминатор")>0

← →
Defunct © (2004-10-01 02:25) [139]

Ок, со всем здесь услышанным, подправил [132], так, что возвращается "0" если строка не найдена, подправлена работа со строками нулевой длинны, и плюс сделал выравнивание адреса как в [120] (спасибо за пример [120]).
Ну теперь получается по скорости, на некоторых строках выигрывает новая функция, на некоторых - [120]. По времени, приблизительно получилось следующее:

на разных строках функция [120] (1.25Gb пересмотр).
результат от 19.069 сек до 19.984.

новая функция тестировалась в тех же условиях (1.25Gb пересмотр)
результат от 18.768 сек до 20.364.

Буфер поиска - 1Mb.

Следует отметить неоспоримое преимущество приведенной здесь функции, она в отличие от [120] способна работать на процессорах у которых нет MMX.

unit Search; interface {$define MMX} Function ConstantPos(const Constant, Buffer: string): Integer; implementation Function ConstantPos(const Constant, Buffer: string): Integer; Assembler; Asm Push EDi Push ESi Push EBx Push EBp MOV ESI, EAX // ESi pointer to constant Mov EDi, EDx // EDi pointer to buffer Mov ECx, [EDi-4] Push ECx // store total buffer size for later calculation pos Test ECx,ECx Jz @@Exit_False Mov EBX, [ESI-4] Test EBx,EBx Jz @@Exit_False Dec EBX Mov Al, [ESi] // Store first char of the constant in AL {$ifdef MMX} Mov Ah, Al // Spreading char to 32bit register MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 PXOR MM5,MM5 // Z mask for later calculations Dec EBx // EBx - length of the constant w/o 1st and last chars Mov Ax,[ESi+EBx] Dec EBx {$endif} {$ifndef MMX} Mov Ah, [ESi+EBx] // Store last char of the constant in AH {$endif} Mov EDx,ECx // EDx - Stored residual buffer size Inc ESi Mov EBp, ESi // EBp - stored pointer to 2nd char of constant {$ifdef MMX} MovD MM4, EAx // store EAx in MM buffer {$endif} @@Scan: {$ifdef MMX} MovQ MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) PACKSSWB MM7, MM7 MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound // yes - 1st char of the constant was found Add EDi, 8 Mov EAx, Edi And EAx, 7 Sub EDi,EAx // Aligning index Sub ECx,8 Add ECx,EAx // and correcting buffer size Js @@Exit_False @@Scan2: MovQ MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) PACKSSWB MM7,MM7 MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound // yes - 1st char of the constant was found Add EDi,8 // correct index Sub ECx,8 // and buffer size Jns @@Scan2 // continue scan if buffer not empty Jmp @@Exit_False // otherwise - leave with no result @@CharFound: MovQ MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) MovD EAx, MM7 Test EAx, EAx Jnz @@Loop1 PSRLQ MM7,32 MovD EAx, MM7 @@Loop1: inc EDi dec Ecx Shr EAx,8 Jz @@ContinueHere jmp @@Loop1 {$endif} Repne ScasB {$ifndef MMX} JNE @@Exit_False // no 1st char of the constant found = exit_false {$else} @@ContinueHere: MovD EAx, MM4 // restore EAx (1st and last chars of the constant) {$endif} @@CheckLastChar: // as proposed in Boyer-Mur alhorithm {$ifndef MMX} Cmp Ah, [EBx+Edi] // check found substring with last char of the constant {$else} Cmp Ax, [EBx+EDi] {$endif} Jz @@CompareWholeString // not match - continue searching Jmp @@Scan @@Exit_False: Pop EAx Xor EAx,EAx // 0 if constant was not found Jmp @@Leave_Proc @@CompareWholeString: Mov EDx, ECx // store new residual buffer size Cmp EDx, EBx // constant still can be settled in buffer Jna @@Exit_False // no - exit with false result Mov ECx, Ebx // ECx - constant chars amount shr ECx, 2 // ECx - constant chars amount div 4 jz @@SkipDTest Repe CmpsD Jnz @@SkipBTest @@SkipDTest: Mov ECx, Ebx and ECx, 3 jz @@Constant_Exists // two least significant bits // of amount are zero so the Constant matches Repe CmpsB Jz @@Constant_Exists @@SkipBTest: Mov ESi, EBp // restore pointer to 2nd char of constant Add EDx, ECx Sub EDx, EBx // correct residual buffer size Mov ECx, EDx // restore residual buffer size to ECx Jnz @@Scan @@Constant_Exists: Pop EAx Sub EAx, EDx @@Leave_Proc: {$ifdef MMX} EMMS // finish mmx operations {$endif} Pop EBp Pop EBx Pop ESi Pop EDi End; end.

На будущее думаю попробовать сделать поиск через SSE/SSE2

> 4. Оригинальная Pos никогда не тестирует символы, идущие за терминатором. Твоя тестирует, что теоретически может вызвать AV.

ни старая, ни исправленная функции не выходили за границу буфера.

← →
Defunct © (2004-10-01 02:28) [140]

> [139] (1.25Gb пересмотр).

не там точку поставил.

12.5Gb пересмотр.

← →
Defunct © (2004-10-01 03:14) [141]

посмотрел тест [137] недостаток теста в том, что он был нацелен именно, на поиск подстроки в строке. Функция же [139] больше нацелена на поиск подстроки в файле, т.е. предполагается просмотр не одного буфера а немкольких. Поэтому по одному тесту скорости у нее высокая оценка (SubBench2), а по второму (SubBench1) - низкая, суммарная оценка получалась лучше чем RTL/RTLa/b но значительно хуже чем у PosJoh и PosSha, сейчас внесу поправки с учетом изменения задачи.

← →
Defunct © (2004-10-01 06:17) [142]

> Sha

Провозился всю ночь с этой функцией, выкладывать пока не буду так как еще не доделал. Есть вопрос, что в вашем тесте означает SubBench1 и SubBench2?

В изначальном варианте [139] было:
SubBench1 = 261
SubBench2 = 159

Сейчас почемуто получается:
SubBench1 = 295
SubBench2 = 121

Суммарный Bench индекс практически не изменился все на том же уровне 410-420.

В функциях PosJoh_MMX и PosSha наблюдаю примерно такую картину:
SubBench1 = 177, 180
SubBench2 = 147, 152

SubBench1 относится к маленьким строкам я правильно понимаю?

← →
Sha © (2004-10-01 09:44) [143]

> Defunct

> Буфер поиска - 1Mb.
Многовато будет :) Наиболее частое применение Pos - поиск первого вхождения в строке до 100 символов. В случае успеха в среднем результат поиска не превышает 40. Именно для этих условий и должна проводиться оптимизация. Для других условий пишутся другие функции, которые сравнивать с Pos будет неверно.

> Следует отметить неоспоримое преимущество приведенной здесь
> функции, она в отличие от [120] способна работать на
> процессорах у которых нет MMX.
По приведенной мной ссылке ты можешь найти реализации Pos на любой вкус.

> ни старая, ни исправленная функции не выходили за границу буфера.
Извини, значит, я был недостаточно внимателен. Тогда пункты 4 и 5 снимаются.

> посмотрел тест [137] недостаток теста в том, что он был
> нацелен именно, на поиск подстроки в строке. Функция же [139]
> больше нацелена на поиск подстроки в файле, т.е.
> предполагается просмотр не одного буфера а немкольких
Вот это я совсем не понял.

> SubBench1 относится к маленьким строкам я правильно понимаю?
Поиск малых строк среди малых строк (первые 35 тестов).

← →
Defunct © (2004-10-01 10:27) [144]

> посмотрел тест [137] недостаток теста в том, что он был
> нацелен именно, на поиск подстроки в строке. Функция же [139]
> больше нацелена на поиск подстроки в файле, т.е.
> предполагается просмотр не одного буфера а немкольких

Имел в виду, что тест не полностью отражает возможности функций. Не учитывается скорость поиска в больших см. сабж до 1Gb строках.

> Поиск малых строк среди малых строк (первые 35 тестов).
Я так и думал. Крутил и так и сяк, на малых строках существенно проигрываю, PosJoh и PosSha. (в PosJoh заметил ведется отдельная обработка маленьких строк)

Зато на больших строках получилось обогнать все функции:
просматриваемый буфер делится на 2 кадра, в каждом кадре просмотр ведется в двух направлениях.

> Для других условий пишутся другие функции, которые сравнивать с Pos будет неверно.

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

← →
Sha © (2004-10-01 10:41) [145]

> Defunct © (01.10.04 10:27) [144]
> Зато на больших строках получилось обогнать все функции

Наверное, точнее так: на больших строках с образом в конце.
Не забывай, что просто для таких строк Джон еще не написал свою функцию :)

PS. Твой результат действительно очень хорош.
Не желаешь принять участие в FastCode?

← →
Defunct © (2004-10-01 11:44) [146]

> Не желаешь принять участие в FastCode?

на тему?

← →
Sha © (2004-10-01 11:52) [147]

Тем там много...
Можно заново открыть PosChallenge, если ты усовершенствуешь свою функцию.
Кстати, было бы неплохо выложить здесь окончательный вариант.

← →
Defunct © (2004-10-01 12:01) [148]

> Тем там много...
это хорошо

> Кстати, было бы неплохо выложить здесь окончательный вариант.
Не вопрос, как только закончу, и тест покажет что функция прошла Validate тест сразу выложу.

> функция прошла Validate

вот, например
const S1="AV"; S2="Guru AV";

procedure TForm1.Button1Click(Sender: TObject);
begin
Caption := Format("Sha = %d, Pos = %d, defunct = %d",
[PosShaPas(S1, S2), Pos(S1, S2), ConstantPos(S1, S2)]);
// Sha = 6, Pos = 6, defunct = 0
end;

← →
Alekc (2004-10-01 20:38) [150]

Кто-то спрашивал почему у борланда такие неоптимальные функции: если тут столько народу одну Pos так долго оптимизирует, то сколько б времени у Borland"ы ушло на всё RTL/VCL ? 10 лет ? :о)

> Sha

Я не понимаю, что я делаю не так, для маленьких строк никак не могу улучшить показания теста. Привожу функцию, которая прошла все 11 Validate тестов. Гляньте, может заметите, что там не так при маленьких строках. На больших строках эта функция побила все, в т.ч. и PosJohMMX_a.

Function ConstantPos(const Constant, Buffer: string): Integer; Assembler; Asm Test eax, eax Jz @@NotFound_Exit {Exit if SubStr = ""} Test edx, edx Jz @@NotFound_Exit {Exit if Str = ""} Mov ECx, [EDx-4] Test ECx, ECx Jz @@NotFound_Exit Cmp [EAx-4],1 Jnz @@WideSearch Cmp ECx,8 Ja @@WideScan // CharPos @@Scan4: Mov Al,[EAx] Push EDi Add EDx, ECx Xchg EDi, EDx Mov EDx, ECx Not ECx Inc ECx @@SLoop4: Cmp AL, [EDi+ECx] Jz @@Found4 Inc ECx Jnz @@SLoop4 Xor EAx, EAx Pop EDi Ret @@Found4: Mov EAx, EDx Add EAx, ECx Inc EAx Pop EDi Ret @@WideScan: Mov Al,[EAx] Mov Ah, Al // Spreading char to 32bit register MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 Push ECx @@Scan5: MovQ MM7, [EDx] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) PACKSSWB MM7, MM7 MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound2 // yes - 1st char of the constant was found Add EDx,8 // correct index Sub ECx,8 // and buffer size Jns @@Scan5 // continue scan if buffer not empty @@Exit_False2: Emms Pop EAx Xor EAx, EAx Ret @@CharFound2: MovQ MM7, [EDx] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) MovD EAx, MM7 Test EAx, EAx Jnz @@Loop2 Sub ECx,4 PSRLQ MM7,32 MovD EAx, MM7 @@Loop2: Dec Ecx Test Al,Al Js @@Check2 Shr EAx,8 Jmp @@Loop2 @@Check2: Test ECx,ECx Js @@Exit_False2 Emms Pop EAx Sub EAx, ECx Ret @@WideSearch: Push EDi Push ESi Push EBx Push EBp MOV ESI, EAX // ESi pointer to constant Mov EDi, EDx // EDi pointer to buffer Push ECx // store total buffer size for later calculation pos Mov EBX, [ESI-4] Test EBx, EBx Jz @@Exit_False Mov Al, [ESi] // Store first char of the constant in AL Cmp EBx, ECx Ja @@Exit_False Jnz @@Normal_Work Cmp AL, [Edi] Jnz @@Exit_False @@Normal_Work: Dec EBX Mov Ah, [ESi+EBx] // Store last char of the constant in AH Dec EBx Mov EDx,ECx // EDx - Stored residual buffer size Inc ESi Mov EBp, ESi // EBp - stored pointer to 2nd char of constant Cmp ECx, 8 Ja @@Wide_String @@Scan3: Xor ECx, ECx @@SLoop: Cmp AL, [Edi+ECx] Jz @@Found Inc ECx Cmp ECx, EDx Jb @@SLoop Jmp @@Exit_False @@Found: Inc ECx Add EDi,ECx Sub EDx, ECx Mov ECx, EDx Cmp EBx, EDx Jge @@Exit_False Jmp @@CheckLastChar {} @@Wide_String: MovD MM4, EAx // store EAx in MM buffer Mov Ah, Al // Spreading char to 32bit register MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 PXOR MM5,MM5 // Z mask for later calculations @@Scan: MovQ MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) PACKSSWB MM7,MM7 MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound // yes - 1st char of the constant was found Add EDi,8 // correct index Sub ECx,8 // and buffer size Jns @@Scan // continue scan if buffer not empty Jmp @@Exit_False // otherwise - leave with no result @@CharFound: MovQ MM7, [Edi] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) MovD EAx, MM7 Test EAx, EAx Jnz @@Loop1 Add EDi,4 Sub ECx,4 PSRLQ MM7,32 MovD EAx, MM7 @@Loop1: inc EDi dec Ecx Test Al,Al Js @@Check Shr EAx,8 Jmp @@Loop1 @@Check: MovD EAx, MM4 // restore EAx (1st and last chars of the constant) @@CheckLastChar: // as proposed in Boyer-Mur alhorithm Mov EDx, ECx // store new residual buffer size Test EDx, EDx Js @@Exit_False Test EBx, EBx Js @@Constant_Exists Cmp Ah, [EBx+Edi] // check found substring with last char of the constant Jz @@CompareWholeString // not match - continue searching Cmp EDx,8 Jnb @@Scan Jmp @@Scan3 @@Exit_False: Pop EAx Xor EAx,EAx // False = (0), check delphi help for more info Jmp @@Leave_Proc @@NotFound_Exit: Xor EAx, EAx Ret @@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx // constant still can be settled in buffer Jna @@Exit_False // no - exit with false result Push EDi Mov ECx, Ebx // ECx - constant chars amount shr ECx, 2 // ECx - constant chars amount div 4 jz @@SkipDTest Repe CmpsD Jnz @@SkipBTest @@SkipDTest: Mov ECx, Ebx and ECx, 3 jz @@Constant_Exists2 // two least significant bits // of amount are zero so the Constant matches Repe CmpsB Jz @@Constant_Exists2 @@SkipBTest: Pop EDi Mov ESi, EBp // restore pointer to 2nd char of constant // Add EDx, ECx // Sub EDx, EBx // correct residual buffer size Mov ECx, EDx // restore residual buffer size to ECx Cmp EDx,8 Jb @@Scan3 Jmp @@Scan @@Constant_Exists2: Add ESp, 4 @@Constant_Exists: Pop EAx Sub EAx, EDx @@Leave_Proc: EMMS // finish mmx operations Pop EBp Pop EBx Pop ESi Pop EDi End;

>Defunct © (02.10.04 01:50) [151]

1. Главное, что отличает функцию-победитель от других - очень быстрая выдача результата в случае нахождения образца в первых 8 позициях после начала сканирования первого символа. Анализ этих позиций вынесен из цикла и проводится очень быстро. Это позволяет отложить подготовительные действия для организации цикла (и сам цикл) до тех пор пока они действительно не потребуются, или иногда вообще их не выполнять.
В результате, даже, если даже цикл и будет выполняться, то будет сэкономлено несколько команд перехода и насыщение цикла наступит позднее.
Также имей ввиду, что использование MMX для строк короче 20 сиволов неоправданно из-за больших расходов на подготовку.

2. В следующем цикле
@@SLoop4: Cmp AL, [EDi+ECx] Jz @@Found4 Inc ECx Jnz @@SLoop4
имеет смысл "inc ecx" заменить на "add ecx,1". После такой замены состояние регистра флагов для второго сравнения будет полностью определяться предыдущей командой, а не формироваться как результат выполнения cmp и inc.
Еще лучше развернуть цикл в 2 или 4 раза.

3. Этот цикл тоже лучше развернуть.
@@SLoop: Cmp AL, [Edi+ECx] Jz @@Found Inc ECx Cmp ECx, EDx Jb @@SLoop

так имхо немного быстрее будет CompareWholeString -
поиск в обратном порядке.
@@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx // constant still can be settled in buffer Jna @@Exit_False // no - exit with false result // Push EDi MOV ECX, EBX @@CW_Loop: SUB ECX, 4 JZ @@CW_LastDWord JL @@CW_Last123bytes MOV EAX, [ESi+ECx] CMP EAX, [EDi+ECx] JNE @@SkipBTest JMP @@CW_Loop @@CW_LastDWord: MOV EAX, [ESi] CMP EAX, [EDi] JNE @@SkipBTest JMP @@Constant_Exists @@CW_Last123bytes: ADD ECX, 2 JZ @@Last2 JNS @@Last3 JS @@Last1 @@Last3: MOV AX, [ESi] CMP AX, [EDi] JNE @@SkipBTest MOV AL, [ESi+2] CMP AL, [EDi+2] JNE @@SkipBTest JMP @@Constant_Exists @@Last2: MOV AX, [ESi] CMP AX, [EDi] JNE @@SkipBTest JMP @@Constant_Exists @@Last1: MOV AX, [ESi] CMP AX, [EDi] JNE @@SkipBTest JMP @@Constant_Exists @@SkipBTest: // Pop EDi // Mov ESi, EBp // restore pointer to 2nd char of constant // Add EDx, ECx // Sub EDx, EBx // correct residual buffer size Mov ECx, EDx // restore residual buffer size to ECx Cmp EDx,8 Jb @@Scan3 Jmp @@Scan @@Constant_Exists: Pop EAx Sub EAx, EDx

> @@Last1:
> MOV AX, [ESi]
> CMP AX, [EDi]
> JNE @@SkipBTest
> JMP @@Constant_Exists

MOV AL, [ESi] // Of course a byte-sized operand is meant CMP AL, [EDi] // That"s a kinda ctrl-C+ctrl-V eror :)

> GuAV

Сейчас я сижу за K6 и не могу проверить скорость на P4,
но два перехода подряд приводят к потерям тактов.

Вот... тестить ща не могу... могут быть ошибки..
@@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx // constant still can be settled in buffer Jna @@Exit_False // no - exit with false result // Push EDi MOV ECX, EBX @@CW_Loop: SUB ECX, 4 JL @@CW_Last123bytes MOV EAX, [ESi+ECx] JZ @@CW_LastDWord // SUB ECX, 4 result was 0 CMP EAX, [EDi+ECx] JE @@CW_Loop Mov ECx, EDx JMP @@SkipBTest1 @@CW_LastDWord: // MOV EAX, [ESi] CMP EAX, [EDi] JE @@Constant_Exists Mov ECx, EDx JMP @@SkipBTest1 @@CW_Last123bytes: ADD ECX, 2 JS @@Last1 // JNS @@Last3 @@Last3: MOV AX, [ESi] JZ @@Last2 CMP AX, [EDi] JNE @@SkipBTest MOV AL, [ESi+2] CMP AL, [EDi+2] JE @@Constant_Exists Mov ECx, EDx JMP @@SkipBTest1 @@Last2: // MOV AX, [ESi] CMP AX, [EDi] JE @@Constant_Exists Mov ECx, EDx JMP @@SkipBTest1 @@Last1: MOV AL, [ESi] CMP AL, [EDi] //JNE @@SkipBTest JE @@Constant_Exists @@SkipBTest: // Pop EDi // Mov ESi, EBp // restore pointer to 2nd char of constant // Add EDx, ECx // Sub EDx, EBx // correct residual buffer size Mov ECx, EDx // restore residual buffer size to ECx @@SkipBTest1: // Mov ECx, EDx moved to places to jump from Cmp EDx,8 Jb @@Scan3 Jmp @@Scan

@@WideScan: Mov Al,[EAx] Mov Ah, Al // Spreading char to 32bit register MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 Push ECx @@Scan5: MovQ MM7, [EDx] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) PACKSSWB MM7, MM7 MovD EAx, MM7 // get mixed dword Test EAx, EAx // was there at least 1 bit set? Jnz @@CharFound2 // yes - 1st char of the constant was found Add EDx,8 // correct index Sub ECx,8 // and buffer size Jns @@Scan5 // continue scan if buffer not empty

тут, в слуаче ECx<8 выход за пределы буфера, причём аж до 7 байт.

при Validate test надо делать как нибудь чтобы нельзя было читать из S[Length(S)+1], где S это и Constant и Buffer
У меня сейчас две идеи: или Break Point на чтение данных или VirtualProtect...

возможно с WideSearch то же, этого кода я вообще не понял...

GuAV © (03.10.04 00:34) [158]

Я делал проверку через VirtualProtect в одном из Challenge, не помню в каком. Надо порыться... Позже...

> GuAV © (03.10.04 00:34) [158]
> тут, в слуаче ECx<8 выход за пределы буфера, причём аж до 7 байт.

Я тут по такому случаю написал еще одну процедуру проверки.
Поразительно, но данный тест ConstantPos проходит.
Разберусь в понедельник если время будет, сейчас еду на дачу.

//Protect/unprotect 4k-block at the end of string procedure SetStringProtected(var s: string; var flags: dword); const block= 4*1024; var p, q: pchar; begin if (flags and PAGE_NOACCESS)<>0 then begin; SetLength(s,3*block); FillChar(s[1],Length(s),0); end; p:=pointer(s); integer(q):=(integer(p) and -block) + 2*block; if (flags and PAGE_NOACCESS)<>0 then pinteger(p-4)^:=(q-p)-1 //Trunk the string else pinteger(p-4)^:=3*block; //Restore string length VirtualProtect(pchar(q),1,flags,@flags); //Set protection flags end; function TMainForm.Validate0: boolean; var s: string; p: pchar; q: pointer; flags: dword; len: integer; begin; flags:=PAGE_NOACCESS; SetStringProtected(s, flags); try len:=Length(s); //Now Length(s)>4k. s[len-0]:="h"; s[len-1]:="g"; s[len-2]:="f"; s[len-3]:="e"; s[len-4]:="d"; s[len-5]:="c"; s[len-6]:="b"; s[len-7]:="a"; Result:=(PosFunction("abcdefgh", s)=len-7) and (PosFunction("bcdefgh", s)=len-6) and (PosFunction("cdefgh", s)=len-5) and (PosFunction("defgh", s)=len-4) and (PosFunction("efgh", s)=len-3) and (PosFunction("fgh", s)=len-2) and (PosFunction("gh", s)=len-1) and (PosFunction("h", s)=len-0) and (PosFunction("abcdefg9", s)=0) and (PosFunction("bcdefg9", s)=0) and (PosFunction("cdefg9", s)=0) and (PosFunction("defg9", s)=0) and (PosFunction("efg9", s)=0) and (PosFunction("fg9", s)=0) and (PosFunction("g9", s)=0) and (PosFunction("9", s)=0) and (PosFunction("9h", s)=0) and (PosFunction("9gh", s)=0) and (PosFunction("9fgh", s)=0) and (PosFunction("9efgh", s)=0) and (PosFunction("9defgh", s)=0) and (PosFunction("9cdefgh", s)=0) and (PosFunction("9bcdefgh", s)=0); //Construct the string inplace. p:=pchar(pointer(s))+(len+1-8); //Set address pInteger(p-4)^:=7; //Set length pInteger(p-8)^:=1; //Set reference count q:=p; Result:=Result and (PosFunction("bcdefgh", string(q))=1) and (PosFunction("cdefgh", string(q))=2) and (PosFunction("defgh", string(q))=3) and (PosFunction("efgh", string(q))=4) and (PosFunction("fgh", string(q))=5) and (PosFunction("gh", string(q))=6) and (PosFunction("h", string(q))=7) and (PosFunction("bcdefg9", string(q))=0) and (PosFunction("cdefg9", string(q))=0) and (PosFunction("defg9", string(q))=0) and (PosFunction("efg9", string(q))=0) and (PosFunction("fg9", string(q))=0) and (PosFunction("g9", string(q))=0) and (PosFunction("9", string(q))=0) and (PosFunction("9h", string(q))=0) and (PosFunction("9gh", string(q))=0) and (PosFunction("9fgh", string(q))=0) and (PosFunction("9efgh", string(q))=0) and (PosFunction("9defgh", string(q))=0) and (PosFunction("9cdefgh", string(q))=0); except Result:=false; end; SetStringProtected(s, flags); if Result then begin; ErrorEdit0.Text := "Passed Validate0"; ErrorEdit0.Color := clGreen; end else begin; ErrorEdit0.Text := "Failed Validate0"; ErrorEdit0.Color := clRed; end; Update; end;

Поиск в бинарном файле Найти похожие ветки