ASM for FUN - #6 SUB [Searching inside random numbers]

[clive]

I added some code to provide stats and bin the groups. Even with printing and saving we are at about 80ms.
-Clive

Code Select Expand

Buffer    1280000 bytes

Generating..

        16 Ticks,   18381900 Cycles

Saving.. 'rndtest.out'

Converting to bit vectors..

         0 Ticks,   17054647 Cycles

Sorting bit vectors..

        47 Ticks,  136977937 Cycles

Scanning..

         0 Ticks,    2399887 Cycles

   67515 Unique
   80000 Elements

Groups occuring 1 times :    56370
Groups occuring 2 times :     9949
Groups occuring 3 times :     1060
Groups occuring 4 times :      128
Groups occuring 5 times :        8
                             67515

Entire Application Totals

        79 Ticks,  229950982 Cycles

[frktons]

I added some code to provide stats and bin the groups. Even with printing and saving we are at about 80ms.
-Clive

Code Select Expand

Buffer    1280000 bytes

Generating..

        16 Ticks,   18381900 Cycles

Saving.. 'rndtest.out'

Converting to bit vectors..

         0 Ticks,   17054647 Cycles

Sorting bit vectors..

        47 Ticks,  136977937 Cycles

Scanning..

         0 Ticks,    2399887 Cycles

   67515 Unique
   80000 Elements

Groups occuring 1 times :    56370
Groups occuring 2 times :     9949
Groups occuring 3 times :     1060
Groups occuring 4 times :      128
Groups occuring 5 times :        8
                             67515

Entire Application Totals

        79 Ticks,  229950982 Cycles

It looks like this is a far better algorithm  :U

Did you write it in C or ASM?

I imagine that all the job is:

1) generating 80,000 random numbers and storing them into memory
2) writing them to a file
3) vectorizing the whole
4) sorting it in groups of four integer
5) counting the occurrences of matching pair of groups
    without generating all the possibile 230,300 combinations
    and without having to match 230,300 against 80,000
6) displaying the results

Well, skipping more than half unnecessary work is in itself
a good optimization  :lol
And you have also used some methods I am not aware of.  :red

Would you mind posting the complete source code?
With some study and effort I could understand pivotal methods of
doing things that I have never used before.

Thanks for your time

[clive]

Let me clean it up a little, it is some what devoid of comments, it was a quick prototype and was done in C. There are probably bits which could be done more efficiently in ASM. The comparison used by qsort() is one that's called a lot. And the whole QuickSort could probably be customized/optimized for 64-bit integers.

The real trick is the sort, because it gets everything in order and you don't need to search for matches. You just check the immediate neighbour(s) in a single linear pass over the 80000 groups.

The bit vectoring flattens your 24 (4!) combinations of [1,2,3,4] in to a single comparison.

The whole taking a few minutes thing is what initially bugged me. But I think that is because you were dealing with 5.5M iterations.

-Clive

[frktons]

Let me clean it up a little, it is some what devoid of comments, it was a quick prototype and was done in C. There are probably bits which could be done more efficiently in ASM. The comparison used by qsort() is one that's called a lot. And the whole QuickSort could probably be customized/optimized for 64-bit integers.

The real trick is the sort, because it gets everything in order and you don't need to search for matches. You just check the immediate neighbour(s) in a single linear pass over the 80000 groups.

The bit vectoring flattens your 24 (4!) combinations of [1,2,3,4] in to a single comparison.

The whole taking a few minutes thing is what initially bugged me. But I think that is because you were dealing with 5.5M iterations.

-Clive

The original plan was about searching a single digit match inside the 4 digit group,
dealing with all the possible combinations of 4 digits for statistical reasons,
but at this point I am more interested in understanding the algo you have used, so
I'd like to deal first with vectorization that is quite new for me, and return to the
previous plan later on.  :U

 

[clive]

App with source.
-Clive

[frktons]

App with source.
-Clive

Thanks Clive, very kind of you.

Being back from week-end, in few days I'll start studying it
and probably bothering you with some questions as well.  :P