szLen optimize...

[NightWare]

if mmx isn't a problem, this version (short, quite fast and reduce branch mispredictions to the minimum) :

Code Select Expand

ALIGN 16
;
; obtenir la taille réelle d'une chaîne de caractères
; note : la chaîne doit être alignée sur 4/8/16 octets (pour une meilleure vitesse)
;
; Syntax :
; mov esi,OFFSET {start address of the string}
; call StringLength_Mmx_Mini
;
; Return :
; eax = string length
;
StringLength_Mmx_Mini PROC
push edx ;; empiler edx

mov eax,esi ;; placer l'adresse de la chaîne dans ecx
; nop ;; ) aucun alignement nécessaire pour un meilleur rendement
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
pxor MM0,MM0 ;; effacer MM0 (ce sera notre registre de comparaison)
Label1: pcmpeqb MM0,QWORD PTR [eax] ;; comparer les octets en parallèle, pour voir si l'un de ceux en MM0 est égal à 0
pmovmskb edx,MM0 ;; générer le masque de MM0 dans edx
add eax,8 ;; ajouter 8 à eax (notre pas de progression)
test edx,edx ;; fixer les flags de edx
jz Label1 ;; si c'est égal à 0, aller Label1
sub eax,esi ;; soustraire l'adresse de départ à eax
bsf edx,edx ;; scanner le premier bit armé à partir de la droite
lea eax,[eax+edx-8] ;; placer eax+edx-8 dans eax

pop edx ;; désempiler edx
ret ;; retourner (sortir de la procédure)
StringLength_Mmx_Mini ENDP
hmm, i don't know the ratio of lamps i could have with this one, but it must be clearly good... (clearly, because of the numbers of lamps, of course...  :lol)

[sinsi]

That algo gets 47 cycles on mine - very fast! Is it only MMX though? I had to use ".xmm" to get it to compile.

[NightWare]

you're right, pmovmskb has been implemented only with sse...  :red

[qWord]

I've modified the testbed (variable alignment) and added an xmm-version:

on my Core2Duo:

Code Select Expand


lstrlenA return value     : 191
AzmtStrLen1A return value : 191
AzmtStrLen2A return value : 191
markl_szlen return value  : 191
StringLength_Mmx_Min
(MMX/SSE2) return value   : 191
StrSizeA(SSE2) value      : 191

align 0

lstrlenA      :       252 cycles
AzmtStrLen1A  :       193 cycles
AzmtStrLen2A  :       193 cycles
markl_szlen   :       106 cycles
StringLength_Mmx_Min: 72 cycles
StrSizeA(SSE2):       38 cycles

align 1

lstrlenA      :       247 cycles
AzmtStrLen1A  :       216 cycles
AzmtStrLen2A  :       221 cycles
markl_szlen   :       152 cycles
StringLength_Mmx_Min: 103 cycles
StrSizeA(SSE2):       102 cycles

align 4

lstrlenA      :       244 cycles
AzmtStrLen1A  :       193 cycles
AzmtStrLen2A  :       192 cycles
markl_szlen   :       90 cycles
StringLength_Mmx_Min: 109 cycles
StrSizeA(SSE2):       92 cycles

align 7

lstrlenA      :       246 cycles
AzmtStrLen1A  :       203 cycles
AzmtStrLen2A  :       202 cycles
markl_szlen   :       126 cycles
StringLength_Mmx_Min: 96 cycles
StrSizeA(SSE2):       105 cycles

Press any key to exit...





[attachment deleted by admin]

[donkey]

I wrote a similar one a few years ago for my string library...

Code Select Expand

lszLenMMX FRAME pString

mov eax,[pString]
nop
nop ; fill in stack frame+mov to 8 bytes

pxor mm0,mm0
nop ; fill pxor to 4 bytes
pxor mm1,mm1
nop ; fill pxor to 4 bytes

: ; this is aligned to 16 bytes
movq mm0,[eax]
pcmpeqb mm0,mm1
add eax,8
pmovmskb ecx,mm0
or ecx,ecx
jz <

sub eax,[pString]

bsf ecx,ecx
sub eax,8
add eax,ecx

emms


   RET

ENDF

[japheth]

lstrlen() is known not to be the fastest algo.
AFAIK strlen() from MSVCRT is significantly faster. You probably should compare your routine with that version as well.

[jdoe]

lstrlen() is known not to be the fastest algo.
AFAIK strlen() from MSVCRT is significantly faster. You probably should compare your routine with that version as well.

Yes, the strlen from the c runtime is quite fast but a little slower than a custom agner fog algo, though I think they use the same tricks. These functions takes speed with long strings but are easy to beat on small strings. But it is a good point that if you don't want to code your algo, the ansi version of strlen from msvcrt is the best alternative to lstrlen. For the unicode version, that's another story.

:U

[NightWare]

hmm, if it's sse due to pmovmskb, then a fully sse version  :toothy :

Code Select Expand

ALIGN 16
;
; obtenir la taille réelle d'une chaîne de caractères
; note : la chaîne doit être alignée sur 4/8/16 octets (pour une meilleure vitesse)
;
; Syntax :
; mov esi,OFFSET {start address of the string}
; call StringLength_Sse
;
; Return :
; eax = string length
;
StringLength_Sse PROC
push ecx ;; empiler ecx
push edx ;; empiler edx

mov edx,esi ;; placer l'adresse de départ dans edx
; nop ;; ) aucun alignement nécessaire pour un meilleur rendement
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
; nop ;; )
pxor XMM0,XMM0 ;; ) effacer XMM0 et XMM1 (ce sera nos registres de comparaison)
pxor XMM1,XMM1 ;; )
; ici, on teste un bloc de 32 caractères, pour voir s'il existe un 0
Label1: pcmpeqb XMM0,OWORD PTR [edx] ;; comparer le qword à l'adresse en edx à XMM0
pcmpeqb XMM1,OWORD PTR [edx+16] ;; comparer le qword à l'adresse en edx+16 à XMM1
por XMM1,XMM0 ;; fusionner XMM1 et XMM0
add edx,OWORD*2 ;; ajouter 32 (notre pas de progression) à edx
pmovmskb eax,XMM1 ;; générer le masque de XMM1 dans eax
test eax,eax ;; fixer les flags de eax
jz Label1 ;; si c'est égal à 0 (pas de 0 trouvé), aller Label1
; ici, on va chercher le 0 dans le bloc de 32 caractères
pmovmskb ecx,XMM0 ;; générer le masque de XMM0 dans ecx
shl eax,16 ;; décaler eax (qui contient déjà le masque XMM1) à gauche d'un dword/2
or eax,ecx ;; fusionner ecx à eax
sub edx,esi ;; enlever l'adresse de départ à edx
sub edx,OWORD*2 ;; enlever la dernière progression à edx
bsf eax,eax ;; scanner le premier bit armé de eax à partir de la droite
add eax,edx ;; ajouter edx à eax pour obtenir la taille finale

pop edx ;; désempiler edx
pop ecx ;; désempiler ecx
ret ;; retourner (sortir de la procédure)
StringLength_Sse ENDP

[lingo]

I use similar algo with masm64... :wink
My results->Windows Vista Ultimate 64bit  - SP1
CPU-DualCore Intel Core 2 Duo E8500, 3.16 GHz

Code Select Expand


C:\My Documents\ASM\strlen>strlena
lstrlenA return value     : 191
strlen64Lingo return value: 191
AzmtStrLen1A return value : 191
AzmtStrLen2A return value : 191
markl_szlen return value  : 191
StringLength_Mmx_Min
(MMX/SSE2) return value   : 191
StrSizeA(SSE2) value      : 191

align 0

lstrlenA      :       258 cycles
strlen64Lingo :       20 cycles
AzmtStrLen1A  :       191 cycles
AzmtStrLen2A  :       191 cycles
markl_szlen   :       100 cycles
StringLength_Mmx_Min: 54 cycles
StrSizeA(SSE2):       39 cycles

align 1

lstrlenA      :       254 cycles
strlen64Lingo :       20 cycles
AzmtStrLen1A  :       220 cycles
AzmtStrLen2A  :       218 cycles
markl_szlen   :       151 cycles
StringLength_Mmx_Min: 112 cycles
StrSizeA(SSE2):       97 cycles

align 4

lstrlenA      :       254 cycles
strlen64Lingo :       20 cycles
AzmtStrLen1A  :       191 cycles
AzmtStrLen2A  :       191 cycles
markl_szlen   :       89 cycles
StringLength_Mmx_Min: 114 cycles
StrSizeA(SSE2):       113 cycles

align 7

lstrlenA      :       254 cycles
strlen64Lingo :       20 cycles
AzmtStrLen1A  :       200 cycles
AzmtStrLen2A  :       200 cycles
markl_szlen   :       119 cycles
StringLength_Mmx_Min: 99 cycles
StrSizeA(SSE2):       109 cycles

Press any key to exit...



[attachment deleted by admin]

[jj2007]

Hi Lingo,
As usual, your algo beats the hell out of 'em... at least for long strings:

Code Select Expand

lstrlenA return value     : 1024
strlen64Lingo return value: 1024
AzmtStrLen1A return value : 1024
AzmtStrLen2A return value : 1024
markl_szlen return value  : 1024
StringLength_Mmx_Min
(MMX/SSE2) return value   : 1024
StrSizeA(SSE2) value      : 1024
_strlen return value      : 1024

align 1k

lstrlenA return value: 1024
lstrlenA      :       3032 cycle
strlen64Lingo :       370 cycles
AzmtStrLen1A  :       1407 cycle
AzmtStrLen2A  :       1407 cycle
markl_szlen   :       581 cycles
StringLength_Mmx_Min: 908 cycles
StrSizeA(SSE2):       600 cycles
_strlen (Agner Fog):  635 cycles

align 0

lstrlenA return value: 191
lstrlenA      :       630 cycles
strlen64Lingo :       369 cycles
AzmtStrLen1A  :       301 cycles
AzmtStrLen2A  :       307 cycles
markl_szlen   :       276 cycles
StringLength_Mmx_Min: 224 cycles
StrSizeA(SSE2):       114 cycles
_strlen (Agner Fog):  103 cycles

align 1

lstrlenA return value: 191
lstrlenA      :       632 cycles
strlen64Lingo :       370 cycles
AzmtStrLen1A  :       383 cycles
AzmtStrLen2A  :       382 cycles
markl_szlen   :       276 cycles
StringLength_Mmx_Min: 304 cycles
StrSizeA(SSE2):       138 cycles
_strlen (Agner Fog):  111 cycles

align 4

lstrlenA return value: 191
lstrlenA      :       628 cycles
strlen64Lingo :       371 cycles
AzmtStrLen1A  :       301 cycles
AzmtStrLen2A  :       304 cycles
markl_szlen   :       251 cycles
StringLength_Mmx_Min: 339 cycles
StrSizeA(SSE2):       142 cycles
_strlen (Agner Fog):  114 cycles

align 7

lstrlenA return value: 191
lstrlenA      :       628 cycles
strlen64Lingo :       369 cycles
AzmtStrLen1A  :       384 cycles
AzmtStrLen2A  :       387 cycles
markl_szlen   :       274 cycles
StringLength_Mmx_Min: 321 cycles
StrSizeA(SSE2):       144 cycles
_strlen (Agner Fog):  115 cycles


I added the last algo, see attachment.

[attachment deleted by admin]

[lingo]

Thanks, but I can't understand why to use so big strings...
I included A.Fog's algo too, but it is slower... :wink

Code Select Expand


C:\My Documents\ASM\strlen>strlena
lstrlenA return value     : 191
strlen64Lingo return value: 191
A.Fog StrLen return value : 191
AzmtStrLen1A return value : 191
AzmtStrLen2A return value : 191
markl_szlen return value  : 191
StringLength_Mmx_Min
(MMX/SSE2) return value   : 191
StrSizeA(SSE2) value      : 191

align 0

lstrlenA      :       259 cycles
strlen64Lingo :       20 cycles
A.Fog StrLen  :       36 cycles
AzmtStrLen1A  :       192 cycles
AzmtStrLen2A  :       191 cycles
markl_szlen   :       100 cycles
StringLength_Mmx_Min: 50 cycles
StrSizeA(SSE2):       39 cycles

align 1

lstrlenA      :       243 cycles
strlen64Lingo :       20 cycles
A.Fog StrLen  :       49 cycles
AzmtStrLen1A  :       222 cycles
AzmtStrLen2A  :       218 cycles
markl_szlen   :       151 cycles
StringLength_Mmx_Min: 113 cycles
StrSizeA(SSE2):       97 cycles

align 4

lstrlenA      :       254 cycles
strlen64Lingo :       20 cycles
A.Fog StrLen  :       44 cycles
AzmtStrLen1A  :       192 cycles
AzmtStrLen2A  :       191 cycles
markl_szlen   :       89 cycles
StringLength_Mmx_Min: 112 cycles
StrSizeA(SSE2):       110 cycles

align 7

lstrlenA      :       243 cycles
strlen64Lingo :       20 cycles
A.Fog StrLen  :       49 cycles
AzmtStrLen1A  :       200 cycles
AzmtStrLen2A  :       200 cycles
markl_szlen   :       119 cycles
StringLength_Mmx_Min: 99 cycles
StrSizeA(SSE2):       109 cycles

Press any key to exit...



[attachment deleted by admin]

[jj2007]

Thanks, but I can't understand why to use so big strings...
I included A.Fog's algo too, but it is slower... :wink

Strange. Here are my Celeron M results, and the Agner Fog algo is a lot faster on non-aligned short strings... ::)

Code Select Expand

align 0

lstrlenA return value: 191
lstrlenA      :       429 cycles
strlen64Lingo :       198 cycles
AzmtStrLen1A  :       283 cycles
AzmtStrLen2A  :       223 cycles
markl_szlen   :       113 cycles
StringLength_Mmx_Min: 72 cycles
StrSizeA(SSE2):       72 cycles
_strlen (Agner Fog):  91 cycles

align 1

lstrlenA return value: 191
lstrlenA      :       422 cycles
strlen64Lingo :       198 cycles
AzmtStrLen1A  :       282 cycles
AzmtStrLen2A  :       230 cycles
markl_szlen   :       144 cycles
StringLength_Mmx_Min: 118 cycles
StrSizeA(SSE2):       87 cycles
_strlen (Agner Fog):  64 cycles

[lingo]

Nothing strange for me...My results are the same as the results of qWord...  :wink
On my old lapi with AMD Turion 64 ML-30, 1.6GHz
and Vista64bit Ultimate-SP1:

Code Select Expand



lstrlenA return value     : 191
strlen64Lingo return value: 191
A.Fog StrLen return value : 191
AzmtStrLen1A return value : 191
AzmtStrLen2A return value : 191
markl_szlen return value  : 191
StringLength_Mmx_Min
(MMX/SSE2) return value   : 191
StrSizeA(SSE2) value      : 191

align 0

lstrlenA      :       425 cycles
strlen64Lingo :       55 cycles
A.Fog StrLen  :       223 cycles
AzmtStrLen1A  :       175 cycles
AzmtStrLen2A  :       174 cycles
markl_szlen   :       109 cycles
StringLength_Mmx_Min: 103 cycles
StrSizeA(SSE2):       101 cycles

align 1

lstrlenA      :       425 cycles
strlen64Lingo :       55 cycles
A.Fog StrLen  :       211 cycles
AzmtStrLen1A  :       213 cycles
AzmtStrLen2A  :       218 cycles
markl_szlen   :       111 cycles
StringLength_Mmx_Min: 112 cycles
StrSizeA(SSE2):       106 cycles

align 4

lstrlenA      :       426 cycles
strlen64Lingo :       55 cycles
A.Fog StrLen  :       198 cycles
AzmtStrLen1A  :       175 cycles
AzmtStrLen2A  :       175 cycles
markl_szlen   :       108 cycles
StringLength_Mmx_Min: 112 cycles
StrSizeA(SSE2):       106 cycles

align 7

lstrlenA      :       425 cycles
strlen64Lingo :       55 cycles
A.Fog StrLen  :       197 cycles
AzmtStrLen1A  :       192 cycles
AzmtStrLen2A  :       191 cycles
markl_szlen   :       113 cycles
StringLength_Mmx_Min: 110 cycles
StrSizeA(SSE2):       104 cycles

Press any key to exit...

[jj2007]

Nothing strange for me...My results are the same as the results of qWord...  :wink
On my old lapi with AMD Turion 64 ML-30, 1.6GHz
and Vista64bit Ultimate-SP1

Either there are dramatic differences between AMD and a Celeron M, or we are not talking about the same Agner Fog algo.

[drizz]

All of the routines, except Agner Fog's, fail on unaligned read beyond end of the buffer

Code Select Expand


invoke VirtualAlloc,0,1000h,MEM_COMMIT,PAGE_READWRITE
mov esi,eax
invoke RtlZeroMemory,esi,1000h

invoke AzmtStrLen1A,addr [esi+1000h-1]
invoke AzmtStrLen2A,addr [esi+1000h-1]
invoke markl_szlen,addr [esi+1000h-1]
invoke StringLength_Mmx_Min,addr [esi+1000h-1]
invoke StrSizeA,addr [esi+1000h-1]
lea ecx,[esi+1000h-1]
call strlen64

invoke _strlen,addr [esi+1000h-1]; *** working, not buggy

invoke VirtualFree,esi,0,MEM_RELEASE
   
zero should be returned, not access violation.


also markl_szlen function is buggy:

   .data
   teststr db 'ab',0,'a',0
   .code
   invoke markl_szlen,addr teststr

reports size 4