szLen optimize...

[Jimg]

roticv-

Thanks for the new routines.  Jens_mmx is clearly faster on large strings (>250 bytes or so).  The CPUID instruction is too big a penalty to pay on small strings.  I've included it in the test routines.  I also tried it without the cpuid (Jens_mmx2, not currently selected for test), and that made it better for strings about 150 or so.  Bitrake's routine is just too specialized for the general purpose test being run here as we are testing alignment errors as well as raw speed.

New code, updated per Phil's correction and added Jens mmx-

[attachment deleted by admin]

[roticv]

The penalty for CPUID is ~500 and I don't think it should be included in the strlen routine as donkey's routine does not include it anyway.

When I have time, I would tweak my own routine and see how it compares. Below are the timings for different routines on my computer.

Code Select Expand

0 byte misalignment
lszLenSSE   35   27   20   36   35   30   37   44   56   72  160  228  305  990
Jens_mmx   546  605  616  606  612  612  614  630  621  625  643  653  694 1031
Ratch       20   14   22   21   25   19   31   41   64   83  151  195  293 1003
szLength    15   22   15   15   10   25   27   28   58   68  136  171  270  908
Jens_mmx2   11   53   53   54   57   61   62   69   78   73   96  108  153  497

1 byte misalignment
lszLenSSE   19   28   26   33   34   30   40   44   57   84  125  254  364 1172
Jens_mmx   552  553  558  557  569  657  646  657  654  666  674  703  745 1077
Ratch       19   14   24   19   27   20   31   37   64   85  180  272  426 1575
szLength    26   17   26   22   25   36   26   40   56   67  139  190  274  923
Jens_mmx2   16   15   28   25   56   79   95  104  121  114  138  169  197  533

2 byte misalignment
lszLenSSE   35   32   27   28   26   30   43   36   55   65  122  259  361 1154
Jens_mmx   552  541  544  544  569  638  635  654  659  656  669  693  719 1066
Ratch        3   14   24   19   11   26   33   37   61   90  185  275  428 1566
szLength    26   18   27   19   12   31   25   41   55   66  148  184  277  914
Jens_mmx2   11   14   29   32   34   95   90   94  118  107  132  155  192  534

3 byte misalignment
lszLenSSE   36   32   27   34   34   29   38   37   51   82  123  272  372 1178
Jens_mmx   544  548  558  546  575  629  642  649  654  646  675  686  723 1050
Ratch       11   22   17   27   19   34   34   40   75  106  181  302  429 1538
szLength    11   27   18   28   24   31   37   41   97  115  155  189  275  920
Jens_mmx2   10   23   21   31   32   76   93   91  114  102  127  149  182  523

Jens' mmx version sure thrash the rest.

[roticv]

I tried wiht my own routine, and it gives weird results.

Code Select Expand

0 byte misalignment
lszLenSSE   19   35   27   35   28   36   38   46   56   73  147  220  301 1001
roticv2      9   13   15   17   17   43  106  131  187  239   65  545  866 3454
Ratch       19   14   24   18   26   19   31   36   62   80  148  195  288  994
szLength    15   23   16   22   17   27   24   36   61   85  140  186  264  913
Jens_mmx2   18   54   51   53   59   54   63   70   93   71  114  104  181  489

1 byte misalignment
lszLenSSE   27   35   34   27   34   40   38   37   44   78  128  259  347 1171
roticv2     17   13   15   10   27   35   99  136  184  244  168  538  863 3456
Ratch       11   20   17   12   20   27   31   33   71   98  184  270  420 1558
szLength    18   26   25   25   20   30   34   33   58   67  137  190  267  924
Jens_mmx2   11   15   13   33   57  101   86  103  121  109  153  160  202  534

2 byte misalignment
lszLenSSE   22   34   28   27   35   38   50   49   57   70  122  258  344 1155
roticv2      9   19   15   28   22   38  101  132  129  151  355  187  235  635
Ratch       11   14   12   20   12   30   33   33   63   72  184  265  439 1570
szLength    14   25   23   24   19   29   25   29   56   75  138  198  268  904
Jens_mmx2   19   15   29   44   33   79   91   95  102   89  131  154  189  541

3 byte misalignment
lszLenSSE   35   27   32   35   35   32   23   45   63   86  119  265  372 1173
roticv2     10   13   20   17   30   42   86  113  189  231  137  549  882 3459
Ratch       11    6   18   13   24   19   31   32   69  107  187  301  433 1531
szLength    27   23   12   28   22   31   38   34  102  115  149  190  276  922
Jens_mmx2   20   14   30   24   39   91   82   99  111   95  135  149  179  531

My code is

Code Select Expand

roticv2 proc lpstring:dword
;int 3
mov eax, [esp+4]
cmp byte ptr[eax], 0
mov ecx, eax
jz done
and ecx, 0FFFFFFE0h
add ecx, 16
sub ecx, eax
cmp ecx, 16
jz aligned
@@:
add eax, 1 ;Simple byte scanner for alignment
cmp byte ptr[eax],0
jz done
sub ecx, 1
jnz @B
aligned:
pxor xmm1, xmm1
align 16
@@:
movdqa xmm0, [eax]
pcmpeqb xmm0, xmm1
add eax, 16
pmovmskb ecx, xmm0
test ecx, ecx
jz @B
bsf ecx, ecx
lea eax, [eax+ecx-16]
done:
sub eax, [esp+4]
retn 4
roticv2 endp

[Codewarp]

Nice, Roticv, I was wondering about an mmx implementation that didn't require sse...  The cpuid may be a moot point, because you can save it once in memory, and read it many.  It seems to me that some standard startup code should be grabbing/saving this value for subsequent access anywhere in the code--in 1 cycle!  The last time I checked, the cpuid doesn't exactly change during program execution ::).  On the other hand, what cpus don't have mmx--P1, PPro--does anyone out there use these any more? 

But maybe we still have to use cpuid, to prevent mmx use in future machines that don't have it.  If so, standard startup code really must be doing this.  Such code can also abort execution if run on machines outside the supported set.  Low level routines such as this must not be spending any more time on cpuid issues than actually required.

Roticv, I could not find any mention of the cpu type you ran on--what is it? :naughty:
Here is the run for my Sempron 2800+, cpuid is not nearly so bad, but still intolerable:

Code Select Expand


Proc/Byte    0    1    2    3    5    8   13   22   39   55   89  144  239  999
========= ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ====

0 byte misalignment
lszLenSSE   26   25   25   25   25   28   28   32   38   47   82  119  167  591
Jens_mmx    82  112  111  111  113  118  121  129  157  122  169  139  201  361
Ratch        7   11   12   15   14   14   20   30   62   78  101  142  230  856
szLength     8    8    8   10   12   15   17   24   34   47   91  131  204  782
Jens_fast   20   20   20   20   21   26   29   36   57   70   99  146  220  929

1 byte misalignment
lszLenSSE   28   28   28   28   28   30   31   34   41   54   93  126  178  620
Jens_mmx    82   83   87   90   98  146  148  156  173  156  183  212  230  374
Ratch        7   11   12   15   18   15   23   32   67   86  109  155  255  954
szLength    13   14   14   16   15   19   20   26   40   51   92  135  208  787
Jens_fast   20   20   20   20   24   28   32   40   62   76  105  158  238 1000

2 byte misalignment
lszLenSSE   28   28   28   28   28   30   30   32   41   55   92  123  176  623
Jens_mmx    82   83   87   90   98  142  144  156  169  148  163  195  212  362
Ratch        9   11   12   15   18   15   23   32   69   86  109  155  255  953
szLength    14   14   16   16   15   20   20   29   40   51   92  136  208  785
Jens_fast   20   20   20   20   24   28   32   40   61   76  105  154  238 1000

3 byte misalignment
lszLenSSE   28   28   28   28   28   31   30   35   43   56   90  123  174  626
Jens_mmx    82   83   87   90   98  128  136  143  153  131  177  188  205  349
Ratch        7   11   12   15   18   15   23   33   70   87  109  155  254  953
szLength    14   16   16   15   19   20   24   29   41   51   94  136  209  787
Jens_fast   20   20   20   20   24   28   32   40   61   76  105  154  239 1001


[Jimg]

Ok, time to show my ignorance.

When trying roticv's routine, masm chokes on the movdqa line-

Assembling: F:\WinAsm\Progs\FastStringLength\timelen4\timelen.asm
F:\WinAsm\Progs\FastStringLength\timelen4\timelen.asm(337) : error A2008: syntax error : xmm

What's the solution for this?

[Codewarp]

The Jens-mmx code is not yet practical, because it can read up to 40 bytes beyond the end of memory.  The best way to resolve this is to align to 32 bytes instead of 8 bytes, then process 32 bytes at a time, instead of 48.  It makes it run faster too, probably because it lays down for the caches.  Because memory blocks are multiples of 4k, they always end on a 32-byte boundary.  Since 32 byte alignment can take up to 31 iterations, first align to 4 bytes, then align to 32 bytes, 4 at a time.  This improves short and long string speed.

[roticv]

I am a using a Celeron(R) 2.40GHz that comes with SSE3.

Anyway, you have to use a newer verison of ml in order to compile movdqa. I'm using Microsoft (R) Macro Assembler Version 7.00.9466.



[attachment deleted by admin]

[Phil]

roticv: Here are the results of running your latest strlen.exe on a 996 MHz P3. There is a problem with 'correctness' with 2-byte misalignment. I also cannot assemble the source because I only have access to the earlier ML version.

Code Select Expand

Test routines for correctness:
0 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   39   55   98  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999
1 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   39   55   98  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999
2 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   48   64   89  144  239 1008
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999
3 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   31   39   55   98  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999

Proc/Byte    0    1    2    3    5    8   13   22   39   55   89  144  239  999
========= ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ====

0 byte misalignment
lszLenSSE   16   16   16   16   17   19   19   22   29   48   63   86  116  403
roticv2      4   10   12   16   12   44   58   87  136  185   49  453  736 3019
Ratch       18   25   32   40   29   25   35   58   78   92  106  144  245  871
szLength    19   19   19   19   23   25   30   37   52   79  116  174  263 1025
Jens_mmx2    7   34   34   34   39   43   45   67   85   49   98   66  135  320

1 byte misalignment
lszLenSSE   16   16   16   16   16   19   19   22   32   60   92  117  184  648
roticv2      4   10   13   16   22   44   58   67  136  185  100  453  738 3017
Ratch       18   25   32   39   29   25   35   58   86  110  124  191  326 1150
szLength    24   25   25   28   28   30   34   41   72   87  119  177  274 1033
Jens_mmx2    7   12   17   18   23   64   73   78  114   77  126  144  169  349

2 byte misalignment
lszLenSSE   16   16   16   16   16   26   26   40   37   54   81  113  173  627
roticv2      4   10   13   16   22   44   58   87   73   77  287  111  135  328
Ratch       18   25   32   39   29   25   57   79   86   96  135  182  303 1140
szLength    25   25   28   28   28   31   34   45   72   87  119  177  274 1033
Jens_mmx2    7   12   17   18   23   66   70   81  112   75  124  142  167  347

3 byte misalignment
lszLenSSE   16   16   16   16   16   19   19   22   32   60   92  117  184  648
roticv2      4   10   13   16   22   44   58   66  138  185   96  453  736 3017
Ratch       18   25   32   39   29   25   35   58   86  110  124  191  326 1149
szLength    25   28   28   28   30   31   39   45   72   89  127  177  270 1032
Jens_mmx2    7   12   17   18   23   51   57   65   96   59  110  127  145  330

Press enter to exit...

It is odd that roticv2 only fails the correctness test with 2-byte misalignment when the string 999 contains extended ASCII characters.

[roticv]

That's extremely weird.

I get

Code Select Expand

Test routines for correctness:
0 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   39   55   89  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999
1 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   39   55   89  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999
2 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   39   55   89  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999
3 byte misalignment
lszLenSSE    0    1    2    3    5    8   13   22   39   55   89  144  239  999
roticv2      0    1    2    3    5    8   13   22   39   55   89  144  239  999
Ratch        0    1    2    3    5    8   13   22   39   55   89  144  239  999
szLength     0    1    2    3    5    8   13   22   39   55   89  144  239  999
Jens_mmx2    0    1    2    3    5    8   13   22   39   55   89  144  239  999

When I run it on my machine. Will take a look into it. It probably has to do with the alignment and stuff like that.

[Jimg]

To anyone having the same problem I did with movdqa-

movdqa requires masm 6.15 or better.  Version 6.14 distributed with Hutch's masm32 distribution won't do.  6.15 is available from his site.

There, now the information will show up on a search :wink

[Jimg]

Victor-

I'm getting the same results as Phil for the 2 byte misalign on the 999 string, and the same large cycle count for the other three.  Also notice there is an error at the 3-byte misalignment for string 22. Also try a string length of 39.

After more testing, it gets even weirder.

Using these test strings:
    SIZES TEXTEQU <7,8,9,10,11,12,13,14,15,16,17,LastString>
I get:

Code Select Expand

Test routines for correctness:
0 byte misalignment
roticv2      7   17   18   19   20   21   22   23   48   16   17  999
1 byte misalignment
roticv2      7    8    9   10   11   12   13   14   15   16   17 1008
2 byte misalignment
roticv2      7    8    9   10   11   12   13   14   15   16   17 1008
3 byte misalignment
roticv2      7    8    9   10   11   12   13   14   15   16   17 1008


but using these strings:
    SIZES TEXTEQU <5,8,9,10,11,12,13,14,15,16,17,LastString>
I get:

Code Select Expand

Test routines for correctness:
0 byte misalignment
roticv2      5    8    9   10   11   12   13   14   15   16   17  999
1 byte misalignment
roticv2      5    8    9   10   11   12   13   14   15   16   17 1008
2 byte misalignment
roticv2      5    8    9   10   11   12   13   14   15   16   17 1008
3 byte misalignment
roticv2      5    8    9   10   11   12   13   14   15   16   17 1008

I just can't see how this can be happening???

[Jimg]

temporarily deleted

[Codewarp]

As far as I know, mmx is supported in all Pentiums except for P1 and PPro.  Does anyone out there know of any examples to the contrary?  If not, I am inclined to drop the cpuid test, but if there are newer 32-bit cpus that don't have mmx, then it must be included with strlen( ) versions intended for use in applications.

[roticv]

Ah it is not weird now. I figured out what is wrong.

The instruction i was using was a SSE2 instruction, but your processor interpreted it as a SSE instruction because it does not recongnise it (The only difference is the 66h prefix to the instruction).

Therefore it did not work as per expected on both your processors.

[Phil]

Well, I'm glad you solved that mystery! I had expected an illegal instruction exception when I ran the program but it just ran without complaint! Does this mean that it would be impractical to write an SSE2/SSE3 emulator? I suppose so, since the processor didn't seem to notice that anything was wrong in its instruction sequence. I'm thinking back to ancient times when you could run programs that used FPU instructions even if you didn't happen to have one. Now it looks like it's all up to the programmer to check capabilities if they are using SSE2/SSE3 to use a less advanced routine to ensure compatibility with older machines. I would have prefered seeing an illegal instruction exception!