3 ms·

Hashing often has much better constant factors than binary search because it isn't super mean to branch predictors

• taeric 4y ago
  The spread of data in the backing store usually hits similar penalties for hash tables, though. Especially in benchmark environments. 10, in particular, just feels odd. That many items almost surely fits in a single cache line. Granted, if you are storing compound data such that each item is a reference elsewhere anyway, I can see this. Speed is likely dominated by the comparison procedures at those sizes.
  • timbray 4y ago
    Remember the "data items" in this case are bytes. Lots of them in a cache line.
    • taeric 4y ago
      Right. Which is why 10 feels an odd number. I thought the benchmark referenced was possibly something else. That is, an unrolled loop on bytes can be N conditional increments on an index, with a check at the end to see if still in the bounds. Assuming N is small, will be hard to compete with that, honestly. The hash would be spreading the data wider than the linear search would be. Though, I agree I'd expect it to still be on a cache line for bytes.