Martin Walker

In part1 we demonstrated that a very short C++ standard library approach could be a very poor way of finding an array intersection and went on to show the simple but reasonably efficient method mostly used. in part2 we showed how the special case of intersecting a short array with a long one would be better done by other means. Now we will try to go further, consider this piece of code. The github is here #include <cstdio> #include <xmmintrin.h> #include <stdint.h> #include <cstring> // bits set in the range of numbers 0 - 15 static uint32_t mask_count [ 16 ] = { 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 }; int main ( int args , char ** argc ) { uint32_t x [] = { 0 , 1 , 3 , 4 }; uint32_t y [] = { 1 , 2 , 3 , 6 }; // the functions that use this need it as a constant known at compile time #define rotate _MM_SHUFFLE ( 0 , 3 , 2 , 1 ) // load the array into a 128 bit variable __m128i a1 = _mm_loadu_si128 (( __m1...

 To recap we have been looking at algorithms to find the intersection of two arrays e.g. the values they have in common. We have moved from a simple but very poor way of doing things, to thinking more sensibly and coming up with an algorithm that worked about 25x faster. However we have made the observation that if our smallest array is very small our method is instinctively inefficient as it involves a linear search of the large array. The most common alternative to a linear search is a binary chop where we repeatedly divide the array in two searching the part where our element may still lie until we find it, or find it is not there. However we have been talking about these arrays possibly being database indexes where we can assume numbers will be spread evenly across a range. If our element is  towards the top of the range, then splitting down the middle seems inefficient. Hence let's leap straight to an interpolation search which will try and aim with a bit more accuracy. ...

 When a database performs a query there is every likelihood sets of matching records find their was into multiple arrays of record numbers that need filtering against each other to arrive at a final set of records. I even myself wrote a database that pretty much exclusively used this method for index. Intersecting common numbers in two or more arrays might sound a little trivial, but there are rather a lot of papers written on how to do this optimally. As such this is going to be a series of articles exploring the subject. One of the things we will be covering along with speed is memory usage. We will start off badly! Though we will still use -O for compiler optimisation. It's unfair not to give the compiler at least a chance to improve on whatever rubbish we have thrown at it. Here's the github link //gcc -O bad.cpp -lstdc++ #include <stdlib.h> #include <stdio.h> #include <set> #include <iterator> #include "common.h" #include <time.h...