Hacker News new | ask | show | jobs
by dietr1ch 321 days ago
I think it just abuses on how reading a few contiguous cache lines at random isn't a whole lot more expensive than reading a single random byte.

I found myself never wanting to use binary heaps, and instead use a wider one with an arity that can use at least a whole cache line, if not multiple ones after I started experimenting with my priority queues. Wider nodes meant fewer jumps, and jumping between nodes was more expensive (time, cache misses) than the work done at each node.