szLen optimize...

[denise_amiga]

StrLen1 <--- from agner
StrLen2 <--- modification from original
szLen1 <--- original
szLen2 <--- modification from original
lstrlen <--- original from system

1472 -- 1378 clocks StrLen1
1472 -- 1196 clocks StrLen2
1472 -- 3077 clocks szLen1
1472 -- 2233 clocks szLen2
1472 -- 5870 clocks lstrlen

Code Select Expand


; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    include     masm32rt.inc

    ;include    timers.asm

    StrLen1 proto   :DWORD
    StrLen2 proto   :DWORD
    szLen1  proto   :DWORD
    szLen2  proto   :DWORD

; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
      str0 db 64 dup ("my other brother darryl"),0

    .code
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    ;repeat 3          ; Used to check sensitivity to alignment
    ;  nop
    ;endm

    invoke  StrLen1, addr str0
    print ustr$(eax)
    print chr$(" -- ")
    counter_begin 10000000, REALTIME_PRIORITY_CLASS
      invoke StrLen1, addr str0
    counter_end
    print ustr$(eax)
    print chr$(" clocks StrLen1",13,10)

    invoke  StrLen2, addr str0
    print ustr$(eax)
    print chr$(" -- ")
    counter_begin 10000000, REALTIME_PRIORITY_CLASS
      invoke StrLen2, addr str0
    counter_end
    print ustr$(eax)
    print chr$(" clocks StrLen2",13,10)

    invoke  szLen1, addr str0
    print ustr$(eax)
    print chr$(" -- ")
    counter_begin 10000000, REALTIME_PRIORITY_CLASS
      invoke szLen1, addr str0
    counter_end
    print ustr$(eax)
    print chr$(" clocks szLen1",13,10)

    invoke  szLen2, addr str0
    print ustr$(eax)
    print chr$(" -- ")
    counter_begin 10000000, REALTIME_PRIORITY_CLASS
      invoke szLen2, addr str0
    counter_end
    print ustr$(eax)
    print chr$(" clocks szLen2",13,10)

    invoke  lstrlen, addr str0
    print ustr$(eax)
    print chr$(" -- ")
    counter_begin 10000000, REALTIME_PRIORITY_CLASS
      invoke lstrlen, addr str0
    counter_end
    print ustr$(eax)
    print chr$(" clocks lstrlen",13,10)

    exit
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE

align 4

StrLen1 proc item:DWORD

    push    ebx

    mov     eax, [esp+2*4]          ; get pointer to string
    lea     edx, [eax+3]            ; pointer+3 used in the end
align 4
@@:
    mov     ebx, [eax]              ; read first 4 bytes
    add     eax, 4                  ; increment pointer
    lea     ecx, [ebx-01010101h]    ; subtract 1 from each byte
    not     ebx                     ; invert all bytes
    and     ecx, ebx                ; and these two
    and     ecx, 80808080h
    jz      @B                      ; no zero bytes, continue loop

    test    ecx, 00008080h          ; test first two bytes
    jnz     @F

    shr     ecx, 16                 ; not in the first 2 bytes
    add     eax, 2

@@:
    shl     cl, 1                   ; use carry flag to avoid branch
    sbb     eax, edx                ; compute length

    pop     ebx

    ret     1*4

StrLen1 endp

align 4

StrLen2 proc src:DWORD

    mov     ecx, [esp+1*4]
    test    ecx, 3
    jz      @max8

@bucle:
    mov     al, [ecx]
    add     ecx, 1
    test    al, al
    jz      @lb1

    test    ecx, 3
    jnz     @bucle
align 4
@max8:
    mov     eax, [ecx]
    mov     edx, 7EFEFEFFh
    add     edx, eax
    xor     eax, 0FFFFFFFFh
    xor     eax, edx
    add     ecx, 4
    test    eax, 81010100h
    jz      @max8

    mov     eax, [ecx-4]
    test    al, al
    jz      @lb4

    test    ah, ah
    jz      @lb3

    test    eax, 0FF0000h
    jz      @lb2

    test    eax, 0FF000000h
    jnz     @max8

@lb1:
    lea     eax, [ecx-1]
    mov     ecx, [esp+1*4]
    sub     eax, ecx
    ret     1*4

@lb2:
    lea     eax, [ecx-2]
    mov     ecx, [esp+1*4]
    sub     eax, ecx
    ret     1*4

@lb3:
    lea     eax, [ecx-3]
    mov     ecx, [esp+1*4]
    sub     eax, ecx
    ret     1*4

@lb4:
    lea     eax, [ecx-4]
    mov     ecx, [esp+1*4]
    sub     eax, ecx
    ret     1*4

StrLen2 endp

align 4

szLen1 proc src:DWORD

    mov     eax, [esp+1*4]    ; src
    sub     eax, 4
align 4
@@:
    add     eax, 4
    cmp     BYTE PTR [eax], 0
    je      @lb1

    cmp     BYTE PTR [eax+1], 0
    je      @lb2

    cmp     BYTE PTR [eax+2], 0
    je      @lb3

    cmp     BYTE PTR [eax+3], 0
    jne     @B

    sub     eax, [esp+1*4]    ; src
    add     eax, 3
    ret     1*4

@lb3:
    sub     eax, [esp+1*4]    ; src
    add     eax, 2
    ret     1*4

@lb2:
    sub     eax, [esp+1*4]    ; src
    add     eax, 1
    ret     1*4

@lb1:
    sub     eax, [esp+1*4]    ; src
    ret     1*4

szLen1 endp

align 4

szLen2 proc src:DWORD

    mov     eax, [esp+1*4]    ; src
    sub     eax, 4
    xor     ecx, ecx
align 4
@@:
    add     eax, 4
    cmp     BYTE PTR [eax], cl
    je      @lb1

    cmp     BYTE PTR [eax+1], cl
    je      @lb2

    cmp     BYTE PTR [eax+2], cl
    je      @lb3

    cmp     BYTE PTR [eax+3], cl
    jne     @B

    sub     eax, [esp+1*4]    ; src
    add     eax, 3
    ret     1*4

@lb3:
    sub     eax, [esp+1*4]    ; src
    add     eax, 2
    ret     1*4

@lb2:
    sub     eax, [esp+1*4]    ; src
    add     eax, 1
    ret     1*4

@lb1:
    sub     eax, [esp+1*4]    ; src
    ret     1*4

szLen2 endp

OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef

end start



[James Ladd]

Have a look at Donkeys string utils for a truely fast length api.
(you will have to search this board)

[denise_amiga]

hi striker

I have looked for in the forum and only I have found a few references to donkey but they do not speak to anything referring, if you could say something to me, you help me, since I am beginning with the assembler and I like much.

right now I do not have long time, and I think that was faster to write here, but will look for the network.

1472 -- 1378 clocks StrLen1
1472 -- 1196 clocks StrLen2
1472 -- 3077 clocks szLen1
1472 -- 2233 clocks szLen2
1472 -- 2241 clocks szLen3
1472 -- 2104 clocks szLen4
1472 -- 5870 clocks lstrlen

Code Select Expand



OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE

align 4

szLen3 proc src:DWORD

    mov     eax, [esp+1*4]    ; src
    sub     eax, 4
    xor     ecx, ecx
align 4
@@:
    add     eax, 4
    mov     ecx, [eax]
    ;cmp    BYTE PTR [eax], 0
    test    cl, cl
    je      @lb1

    ;cmp    BYTE PTR [eax+1], 0
    test    ch, ch
    je      @lb2

    mov     ecx, [eax+2]
    ;cmp    BYTE PTR [eax+2], 0
    test    cl, cl
    je      @lb3

    ;cmp    BYTE PTR [eax+3], 0
    test    ch, ch
    jne     @B

    sub     eax, [esp+1*4]    ; src
    add     eax, 3
    ret     1*4

@lb3:
    sub     eax, [esp+1*4]    ; src
    add     eax, 2
    ret     1*4

@lb2:
    sub     eax, [esp+1*4]    ; src
    add     eax, 1
    ret     1*4

@lb1:
    sub     eax, [esp+1*4]    ; src
    ret     1*4

szLen3 endp

align 4

szLen4 proc src:DWORD

    mov     eax, [esp+1*4]    ; src
    sub     eax, 4
    ;xor    ecx, ecx
align 4
@@:
    add     eax, 4
    movzx   ecx, word ptr [eax]
    ;cmp    BYTE PTR [eax], 0
    test    cl, cl
    je      @lb1

    ;cmp    BYTE PTR [eax+1], 0
    test    ch, ch
    je      @lb2

    movzx   ecx, word ptr [eax+2]
    ;cmp    BYTE PTR [eax+2], 0
    test    cl, cl
    je      @lb3

    ;cmp    BYTE PTR [eax+3], 0
    test    ch, ch
    jne     @B

    sub     eax, [esp+1*4]    ; src
    add     eax, 3
    ret     1*4

@lb3:
    sub     eax, [esp+1*4]    ; src
    add     eax, 2
    ret     1*4

@lb2:
    sub     eax, [esp+1*4]    ; src
    add     eax, 1
    ret     1*4

@lb1:
    sub     eax, [esp+1*4]    ; src
    ret     1*4

szLen4 endp

OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef



(sorry by the language, I am learning english and assembler  :dazzled:)

[MichaelW]

I couldn't find any reference to Donkey's libraries on this forum, but they are available from his web site:

http://donkey.visualassembler.com/

Donkey uses GoAsm, so the library code will need to be converted to MASM syntax. I seem to recall that Donkey or someone else posted instructions for performing the conversion, but I couldn't find the post. In any case the conversion is not difficult.

Another readily available string length procedure is the strlen function from MSVCRT.DLL. In the MASM32 include file it is named crt_strlen. I don't recall how it compares speed-wise to the optimized procedures.

Here is a small app that performs a function test of the procedures. I moved your procedures into an include file that contains the procedure code with a leading ".code" directive (and no END directive).

Code Select Expand


; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .486                       ; create 32 bit code
    .model flat, stdcall       ; 32 bit memory model
    option casemap :none       ; case sensitive

    include \masm32\include\windows.inc
    include \masm32\include\masm32.inc
    include \masm32\include\kernel32.inc
    include \masm32\include\msvcrt.inc
    includelib \masm32\lib\masm32.lib
    includelib \masm32\lib\kernel32.lib
    includelib \masm32\lib\msvcrt.lib
    include \masm32\macros\macros.asm
    include procs.asm
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
        str0    db 0
        str1    db 'X',0
        str2    db 'XX',0
        str3    db 'XXX',0
        str4    db 'XXXX',0
        str5    db 'XXXXX',0
        str15   db 15 dup('X'),0
        str16   db 16 dup('X'),0
        str17   db 17 dup('X'),0
        str255  db 255 dup('X'),0
        str1000 db 250 dup('X')
                db 250 dup('X')
                db 250 dup('X')
                db 250 dup('X'),0
    .code
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    FOR teststr,<str0,str1,str2,str3,str4,str5,\
            str15,str16,str17,str255,str1000>
        FOR testproc,<StrLen,StrLen1,StrLen2,szLen,szLen1,\
                szLen2,szLen3,szLen4,crt_strlen,lstrlen>
            invoke testproc,ADDR teststr
            print ustr$(eax),32
        ENDM
        print chr$(13,10)
    ENDM
    mov   eax,input(13,10,"Press enter to exit...")
    exit
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start


[hutch--]

I have seen a lot of string length algos in my time but they still break down to 2 types, variations of Agner Fog's strlen DWORD version and various forms of byte scanners. The DWORD version is faster but it has problem with alignment and it can under some circumstances fail if the length is at the end of a memory page. The "szLen" algo is a classic byte scanner unrolled by 4 that is both insensitive to alignment and has no page ending problems so it is properly general purpose.

From memory Donkey had a variation of the Agner Fog design where he aligned the beginning of the algo then read in DWORD size chunks which solves the alignment problem but not the page end problem.

Most zero terminated strings are relatively short (< 128  bytes) and with a byte scanner running at something like 100 meg/sec, I wonder if there is a gain in chasing faster but less general purpose algos.

[denise_amiga]

hello MichaelW

thx for the link to "donkey´s stable"  and thx very much for the small app for test the procedures, it´s help me  :U
the StrLen1 that i post is from msvcr70.dll

I am finishing modifying the masm32.lib, and your small application is to me helpful for test the different versions.
the main changes are changes of the comparisons memory-immediate in the loops, elimination of stack´s frame in algo without locals, and some  small tricks.
the average speed has raised in a 37% and I am very happy.

I like to learn from the bests as some gurus. like (hutch-, you, etc)

and I continue learning

[denise_amiga]

thx MichaelW

Code Select Expand


; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

include masm32rt.inc
include procs.asm

; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
.data
    str0    db 0
    str1    db 128  dup ('Xx'),0
    str2    db 512  dup ('Xx'),0
    str3    db 1024 dup ('Xx'),0
align 4
    txt0    db  "0 bytes",0
    txt1    db  "256 bytes",0
    txt2    db  "1024 bytes",0
    txt3    db  "2048 bytes",0
align 4
    tb_txt  dd  txt0,txt1,txt2,txt3
    alg0    db  "StrLen",0
    alg1    db  "StrLen1",0
    alg2    db  "szLen",0
    alg3    db  "lstrlen",0
align 4
    tb_alg  dd  alg0,alg1,alg2,alg3
.code
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    push    edi
    push    esi
    lea     edi, [tb_alg]
    lea     esi, [tb_txt]
    FOR teststr,<str0,str1,str2,str3>
        FOR testproc,<StrLen,StrLen1,szLen,lstrlen>
            counter_begin 10000000, REALTIME_PRIORITY_CLASS
                invoke  testproc,ADDR teststr
            counter_end
            print   ustr$(eax),9
            print   " clocks for proc - "
            print   [edi],13,10
            add     edi, 4
        ENDM
        lea     edi, [tb_alg]
        print   "--------------------------------  "
        print   [esi],13,10
        add     esi, 4
        print   chr$(13,10)
    ENDM
    mov     eax, input("Press enter to exit...")
    pop     esi
    pop     edi
    exit
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start



[Mark Jones]

Here's my hacked and botched attempt. Be nice to the new guy. :) Results on an AMD XP 1800+. Two results shown, with and without the Sleep API.

Zero Sleep between tests:

Code Select Expand


            StrLen StrLen1 StrLen2 szLen szLen1 szLen2 szLen3 szLen4 lstrlen
0 bytes:      12      10     10     8      5      6      8      5      33
1 bytes:      12      10     11     9      9      8      9      8      39
2 bytes:      14      12     11     13     9      8      10     10     42
3 bytes:      14      12     11     13     9      10     11     10     56
4 bytes:      18      16     13     18     11     10     11     12     45
5 bytes:      18      16     14     18     14     13     13     12     48
15 bytes:     25      22     22     30     24     23     29     29     105
16 bytes:     31      25     25     32     26     25     30     33     96
17 bytes:     31      25     25     34     27     29     34     35     110
255 bytes:    283     249    248    359    342    355    435    451    822
1023 bytes:   1086    933    945    1346   1332   1345   1728   1734   3208


250ms Sleep between tests:

Code Select Expand


            StrLen StrLen1 StrLen2 szLen szLen1 szLen2 szLen3 szLen4 lstrlen
0 bytes:      12      10     9      8      8      8      6      7      33
1 bytes:      12      10     11     9      8      7      7      9      39
2 bytes:      14      13     12     13     8      9      10     10     42
3 bytes:      14      13     12     13     9      10     11     10     44
4 bytes:      18      16     15     18     10     11     12     14     45
5 bytes:      18      16     16     18     12     14     13     14     48
15 bytes:     25      23     23     30     23     24     26     29     93
16 bytes:     31      28     28     32     25     27     30     31     96
17 bytes:     31      28     29     33     26     29     32     32     99
255 bytes:    283     282    296    347    344    345    425    409    823
1023 bytes:   1064    1076   1137   1324   1333   1332   1659   1589   3203


Interesting. Unsure what's going on there. It might be interesting to calculate the mean deviation of some datasets in an effort to determine if Sleep is increasing or decreasing accuracy.

Michael, could I request a CPUID function in timers.asm, so we can have our CPU details right in the console? :toothy

[attachment deleted by admin]

[MichaelW]

Michael, could I request a CPUID function in timers.asm, so we can have our CPU details right in the console? :toothy

Good idea. I already have one, but it's a hack (the original meaning of the term :eek). I'll see what I can do.

[denise_amiga]

result on   PIV 2800@3300

Zero Sleep tests:

                 StrLen  StrLen1 StrLen2  szLen   szLen1  szLen2  szLen3  szLen4 lstrlen
0 bytes:            7       2       1       2       10      -1      -3      8       41
1 bytes:            1       9       2       -2      10      2       1       -1      49
2 bytes:            2       14      10      0       2       1       5       0       40
3 bytes:            2       1       14      15      5       4       11      11      45
4 bytes:            4       5       10      11      12      4       3       10      48
5 bytes:            8       13      6       4       8       4       14      4       56
15 bytes:           13      5       26      19      33      36      22      18      62
16 bytes:           16      16      19      18      32      22      28      29      90
17 bytes:           17      16      27      38      58      24      33      27      78
255 bytes:          238     236     229     353     548     419     422     352     620
1023 bytes:         844     854     849     1341    2077    1573    1586    1333    2325

250ms   Sleep   tests:

                 StrLen  StrLen1 StrLen2  szLen   szLen1  szLen2  szLen3  szLen4 lstrlen
0 bytes:            3       2       0       -3      -3      -3      6       -1      34
1 bytes:            1       1       3       -1      -1      -1      1       -3      38
2 bytes:            14      3       3       3       2       0       0       0       42
3 bytes:            2       5       5       2       14      2       3       0       46
4 bytes:            4       5       6       3       6       3       8       3       47
5 bytes:            4       4       6       4       9       5       5       4       47
15 bytes:           24      13      16      19      32      26      18      19      81
16 bytes:           18      17      19      17      33      22      23      20      75
17 bytes:           16      17      17      26      57      23      39      30      85
255 bytes:          228     222     221     353     535     407     414     349     647
1023 bytes:         838     819     809     1350    2079    1562    1551    1331    2379

note: in my system, StrLen = Strlen1 and szLen = szLen4 (masm32.lib modified), szLen1 is the original without stack´s frame

[Maelstrom]

Dont know if you have seen this one or not...
I saved this from quite awile back when the same thing was tried on another board.

I think the tail end can be modified for faster performance (I remember playing with it) but the inner loop is where this one shines...
If I remember correctly the inner loop, because of the U/V pipes, ran 1 DWORD per 2 cycles?  Maybe my memories faulty :green2

Code Select Expand


; FStrLen - buliaNaza, Lingo12
;
; Returns the length of a null terminated
; string not including the null.

FStrLen proto :dword

.code

option prologue:none
option epilogue:none
FStrLen proc string:dword
        push   esi
        push   ebx
        mov    esi, [esp+8]
        mov    ebx, 80808080h
        mov    eax, [esi]
        xor    edx, edx

    FStrLen_Loop:
        lea    ecx, [eax-10101010h]
        inc    edx
        and    ecx, ebx
        mov    eax, [esi+edx*4]
        jz     FStrLen_Loop

        bsf    ebx, ecx
        dec    edx
        shr    ebx, 3
        lea    eax, [ebx+edx*4]
        pop    ebx
        pop    esi
    ret
FStrLen endp
option prologue:PrologueDef
option epilogue:EpilogueDef

[Maelstrom]

Did some searching on the old boards and found the original posting with comments...

Would be interesting to do a compare with this one :wink

Code Select Expand


FStrLen proc string:dword
        mov     esi, [esp+8]
        mov     eax, [esi]          ; get a dword (buffer is aligned)
        mov     ebx, 80808080h      ; we'll use register ebx rather then immediate 80808080h
        xor     edx, edx            ; edx=0
    C2_loop:
        lea     ecx, [eax-1010101h] ; sub 1 from each byte in eax
        inc     edx                 ; ready for next dword
        test    ecx, ebx            ; test  sign ; ebx= 80808080h     
        mov     eax, [esi+edx*4]    ; get next dword
        jz      C2_loop             ; if not loop again

        test    eax, 000000FFh      ; is al zero?
        jz      C2_minus4           ;
        test    eax, 0000FF00h      ; is ah zero?
        jz      C2_minus3           ;
        test    eax, 00FF0000h      ; is zero?
        jz      C2_minus2           ;
        test    eax, 0FF000000h     ; is zero?
        jnz     C2_loop             ; if not zeroes loop again
        lea     eax, [edx-1]        ; eax= length of string
        ret
    C2_minus2:
        lea     eax, [edx-2]        ; eax= length of string
        ret
    C2_minus3:
        lea     eax, [edx-3]        ; eax= length of string
        ret
    C2_minus4:
        lea     eax, [edx-4]        ; eax= length of string
        ret
FStrLen endp


[hutch--]

First thing to do with that version is to swap EAX and EDX, then use ADD or SUB for the corections instead of LEA which is slow on post PIII hardware.

[denise_amiga]

Maelstrom

Code Select Expand



option prologue:none
option epilogue:none
FStrLen proc string:dword
        push   esi
        push   ebx
        mov    esi, [esp+8]    ; <<< It´s wrong, It has to be 12, because 2 push



[hutch--]

hmmmm,

In its current form, it always returns zero.