Hacker News Reader

Comment by beagle3 | Hacker News Reader

Constant speedup, but you need to optimize for page size; if you optimized for the wrong page size, you may get a lower constant, perhaps even < 1.

And the computation is much less trivial.

Still, an interesting and important observation - page sizes change every decade or two, and almost exclusively upwards, so this is worth pursuing if you need to squeeze more speed from your heap.

View on HN

In addition to optimizing for page size, you want to optimize for cache line alignment to minimize the amount of false sharing that happens in the CPU cache. If you're reading these data structures (safely) from multiple threads, ensuring your blocks are (say) 4080 bytes in a 4096 page can dramatically increase performance because otherwise the address bits used by the cache might line up across multiple blocks.

The last time I had to optimize a b-tree based k/v store getting this right literally could boost performance in test cases by 40%.

> if you need to squeeze more speed from your heap

Everyone needs to "squeeze more speed from their heap". CPU-bound problems are quite rare in modern software - despite the legions of software engineers who will stare at a CPU profile that says 100% utilisation, and declare "it's CPU bound, nothing to be done".

(this is a pet peeve of mine, in case you couldn't tell)

Latency kills: memory latency, network latency, and storage latency. In that order.

> Latency kills: memory latency, network latency, and storage latency.

I think the point of the article is that

> memory latency

Is actually a hierarchy of its own, and non-linear depending on access patterns.

Instruction fetch latency, branch mis-predict latency, cache hit/miss latency (L1 through L3), cache pressure, register pressure, TLB hit/miss, VM pressure, etc. all become significant at scale.

Just knowing big-O/big-Ω characteristics aren't enough.

Why would someone see 100% CPU and say there’s nothing to be done? CPU is the part we have the most control over. In my experience it’s the opposite where you can’t get people to engage you or their own brains. We aren’t CPU bound, nothing to do!

I’m interested to know what you think that CPU is fully engaged doing if it’s not making progress toward a solution?

Is there any reason to not just produce a larger binary that contains a code path for every possible (well, probable) page size? Only one code path will be taken at runtime, so it's not like it'll harm cache locality.

Reply on news.ycombinator.com