A good rule of thumb is "if it fits in a cache line, then computation is free", where "computation" could mean search, hashing, compression, etc. This means, e.

A good rule of thumb is "if it fits in a cache line, then computation is free", where "computation" could mean search, hashing, compression, etc. This means, e.g., that linear search generally beats binary search if the whole array fits in a single cache line (or half a cache line if it's unaligned).