Linear vs. Binary Search

I had two points in that post. The first, obvious, one is that binary search can be micro-optimised to combine decent algorithmic properties with an enviable constant factor.

The second one is that, when linear search outperforms binary search, it does so by breaking out of the search, which needs conditional branches. Binary search, despite its bad reputation, has conditional branches that are easily converted to conditional moves or masks; even a loopy implementation is amenable to trip count prediction (it's a function of the log of the size of the array). If we must avoid mispredicted branches, binary search is intrinsically a better option than linear search.

I suspect memory bus width and latency also plays a role.

I really doubt there's any data size for which sort + binary search is going to be faster than linear search. The former has higher complexity (so it's going to be slower for large inputs) and more expensive operations (so it will be slower for small inputs).

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.

I think the assumption is that you sort once and search several times (enough to amortize the cost of the sort). The linear search algorithm also had an early exit, so the array has to be sorted for that too. That makes this a fair comparison, but I agree that seeing a linear unsorted search would have been interesting too.

This is an aspect of multi-core programming. As the programmer, you must be painfully aware of the cache lines you're touching and which cores touch them. Having two or more cores touch a cache line will cause expensive core-to-core synchronization taking place. The case is easier in a message passing system like yours, where the other core is clearly the sender and can flush the caches. In kernel space, you can disable caches or use write-combine or write-through caches for memory regions as needed but this isn't really available in userspace.

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.