| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск в бинарном файле [D5, WinXP]
Dimaxx © (2004-09-24 23:32:00)
Страницы: < 1 2 3 4 5 6 7 8 9 10 ... 13 14 >
Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.
Defunct (2004-10-01 10:27:00) [121]> посмотрел тест [137] недостаток теста в том, что он был
> нацелен именно, на поиск подстроки в строке. Функция же [139]
> больше нацелена на поиск подстроки в файле, т.е.
> предполагается просмотр не одного буфера а немкольких
Имел в виду, что тест не полностью отражает возможности функций. Не учитывается скорость поиска в больших см. сабж до 1Gb строках.
> Поиск малых строк среди малых строк (первые 35 тестов).
Я так и думал. Крутил и так и сяк, на малых строках существенно проигрываю, PosJoh и PosSha. (в PosJoh заметил ведется отдельная обработка маленьких строк)
Зато на больших строках получилось обогнать все функции:
просматриваемый буфер делится на 2 кадра, в каждом кадре просмотр ведется в двух направлениях.
> Для других условий пишутся другие функции, которые сравнивать с Pos будет неверно.
согласен, но так или иначе, даже с оптимизацией совсем под другую задачу (сабж) результат сравнения с Pos тоже не плох, индекс 416 (как я понял в 3 раза быстрее стандартной Pos) по вашему тесту дают не многие функции.
Sha (2004-10-01 09:44:00) [122]> Defunct
> Буфер поиска - 1Mb.
Многовато будет :) Наиболее частое применение Pos - поиск первого вхождения в строке до 100 символов. В случае успеха в среднем результат поиска не превышает 40. Именно для этих условий и должна проводиться оптимизация. Для других условий пишутся другие функции, которые сравнивать с Pos будет неверно.
> Следует отметить неоспоримое преимущество приведенной здесь
> функции, она в отличие от [120] способна работать на
> процессорах у которых нет MMX.
По приведенной мной ссылке ты можешь найти реализации Pos на любой вкус.
> ни старая, ни исправленная функции не выходили за границу буфера.
Извини, значит, я был недостаточно внимателен. Тогда пункты 4 и 5 снимаются.
> посмотрел тест [137] недостаток теста в том, что он был
> нацелен именно, на поиск подстроки в строке. Функция же [139]
> больше нацелена на поиск подстроки в файле, т.е.
> предполагается просмотр не одного буфера а немкольких
Вот это я совсем не понял.
> SubBench1 относится к маленьким строкам я правильно понимаю?
Поиск малых строк среди малых строк (первые 35 тестов).
Defunct (2004-10-01 06:17:00) [123]> 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 относится к маленьким строкам я правильно понимаю?
Defunct (2004-10-01 03:14:00) [124]посмотрел тест [137] недостаток теста в том, что он был нацелен именно, на поиск подстроки в строке. Функция же [139] больше нацелена на поиск подстроки в файле, т.е. предполагается просмотр не одного буфера а немкольких. Поэтому по одному тесту скорости у нее высокая оценка (SubBench2), а по второму (SubBench1) - низкая, суммарная оценка получалась лучше чем RTL/RTLa/b но значительно хуже чем у PosJoh и PosSha, сейчас внесу поправки с учетом изменения задачи.
Defunct (2004-10-01 02:28:00) [125]> [139] (1.25Gb пересмотр).
не там точку поставил.
12.5Gb пересмотр.
Defunct (2004-10-01 02:25:00) [126]Ок, со всем здесь услышанным, подправил [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.
ни старая, ни исправленная функции не выходили за границу буфера.
Sha (2004-10-01 00:38:00) [127]> Defunct
5. Похоже, твоя функция иногда будет выдавать неверный результат (следствие пункта 4):
ConstantPos(#0,'Мы находим даже терминатор')>0
Sha (2004-10-01 00:16:00) [128]> GuAV © (30.09.04 23:58) [135]
> Какие размеры для замера предлагаете?
Предлагаю использовать неплохой (хотя и не без нереканий) вариант
http://dennishomepage.gugs-cats.dk/PosBV45.zip
Sha (2004-10-01 00:12:00) [129]> 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.
GuAV (2004-09-30 23:58:00) [130]Sha © (30.09.04 23:53) [134]
Какие размеры для замера предлагаете?
имхо 0, 128 байт, 1 кБ и 1 МБ.
Sha (2004-09-30 23:53:00) [131]> Defunct
1. Функция не является полным аналогом Pos.
Не будет работать для пустых строк, т.к. за длиной строки полезет по адресу (0-4)=FFFFFFFC.
2. Не корректно замерять скорость Pos на файлах или на буфере длиной 2Gb. Погрешности за счет дисковых очень велики и не предсказуемы.
Defunct (2004-09-30 23:46:00) [132]Вот более достоверные результаты (просмотр 25Gb):
[132] - 42.230 сек
[120] - 38.800 сек
[123] - 46.831 сек
Опять же скорость сильно зависит от частоты появления первого символа искомой подстроки, причем для всех трех функций.
2 Sha, если вашу функцию сделать в MMX исполнении, она поидее побъет всех ;) т.к. [132] без MMX - 65.453
Defunct (2004-09-30 23:22:00) [133]> Дай полный код своего аналога 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.
GuAV (2004-09-30 22:40:00) [134]
> Пока не не адаптировал фукнкцию к 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
Sha (2004-09-30 22:27:00) [135]> Defunct © (30.09.04 22:24) [128]
Дай полный код своего аналога Pos. Я его завтра потестирую.
Defunct (2004-09-30 22:26:00) [136]> а также маленькой хитрости - изменения направления сравнения.
О, стоит применить к [112] ;)
Defunct (2004-09-30 22:24:00) [137]С вот таким вот изменением, скорость [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 раз подряд).
Sha (2004-09-30 22:22:00) [138]> Defunct © (30.09.04 21:05) [124]
> За счет чего достигается такое быстродействие в [123]?
За счет алгоритма, основанного на использовании внутреннего представления AnsiString, двухкратного развертывания циклов поиска первого совпадения и сравнения последующих символов, а также маленькой хитрости - изменения направления сравнения.
Так что дело тут, как видишь, совсем не в выборе языка :)
Defunct (2004-09-30 21:37:00) [139]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]).
GuAV (2004-09-30 21:20:00) [140]У меня быстрее [120], [123] немного медленнее.
на коротком файле (autoecex.bat) быстрее всего [112].
Celeron 2000, win9x.
не ММХ - ф-ция ваще в пролёте.
| |
