Hacker News Reader

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.

View on HN

Remember the "data items" in this case are bytes. Lots of them in a cache line.

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.

Reply on news.ycombinator.com