QuickSearch Algorithm (Blitzes Findstring)

[Michael Vogel]

@ Michael Vogel: For Fun a Procedure for FindString with SSE4.2:
:
:
I hope, this is "waterproof", I will make another tests. The speed-factor is 5-6 with PB.
Have Fun!
Helle

Thanks, Helle...
...like all things to speed up my programs

Bad luck, my old notebook has an ancient CPU, so testing will be delayed until I'll buy a new one

[RichAlgeni]

Klaus, did you say you also have a 64 bit version???



Rich

[Helle]

For 64-Bit-Windows with SSE4.2-CPU-support:

Code: Select all

Procedure.q FindString_SSE42_64Bit(pStr1, pStr2, StartPos)
  !mov rax,r8                               ;need RAX for return-value ProcedureReturn, R8=StartPos
  !cmp rax,1
  !jge @f
  !mov rax,1                                ;or End or Error
!@@:
  !mov r8,rcx                               ;need RCX for return-value PCMPISTRI, RCX=pStr1 
  !sub r8,1
  !add r8,rax                               ;rax=StartPos
  !movdqu xmm0,[rdx]                        ;first max.16 Bytes of Find$, RDX=pStr2
  !xor rcx,rcx
!Search:
  !add rax,rcx
  !add r8,rcx
  !pcmpistri xmm0,dqword[r8],00001100b      ;Least Significant Index, Positive Polarity (IntRes2=IntRes1), Equal Ordered, Unsigned Bytes (=No Unicode)  
  !jz Base$End                              ;Zero-Flag is set if found end of Base$
  !js Find$End                              ;Sign-Flag is set if found end of Find$  
  !jrcxz @f                                 ;jump if RCX is zero 
  !jmp Search
!@@:
  !movdqa xmm1,xmm0                         ;save xmm0
  !mov r9,r8
  !mov r10,rdx
!@@:
  !add r10,16
  !add r9,16                                ;next 16 Bytes of Base$
  !movdqu xmm1,[r10]                        ;next 16 Bytes of Find$
  !pcmpistri xmm1,dqword[r9],00001100b      ;compare the strings 
  !jz Base$End
  !js Find$End
  !jrcxz @b
  !jmp Search
!Base$End:
  !cmp rcx,16
  !jne Found
  !xor rax,rax
  !jmp NoFound
!Find$End:
  !or rcx,rcx                               ;RCX Zero? Conventional
  !jnz Search
!Found:
  !add rax,rcx
!NoFound:
 ProcedureReturn                            ;rax 
EndProcedure 

Base$ = "This is a simple string for testing several find procedures ~ the results will show, if any of the tested functions are faster than the internal FindString() function"
Find$ = "Find"

Pos = 1

FindSSE42 = FindString_SSE42_64Bit(@Base$, @Find$, Pos)
SSE42$ = "Found String at Position : " + Str(FindSSE42)

PB$ = "Test with PB : " + Str(FindString(Base$, Find$, Pos))

MessageRequester("FindString with SSE4.2", SSE42$ + #LFCR$ + PB$)

You can use FindString e.g. for Replacestring. This is a simple version (64-Bit) like PB with mode "#PB_String_InPlace":

Code: Select all

Procedure.q ReplaceString_SSE42_64Bit(pStr1, pStr2, pStr3, StartPos)
  !mov rax,r9                               ;need RAX for return-value ProcedureReturn, R9=StartPos 
  !cmp rax,1
  !jge @f
  !mov rax,1                                ;or End or Error
!@@:
  !mov r8,rcx                               ;need RCX for return-value PCMPISTRI, RCX=pStr1
  !add r8,rax                               ;rax=StartPos
  !movdqu xmm0,[rdx]                        ;first max.16 Bytes of Find$, RDX=pStr2
  !movdqa xmm1,xmm0                         ;for Length Find$ <=16
  !xor r10,r10
  !xor rcx,rcx
!Search:
  !add rax,rcx
  !add r8,rcx
  !pcmpistri xmm0,dqword[r8],00001100b      ;Least Significant Index, Positive Polarity (IntRes2=IntRes1), Equal Ordered, Unsigned Bytes (=No Unicode)  
  !jz Base$End                              ;Zero-Flag is set if found end of Base$
  !js Find$End                              ;Sign-Flag is set if found end of Find$  
  !jrcxz @f                                 ;jump if RCX is zero 
  !jmp Search
!@@:
  !movdqa xmm1,xmm0                         ;save xmm0
  !mov r9,r8
  !xor r10,r10
!@@:
  !add r10,16
  !add r9,16                                ;next 16 Bytes of Base$
  !movdqu xmm1,[rdx+r10]                    ;next 16 Bytes of Old$
  !pcmpistri xmm1,dqword[r9],00001100b      ;compare the strings 
  !jz Base$End
  !js Find$End
  !jrcxz @b
  !jmp Search
!Base$End:
  !cmp rcx,16
  !jne Found
  !xor rax,rax
  !jmp Found?
!Find$End:
  !or rcx,rcx                               ;RCX Zero? Conventional
  !jnz Search
!Found:
  !add rax,rcx                              ;RAX=Start-Position Old$
  !pxor xmm0,xmm0
  !pcmpistri xmm0,xmm1,00001000b            ;for Length Old$
  !add rcx,r10
  !add rcx,rdx
  !sub rcx,[p.v_pStr2]                      ;RCX=Length Old$
  !mov r8,[p.v_pStr1]                       ;Base$
  !add r8,rax
  !mov r9,[p.v_pStr3]                       ;New$
!Again:
  !mov r11,[r8]
  !mov rdx,[r9]
  ;this part is not optimal... Schau´n ´mer mal! :-)
  !cmp rcx,7
  !ja @f
  !shl rcx,3
  !shr r11,cl  ;Base$
  !shl r11,cl
  !shr rcx,3
  !mov r10,8
  !sub r10,rcx
  !mov rcx,r10
  !shl rcx,3
  !shl rdx,cl  ;New$
  !shr rdx,cl
  !or rdx,r11
  !mov [r8],rdx
  !jmp Found?
!@@:
  !mov [r8],rdx
  !add r8,8
  !add r9,8
  !sub rcx,8
  !jmp Again
!Found?:
 ProcedureReturn                            ;rax 
EndProcedure 

Base$ = "Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2B: PCMPxSTRx instructions perform arithmetic comparisons between all possible pairs of bytes or words, one from each packed input source operand. The boolean results of those comparisons are then aggregated in order to produce meaningful results. The Imm8 Control Byte is used to affect the interpretation of individual input elements as well as control the arithmetic comparisons used and the specific aggregation scheme."
Old$ = "meaningful results"
New$ = "XXXXXXXXXXXXXXXXXX"

Pos = 1                                     ;Start-Position 

OK = ReplaceString_SSE42_64Bit(@Base$, @Old$, @New$, Pos)  ;OK is a goodie! You can check for success

If OK
  MessageRequester("ReplaceString with SSE4.2", Base$)
 Else 
  MessageRequester("ReplaceString with SSE4.2", "Nothing for replace !")
EndIf

Have fun and please report errors!
Helle

[RichAlgeni]

Thanks so much Klaus!

Just a question, should we select CPU with SSE2 under compiler options?

[Helle]

Ha, this is a question for Fred/Freak!
IMHO this options are placebos .

[Thorium]

The instruction set options are only for userlibs, PB does not use any of them.

[RichAlgeni]

Understood. I wasn't sure that if you selected one, it might turn off the others?

[Thunder93]

I came cross this old but interesting memory findstring code that pdwyer posted. Very nice, thank you for sharing.

I went straight to the latest one that pdwyer had updated and shared. When I went to use it, I noticed a problem. When looking further into.. for a match, the result would return the very first matching position. At a close inspection I have found that the starting position parameter was being forced to starting position from the beginning. Making the start position parameter irrelevant. Simply disabling the line in question made it right and all is well. Direct Link to this post http://www.purebasic.fr/english/viewtop ... 58#p218258


On my initial arrival to this topic and during the time I was looking for the latest updated code pdwyer sharing. I also came across mback2k Unicode supported version that I also grabbed. Thanks mback2k, nice job.

... However again, it shared the forced starting position, painless minor alteration. I thought I had it beat but in unicode mode I still experienced the same problem with the returning result being the very first matching position. Further inspection of the code I noticed that the starting parameter needed a minor tweak. Another problem I've noticed, but before making any alterations. The returning value was always 1 instead of 0 on no more found matches.

I've made the necessary corrections, I think it all should be sound, but have a look anyways. I'm still a newb.

Code: Select all

;QuickSearch Algorithm (Blitzes Findstring)
; mback2k - Updated: Sun Nov 16, 2008 (Unicode support) 
;        http://www.purebasic.fr/english/viewtopic.php?p=267475#p267475

; pdwyer - Last Updated: Mon Nov 12, 2007 
;        http://www.purebasic.fr/english/viewtopic.php?p=218258#p218258

Structure MemoryArray
  Byte.b[0]
EndStructure

Procedure.l QuickSearch(StartPos, *MainMem, MainLen, *FindMem, FindLen)
  Protected MainArrayLoop, EndSearchPos, *MainByteArray.MemoryArray, *FindByteArray.MemoryArray
  
  *MainByteArray = *MainMem
  *FindByteArray = *FindMem
;   StartPos =- 1
  
  ; Build BadChr Array
  Protected Dim BadChar(255)
  
  ; set all alphabet to max shift pos (length of find string plus 1)
  For i = 0 To 255
    BadChar(i)  =  FindLen + 1
  Next
  
  ;Update chars that are in the find string to their position from the end.
  For i = 0 To FindLen -1
    BadChar(*FindByteArray\Byte[i]) = FindLen - i   
  Next     
  
  MainArrayLoop = StartPos
  EndSearchPos = MainLen - (FindLen -1)
  
  While MainArrayLoop <= EndSearchPos
    
    If CompareMemory(*MainMem + MainArrayLoop, *FindMem, FindLen) = 1
      FoundPos = MainArrayLoop + 1
      Break
    EndIf
    
    ;Didn't find the string so shift as per the table.
    MainArrayLoop + BadChar(*MainByteArray.MemoryArray\Byte[MainArrayLoop + FindLen])
    
  Wend  

  ProcedureReturn FoundPos 
  
EndProcedure

Procedure QuickStringSearch(StartPos, String$, StringToFind$)
  
  CompilerIf #PB_Compiler_Unicode
;         ProcedureReturn QuickSearch(StartPos, @String$, StringByteLength(String$), @StringToFind$, StringByteLength(StringToFind$))/2+1
            ValReturn.l = QuickSearch(StartPos*2, @String$, StringByteLength(String$), @StringToFind$, StringByteLength(StringToFind$))
            If ValReturn : ValReturn / 2+1 : EndIf
            ProcedureReturn ValReturn
        
  CompilerElse
    ProcedureReturn QuickSearch(StartPos, @String$, Len(String$), @StringToFind$, Len(StringToFind$))
  CompilerEndIf

EndProcedure

Debug QuickStringSearch(1, "ABCDEF34637347347", "7")
Debug QuickStringSearch(1, "ABCDEF34637347347", "F")
Debug QuickStringSearch(1, "ABCDEF34637347347", "BC")

[IdeasVacuum]

PB's own FindString() has been enhanced since QuickSearch was posted here - have you compared them?

[davido]

My tests seem to indicate that, as expected FindString is about 30 times faster.
Well didn't Fred write it?

[Tenaja]

My tests seem to indicate that, as expected FindString is about 30 times faster.
Well didn't Fred write it?

I suspect those loops really kill the cycle time.

[Thunder93]

To be honest... I wasn't really thinking about the speed so soon after coming cross this. However, now that you mentioned it.

It depends on how you using it.

- Allocated memory of 8143 bytes and loaded a text file with this size.
- 32 length string match to be used.
- 7996 is the returning position on my test.
- Elapsed time return values are in milliseconds.
- w/Debugger

QuickStringSearch() the Unicode Edition w/Unicode mode Off.

Using loop 1 – 1000 the elapsed time is 96.

Without the loop, just a single pass it was 0.
-----

PB native FindString().

Using loop 1 – 1000 the elapsed time was 47

Without the loop, just a single pass it was 0.

* In this case using in the loop of 1000 the use of PB native FindString() was just over half the time of QuickStringSearch().