3 ms·

True: Big O doesn't predict performance of algorithms on actual physical hardware. But... it was never meant to? And I'm not sure anybody was under the mistake

True: Big O doesn't predict performance of algorithms on actual physical hardware. But... it was never meant to? And I'm not sure anybody was under the mistaken impression that it does? I guess if a person wasn't aware that L1/L2/L3/main memory have different performance characteristics, then this would be a great article for them. Feels about as useful as telling me that my dog can't predict the stock market. It's true: he can't, but also I wasn't thinking that he could.

tsimionescu 3y ago
The whole reason we do big-O complexity analysis is to compare the performance of algorithms. If asymptoyic complexity analysis had nothing to teach about the actual performance of actual algorithms in hardware, we wouldn't be doing it at all. The point is now to refine the computational model to make it even better at predicting performance on actual hardware. It is well known for example that algorithms which require arbitrary jumps in memory are worse than those that require linear scans - so this is an attempt to model this aspect of performance as well.
- JohnBooty 3y ago
  "It is well known for example that algorithms which require arbitrary jumps in memory are worse than those that require linear scans" Even this is a suspect assumption once you factor in things like address space randomization, whatever weirdo microcode stuff systems are doing to mitigate timing attacks, multiple cores, etc. Or rather: arbitrary jumps are bad, but you can't make any assumptions about what is a "linear" scan, so good luck attempting to model that with some kind of generalized notation. Even with all of that considered, admittedly, theoretically-linear memory accesses will still tend to be actually linear, I guess, if they fall inside the same memory page or whatever. In which case this shiny new notation may actually be moderately predictive. Which isn't that much better or different than where we're already at with old-school Big O.
  - tsimionescu 3y ago
    ASLR has absolutely nothing to do with this. All it does is to ensure that the address of, say, the value of (int) ((void*)malloc) is not always 0x12345678 or something predictable, and the same is true for the start of the stack and heap etc. What it obviously doesn't do is to randomly scatter every allocation at different addresses. If the address of arr[0] is 0x1000000, then the address of arr[1000000] is very much guaranteed to be 0x2000000. Now, the actual layout of your address space in RAM is not necessarily contiguous of course. That has nothing to do with ASLR, it is all related to virtual memory, a much older concept. However, this is also irrelevant for performance, at least until you get to NUMA architectures which anyway need their own specific models. The reason virtual memory to physical memory mapping doesn't really matter for performance is that RAM is, actually, random access at this level. Reading two contiguous cache lines worth of data from physical RAM into the processor cache is just as fast as reading two non-contiguous ones. The reason random memory accesses are much slower than linear ones is not the physical layout in RAM. It is because when doing linear reads, you'll get most of the data from the processor cache with a single slow read from RAM, whereas with random access you'll need to go all the way to RAM (or gods forbid, to disk) for each and every read. The difference is exacerbated even more by predictive pre-fetchers, which can paralleize reading the next cache line from RAM while your code is running on the current cache line - but those only work if your code will indeed use the predicted next cache line, otherwise you'll stall. So, random access code is slow because it is actually running at the RAM's speed. Linear access code is fast because it is actually running at the L1 cache's speed. Physical layout of your pages in memory is almost entirely irrelevant (it's only a problem if your reads are not page-size aligned, which is not normally possible). And finally, the cache-oblivious computing model for complexity analysis is pretty well established, and it is known to be significantly better at predicting real-world performance differences than the more traditional system. It is more complex to work with, though, so some people don't bother. And it is not of that much theoretical interest in the field of computational complexity analysis, since it doesn't fundamentally change the complexity class of any algorithms (e.g. both this and the simpler O(1) memory access model will agree on whether an algorithm is polynomial or exponential).

tsimionescu 3y ago

The whole reason we do big-O complexity analysis is to compare the performance of algorithms. If asymptoyic complexity analysis had nothing to teach about the actual performance of actual algorithms in hardware, we wouldn't be doing it at all. The point is now to refine the computational model to make it even better at predicting performance on actual hardware. It is well known for example that algorithms which require arbitrary jumps in memory are worse than those that require linear scans - so this is an attempt to model this aspect of performance as well.

JohnBooty 3y ago
"It is well known for example that algorithms which require arbitrary jumps in memory are worse than those that require linear scans" Even this is a suspect assumption once you factor in things like address space randomization, whatever weirdo microcode stuff systems are doing to mitigate timing attacks, multiple cores, etc. Or rather: arbitrary jumps are bad, but you can't make any assumptions about what is a "linear" scan, so good luck attempting to model that with some kind of generalized notation. Even with all of that considered, admittedly, theoretically-linear memory accesses will still tend to be actually linear, I guess, if they fall inside the same memory page or whatever. In which case this shiny new notation may actually be moderately predictive. Which isn't that much better or different than where we're already at with old-school Big O.
- tsimionescu 3y ago
  ASLR has absolutely nothing to do with this. All it does is to ensure that the address of, say, the value of (int) ((void*)malloc) is not always 0x12345678 or something predictable, and the same is true for the start of the stack and heap etc. What it obviously doesn't do is to randomly scatter every allocation at different addresses. If the address of arr[0] is 0x1000000, then the address of arr[1000000] is very much guaranteed to be 0x2000000. Now, the actual layout of your address space in RAM is not necessarily contiguous of course. That has nothing to do with ASLR, it is all related to virtual memory, a much older concept. However, this is also irrelevant for performance, at least until you get to NUMA architectures which anyway need their own specific models. The reason virtual memory to physical memory mapping doesn't really matter for performance is that RAM is, actually, random access at this level. Reading two contiguous cache lines worth of data from physical RAM into the processor cache is just as fast as reading two non-contiguous ones. The reason random memory accesses are much slower than linear ones is not the physical layout in RAM. It is because when doing linear reads, you'll get most of the data from the processor cache with a single slow read from RAM, whereas with random access you'll need to go all the way to RAM (or gods forbid, to disk) for each and every read. The difference is exacerbated even more by predictive pre-fetchers, which can paralleize reading the next cache line from RAM while your code is running on the current cache line - but those only work if your code will indeed use the predicted next cache line, otherwise you'll stall. So, random access code is slow because it is actually running at the RAM's speed. Linear access code is fast because it is actually running at the L1 cache's speed. Physical layout of your pages in memory is almost entirely irrelevant (it's only a problem if your reads are not page-size aligned, which is not normally possible). And finally, the cache-oblivious computing model for complexity analysis is pretty well established, and it is known to be significantly better at predicting real-world performance differences than the more traditional system. It is more complex to work with, though, so some people don't bother. And it is not of that much theoretical interest in the field of computational complexity analysis, since it doesn't fundamentally change the complexity class of any algorithms (e.g. both this and the simpler O(1) memory access model will agree on whether an algorithm is polynomial or exponential).