11–19 of 19 posts
Back around 1980 when I first looked into this the generally accepted cutoff was 25 rather than 64. I don't think people were unrolling loops in the tests back then so it's hard to tell whether loop unrolling or changes in CPU architecture is the greater factor in moving the cutoff point from 25 to 64.
>> ...use linear search if your array is below around 64 elements in size, binary search if it’s above. Back around 1980 when I first looked into this the generally accepted cutoff was 25 rather than 64. I don't think people were unrolling loops in the tests back then so it's hard to tell whether loop unrolling or changes in CPU architecture is the greater factor in moving the cutoff point from 25 to 64.
>> ...use linear search if your array is below around 64 elements in size, binary search if it’s above. Back around 1980 when I first looked into this the generally accepted cutoff was 25 rather than 64. I don't think people were unrolling loops in the tests back then so it's hard to tell whether loop unrolling or changes in CPU architecture is the greater factor in moving the cutoff point from 25 to 64.
Something to do with the ratio between instruction cache size and cost of a jump to the pipeline?
When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case.
While this is somewhat interesting, the lesson to take home should be that most of the time, smart memory usage is more important than what the CPU executes. Warming up the caches (e.g. __builtin_prefetch) is as efficient an optimization as rewriting and unrolling the entire loop and should be done first. If the caches are warm and the search is still the bottleneck, then it's time to consider the other optimizations.
This is a bit contrived example because if just searching for an integer in a large array, the memory bandwidth is going to be the bottle neck. When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case. While this is somew…
This is a bit contrived example because if just searching for an integer in a large array, the memory bandwidth is going to be the bottle neck. When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case. While this is somew…
This is a bit contrived example because if just searching for an integer in a large array, the memory bandwidth is going to be the bottle neck. When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case. While this is somew…
I also think he should have covered the time it would take to sort an array. A linear search wouldn't need to be sorted, but a binary search would. He made his cut off at around 64 elements, but if you'd include the time needed by binary search to sort the array, the cut off limit would be a higher than that -- but would also introduce a lot of other complexities to consider in a production system.
You can also think about it as a sort of reductio ad absurdum: Assume that the array is actually already sorted and you use a sorting algorithm with O(n) complexity for already sorted data. In this ideal case you'd need to do n (for sorting) + log n (binary search) predictable operations. For linear search you'd only need to n operations of the same type. In practice you'd need to do n log n operations for sorting, I don't think you can avoid unpredictable branches, and instead of just loading elements sometimes you'll move them around.
This is a bit contrived example because if just searching for an integer in a large array, the memory bandwidth is going to be the bottle neck. When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case. While this is somew…
Getting stuff out of cache is also worthwhile in some cases. I had some message passing between cores, and apparently the CPU wasn't good at telling that my chance of using a populated and sent message slot again was zero. Adding a clflush after send significantly reduced my number of cache misses.
This can happen in very unintuitive places. For example, in Java, array.size() reads from the same cache line as the beginning of the array. If you're partitioning an array processing routine for many cores, you should not call array.size() to avoid very expensive synchronization.
This is a bit contrived example because if just searching for an integer in a large array, the memory bandwidth is going to be the bottle neck. When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case. While this is somew…
I also think he should have covered the time it would take to sort an array. A linear search wouldn't need to be sorted, but a binary search would. He made his cut off at around 64 elements, but if you'd include the time needed by binary search to sort the array, the cut off limit would be a higher than that -- but would also introduce a lot of other complexities to consider in a production system.