Array Intersections - part 4
In our last visit to array intersections we looked at using "simd" instructions to speed up the process of array intersections.
It's a quite well documented technique and one I have used successfully myself.
Things didn't go quite to plan. The code worked but was slower than the basic technique of scanning two arrays.
Now admittedly I had simplified ever so slightly I used:
to copy the elements into the output array when they match according to the mask we found using the simd instructions.
The real world implementations I have seen use more simd instructions for this task.
This is usually done, not with a case statement but an array of masks, but curiously my gcc compiler is determined that _mm_shuffle_epi32(value, mask) sees mask as a constant discernable at compile time.
So: simd_intersect_mk2.cpp
This mouthful shuffles the integers to be output to the lowest element of the array.
The numbers start to be understandable by looking at 15 which is to add all the values without changing order and then at 10 where we want positions 1 and 3 written out.
Running this makes for a very small improvement, but we might as well go a bit further, as we have a case statement we are being surely a bit silly with the cases where we just want to write out elements that are in contiguous order.
So: simd_intersect_mk3.cpp
Might seem to be cleverer, but is in fact slower. Shows something about the speed of the simd instructions even if they are not playing well for us.
What might this mystery be? The truth is in the horrors of memory alignment, we are dealing in 32bit values on 64bits systems.
In the code we have:
Which moves us forward through both arrays, one moves 128bytes forward the other will move a multiple of 32bytes forward breaking 64bit alignment.
If we take the hit of not moving forward on the other array.
simd_interesect_mk4.cpp:
We finally see an output:
Total linear time 0.832165 seconds, total simd time 0.390565 ratio 0.469336
Which makes the simd time significantly faster.
Can we improve further?
I made a series of attempts.
mk1 Total linear time 0.580798 seconds, total simd time 0.987996 ratio 1.701101
The original unaligned first try.
mk2 Total linear time 0.554349 seconds, total simd time 0.907844 ratio 1.637676
Use simd instructions to copy the intersections to the output array. A noticable improvement.
mk3 Total linear time 0.609809 seconds, total simd time 1.032354 ratio 1.692914
Try and pick and choose when to use simd for the intersection copy. Well that did not work.
mk4 Total linear time 0.832165 seconds, total simd time 0.390565 ratio 0.469336
Simply solve the alignment issue. We have lift off.
mk5 Total linear time 0.763136 seconds, total simd time 0.678215 ratio 0.888721
Set up the first shuffle values outside the loop, and only redo the needed values when we shift to the next element. A surprising failure.
mk6 Total linear time 0.753321 seconds, total simd time 0.684975 ratio 0.909274
Try and push both arrays forward but respecting 64 bit alignment.
mk7 Total linear time 0.670275 seconds, total simd time 0.534649 ratio 0.797656
revisit simple output of values.
mk8 Total linear time 0.558853 seconds, total simd time 0.426161 ratio 0.762564
try and cherry pick output using simd for anything more than one value.
Comments
Post a Comment