Yeah, I don't expect it would be a cache-friendly algorithm. I didn't expect you were swapping buffers that large, or I'd've probably gone with something that would do blocks at a time, rather than entries.
The pathological behaviour only exhibits with buffer/offset pairings specifically chosen to cause it.
The paramaters in the following run, 536,870,912/268,435,456 represent an exactly 2GB buffer with the partition half way along:
C:\test\C>bufswap 536870912 268435456 2 ### 2^29 2^28
size:536870912 offset;268435456
[ 0 1 ... 268435454 268435455 ^ 268435456 268
+435457 ... 536870910 536870911 ]
[ 268435456 268435457 ... 536870910 536870911 ^ 0
+ 1 ... 268435454 268435455 ]
iterative: swaps:536870912 took 4.364767872 secs.
[ 0 1 ... 268435454 268435455 ^ 268435456 268
+435457 ... 536870910 536870911 ]
[ 268435456 268435457 ... 536870910 536870911 ^ 0
+ 1 ... 268435454 268435455 ]
recursive: swaps:268435456 took 2.476348362 secs.
Note that although the iterative algorithm does double the swaps, (equal to the total number of U64 elements in the buffer ) of the recursive version, the time taken is substantially less than double (175% .v. 200%) than the time taken by the recursive version. So, there is nothing wrong with the efficiency of the implementation of the algorithm.
And in many (maybe most) buffer/offset ratios, they both do the same number of swaps:
By anyone's standards, performing 1/4 billion swaps of two, 64-bit values, shifting 4GB of data around in the process, all in 4.36 seconds, ain't at all tardy!
Oh to be able to get the data off my discs fast enough to make use of that ~1GB/s throughput. The best I get out of my HD is about 200MB/s. My new SSD gets close, but only if the cache is warm.
Also note that the total memory above is only 57 x U64s (456 bytes) different to the pathological case, where the buffer/offset pairing is 536,870,855/268,435,399 (2GB+largest prime smaller/largest prime smaller): C:\test\C>bufswap 536870855 268435399 2 ### 2^28+prime prime
size:536870855 offset;268435399
[ 0 1 ... 268435397 268435398 ^ 268435399 268
+435400 ... 536870853 536870854 ]
[ 268435399 268435400 ... 536870853 536870854 ^ 0
+ 1 ... 268435397 268435398 ]
iterative: swaps:536870855 took 23.912365889 secs.
[ 0 1 ... 268435397 268435398 ^ 268435399 268
+435400 ... 536870853 536870854 ]
[ 268435399 268435400 ... 536870853 536870854 ^ 0
+ 1 ... 268435397 268435398 ]
recursive: swaps:536870854 took 3.633964430 secs.
Note that the number of swaps are only 1 different, but the time is 658% longer. That threw me through a lot of hoops!
Even though I chose the numbers, (power of 2/largestest prime smaller; based on previous experience of a modulo arithmetic driven process), to exacerbate the scattering effect of the modulo arithmetic -- maximising the number of times the pointer has to wrap around -- it took me completely by surprise at the size of the difference it made. I went over and over and over the code looking for some cock-up before the reality of cache misses hit me.
But I also 'lucked out'. I've since tried various other power-of-two/largest prime smaller combinations, and none of them come close to triggering the same kind of differences:
And it is only when the buffer size gets up into the GB range that the shear space which the modulo arithmetic has to distributes the wraps in, ultimately defeats the combined L1/L2/L3 caches and their LRU algorithms and starts to slow things down.
I set out to find an algorithm. I lucked out that I had some of the best minds -- which must include this particular anonymonk -- apparently looking for diversion on a Lazy Sunday, and got three excellent ones to choose from. And, being me, once they were all coded & running, the only way I was going to choose was with a benchmark :)
BTW: the third algorithm, labeled "reversive" in the spoiler above, is the first one suggested, by bitingduck, that would obviously work. It does 3 successive reverses of the buffer (thus two full passes): abcdef123
321fedcba reverse the entire buffer.
123fedcba reverse the smaller partition.
123abcdef reverse the larger partition.
I originally dismissed this/saved it as a last resort, because (I thought) that it would do far more swaps than was necessary. In reality, it does exactly the same as the recursive solution (1 less) in every situation I've tested. And it is very clean to program: U32 reverseBuffer( register U64 *p, const U32 start, const U32 size )
+{
register U32 i, swaps = 0;
const U32 half = size >> 1;
for( i = start; i < half; ++i ) {
swapElems( p, i, size -1 -i );
++swaps;
}
return swaps;
}
U32 xchgBufferV( U64 *p, U32 size, U32 offset ) {
register U32 swaps = 0;
swaps += reverseBuffer( p, 0, size );
swaps += reverseBuffer( p, 0, size - offset );
swaps += reverseBuffer( p + (size - offset), 0, offset );
return swaps;
}
The only saving graces from that summary dismissal is that a) bitingduck was himself somewhat dismissive of it; b) it led to a highly entertaining thread; far more analysis than I would ever have done otherwise; and the brilliant outcome of an algorithm that seems to perform near optimally under all the circumstances I've thrown at it.
I hope other people were as entertained by it as I was.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
|