| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Поиск в бинарном файле [D5, WinXP]

Страницы:   < 1 2 3 4 5 6 7 8 9 10 ... 13 14 >

Dimaxx ©   (2004-09-24 23:32:00) 

Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.

---

Ihor Osov'yak   (2004-10-06 01:06:00) [61]

Ребята, влом отслеживать полет изменений кода.. :-)
Если можно, полный код в студию...

---

GuAV   (2004-10-06 01:03:00) [62]

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

Я сам уже понял, когда написал WideScan а он не хочет проходить валидацию. Вот код, если интересно:

@@WideScan:
 Cmp  ECx, 16
 Jb   @@SmallScan

 Mov  Al,[EAx]
 Mov  Ah, Al
 MovD MM6, EAx
 PUNPCKLWD MM6, MM6
 PUNPCKLDQ MM6, MM6

 Push EBx
 Push ECx
 Mov  EBx, ECx
 And  EBx, not 7
 And  ECx, 7
 Jz   @@ReverseScan
 Xor  ECx, ECx

@@RemainingDword:
 MovD      MM7, [EDx+EBx]  // 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        // get mixed dword
 Test  EAx, EAx
 Jnz   @@FoundInDWord
 Add  ECx, 4
 Jna  @@ReverseScan

 MovD      MM7, [EDx+EBx+4]  // 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        // get mixed dword
 Test  EAx, EAx
 Jnz   @@FoundInDWord

 Jmp  @@ReverseScan

@@FoundInDWord:
 Inc   Ecx
 Test  Al,Al
 Js    @@InDWord_pos
 Shr   EAx,8
 Jmp   @@FoundInDWord

@@InDWord_pos:
 Emms
 Pop  EAx
 Test ECx, ECx
 Js   @@InDWord_Failed
 Mov  EAx, ECx
 Add  EAx, EBx
 Pop  EBx
 Ret

@@InDWord_Failed:
 Xor  EAx, EAx
 Pop  EBx
 Ret

@@ReverseScan:
 Mov  ECx, EBx
@@ScanLoop:
 Sub       ECx, 8
 Js        @@ScanLoopExit
 MovQ      MM7, [EDx+ECx]
 PCMPEQB   MM7, MM6
 PACKSSWB  MM7, MM7
 MovD  EAx, MM7
 Test  EAx, EAx
 Jz   @@ScanLoop

@@ScanLoopFound:
 MovQ      MM7, [EDx+ECx]
 PCMPEQB   MM7, MM6
 MovD  EAx, MM7
 Test  EAx, EAx
 Jnz   @@SLFoundInDword
 Add   ECx,4
 PSRLQ MM7,32
 MovD  EAx, MM7
@@SLFoundInDword:
 Inc   Ecx
 Test  Al,Al
 Js    @@SLInDWord_pos
 Shr   EAx,8
 Jmp   @@SLFoundInDword

@@SLInDWord_pos:
 Mov   EAx, ECx
 Pop   ECx
 Pop   EBx
 Emms
 Ret

@@ScanLoopExit:
 Pop   ECx
 Pop   EBx
 Xor   EAx, EAx
 Emms
 Ret

---

Defunct   (2004-10-05 23:31:00) [63]

> ИМХО, ещё быстрее будет, если искать в обратном порядке.

Не совсем понял вашу идею. Можно пояснить? мы же ищем первое вхождение, а если сканировать в обратном порядке, тогда можно получить неверный результат.

PS: для инициализации MMX требуется значительное время, сканирование целесообразно делать на MMX только для больших строк.

---

GuAV   (2004-10-05 22:15:00) [64]

> Попробуйте для Celeron'a найти наилучшее соотношение символов
> в строке, которое обробатывается как маленькая строка. Поменяйте
> цифры в сл. коде:

Лучше не становится, только хуже.

ИМХО, ещё быстрее будет, если искать в обратном порядке. Можно сначала что-то типа And ECx, 7 и просмотреть остаток, потом вернуть ECx и сделать And ECx not 7 и искать строку используя ММХ... это ИМХО сделает запрет выхода за буфер проще.... попробую сам сделать... если получится, выложу.

---

Defunct   (2004-10-05 13:50:00) [65]

> Поздравляю! Пора заново открывать PosChallenge.
пасиба

GuAV ©   (05.10.04 12:19) [197]
> Не всё так однозначно...

Попробуйте для Celeron'a найти наилучшее соотношение символов в строке, которое обробатывается как маленькая строка. Поменяйте цифры в сл. коде:

 ....
 Cmp  ECx,32
 Jb   @Small_String
 ...
 ...
 Cmp  ECx, 16
 Jb   @@SmallScan

Sha ©   (05.10.04 12:25) [198]
> Подправь свою функцию, чтобы проходила тест Validation0 (здесь учтены предложения GuAV):

Ок вечерком, посмотрю.

---

Sha   (2004-10-05 12:29:00) [66]

> GuAV ©   (05.10.04 12:19) [197]

> Не всё так однозначно...
про Celeron скоро можно будет забыть

> У них там случайно Case-unsensitive Pos нету ?
Нет. Все, что есть, здесь http://dennishomepage.gugs-cats.dk/FastCodeProject.htm

---

Sha   (2004-10-05 12:25:00) [67]

> Defunct ©   (05.10.04 04:39) [193]

Подправь свою функцию, чтобы проходила тест Validation0 (здесь учтены предложения GuAV):

procedure SetStringProtected(var s: string; var flags: dword);
const
 block= 4*1024;
var
 p, q: pchar;
begin
 if (flags and PAGE_NOACCESS)<>0 then SetLength(s,3*block);

 p:=pointer(s);
 integer(q):=(integer(p) and -block) + 2*block;

 if (flags and PAGE_NOACCESS)<>0
 then pinteger(p-4)^:=(q-p)-1
 else pinteger(p-4)^:=3*block;

 VirtualProtect(q,1,flags,@flags);
 end;

function ValidateStringProtected(var s: string; LengthToValidate: integer): boolean;
var
 len: integer;
 p: pointer;
begin;
 len:=Length(s);
 if ((LengthToValidate and 3)<>3)
 or (LengthToValidate<3)
 or (LengthToValidate>len-8) then begin;
   Result:=false;
   exit;
   end;

 FillChar(s[1],len,0);
 s[len-0]:='g';
 s[len-1]:='f';
 s[len-2]:='e';
 s[len-3]:='d';
 s[len-4]:='c';
 s[len-5]:='b';
 s[len-6]:='a';

 p:=pchar(pointer(s))+(len-LengthToValidate);
 pInteger(pchar(p)-4)^:=LengthToValidate;
 pInteger(pchar(p)-8)^:=1;

 Result:=(PosFunction('abcdef9', string(p))=0)
     and (PosFunction('bcdef9', string(p))=0)
     and (PosFunction('cdef9', string(p))=0)
     and (PosFunction('def9', string(p))=0)
     and (PosFunction('ef9', string(p))=0)
     and (PosFunction('f9', string(p))=0)
     and (PosFunction('9', string(p))=0)
     and (PosFunction('9g', string(p))=0)
     and (PosFunction('9fg', string(p))=0)
     and (PosFunction('9efg', string(p))=0)
     and (PosFunction('9defg', string(p))=0)
     and (PosFunction('9cdefg', string(p))=0)
     and (PosFunction('9bcdefg', string(p))=0)
     and (PosFunction('g', string(p))=LengthToValidate-0)
     and (PosFunction('fg', string(p))=LengthToValidate-1)
     and (PosFunction('efg', string(p))=LengthToValidate-2)
     and ((LengthToValidate=3)
      or (PosFunction('defg', string(p))=LengthToValidate-3)
     and (PosFunction('cdefg', string(p))=LengthToValidate-4)
     and (PosFunction('bcdefg', string(p))=LengthToValidate-5)
     and (PosFunction('abcdefg', string(p))=LengthToValidate-6));
 end;

function TMainForm.Validate0: boolean;
var
 s: string;
 flags: dword;
begin;
 flags:=PAGE_NOACCESS;
 SetStringProtected(s, flags);
 try
   Result:=ValidateStringProtected(s, 3)
       and ValidateStringProtected(s, 7)
       and ValidateStringProtected(s, 11)
       and ValidateStringProtected(s, 15)
       and ValidateStringProtected(s, 1023)
       and ValidateStringProtected(s, 1027);
 except
   Result:=false;
   end;
 SetStringProtected(s, flags);

 if Result then begin;
   ErrorEdit1.Text := 'Passed Validate0';
   ErrorEdit1.Color := clGreen;
  end
 else begin;
   ErrorEdit1.Text := 'Failed Validate0';
   ErrorEdit1.Color := clRed;
  end;
 Update;
 end;

---

GuAV   (2004-10-05 12:19:00) [68]

Defunct ©   (05.10.04 05:06) [195]
Не всё так однозначно...

PosJOH_SSE_a    4  193  186  379
PosJOH_SSE_b    C  198  181  379
PosDefunct      4  220  165  385
PosJOH_MMX_b    4  203  187  390
PosJOH_MMX_a    4  203  192  395
PosJOH_SSE2_a   4  214  187  401
PosJOH_SSE2_b   0  214  187  401

ps: Celeron 2000 MHz Northwood L2=128 kB

Sha ©   (05.10.04 10:42) [196]
У них там случайно Case-unsensitive Pos нету ?

---

Sha   (2004-10-05 10:42:00) [69]

> Defunct ©   (05.10.04 05:06) [195]

Поздравляю! Пора заново открывать PosChallenge.

Кстати, в FastCode намечается StringReplaceChallenge, можешь применить свои наработки там.

---

Defunct   (2004-10-05 05:06:00) [70]

[194] зззз.. так и знал..

Результаты тестирования на P4-2.8


Функция         Смещ. SB1   SB2 Overall

PosDef_MMX.......C....194...139...333
PosShaPas_b......8....194...169...362
PosJOH_MMX_a.....4....200...164...364
PosJOH_MMX_b.....4....202...162...364
PosShaPas_a......4....198...167...366
PosJOH_SSE_a.....4....198...175...373
PosJOH_SSE_b.....C....198...175...373
PosJOH_IA32_b....0....194...183...377
PosJOH_IA32_a....C....197...183...380
PosJOH_SSE2_b....0....213...169...381
PosJOH_SSE2_a....4....214...169...383
PosJOH_PAS_a.....4....309...255...564
PosJOH_PAS_b.....0....320...250...570
PosDKC65_b.......0....366...267...633
PosDKC65_a.......8....394...267...661
PosRL1_b.........C....420...480...900
PosRTL...........4....530...628...1158

Результаты тестирования на P2-400:


Функция         Смещ.  SB1   SB2   Overall

PosDef_MMX.......C....1168...699....1867
PosJOH_IA32_b....0....1115...964....2079
PosJOH_MMX_a.....4....1164...925....2089
PosJOH_MMX_b.....4....1176...927....2103
PosJOH_IA32_a....C....1128...989....2117
PosShaPas_a......4....1120...1345...2464
PosShaPas_b......8....1111...1386...2497
PosDKC65_b.......0....1468...1319...2787
PosDKC65_a.......8....1486...1336...2822
PosJOH_PAS_a.....4....1512...2009...3521
PosJOH_PAS_b.....0....1558...2058...3616
PosRL1_b.........C....1423...2904...4327
PosRTL...........4....1721...3224...4945

вот теперь можно спокойно идти спать с чуством выполненного долга
;)

---

Defunct   (2004-10-05 04:55:00) [71]

Результаты тестирования на P4-2.8


Функция         Смещ. SB1 SB2 Overall

PosDef_MMX C 194 139 333
PosShaPas_b 8 194 169 362
PosJOH_MMX_a 4 200 164 364
PosJOH_MMX_b 4 202 162 364
PosShaPas_a 4 198 167 366
PosJOH_SSE_a 4 198 175 373
PosJOH_SSE_b C 198 175 373
PosJOH_IA32_b 0 194 183 377
PosJOH_IA32_a C 197 183 380
PosJOH_SSE2_b 0 213 169 381
PosJOH_SSE2_a 4 214 169 383
PosJOH_PAS_a 4 309 255 564
PosJOH_PAS_b 0 320 250 570
PosDKC65_b 0 366 267 633
PosDKC65_a 8 394 267 661
PosRL1_b C 420 480 900
PosRTL         4 530 628 1158

Результаты тестирования на P2-400:

Функция         Смещ. SB1 SB2 Overall

PosDef_MMX C 1168 6991867
PosJOH_IA32_b 0 1115 964 2079
PosJOH_MMX_a 4 1164 925 2089
PosJOH_MMX_b 4 1176 927 2103
PosJOH_IA32_a C 1128 989 2117
PosShaPas_a 4 1120 1345 2464
PosShaPas_b 8 1111 1386 2497
PosDKC65_b 0 1468 1319 2787
PosDKC65_a 8 1486 1336 2822
PosJOH_PAS_a 4 1512 2009 3521
PosJOH_PAS_b 0 1558 2058 3616
PosRL1_b C 1423 2904 4327
PosRTL         4 1703 3238 4940
PosRTL         4 1721 3224 4945

SB1 - Время прохождения теста работы с маленькими строками (до 8-ми символов)
SB2 - Время прохождения теста работы с большими строками (больше 8-ми символов)

Надеюсь таблица нормально запостится.

---

Defunct   (2004-10-05 04:39:00) [72]

Итак долгожданный победитель заезда ;)


Function ConstantPos(const Constant, Buffer: string): Integer; Assembler;
Asm
  Test eax, eax
  Jz   @@NotFound_Exit    
  Test edx, edx
  Jz   @@NotFound_Exit    
  Mov  ECx, [EDx-4]
  Test ECx, ECx
  Jz   @@NotFound_Exit
  Cmp  [EAx-4],1
  Jnz   @@WideSearch

  Cmp   ECx,8
  Ja    @@WideScan

// CharPos
@@Scan4:
  Mov  Ch,[EAx]
// Ch - char
// EDx - pointer to buffer
// cl - length
@@CharPos:
  Mov  EAx,[EDx]

  Cmp  Ch,Al
  Jz   @Found1
  cmp  Ch,Ah
  Jz   @Found2
  Shr  EAx,16
  Cmp  Ch,Al
  Jz   @Found3
  Cmp  Ch,Ah
  Jz   @Found4

  Cmp  Cl,4
  Jna  @NotFound
  Mov  EAx,[EDx+4]

  Cmp  Ch, Al
  Jz   @Found5
  Cmp  Ch, Ah
  Jz   @Found6
  Shr  EAx, 16
  Cmp  Ch, Al
  Jz   @Found7
  Cmp  Ch, Ah
  Jz   @Found8

@NotFound:
  XOr  EAx, EAx
  Ret
@Found1:
  Mov  EAx,1
  Jmp  @Validation
@Found2:
  Mov  EAx,2
  Jmp  @Validation
@Found3:
  Mov  EAx,3
  Jmp  @Validation
@Found4:
  Mov  EAx,4
  Jmp  @Validation
@Found5:
  Mov  EAx,5
  Jmp  @Validation
@Found6:
  Mov  EAx,6
  Jmp  @Validation
@Found7:
  Mov  EAx,7
  Jmp  @Validation
@Found8:
  Mov  EAx,8
  Jmp  @Validation

@Validation:
  Cmp  Al,Cl
  Ja   @NotFound
  ret

  nop
  nop                  // alignment for better performance

@@SmallScan:
  Push  ECx
  Mov   Ch,[EAx]
@@Scan8:
  Push  ECx
  Call  @@CharPos
  Pop   ECx
  Test  EAx, EAx
  Jz    @Validation3

  Sub   Cl, Al
  Pop   EAx
  Sub   Al, Cl
  Ret

@Validation3:
  Sub   Cl, 8
  Add   EDx, 8
  Cmp   Cl, 0
  Jg    @@Scan8

  Add   ESP, 4
  Ret

@@LastDword2:
  Test ECx, ECx
  Js   @@Exit_False2
  Jz   @@Exit_False2
  MovD      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        // get mixed dword
  Test  EAx, EAx
  Jnz   @@Loop2
  Jz    @@Exit_False2

@@WideScan:
  Cmp  ECx, 16
  Jb   @@SmallScan
  Mov  Al,[EAx]
  Mov  Ah, Al
  MovD MM6, EAx
  PUNPCKLWD MM6, MM6
  PUNPCKLDQ MM6, MM6

  Push ECx
@@Scan5:
  MovQ      MM7, [EDx]
  PCMPEQB   MM7, MM6
  PACKSSWB  MM7, MM7
  MovD  EAx, MM7
  Test  EAx, EAx
  Jnz   @@CharFound2
  Add   EDx,8
  Sub   ECx,8
  Cmp   ECx,4
  Jg    @@Scan5
  Jmp   @@LastDword2

@@Exit_False2:
  Emms
  Pop   EAx
  Xor   EAx, EAx
  Ret

@@CharFound2:
  MovQ      MM7, [EDx]
  PCMPEQB   MM7, MM6
  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

@Small_String:
  Cmp  ECx, [EAx-4]
  Jb   @NotFound
  Mov  Ch, [EAx]
  Push ECx
  Push EBx
  Push ESi
  Mov  ESi, EAx
  Mov  EBx,[ESi-4]
  Dec  EBx
@Scan6:
  Push ECx
@Scan7:
  Call @@CharPos
  Pop  ECx
  Test EAx, EAx
  Jz   @Validation2
  Sub  Cl, Al
  Add  EDx, EAx
  Cmp  Cl, Bl
  Jb   @NotFound2

  Push ECx
  Mov  ECx, EBx
@Loop2:
  Mov  Al, [ESi+ECx]
  Cmp  Al, [EDx+ECx-1]
  Jnz  @Scan7
  Loop @Loop2

  Pop  ECx
  Mov  Ah, 0
  Pop  ESi
  Pop  EBx
  Pop  EAx
  Sub  EAx, ECx
  ret

@Validation2:
  Sub  Cl, 8
  Add  EDx, 8
  Cmp  Cl, 0
  Jg   @Scan6

@NotFound2:
  Pop  ESi
  Pop  EBx
  Add  ESp, 4
  Xor  EAx, EAx
  Ret

  nop                // code alignment
  nop

@@WideSearch:
  Cmp  ECx,32
  Jb   @Small_String

  Push EDi
  Push ESi
  Push EBx
  Push EBp

  MOV  ESI, EAX
  Mov  EDi, EDx
  Push ECx
  Mov  EBX, [ESI-4]
  Test EBx, EBx
  Jz   @@Exit_False
  Mov  Al, [ESi]
  Cmp  EBx, ECx
  Ja   @@Exit_False
  Jnz  @@Normal_Work
  Cmp  AL, [Edi]
  Jnz  @@Exit_False

@@Normal_Work:
  Dec  EBX

  Mov  Ah, [ESi+EBx]
  Dec  EBx
  Mov  EDx,ECx
  Inc  ESi
  Mov  EBp, ESi
  Cmp  ECx, 8
  Ja   @@Wide_String

@@Scan3:
  Push EAx
  Mov  Ch, Al
  Mov  EDx, EDi
  Call @@CharPos
  Mov  Ch, 0
  Sub  ECx, EAx
  Add  EDi, EAx
  Pop  EDx
  Test EAx,EAx
  Jz   @@Exit_False
  Xchg EAx, EDx
  Jmp  @@CheckLastChar
  nop
  nop
@@LastDword:
  Test ECx, ECx
  Js   @@Exit_False
  Jz   @@Exit_False
  MovD      MM7, [Edi]
  PCMPEQB   MM7, MM6
  MovD  EAx, MM7
  Test  EAx, EAx
  Jz    @@Exit_False
  Jmp   @@Loop1
  nop
  nop                 // Aligning code for greater performance
@@Wide_String:
  MovD MM4, EAx
  Mov  Ah, Al
  MovD MM6, EAx
  PUNPCKLWD MM6, MM6
  PUNPCKLDQ MM6, MM6

@@Scan:

  MovQ      MM7, [Edi]
  PCMPEQB   MM7, MM6
  PACKSSWB  MM7, MM7
  MovD  EAx, MM7
  Test  EAx, EAx
  Jnz   @@CharFound
  Add   EDi, 8
  Mov   EAx, Edi
  And   EAx, 7
  Sub   EDi,EAx         // Aligning index
  Sub   ECx,8
  Add   ECx,EAx
  Cmp   ECx,4
  Jnge  @@LastDword

@@Scan2:
  MovQ      MM7, [Edi]
  PCMPEQB   MM7, MM6
  PACKSSWB  MM7,MM7
  MovD  EAx, MM7
  Test  EAx, EAx
  Jnz   @@CharFound
  Add   EDi,8
  Sub   ECx,8
  Cmp   ECx,4
  Jg    @@Scan
  Jmp   @@LastDword

@@CharFound:
  MovQ      MM7, [Edi]
  PCMPEQB   MM7, MM6
  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

@@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]
  Jz    @@CompareWholeString
  Cmp   EDx,4
  Jg   @@Scan
  Jmp  @@LastDWord

@@Exit_False:
  Pop  EAx
  Xor  EAx,EAx
  Jmp  @@Leave_Proc

@@NotFound_Exit:
  Xor  EAx, EAx
  Ret

@@CompareWholeString:
  Test  EBx, EBx
  Jz    @@Constant_Exists
  Cmp   EDx, EBx
  Jna   @@Exit_False

  MOV   ECX, EBX
@@CW_Loop:
  SUB   ECX, 4
  JL    @@CW_Last123bytes
  MOV   EAX, [ESi+ECx]
  JZ    @@CW_LastDWord

  CMP   EAX, [EDi+ECx]
  JE   @@CW_Loop
  Mov   ECx, EDx
  JMP   @@SkipBTest1

@@CW_LastDWord:
  CMP   EAX, [EDi]
  JE    @@Constant_Exists
  Mov   ECx, EDx
  JMP   @@SkipBTest1

@@CW_Last123bytes:

  ADD   ECX, 2
  JS    @@Last1

@@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:
  CMP   AX, [EDi]
  JE    @@Constant_Exists
  Mov   ECx, EDx
  JMP   @@SkipBTest1

@@Last1:
  MOV   AL, [ESi]
  CMP   AL, [EDi]
  JE    @@Constant_Exists

@@SkipBTest:
  Mov   ECx, EDx

@@SkipBTest1:
  Cmp   EDx,4
  Jg    @@Scan
  Jmp   @@LastDWord

@@Constant_Exists2:
  Add   ESp, 4

@@Constant_Exists:
  Pop   EAx
  Sub   EAx, EDx

@@Leave_Proc:
  EMMS
  Pop  EBp
  Pop  EBx
  Pop  ESi
  Pop  EDi
End;

---

Defunct   (2004-10-05 02:20:00) [73]

> Однако часто проверяется и флаг С - а там уж точно задержка возникнет.
Помним и об этом, поэтому JA/JB после Inc/Dec никогда не используем. Только JZ/JS.

> Ну так исправь - и ты победитель :)

Дык, над этим и работаю в свободное время. ;)
Функция уже ~400 строк, начинаю малость теряться.



GuAV ©   (05.10.04 00:41) [190]
> никто не проверил на Р4 [157] ?

5 баллов GuruAV! (3-5)% ускорение на больших строках по сравнению с [151] и даже на мелких строках ускорение на лицо - (5-10)%

---

Sha   (2004-10-05 00:45:00) [74]

Так это ж не конец :)

---

GuAV   (2004-10-05 00:41:00) [75]

икто не проверил на Р4 [157] ?

---

Sha   (2004-10-05 00:28:00) [76]

> Defunct ©   (04.10.04 23:59) [188]

>> На современных процессорах inc и add работают одинаково быстро.
> А размер?

А что размер? Мы оптимизируем скорость, а не экономим несколько байт в exe.

> О какой зависимости идет речь?
> О CF помним, но в циклах, как правило, проверяются SF/ZF так
> что чихать на зависимоть. С учетом меньшего размера 1 байт
> против 5-ти, сэкономим время на загрузку другой команды.

Ты не совсем прав. Partial flags stalls действительно не возникает в случае проверки на равенство. Однако часто проверяется и флаг С - а там уж точно задержка возникнет.
А время загрузки команды в цикле почти всегда значения не имеет.

> В раскрученных циклах идет по два сравнения, которые чудесно
> параллелятся AH/AL без лишних обращений к кешу данных.
> Зависимость от сдвига не играет роли из-за количества
> физических АЛБ.

Оба конвейера будут ждать завершения сдига. Это 3 такта.

> Этот код [179] работает быстрее чем [120] там где было
> 8*([cmp reg, rel32],[jz],[dec]).

Надо бы проверить.  

> Причина замедления, сразу скажу, кроется в поиске подстроки
> Length(SubString)>1 и Length(S)<8.

Ну так исправь - и ты победитель :)

---

Defunct   (2004-10-04 23:59:00) [77]

> Если для других, то даже ничтожная вероятность AV, перечеркивает твой труд. Вряд ли кто захочет использовать ненадежную фукцию,
когда есть чуть более медленная, но надежная.

Одно дело ничтожная вероятность AV, другое дело синтетически созданная ситуация, имитирующая AV. Ну да ладно с этим разберусь, там только 2 места с выходом за пределы буфера максимум на 7 байт.

> На современных процессорах inc и add работают одинаково быстро.
А размер?
Add reg32, 1  (5 байт)
Inc reg       (1 байт)

> Однако, add часто предпочтительнее, если надо устранить зависимость регистра флагов от результата предыдущей команды.

О какой зависимости идет речь?

Inc/Dec Flags Affected:
The CF flag is not affected. The OF, SF, ZF, AF, and PF flags are set according to the result.

О CF помним, но в циклах, как правило, проверяются SF/ZF так что чихать на зависимоть. С учетом меньшего размера 1 байт против 5-ти, сэкономим время на загрузку другой команды.

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

не хватит АЛБ чтобы все распараллелить. в P4 если мне не изменяет память 2 АЛБ (В AMD64 - 3). В раскрученных циклах идет по два сравнения, которые чудесно параллелятся AH/AL без лишних обращений к кешу данных. Этот код [179] работает быстрее чем [120] там где было 8*([cmp reg, rel32],[jz],[dec]). Зависимость от сдвига не играет роли из-за количества физических АЛБ.

Причина замедления, сразу скажу, кроется в поиске подстроки Length(SubString)>1 и Length(S)<8.

---

Sha   (2004-10-04 23:37:00) [78]

Здесь имеется ввиду, что загрузка - пересылка память-регистр (mov reg,[mem])

---

Sha   (2004-10-04 23:00:00) [79]

> Defunct ©   (04.10.04 21:27) [179]

> Важна скорость или синтетический AV?

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

> Inc работает быстрее чем Add Reg,1
> Inc Inc  - быстрее чем Add Reg,2
> а вот 3 Inc будет уже медленнее чем Add Reg,3

Раньше действительно так было. На современных процессорах inc и add работают одинаково быстро. Однако, add часто предпочтительнее, если надо устранить зависимость регистра флагов от результата предыдущей команды. Обычно это требуется когда inc или dec - предпоследняя команда в цикле.

> сравните мою раскрутку для маленьких строк, с раскруткой от John [120]

На P4 сдвиг - сравнительно медленная U-команда, загрузка - быстрая (UV).
Кроме того, сдвиг подразумевает зависимость последующего кода от результата сдвига, а загрузка позволяет распараллелить выполнение за счет переназначения регистров. Так что сдвиги без необходимости использовать не стоит.

> НО, САМОЕ ИНТЕРЕСНОЕ, НА P4-HT функция почему-то проигрывает

Джон как раз оптимизирует свои программы под P4. Советую приглядеться к его коду.

---

Defunct   (2004-10-04 22:59:00) [80]

> Какая именно ?

[151] с раскрытыми циклами.

---

Страницы:   < 1 2 3 4 5 6 7 8 9 10 ... 13 14 >

Наверх