4 ms·
There was a paper a few years back that came down to "Given a large enough active address space and a random enough access pattern, randomly accessing N address
by corysama 5y ago
There was a paper a few years back that came down to "Given a large enough active address space and a random enough access pattern, randomly accessing N addresses becomes an O(N log N) operation in practice because of TLB cache hierarchy. This penalty does not appear to be avoidable in the long run."
- continuational 5y agoCorollary: Constant time random access data structures don't exist.
- bee_rider 5y agoAnd in the long-long run we'll always have a latency of at least 2r/c to randomly access memory elements within a radius r of our compute elements!
- magicalhippo 5y agoThis reminds me of the ZFS talk where they note that if you have enough clients doing sequential IO, it looks like random IO to the server. https://youtu.be/yHgSU6iqrlE?t=2577 https://youtu.be/yHgSU6iqrlE?t=2577
- labawi 5y agoWhile just about any "constant-time" operation gets a log N factor, given large enough N, the TLB issue is mostly surmountable. Assuming you do want to keep using virtual memory, you can not-simply¹ use huge pages and avoid the log N TLB factor. Which is a big thing, because TLB misses are very costly, so it can be worth it, even though you are giving up a lot of the paged-memory benefits. ¹ Lots of limitations and caveats. Your MMU needs big enough pages with a reasonable amount of TLB entries. Managing memory becomes more difficult. Your CPU likely has few large TLB entries, so only certain size ranges fit, etc.