4 ms·
I agree with aaronbwebber that for general use, and for teaching, that it's far easier to assume O(1) memory access. It's a decent approximation, and works unti
by jcbeard 10y ago
I agree with aaronbwebber that for general use, and for teaching, that it's far easier to assume O(1) memory access. It's a decent approximation, and works until you start having applications where loads/stores dominate. It also falls apart when things like multi-threaded apps start spinning on locks, but lets not go there in a HN post, could make an entire blog out of mem issues.
Here's why we should continue to use O(1) access in general. Unless you enjoy rat-holes (I wouldn't have a job without them...so, why not). If we really wanted to, for every algorithm we could consider things like:
1) pre-fetch algorithm (assuming you know which one will be chosen)
2) associativity
3) cache size at each level (including buffering)
4) queueing depth at all levels
5) DDR controller capacity & while we're at it, do we have latency of mem controller on-chip..wait, which one?
6) bank conflicts in DDR
7) NUMAness (how about NUMA cache behavior?)
8) even worse...should we consider cost of differing mem tech.
9) TLB behavior...there's a lot there, can't list
Here's why we don't: YOU CAN'T. Do you realize the incredible amount of work required to get the info for the analysis? The list of things that influence memory behavior is huge. Even if you can get all of it, you work it out for one algorithm...you've now wasted a year, and figured out a cost for one architecture/OS/run-time combo. Congratulations. I'm all for including the cost of memory...just realize what you're asking before you write a post asking about it. There's no end to how detailed you want to go. And in the end you end up destroying the asymptotic bound you're trying to create b/c you'll realize that it's now a probability distribution that really doesn't lend itself to generalizable asymptotic behavior, which is what you want when considering algorithms.
When choosing an algorithm for a specific hardware, then you can choose an algorithm for that arch.....but most people don't do this, it's not necessary unless you're in HPC, Datacenter scale analytics, or in the embedded space/cyper-physical space.
- xenadu02 10y agoPermit me to disagree; I think it is useful to internalize the general rule that for every 100x increase in data size the theoretical performance will drop by 10x. This isn't a perfect rule but it is just as valid a shortcut as saying hash lookups are O(1). For all intents and purposes all modern CPU hardware works the same way (a cache hierarchy, superscalar, pipelined, with relatively slow DRAM hanging off some bus). In practice measure different approaches to performance-critical code with realistic datasets and don't make assumptions. Don't assume that you know dictionaries are O(1) and therefore searching an array must be slower.
- jcbeard 10y agoThe problem is, that's not really true. There isn't a hard/fast rule that'll get you what you want given the way modern hardware is designed. Run something on a core designed for mobile workloads and that changes vs. one designed for server workloads vs. one designed for HPC. They're definitely not all the same, and the differences will kick you in the rear when trying to simplify. I do agree teaching people that there are differences, and give them the tools to learn when algorithmic changes are necessary to optimize for the hardware.
- neolefty 10y agoThe article rationalizes with physics, arguing that a physically large data store, when it is efficiently implemented, is limited by the inverse-square of distance inherent in a 3D world. Certainly there are exceptions when you make a system more efficient (for example, filling empty memory slots or moving systems closer together or paying for a better interconnect).
- brassic 10y agoThere is a middle ground between tuning an algorithm to the exact memory hierarchy of the system it is running on and ignoring the problem altogether: https://en.wikipedia.org/wiki/Cache-oblivious https://en.wikipedia.org/wiki/Cache-oblivious
- jcbeard 10y agothis is true....and thankfully this technique is also being taught in some CS algorithms classes.
- claudius 10y ago> Here's why we don't: YOU CAN'T. But that’s one of the main points of the article: You don’t have to. Asymptotically, you won’t be better than O(sqrt(N)) because physics does not allow it. You can put all the different caches in you want, you can buy the most expensive RAM there is, you can buy the best interconnect systems for the fanciest NUMA cluster you can find: You won’t beat O(sqrt(N)) if you wish to go to arbitrary N. Of course, if you bound your problem size, you may well get O(1) access times and for some applications, it may well be sensible to consider the coefficient associated to the square-root scaling small enough to neglect it, but if you truly want to talk about algorithmic complexity (and not just the scaling of one particular implementation for one particular range of valid N), you should take that additional square root into account.
- AstralStorm 10y agoThe one exception is possibly quantum computation in some cases.
- claudius 10y agoI don’t know of a mechanism in quantum mechanics that would allow to pack information more densely (or even infinitely dense as would be required by O(1) random access times), what did you have in mind?
- fanf2 10y agoCheck out "cache-oblivious algorithms" for code that is designed to work well with memory hierarchies but which does not need to be tuned for the specifics of any particular architecture.
- kazinator 10y agoI like it: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm It gives a name to a good default way of writing code.