Author Topic: String reverse algo  (Read 2091 times)

nidud

  • Member
  • *****
  • Posts: 2215
    • https://github.com/nidud/asmc
Re: String reverse algo
« Reply #30 on: May 11, 2021, 12:10:25 AM »
Some extended testing.

1. The worst possible solution
Code: [Select]
    .386
    .model flat, c
    .code

    push    ebp
    mov     ebp,esp
    push    esi
    push    edi
    push    ecx
    mov     edi,[ebp+8]
    mov     ecx,-1
    xor     eax,eax
    repnz   scasb
    not     ecx
    dec     ecx
    mov     edi,[ebp+8]
    lea     esi,[edi+ecx-1]
    shr     ecx,1
    jz      done
lupe:
    mov     al,[edi]
    movsb
    mov     [esi-1],al
    sub     esi,2
    loop    lupe
done:
    mov     eax,[ebp+8]
    pop     ecx
    pop     edi
    pop     esi
    leave
    ret

    end

2. Regular x86
Code: [Select]
    .386
    .model flat, c
    .code

    mov     edx,[esp+4]
    mov     ecx,[esp+4]
    xor     eax,eax
slen:
    add     ecx,1
    cmp     al,[ecx-1]
    jne     slen
    sub     ecx,2
lupe:
    cmp     edx,ecx
    ja      done
    mov     al,[edx]
    mov     ah,[ecx]
    mov     [ecx],al
    mov     [edx],ah
    lea     edx,[edx+1]
    lea     ecx,[ecx-1]
    jne     lupe
done:
    mov     eax,[esp+4]
    ret

    end

3. Unaligned XMM strlen()
Code: [Select]
    .686
    .xmm
    .model flat
    .code

    mov     eax,[esp+4]
L1:
    movups  xmm1,[eax]
    pcmpeqb xmm1,xmm0
    pmovmskb ecx,xmm1
    add     eax,16
    test    ecx,ecx
    jz      L1
L2:
    bsf     ecx,ecx
    lea     ecx,[eax+ecx-16-1]
    mov     edx,[esp+4]
lupe:
    cmp     edx,ecx
    ja      done
    mov     al,[edx]
    mov     ah,[ecx]
    mov     [ecx],al
    mov     [edx],ah
    lea     edx,[edx+1]
    lea     ecx,[ecx-1]
    jne     lupe
done:
    mov     eax,[esp+4]
    ret

    end

4. Unaligned XMM strlen() + BSWAP
Code: [Select]
    .686
    .xmm
    .model flat
    .code

    push    esi
    push    edi
    mov     eax,[esp+4][8]
    mov     edi,eax
L1:
    movups  xmm1,[eax]
    pcmpeqb xmm1,xmm0
    pmovmskb ecx,xmm1
    add     eax,16
    test    ecx,ecx
    jz      L1
    bsf     ecx,ecx
    lea     ecx,[eax+ecx-16]
    lea     esi,[ecx-1]
    sub     ecx,edi
    shr     ecx,1
    jz      done
    cmp     ecx,4
    jb      L3
    sub     esi,3
L2:
    mov     eax,[edi]
    mov     edx,[esi]
    bswap   eax
    bswap   edx
    mov     [esi],eax
    mov     [edi],edx
    add     edi,4
    sub     esi,4
    sub     ecx,4
    cmp     ecx,4
    jae     L2
L3:
    cmp     edi,esi
    jae     done
    mov     al,[edi]
    mov     dl,[esi]
    mov     [esi],al
    mov     [edi],dl
    inc     edi
    dec     esi
    jmp     L3
done:
    pop     edi
    pop     esi
    mov     eax,[esp+4]
    ret

    end

Result for strings 10, 100, and 1000:
Code: [Select]
Intel(R) Core(TM) i5-6500T CPU @ 2.50GHz (AVX2)
----------------------------------------------
-- test(10)
    88394 cycles, rep(1000), code(  0) 0.asm: msvcrt.strrev()
    27312 cycles, rep(1000), code( 46) 1.asm: x86
    34096 cycles, rep(1000), code( 58) 2.asm: xmm
    27771 cycles, rep(1000), code( 99) 3.asm: xmm+bswap
   116848 cycles, rep(1000), code( 51) 4.asm: movs/scans/push/loop
-- test(11)
    87652 cycles, rep(1000), code(  0) 0.asm: msvcrt.strrev()
    28214 cycles, rep(1000), code( 46) 1.asm: x86
    38784 cycles, rep(1000), code( 58) 2.asm: xmm
    29538 cycles, rep(1000), code( 99) 3.asm: xmm+bswap
   118010 cycles, rep(1000), code( 51) 4.asm: movs/scans/push/loop
-- test(12)
    92374 cycles, rep(1000), code(  0) 0.asm: msvcrt.strrev()
    28886 cycles, rep(1000), code( 46) 1.asm: x86
    33395 cycles, rep(1000), code( 58) 2.asm: xmm
    28642 cycles, rep(1000), code( 99) 3.asm: xmm+bswap
   130416 cycles, rep(1000), code( 51) 4.asm: movs/scans/push/loop

total [10 .. 12], 1++
    84412 cycles 1.asm: x86
    85951 cycles 3.asm: xmm+bswap
   106275 cycles 2.asm: xmm
   268420 cycles 0.asm: msvcrt.strrev()
   365274 cycles 4.asm: movs/scans/push/loop

-- test(100)
   160753 cycles, rep(500), code(  0) 0.asm: msvcrt.strrev()
   106156 cycles, rep(500), code( 46) 1.asm: x86
    61151 cycles, rep(500), code( 58) 2.asm: xmm
    26790 cycles, rep(500), code( 99) 3.asm: xmm+bswap
   337887 cycles, rep(500), code( 51) 4.asm: movs/scans/push/loop
-- test(101)
   160862 cycles, rep(500), code(  0) 0.asm: msvcrt.strrev()
   107870 cycles, rep(500), code( 46) 1.asm: x86
    58470 cycles, rep(500), code( 58) 2.asm: xmm
    28809 cycles, rep(500), code( 99) 3.asm: xmm+bswap
   338037 cycles, rep(500), code( 51) 4.asm: movs/scans/push/loop
-- test(102)
   162826 cycles, rep(500), code(  0) 0.asm: msvcrt.strrev()
   107407 cycles, rep(500), code( 46) 1.asm: x86
    60728 cycles, rep(500), code( 58) 2.asm: xmm
    25726 cycles, rep(500), code( 99) 3.asm: xmm+bswap
   342103 cycles, rep(500), code( 51) 4.asm: movs/scans/push/loop

total [100 .. 102], 1++
    81325 cycles 3.asm: xmm+bswap
   180349 cycles 2.asm: xmm
   321433 cycles 1.asm: x86
   484441 cycles 0.asm: msvcrt.strrev()
  1018027 cycles 4.asm: movs/scans/push/loop

-- test(1000)
   135563 cycles, rep(50), code(  0) 0.asm: msvcrt.strrev()
    92943 cycles, rep(50), code( 46) 1.asm: x86
    55740 cycles, rep(50), code( 58) 2.asm: xmm
    20378 cycles, rep(50), code( 99) 3.asm: xmm+bswap
   310473 cycles, rep(50), code( 51) 4.asm: movs/scans/push/loop
-- test(1001)
   138692 cycles, rep(50), code(  0) 0.asm: msvcrt.strrev()
    93863 cycles, rep(50), code( 46) 1.asm: x86
    52634 cycles, rep(50), code( 58) 2.asm: xmm
    22276 cycles, rep(50), code( 99) 3.asm: xmm+bswap
   305763 cycles, rep(50), code( 51) 4.asm: movs/scans/push/loop
-- test(1002)
   136968 cycles, rep(50), code(  0) 0.asm: msvcrt.strrev()
    92692 cycles, rep(50), code( 46) 1.asm: x86
    55150 cycles, rep(50), code( 58) 2.asm: xmm
    21963 cycles, rep(50), code( 99) 3.asm: xmm+bswap
   312311 cycles, rep(50), code( 51) 4.asm: movs/scans/push/loop

total [1000 .. 1002], 1++
    64617 cycles 3.asm: xmm+bswap
   163524 cycles 2.asm: xmm
   279498 cycles 1.asm: x86
   411223 cycles 0.asm: msvcrt.strrev()
   928547 cycles 4.asm: movs/scans/push/loop

nidud

  • Member
  • *****
  • Posts: 2215
    • https://github.com/nidud/asmc
Re: String reverse algo
« Reply #31 on: May 11, 2021, 03:02:40 AM »
Note that the unaligned memory read will blow up as it reads ahead so all 16 byte fetches should be aligned. This add some overhang on small lengths but improves with increased size.

Code: [Select]
    .686
    .xmm
    .model flat
    .code

    mov     eax,[esp+4]
    mov     ecx,eax
    and     eax,-16
    and     ecx,16-1
    or      edx,-1
    shl     edx,cl
    xorps   xmm0,xmm0
    pcmpeqb xmm0,[eax]
    add     eax,16
    pmovmskb ecx,xmm0
    xorps   xmm0,xmm0
    and     ecx,edx
    jnz     L2
L1:
    movaps  xmm1,[eax]
    pcmpeqb xmm1,xmm0
    pmovmskb ecx,xmm1
    add     eax,16
    test    ecx,ecx
    jz      L1
L2:
    bsf     ecx,ecx
    lea     ecx,[eax+ecx-16-1]
    mov     edx,[esp+4]
lupe:
    cmp     edx,ecx
    ja      done
    mov     al,[edx]
    mov     ah,[ecx]
    mov     [ecx],al
    mov     [edx],ah
    lea     edx,[edx+1]
    lea     ecx,[ecx-1]
    jne     lupe
done:
    mov     eax,[esp+4]
    ret

    end

Code: [Select]
    .686
    .xmm
    .model flat
    .code

    push    esi
    push    edi
    mov     eax,[esp+4][8]
    mov     edi,eax
    mov     ecx,eax
    and     eax,-16
    and     ecx,16-1
    or      edx,-1
    shl     edx,cl
    xorps   xmm0,xmm0
    pcmpeqb xmm0,[eax]
    add     eax,16
    pmovmskb ecx,xmm0
    xorps   xmm0,xmm0
    and     ecx,edx
    jnz     L2
L1:
    movaps  xmm1,[eax]
    pcmpeqb xmm1,xmm0
    pmovmskb ecx,xmm1
    add     eax,16
    test    ecx,ecx
    jz      L1
L2:
    bsf     ecx,ecx
    lea     ecx,[eax+ecx-16]
    lea     esi,[ecx-1]
    sub     ecx,edi
    shr     ecx,1
    jz      done
    cmp     ecx,4
    jb      L4
    sub     esi,3
L3:
    mov     eax,[edi]
    mov     edx,[esi]
    bswap   eax
    bswap   edx
    mov     [esi],eax
    mov     [edi],edx
    add     edi,4
    sub     esi,4
    sub     ecx,4
    cmp     ecx,4
    jae     L3
L4:
    cmp     edi,esi
    jae     done
    mov     al,[edi]
    mov     dl,[esi]
    mov     [esi],al
    mov     [edi],dl
    inc     edi
    dec     esi
    jmp     L4
done:
    pop     edi
    pop     esi
    mov     eax,[esp+4]
    ret

    end

Code: [Select]
Intel(R) Core(TM) i5-6500T CPU @ 2.50GHz (AVX2)
----------------------------------------------
-- test(10)
    76758 cycles, rep(1000), code(  0) 0.asm: msvcrt.strrev()
    24739 cycles, rep(1000), code( 46) 1.asm: x86
    30804 cycles, rep(1000), code( 58) 2.asm: xmm
    25991 cycles, rep(1000), code( 99) 3.asm: xmm+bswap
   106787 cycles, rep(1000), code( 51) 4.asm: movs/scans/push/loop
    27042 cycles, rep(1000), code(133) 5.asm: xmm+bswap aligned
    31438 cycles, rep(1000), code( 92) 6.asm: xmm aligned
-- test(11)
    78295 cycles, rep(1000), code(  0) 0.asm: msvcrt.strrev()
    26293 cycles, rep(1000), code( 46) 1.asm: x86
    35994 cycles, rep(1000), code( 58) 2.asm: xmm
    26041 cycles, rep(1000), code( 99) 3.asm: xmm+bswap
   109591 cycles, rep(1000), code( 51) 4.asm: movs/scans/push/loop
    27308 cycles, rep(1000), code(133) 5.asm: xmm+bswap aligned
    37064 cycles, rep(1000), code( 92) 6.asm: xmm aligned
-- test(12)
    84334 cycles, rep(1000), code(  0) 0.asm: msvcrt.strrev()
    26791 cycles, rep(1000), code( 46) 1.asm: x86
    32476 cycles, rep(1000), code( 58) 2.asm: xmm
    26098 cycles, rep(1000), code( 99) 3.asm: xmm+bswap
   117670 cycles, rep(1000), code( 51) 4.asm: movs/scans/push/loop
    27989 cycles, rep(1000), code(133) 5.asm: xmm+bswap aligned
    35030 cycles, rep(1000), code( 92) 6.asm: xmm aligned

total [10 .. 12], 1++
    77823 cycles 1.asm: x86
    78130 cycles 3.asm: xmm+bswap
    82339 cycles 5.asm: xmm+bswap aligned
    99274 cycles 2.asm: xmm
   103532 cycles 6.asm: xmm aligned
   239387 cycles 0.asm: msvcrt.strrev()
   334048 cycles 4.asm: movs/scans/push/loop

-- test(100)
   148608 cycles, rep(500), code(  0) 0.asm: msvcrt.strrev()
    97157 cycles, rep(500), code( 46) 1.asm: x86
    55544 cycles, rep(500), code( 58) 2.asm: xmm
    24806 cycles, rep(500), code( 99) 3.asm: xmm+bswap
   309528 cycles, rep(500), code( 51) 4.asm: movs/scans/push/loop
    24176 cycles, rep(500), code(133) 5.asm: xmm+bswap aligned
    55843 cycles, rep(500), code( 92) 6.asm: xmm aligned
-- test(101)
   148643 cycles, rep(500), code(  0) 0.asm: msvcrt.strrev()
    98903 cycles, rep(500), code( 46) 1.asm: x86
    56304 cycles, rep(500), code( 58) 2.asm: xmm
    26111 cycles, rep(500), code( 99) 3.asm: xmm+bswap
   309416 cycles, rep(500), code( 51) 4.asm: movs/scans/push/loop
    24892 cycles, rep(500), code(133) 5.asm: xmm+bswap aligned
    55695 cycles, rep(500), code( 92) 6.asm: xmm aligned
-- test(102)
   150413 cycles, rep(500), code(  0) 0.asm: msvcrt.strrev()
    99857 cycles, rep(500), code( 46) 1.asm: x86
    58230 cycles, rep(500), code( 58) 2.asm: xmm
    26703 cycles, rep(500), code( 99) 3.asm: xmm+bswap
   326146 cycles, rep(500), code( 51) 4.asm: movs/scans/push/loop
    25979 cycles, rep(500), code(133) 5.asm: xmm+bswap aligned
    57621 cycles, rep(500), code( 92) 6.asm: xmm aligned

total [100 .. 102], 1++
    75047 cycles 5.asm: xmm+bswap aligned
    77620 cycles 3.asm: xmm+bswap
   169159 cycles 6.asm: xmm aligned
   170078 cycles 2.asm: xmm
   295917 cycles 1.asm: x86
   447664 cycles 0.asm: msvcrt.strrev()
   945090 cycles 4.asm: movs/scans/push/loop

-- test(1000)
   126402 cycles, rep(50), code(  0) 0.asm: msvcrt.strrev()
    85049 cycles, rep(50), code( 46) 1.asm: x86
    52236 cycles, rep(50), code( 58) 2.asm: xmm
    18995 cycles, rep(50), code( 99) 3.asm: xmm+bswap
   289386 cycles, rep(50), code( 51) 4.asm: movs/scans/push/loop
    17431 cycles, rep(50), code(133) 5.asm: xmm+bswap aligned
    50423 cycles, rep(50), code( 92) 6.asm: xmm aligned
-- test(1001)
   127013 cycles, rep(50), code(  0) 0.asm: msvcrt.strrev()
    84896 cycles, rep(50), code( 46) 1.asm: x86
    49921 cycles, rep(50), code( 58) 2.asm: xmm
    19098 cycles, rep(50), code( 99) 3.asm: xmm+bswap
   287230 cycles, rep(50), code( 51) 4.asm: movs/scans/push/loop
    17220 cycles, rep(50), code(133) 5.asm: xmm+bswap aligned
    49247 cycles, rep(50), code( 92) 6.asm: xmm aligned
-- test(1002)
   126678 cycles, rep(50), code(  0) 0.asm: msvcrt.strrev()
    85061 cycles, rep(50), code( 46) 1.asm: x86
    52449 cycles, rep(50), code( 58) 2.asm: xmm
    19079 cycles, rep(50), code( 99) 3.asm: xmm+bswap
   288797 cycles, rep(50), code( 51) 4.asm: movs/scans/push/loop
    17289 cycles, rep(50), code(133) 5.asm: xmm+bswap aligned
    50188 cycles, rep(50), code( 92) 6.asm: xmm aligned

total [1000 .. 1002], 1++
    51940 cycles 5.asm: xmm+bswap aligned
    57172 cycles 3.asm: xmm+bswap
   149858 cycles 6.asm: xmm aligned
   154606 cycles 2.asm: xmm
   255006 cycles 1.asm: x86
   380093 cycles 0.asm: msvcrt.strrev()
   865413 cycles 4.asm: movs/scans/push/loop