Sorting strings

[RuiLoureiro]

Hi Gunther,
                   yes for all 3, if you dont mind
                   Thanks.

[RuiLoureiro]

In the following example, each procedure
moves 100 bytes (string length) to the right
to insert strings at position 0.

Strange result (i need to see why: nothing wrong!):

289 milliseconds, INSAtoB_XZZE-1027 bytes
492 milliseconds, INSAtoB_XZZE- 503 bytes   

INSAtoB_X   ->>> moves only BYTES

INSAtoB_BA and INSAtoB_BB use an auxiliary buffer

INSAtoB_BA   ->>> moves only BYTES
INSAtoB_BB   ->>> moves DWORDS+BYTES

It seems that "auxiliary buffer" is not a good idea.

INSERTING AT POSITION 0 -string length=100
-----------------------------------------------------
Intel(R) Pentium(R) 4 CPU 3.40GHz (SSE3)
-----------------------------------------------------
***** Time table *****

  39 milliseconds, INSAtoB_XZZE-   3 bytes
  41 milliseconds, INSAtoB_XZZE-   1 bytes
  55 milliseconds, INSAtoB_XZZF-   3 bytes
  62 milliseconds, INSAtoB_XZZF-  15 bytes
  62 milliseconds, INSAtoB_XZZF-   1 bytes
  74 milliseconds, INSAtoB_XZZE-  55 bytes
  84 milliseconds, INSAtoB_XZZE-  15 bytes
  86 milliseconds, INSAtoB_XZZE-   2 bytes
  95 milliseconds, INSAtoB_XZZE-   4 bytes
  96 milliseconds, INSAtoB_XZZF-  55 bytes
  96 milliseconds, INSAtoB_XZZF-   2 bytes
  96 milliseconds, INSAtoB_XZZF-   4 bytes
102 milliseconds, INSAtoB_X-      2 bytes
103 milliseconds, INSAtoB_X-      1 bytes
113 milliseconds, INSAtoB_XZZF- 103 bytes
119 milliseconds, INSAtoB_X-     15 bytes
121 milliseconds, INSAtoB_XZZE- 103 bytes
126 milliseconds, INSAtoB_X-      3 bytes
129 milliseconds, INSAtoB_X-      4 bytes
130 milliseconds, INSAtoB_BB-     2 bytes
146 milliseconds, INSAtoB_X-     55 bytes
161 milliseconds, INSAtoB_XZZF- 203 bytes
168 milliseconds, INSAtoB_BB-     1 bytes
173 milliseconds, INSAtoB_BB-     3 bytes
173 milliseconds, INSAtoB_X-    103 bytes
174 milliseconds, INSAtoB_BA-     1 bytes
178 milliseconds, INSAtoB_BA-     4 bytes
178 milliseconds, INSAtoB_BB-     4 bytes
183 milliseconds, INSAtoB_BA-     3 bytes
186 milliseconds, INSAtoB_BA-     2 bytes
197 milliseconds, INSAtoB_BB-    15 bytes
202 milliseconds, INSAtoB_BB-    55 bytes
204 milliseconds, INSAtoB_BA-    15 bytes
217 milliseconds, INSAtoB_XZZE- 203 bytes
259 milliseconds, INSAtoB_BA-    55 bytes
283 milliseconds, INSAtoB_X-    203 bytes

289 milliseconds, INSAtoB_XZZE-1027 bytes

320 milliseconds, INSAtoB_BA-   103 bytes
363 milliseconds, INSAtoB_BB-   103 bytes
417 milliseconds, INSAtoB_X-    503 bytes
448 milliseconds, INSAtoB_BA-   203 bytes
476 milliseconds, INSAtoB_BB-   203 bytes

492 milliseconds, INSAtoB_XZZE- 503 bytes
494 milliseconds, INSAtoB_XZZF- 503 bytes

754 milliseconds, INSAtoB_X-   1027 bytes
768 milliseconds, INSAtoB_XZZF-1027 bytes

841 milliseconds, INSAtoB_BA-   503 bytes
950 milliseconds, INSAtoB_BB-   503 bytes
1081 milliseconds, INSAtoB_BB-  1027 bytes
1489 milliseconds, INSAtoB_BA-  1027 bytes
********** END III **********

[Gunther]

Hi Rui,

here are the results. String position 7:

Code Select Expand


INSERTING AT POSITION 7 -string length=100
------------------------------------------
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
------------------------------------------
***** Time table *****

0 milliseconds, INSAtoB_XZZF-   0 bytes
0 milliseconds, INSAtoB_X-    0 bytes
1 milliseconds, INSAtoB_XZZE-   0 bytes
13 milliseconds, INSAtoB_XZZF-   4 bytes
14 milliseconds, INSAtoB_XZZE-   1 bytes
14 milliseconds, INSAtoB_XZZF-   1 bytes
14 milliseconds, INSAtoB_XZZF-   2 bytes
15 milliseconds, INSAtoB_XZZE-   3 bytes
15 milliseconds, INSAtoB_XZZF-   3 bytes
17 milliseconds, INSAtoB_XZZF-  15 bytes
18 milliseconds, INSAtoB_XZZE-  15 bytes
18 milliseconds, INSAtoB_XZZE-   4 bytes
20 milliseconds, INSAtoB_XZZE-   2 bytes
23 milliseconds, INSAtoB_XZZF-  55 bytes
32 milliseconds, INSAtoB_XZZE- 103 bytes
32 milliseconds, INSAtoB_XZZE-  55 bytes
32 milliseconds, INSAtoB_XZZF- 103 bytes
53 milliseconds, INSAtoB_XZZF- 203 bytes
55 milliseconds, INSAtoB_X-    1 bytes
56 milliseconds, INSAtoB_XZZE- 203 bytes
57 milliseconds, INSAtoB_X-    3 bytes
62 milliseconds, INSAtoB_X-    2 bytes
63 milliseconds, INSAtoB_X-    4 bytes
64 milliseconds, INSAtoB_X-   15 bytes
84 milliseconds, INSAtoB_XZZE- 503 bytes
91 milliseconds, INSAtoB_XZZF- 503 bytes
92 milliseconds, INSAtoB_X-   55 bytes
112 milliseconds, INSAtoB_X-  103 bytes
160 milliseconds, INSAtoB_XZZF-1027 bytes
160 milliseconds, INSAtoB_XZZE-1027 bytes
171 milliseconds, INSAtoB_X-  203 bytes
319 milliseconds, INSAtoB_X-  503 bytes
601 milliseconds, INSAtoB_X- 1027 bytes
********** END III **********

String position 50:

Code Select Expand


INSERTING AT POSITION 50 -string length=100
------------------------------------------
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
------------------------------------------
***** Time table *****

0 milliseconds, INSAtoB_XZZF-   0 bytes
0 milliseconds, INSAtoB_X-    0 bytes
1 milliseconds, INSAtoB_XZZE-   0 bytes
8 milliseconds, INSAtoB_XZZF-   4 bytes
9 milliseconds, INSAtoB_XZZF-   1 bytes
9 milliseconds, INSAtoB_XZZE-   1 bytes
10 milliseconds, INSAtoB_XZZF-   3 bytes
10 milliseconds, INSAtoB_XZZF-   2 bytes
10 milliseconds, INSAtoB_XZZE-   3 bytes
11 milliseconds, INSAtoB_XZZE-   4 bytes
12 milliseconds, INSAtoB_XZZE-   2 bytes
12 milliseconds, INSAtoB_XZZF-  15 bytes
13 milliseconds, INSAtoB_XZZE-  15 bytes
18 milliseconds, INSAtoB_XZZF-  55 bytes
21 milliseconds, INSAtoB_XZZE-  55 bytes
22 milliseconds, INSAtoB_XZZE- 103 bytes
28 milliseconds, INSAtoB_XZZF- 103 bytes
33 milliseconds, INSAtoB_X-    1 bytes
34 milliseconds, INSAtoB_X-    3 bytes
40 milliseconds, INSAtoB_X-    2 bytes
41 milliseconds, INSAtoB_X-    4 bytes
42 milliseconds, INSAtoB_X-   15 bytes
48 milliseconds, INSAtoB_XZZF- 203 bytes
51 milliseconds, INSAtoB_XZZE- 203 bytes
71 milliseconds, INSAtoB_X-   55 bytes
79 milliseconds, INSAtoB_XZZE- 503 bytes
86 milliseconds, INSAtoB_XZZF- 503 bytes
91 milliseconds, INSAtoB_X-  103 bytes
150 milliseconds, INSAtoB_X-  203 bytes
155 milliseconds, INSAtoB_XZZF-1027 bytes
158 milliseconds, INSAtoB_XZZE-1027 bytes
299 milliseconds, INSAtoB_X-  503 bytes
579 milliseconds, INSAtoB_X- 1027 bytes
********** END III **********

String position 93:

Code Select Expand


INSERTING AT POSITION 93 -string length=100
------------------------------------------
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
------------------------------------------
***** Time table *****

1 milliseconds, INSAtoB_XZZF-   0 bytes
1 milliseconds, INSAtoB_XZZE-   0 bytes
1 milliseconds, INSAtoB_X-    0 bytes
3 milliseconds, INSAtoB_X-    1 bytes
4 milliseconds, INSAtoB_XZZF-   1 bytes
4 milliseconds, INSAtoB_XZZF-   2 bytes
4 milliseconds, INSAtoB_XZZE-   1 bytes
5 milliseconds, INSAtoB_XZZE-   2 bytes
5 milliseconds, INSAtoB_XZZF-   3 bytes
5 milliseconds, INSAtoB_XZZF-   4 bytes
5 milliseconds, INSAtoB_X-    3 bytes
5 milliseconds, INSAtoB_XZZE-   4 bytes
5 milliseconds, INSAtoB_XZZE-   3 bytes
7 milliseconds, INSAtoB_XZZE-  15 bytes
7 milliseconds, INSAtoB_X-    2 bytes
7 milliseconds, INSAtoB_XZZF-  15 bytes
7 milliseconds, INSAtoB_X-    4 bytes
13 milliseconds, INSAtoB_X-   15 bytes
13 milliseconds, INSAtoB_XZZF-  55 bytes
14 milliseconds, INSAtoB_XZZE-  55 bytes
17 milliseconds, INSAtoB_XZZE- 103 bytes
23 milliseconds, INSAtoB_XZZF- 103 bytes
38 milliseconds, INSAtoB_X-   55 bytes
42 milliseconds, INSAtoB_XZZE- 203 bytes
42 milliseconds, INSAtoB_XZZF- 203 bytes
62 milliseconds, INSAtoB_X-  103 bytes
74 milliseconds, INSAtoB_XZZE- 503 bytes
81 milliseconds, INSAtoB_XZZF- 503 bytes
116 milliseconds, INSAtoB_X-  203 bytes
149 milliseconds, INSAtoB_XZZE-1027 bytes
149 milliseconds, INSAtoB_XZZF-1027 bytes
271 milliseconds, INSAtoB_X-  503 bytes
545 milliseconds, INSAtoB_X- 1027 bytes
********** END III **********


I hope that helps.

Gunther

[RuiLoureiro]

Thank you so much, Gunther  :t

XZZE or XZZF are good options

18 milliseconds to insert 55 bytes at the middle
seems to be good.

----------------------------
Results from Gunther
----------------------------

INSERTING AT POSITION 7 -string length=100
-------------------------------------------------------------
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
-------------------------------------------------------------
***** Time table *****

17 milliseconds, INSAtoB_XZZF-  15 bytes
18 milliseconds, INSAtoB_XZZE-  15 bytes
23 milliseconds, INSAtoB_XZZF-  55 bytes
32 milliseconds, INSAtoB_XZZE- 103 bytes
32 milliseconds, INSAtoB_XZZE-  55 bytes
32 milliseconds, INSAtoB_XZZF- 103 bytes
53 milliseconds, INSAtoB_XZZF- 203 bytes
56 milliseconds, INSAtoB_XZZE- 203 bytes
64 milliseconds, INSAtoB_X-     15 bytes
84 milliseconds, INSAtoB_XZZE- 503 bytes
91 milliseconds, INSAtoB_XZZF- 503 bytes
92 milliseconds, INSAtoB_X-     55 bytes
112 milliseconds, INSAtoB_X-    103 bytes
160 milliseconds, INSAtoB_XZZF-1027 bytes
160 milliseconds, INSAtoB_XZZE-1027 bytes
171 milliseconds, INSAtoB_X-    203 bytes
319 milliseconds, INSAtoB_X-    503 bytes
601 milliseconds, INSAtoB_X-   1027 bytes
********** END III **********

INSERTING AT POSITION 50 -string length=100
--------------------------------------------------------------
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
--------------------------------------------------------------
***** Time table *****

12 milliseconds, INSAtoB_XZZF-  15 bytes
13 milliseconds, INSAtoB_XZZE-  15 bytes
18 milliseconds, INSAtoB_XZZF-  55 bytes
21 milliseconds, INSAtoB_XZZE-  55 bytes
22 milliseconds, INSAtoB_XZZE- 103 bytes
28 milliseconds, INSAtoB_XZZF- 103 bytes
42 milliseconds, INSAtoB_X-     15 bytes
48 milliseconds, INSAtoB_XZZF- 203 bytes
51 milliseconds, INSAtoB_XZZE- 203 bytes
71 milliseconds, INSAtoB_X-     55 bytes
79 milliseconds, INSAtoB_XZZE- 503 bytes
86 milliseconds, INSAtoB_XZZF- 503 bytes
91 milliseconds, INSAtoB_X-    103 bytes
150 milliseconds, INSAtoB_X-    203 bytes
155 milliseconds, INSAtoB_XZZF-1027 bytes  <<<<-----
158 milliseconds, INSAtoB_XZZE-1027 bytes
299 milliseconds, INSAtoB_X-    503 bytes
579 milliseconds, INSAtoB_X-   1027 bytes
********** END III **********

INSERTING AT POSITION 93 -string length=100
-------------------------------------------------------------
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
-------------------------------------------------------------
***** Time table *****

  7 milliseconds, INSAtoB_XZZE-  15 bytes
  7 milliseconds, INSAtoB_XZZF-  15 bytes
13 milliseconds, INSAtoB_X-     15 bytes
13 milliseconds, INSAtoB_XZZF-  55 bytes
14 milliseconds, INSAtoB_XZZE-  55 bytes
17 milliseconds, INSAtoB_XZZE- 103 bytes
23 milliseconds, INSAtoB_XZZF- 103 bytes
38 milliseconds, INSAtoB_X-     55 bytes
42 milliseconds, INSAtoB_XZZE- 203 bytes
42 milliseconds, INSAtoB_XZZF- 203 bytes
62 milliseconds, INSAtoB_X-    103 bytes
74 milliseconds, INSAtoB_XZZE- 503 bytes
81 milliseconds, INSAtoB_XZZF- 503 bytes
116 milliseconds, INSAtoB_X-    203 bytes
149 milliseconds, INSAtoB_XZZE-1027 bytes
149 milliseconds, INSAtoB_XZZF-1027 bytes
271 milliseconds, INSAtoB_X-    503 bytes
545 milliseconds, INSAtoB_X-   1027 bytes
********** END III **********

[Gunther]

Hi Rui,

Thank you so much, Gunther  :t

You're welcome.

XZZE or XZZF are good options

18 milliseconds to insert 55 bytes at the middle
seems to be good.

Yes, indeed. Not so bad.

Gunther

[RuiLoureiro]

Hi Gunther  :t
              In my reply #71 we see that we need 137 milliseconds to MOV or ADD 1027 bytes. Now, to insert at position 50, moving bytes (50 bytes), we need 155 milliseconds to insert 1027 bytes. Seems to be good. Of course, in your powerful i7 !
note: "moving bytes" means DWORDS+BYTES. If we need to move 15 bytes, we move 3 DWORDS + 3 BYTES.

[guga]

Hi Rui
here is a function i made that you could adapt to your needs or even improve it. It copies from 128 to 128 bits.

It works for strings or any other data set. Didn´t fully tested, but so far t is very very fast.

Code Select Expand


; A replacement for memcpy inside msvcrt.dll. Fast memory copy of large buffers. It copies from 128 to 128 bits at once. (4 Dwords)
Proc memcpy:
    Arguments @pDest, @pSource, @Length
    Uses esi, edi, ecx, edx, eax

    mov edi D@pDest
    mov esi D@pSource

    ; we are copying a memory from 128 to 128 bytes at once
    mov ecx D@Length
    mov eax ecx | shr ecx 4 ; integer count. Divide by 16 (4 dwords)
    mov edx ecx | shl edx 4 | sub eax edx ; remainder

    xor edx edx ; here it is used as an index
    While ecx <> 0
        movupd XMM1 X$esi+edx*8 ; copy the 1st 4 dwords from esi to register XMM
        movupd X$edi+edx*8 XMM1 ; copy the 1st 4 dwords from register XMM to edi
        add edx 2 ; we are copying the 128 bits. So instead simply inc by 1, we made it by 2, because each index holds only 8 bytes (limitation of the operand multiplication edx*8 / esi*8 etc)
                  ; So, when edx = 0. edx*8 = 0. X$esi will point to esi+0 bytes
                  ; when edx = 2. edx*8*2 = edx*16. X$esi will point to esi+16 bytes
                  ; when edx = 4. edx*8*4 =edx*32. X$esi will point to esi+32  bytes.
                  ; So. The important is that after each loop esiand edi must points 16 bytes ahead.
        dec ecx   ; ecx is our counter. It simply computes the lenght/16. Why 16 ? because we are jumping from 4 to 4 dwords. Which means that the loop is 16 x faster then using a regular byte by byte operation.
    End_While
    emms ; clear the regsters back to use on FPU
    shl edx 3 ; mul edx by 8 to get the pos
    add edi edx
    add esi edx

    ; If the memory of not 4 dword aligned we may have some remainder here So, just clean them.
    mov ecx eax
    While ecx <> 0
        movsb
        dec ecx
    End_While

EndP


[jj2007]

Hi Gustavo,

The emms must be a leftover from previous MMX versions ;-)

BTW memcpy has been beaten to death here.

[guga]

Hi JJ, tks

I searched the link, but the file was deleted from the old forum. Do you have the source for the memcpy so i can test ?

Btw..the memcpy is from lingo ? He usually code well for speed.

[guga]

I found one from my old copy of the 2012 masm form

Code Select Expand



regcopy proc src:DWORD,dst:DWORD,ln:DWORD

    push ebx
    push esi
    push edi
    push ebp

    mov esi, [esp+4+16]     ; src
    mov edi, [esp+8+16]     ; dst
    mov ecx, [esp+12+16]    ; ln

    shr ecx, 4              ; div by 16
    jz tail

  @@:
    mov eax, [esi]
    mov ebx, [esi+4]
    mov edx, [esi+8]
    mov ebp, [esi+12]
    mov [edi], eax
    mov [edi+4], ebx
    mov [edi+8], edx
    mov [edi+12], ebp
    add esi, 16
    add edi, 16
    sub ecx, 1
    jns @B

  tail:
    mov ecx, [esp+12+16]    ; ln
    and ecx, 4
    jz quit

  @@:
    movzx eax, BYTE PTR [esi]
    mov [edi], al
    add esi, 1
    add edi, 1
    sub ecx, 1
    jnz @B

  quit:
    pop ebp
    pop edi
    pop esi
    pop ebx

    ret 12

regcopy endp


But...If is this one....on my tests, the function i made is twice as faster ? Or im analyzing the wrong function to test ?

[jj2007]

I searched the link, but the file was deleted from the old forum. Do you have the source for the memcpy so i can test ?

Here it is.

[nidud]

deleted

[guga]

Tks JJ. I forgot I was already tested it :)

I´ll take a look and test on the new BenchMark Template app

[RuiLoureiro]

guga, logo que possa vou tentar  :t

[RuiLoureiro]

Hi
In the following example, each procedure
moves 100 bytes (string length) to the right
to insert strings at position 0.

This is my first version with SSE instructions

INSAtoB_SSEE uses «movups  xmm0,[...]»

    Gunther, could you run it, please ?
    Thanks

INSERTING AT POSITION 0 -string length=100
-----------------------------------------------------
Intel(R) Pentium(R) 4 CPU 3.40GHz (SSE3)
-----------------------------------------------------
***** Time table *****

  37 milliseconds, INSAtoB_SSEE-   3 bytes
  38 milliseconds, INSAtoB_XZZE-   1 bytes
  40 milliseconds, INSAtoB_XZZE-   3 bytes
  55 milliseconds, INSAtoB_XZZF-   3 bytes
  58 milliseconds, INSAtoB_SSEE-   1 bytes
  61 milliseconds, INSAtoB_XZZF-   1 bytes
  62 milliseconds, INSAtoB_XZZF-  15 bytes

  66 milliseconds, INSAtoB_XZZE-  55 bytes
  73 milliseconds, INSAtoB_SSEE-  55 bytes
 
  73 milliseconds, INSAtoB_SSEE-   2 bytes
  73 milliseconds, INSAtoB_SSEE-  15 bytes
  81 milliseconds, INSAtoB_SSEE-   4 bytes
  83 milliseconds, INSAtoB_XZZE-  15 bytes
  84 milliseconds, INSAtoB_XZZE-   2 bytes
  94 milliseconds, INSAtoB_XZZE-   4 bytes
  96 milliseconds, INSAtoB_XZZF-  55 bytes
  96 milliseconds, INSAtoB_XZZF-   2 bytes
  96 milliseconds, INSAtoB_XZZF-   4 bytes
103 milliseconds, INSAtoB_X-      4 bytes
104 milliseconds, INSAtoB_X-      1 bytes
105 milliseconds, INSAtoB_X-      2 bytes
105 milliseconds, INSAtoB_X-      3 bytes
118 milliseconds, INSAtoB_X-     15 bytes

120 milliseconds, INSAtoB_SSEE- 103 bytes
121 milliseconds, INSAtoB_XZZE- 103 bytes
123 milliseconds, INSAtoB_XZZF- 103 bytes

144 milliseconds, INSAtoB_X-     55 bytes
151 milliseconds, INSAtoB_BB-     2 bytes
158 milliseconds, INSAtoB_XZZF- 203 bytes
174 milliseconds, INSAtoB_BA-     1 bytes
175 milliseconds, INSAtoB_BB-     1 bytes
182 milliseconds, INSAtoB_BA-     3 bytes
185 milliseconds, INSAtoB_BB-     3 bytes
185 milliseconds, INSAtoB_X-    103 bytes
186 milliseconds, INSAtoB_BA-     4 bytes
189 milliseconds, INSAtoB_BA-     2 bytes
193 milliseconds, INSAtoB_BA-    15 bytes
196 milliseconds, INSAtoB_SSEE- 203 bytes
211 milliseconds, INSAtoB_BB-     4 bytes
214 milliseconds, INSAtoB_XZZE- 203 bytes
223 milliseconds, INSAtoB_BB-    55 bytes
228 milliseconds, INSAtoB_BB-    15 bytes
238 milliseconds, INSAtoB_X-    203 bytes
256 milliseconds, INSAtoB_BA-    55 bytes
306 milliseconds, INSAtoB_XZZE-1027 bytes
342 milliseconds, INSAtoB_BA-   103 bytes

389 milliseconds, INSAtoB_SSEE- 503 bytes
397 milliseconds, INSAtoB_BB-   103 bytes
415 milliseconds, INSAtoB_X-    503 bytes
445 milliseconds, INSAtoB_BA-   203 bytes
506 milliseconds, INSAtoB_BB-   203 bytes

509 milliseconds, INSAtoB_XZZF- 503 bytes
518 milliseconds, INSAtoB_XZZE- 503 bytes
602 milliseconds, INSAtoB_SSEE-1027 bytes
753 milliseconds, INSAtoB_X-   1027 bytes
779 milliseconds, INSAtoB_XZZF-1027 bytes
822 milliseconds, INSAtoB_BA-   503 bytes
1000 milliseconds, INSAtoB_BB-   503 bytes
1073 milliseconds, INSAtoB_BB-  1027 bytes
1485 milliseconds, INSAtoB_BA-  1027 bytes
********** END III **********