ASM for FUN NEW step #1

[raymond]

I would think that using Look-up tables for converting numbers from ascii format to binary may be the fastest option. I don't have the facilities to compare various procedures but someone else may want to test it.
I wrote some code to prepare such an LUT (once which should take only a few nanosecs) then used it to convert an ascii number 1,000,000,000 times (10^9). The timing on my older laptop was 1.5 secs!

Code for preparing LUT

Code Select Expand

.data
      t10   dd    10 DUP(0)
      t100  dd    10 DUP(0)
      t1000 dd    10 DUP(0)

      numbers     db    "3578"

start:

;fill LUTs of multiples
;of 10
      lea   edi,t10
      xor   eax,eax
      mov   edx,10
      mov   ecx,10
   @@:
      stosd
      add   eax,edx
      dec   ecx
      jnz   @B

;of 100
      xor   eax,eax
      mov   edx,100
      mov   ecx,10
   @@:
      stosd
      add   eax,edx
      dec   ecx
      jnz   @B

;of 1000
      xor   eax,eax
      mov   edx,1000
      mov   ecx,10
   @@:
      stosd
      add   eax,edx
      dec   ecx
      jnz   @B

;there is NO need to have a look-up table for multiples of units!!!


Then I ran the following code for converting ascii to binary, using the QueryPerformanceFrequency function for the timing

Code Select Expand

      mov   ecx,1000000000
start1:

      lea   esi,numbers
      mov   edx,[esi]
      and   edx,0f0f0f0fh
      movzx ebx,dl            ;1000s
      mov   eax,t1000[ebx*4]
      movzx ebx,dh            ;100s
      add   eax,t100[ebx*4]
      bswap edx
      movzx ebx,dh            ;10s
      add   eax,t10[ebx*4]
      movzx ebx,dl            ;units
      add   eax,ebx

      dec   ecx
      jnz   start1


[TimoVJL]

Code Select Expand

AMD Athlon(tm) II X2 220 Processor (SSE3)

833     cycles for 100 * C2D_J
2410    cycles for 100 * atodw
34220   cycles for 100 * sscanf
1296    cycles for 100 * min2cvt
1057    cycles for 100 * min1cvt

806     cycles for 100 * C2D_J
2437    cycles for 100 * atodw
34498   cycles for 100 * sscanf
1297    cycles for 100 * min2cvt
1053    cycles for 100 * min1cvt

805     cycles for 100 * C2D_J
2436    cycles for 100 * atodw
34558   cycles for 100 * sscanf
1297    cycles for 100 * min2cvt
1055    cycles for 100 * min1cvt

805     cycles for 100 * C2D_J
2410    cycles for 100 * atodw
34503   cycles for 100 * sscanf
1296    cycles for 100 * min2cvt
1060    cycles for 100 * min1cvt

50      bytes for C2D_J
10      bytes for atodw
22      bytes for sscanf
98      bytes for min2cvt
62      bytes for min1cvt

1234    = eax C2D_J
1234    = eax atodw
1234    = eax sscanf
1234    = eax min2cvt
1234    = eax min1cvt

--- ok ---LUT with Pelles C

Code Select Expand

1: #include <stdio.h>
2: int a10[] = {0,10,20,30,40,50,60,70,80,90};
3: int a100[] = {0,100,200,300,400,500,600,700,800,900};
4: int a1000[] = {0,1000,2000,3000,4000,5000,6000,7000,8000,9000};
5:
6: int __cdecl main(void)

_main:
  [00000000] 55                     push              ebp
  [00000001] 89E5                   mov               ebp,esp
  [00000003] 83EC08                 sub               esp,8
7: {
8: char anum[] = "1234";
  [00000006] C745FB31323334         mov               dword ptr [ebp-5],34333231
  [0000000D] C645FF00               mov               byte ptr [ebp-1],0
9: int num;
10:
11: (*(int*)&anum) &= 0x0f0f0f0f;
  [00000011] 8165FB0F0F0F0F         and               dword ptr [ebp-5],F0F0F0F
12: num = a1000[anum[0]] + a100[anum[1]] + a10[anum[2]] + anum[3];
  [00000018] 0FBE45FB               movsx             eax,byte ptr [ebp-5]
  [0000001C] 8B048500000000         mov               eax,dword ptr [eax*4+_a1000]
  [00000023] 0FBE55FC               movsx             edx,byte ptr [ebp-4]
  [00000027] 03049500000000         add               eax,dword ptr [edx*4+_a100]
  [0000002E] 0FBE55FD               movsx             edx,byte ptr [ebp-3]
  [00000032] 03049500000000         add               eax,dword ptr [edx*4+_a10]
  [00000039] 0FBE55FE               movsx             edx,byte ptr [ebp-2]
  [0000003D] 01D0                   add               eax,edx
13: printf("%u\n", num);
  [0000003F] 50                     push              eax
  [00000040] 6800000000             push              @6
  [00000045] E800000000             call              _printf
  [0000004A] 83C408                 add               esp,8
14: return 0;
  [0000004D] 31C0                   xor               eax,eax
  [0000004F] 89EC                   mov               esp,ebp
  [00000051] 5D                     pop               ebp
  [00000052] C3                     ret               
using temporary string

Code Select Expand


char anum2[] = "1234";
char anum[5];
int num;

12: (*(int*)&anum) = (*(int*)&anum2) & 0x0f0f0f0f;
  [00000011] 8B45FB                 mov               eax,dword ptr [ebp-5]
  [00000014] 250F0F0F0F             and               eax,F0F0F0F
  [00000019] 8945F6                 mov               dword ptr [ebp-A],eax


[jj2007]

I would think that using Look-up tables for converting numbers from ascii format to binary may be the fastest option. I don't have the facilities to compare various procedures but someone else may want to test it.

Thank you, Raymond. Here it is as ConvertLUT:

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz (SSE4)

475     cycles for 100 * C2D_J
1597    cycles for 100 * atodw
22224   cycles for 100 * sscanf
772     cycles for 100 * min2cvt
555     cycles for 100 * min1cvt
640     cycles for 100 * ConvertLUT

497     cycles for 100 * C2D_J
1595    cycles for 100 * atodw
22401   cycles for 100 * sscanf
800     cycles for 100 * min2cvt
584     cycles for 100 * min1cvt
631     cycles for 100 * ConvertLUT

489     cycles for 100 * C2D_J
1598    cycles for 100 * atodw
22796   cycles for 100 * sscanf
776     cycles for 100 * min2cvt
551     cycles for 100 * min1cvt
640     cycles for 100 * ConvertLUT

50      bytes for C2D_J
10      bytes for atodw
22      bytes for sscanf
98      bytes for min2cvt
62      bytes for min1cvt
118     bytes for ConvertLUT

1234    = eax C2D_J
1234    = eax atodw
1234    = eax sscanf
1234    = eax min2cvt
1234    = eax min1cvt
1234    = eax ConvertLUT

[mineiro]

Good job sir raymond and sir TimoVJL;
I created a static aligned LUT table to your procedures in data section.
I passed data pointer by stack, so, inserted a few modifications to deal with this in both codes.

raymond; when I changed bswap in your code by shr and respective changes it performed a bit better in my machine.
I'm leaving original code in testcase, only changed ebx to ecx register usage to follow register preservations without need of push/pop ebx.

TimoVJL; your code suffered performance because value being passed by stack instead of data pointer being passed by stack. I know this can be done inside our code, but just to follow rules. I have tried to insert same overhead in all procedures so result should be honest.
After "and 0f0f0f0fh" I inserted value back to stack. So, I confess it's not the best try because data is in register and go back to stack and read stack data digits each time. If you know better modifications please tell.

I have tried to not touch in yours code, only adapt to windows rules.

sir jj2007; in your testcase some procedures are getting data pointer from register while other procedures are receiving that from stack. This is creating different overheads. In first case it's necessary "mov reg,[reg]" while in other "mov reg,[esp+4] mov reg,[reg]", and at end of procedure first procedure do only "retn" while other "ret 4". Suggestions?

Code Select Expand


wine FourCharsToDword.exe
Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz (SSE4)

562 cycles for 100 * C2D_J
1482 cycles for 100 * atodw
12649 cycles for 100 * sscanf
752 cycles for 100 * min2cvt
477 cycles for 100 * min1cvt
471 cycles for 100 * ray_LUT
741 cycles for 100 * TimoVJL_PellesC_LUT

638 cycles for 100 * C2D_J
1480 cycles for 100 * atodw
12835 cycles for 100 * sscanf
756 cycles for 100 * min2cvt
433 cycles for 100 * min1cvt
476 cycles for 100 * ray_LUT
744 cycles for 100 * TimoVJL_PellesC_LUT

564 cycles for 100 * C2D_J
1505 cycles for 100 * atodw
12630 cycles for 100 * sscanf
778 cycles for 100 * min2cvt
427 cycles for 100 * min1cvt
470 cycles for 100 * ray_LUT
729 cycles for 100 * TimoVJL_PellesC_LUT

561 cycles for 100 * C2D_J
1478 cycles for 100 * atodw
12558 cycles for 100 * sscanf
751 cycles for 100 * min2cvt
432 cycles for 100 * min1cvt
465 cycles for 100 * ray_LUT
730 cycles for 100 * TimoVJL_PellesC_LUT

54 bytes for C2D_J
10 bytes for atodw
22 bytes for sscanf
84 bytes for min2cvt
52 bytes for min1cvt
62 bytes for ray_LUT
70 bytes for TimoVJL_PellesC_LUT

1234 = eax C2D_J
1234 = eax atodw
1234 = eax sscanf
1234 = eax min2cvt
1234 = eax min1cvt
1234 = eax ray_LUT
1234 = eax TimoVJL_PellesC_LUT


PS: sir jj2007 told me in pm that my executables are not running from GUI, so, you must open console to run; or if someone can create an executable direct using windows just post that. I'm doing these thing using linux. Appreciate.

[mineiro]

These are results from jj2007 testcase:

Code Select Expand


wine FourCharsToDword.exe
Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz (SSE4)

479 cycles for 100 * C2D_J
1528 cycles for 100 * atodw
12745 cycles for 100 * sscanf
725 cycles for 100 * min2cvt
493 cycles for 100 * min1cvt
502 cycles for 100 * ConvertLUT

478 cycles for 100 * C2D_J
1610 cycles for 100 * atodw
12623 cycles for 100 * sscanf
745 cycles for 100 * min2cvt
495 cycles for 100 * min1cvt
501 cycles for 100 * ConvertLUT

550 cycles for 100 * C2D_J
1483 cycles for 100 * atodw
12590 cycles for 100 * sscanf
741 cycles for 100 * min2cvt
581 cycles for 100 * min1cvt
500 cycles for 100 * ConvertLUT

50 bytes for C2D_J
10 bytes for atodw
22 bytes for sscanf
98 bytes for min2cvt
62 bytes for min1cvt
118 bytes for ConvertLUT

1234 = eax C2D_J
1234 = eax atodw
1234 = eax sscanf
1234 = eax min2cvt
1234 = eax min1cvt
1234 = eax ConvertLUT


[mineiro]

Thanks for the tip sir jj2007;
I checked command line when building executable and subsystem:WINDOWS was default; I changed that to CONSOLE.
Link version that I was using is v8.???, changed that to Version 5.12.8078.
So, I suppose now can work by double clicking.

[jj2007]

Thanks, mineiro - it works, and now we have a clear winner, at least on my cpu:

Code Select Expand

min1cvt proc _data:dword
option prologue:none
option epilogue:none

mov ecx,[esp+4]
mov eax,[ecx]
xor eax,"0000"      ;and eax,0f0f0f0fh
movd xmm0,eax       ;01020304h
punpcklbw xmm0,xmm2 ;0001000200030004h
pmaddwd xmm0,xmm1   ;mul and add
;---------------------------
;db 66h,0fh,38h,02h,0c0h ;          phaddd xmm0,xmm0 ;SSE3
;movd eax,xmm0

movd eax,xmm0
psrlq xmm0,32
movd ecx,xmm0
add eax,ecx
ret 4
min1cvt endp

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz (SSE4)

655     cycles for 100 * C2D_J
1605    cycles for 100 * atodw
22178   cycles for 100 * sscanf
785     cycles for 100 * min2cvt
475     cycles for 100 * min1cvt
599     cycles for 100 * ray_LUT
661     cycles for 100 * TimoVJL_PellesC_LUT

651     cycles for 100 * C2D_J
1599    cycles for 100 * atodw
22808   cycles for 100 * sscanf
823     cycles for 100 * min2cvt
508     cycles for 100 * min1cvt
607     cycles for 100 * ray_LUT
717     cycles for 100 * TimoVJL_PellesC_LUT

714     cycles for 100 * C2D_J
1615    cycles for 100 * atodw
22657   cycles for 100 * sscanf
778     cycles for 100 * min2cvt
488     cycles for 100 * min1cvt
587     cycles for 100 * ray_LUT
657     cycles for 100 * TimoVJL_PellesC_LUT

696     cycles for 100 * C2D_J
1613    cycles for 100 * atodw
22193   cycles for 100 * sscanf
778     cycles for 100 * min2cvt
487     cycles for 100 * min1cvt
595     cycles for 100 * ray_LUT
664     cycles for 100 * TimoVJL_PellesC_LUT

54      bytes for C2D_J
10      bytes for atodw
22      bytes for sscanf
84      bytes for min2cvt
52      bytes for min1cvt
62      bytes for ray_LUT
70      bytes for TimoVJL_PellesC_LUT

1234    = eax C2D_J
1234    = eax atodw
1234    = eax sscanf
1234    = eax min2cvt
1234    = eax min1cvt
1234    = eax ray_LUT
1234    = eax TimoVJL_PellesC_LUT

It's a pity that this is limited to the exotic test case "four digits"

[daydreamer]

It's a pity that this is limited to the exotic test case "four digits"

its not,thanks everyone for testing different approaches to fast ascii->integer
there is still fastest ascii->double and fastest ascii->64bit integer

[mineiro]

Thanks, mineiro - it works, and now we have a clear winner, at least on my cpu:

Not really, I have absolute sure that this code can be defeat by others, and will perform different in others cpus. This is what I learn in this board.

I forgot how to activate xmm, do you remember? That code is being translated to mmx.
I'm adding a "66h byte" as preffix in instructions in other tests to work with xmm, but I remember that exist other way to do this. Maybe macros!?
db 66h
movd xmm0,eax       ;01020304h
db 66h
punpcklbw xmm0,xmm2 ;0001000200030004h
...

[daydreamer]

Thanks, mineiro - it works, and now we have a clear winner, at least on my cpu:

Not really, I have absolute sure that this code can be defeat by others, and will perform different in others cpus. This is what I learn in this board.

I forgot how to activate xmm, do you remember? That code is being translated to mmx.
I'm adding a "66h byte" as preffix in instructions in other tests to work with xmm, but I remember that exist other way to do this. Maybe macros!?
db 66h
movd xmm0,eax       ;01020304h
db 66h
punpcklbw xmm0,xmm2 ;0001000200030004h
...

change to newer assembler than ml 6.14 solves it without need for macros

[mineiro]

change to newer assembler than ml 6.14 solves it without need for macros

Thanks sir daydreamer.

[frktons]

That's great Guys.

I am happy to see many options are coming out and the speed of the code is quite nice. 

Compliments to everyone partecipating in the game. 

[hutch--]

Here is another approach, a finite state machine, AKA look up tree. 4 character strings fed in, integers fed out. Its big but its reasonably fast. Timings below are with my old i7.

Output

2
9999
5432
8619
9876
2345
1234
7776
8193
4352
test return values - done

timing 10 million matches next, press any key ....

ms = 109 duration
Press any key to continue ...

[jj2007]

Finite state machine, AKA look up tree vs my algo. I hope I didn't make any mistakes in translation. The attachment does not contain the num.asm file - see Hutch' post.

[hutch--]

 

That is genuinely fast and it looks like its producing the right output numbers.