5 ms·

There is also a simple, weaker argument about why memory addressing is not O(1). To address memory of size N, you need a log(N) sized addresses. Operations on

• jplrssn 3y ago
  I’m struggling to understand this argument. The size of memory that you can address on any particular hardware is fixed, just like the word size for additions. Restricting yourself to a smaller part of that address space in software won’t change anything about how the address is decoded.
  • mikebenfield 3y ago
    Big O notation deals with asymptotic behavior of a function - in other words, as N goes to infinity. If we're accepting the premise that N has an upper bound, the rest of the discussion is meaningless. Presumably the argument is an abstract one, not applying to any particular machine that actually exists.
    • charcircuit 3y ago
      Big O notation is often used with assumptions like adding numbers is always constant time. You can't physically build a machine where addition between any two numbers is constant time, but that doesn't matter.
      • xvedejas 3y ago
        It depends what you mean by "numbers": all integers or just 64-bit ones?
        • deleted 3y ago
          [deleted]
        • charcircuit 3y ago
          My point is relevant to additions that are the same type as n as n has no upper bound. n will never be a 64 bit integer.
  • utopcell 3y ago
    The argument makes sense once you think of memory as a hierarchy of different sizes. The log of the size of the set of registers is smaller than the logs of the sizes of Li caches, which in turn are smaller than the log of the size of main memory.
• mumblemumble 3y ago
  I think, though, that your argument depends very directly on hardware implementation concerns, which is exactly the kind of thing that big O notation is meant to abstract away.
  • chowells 3y ago
    It doesn't. It merely depends on processing speed being finite. If you need to address the 2^(2^64)th item (remember, big O notation is about behavior as n goes to infinity), your item index needs 2^64 bits. You can't determine what item to get without looking at all the bits in the index. If your processing speed is finite, that requires time proportional to the number of bits in the index.
• gizmo686 3y ago
  You sometimes see Õ(_) as a variant of O(_) that ignores logarithmic factors. Unfortunately, you cannot extend Big-O to ignore sqrt(n) without ignoring all polynomials.
  • kaba0 3y ago
    O already ignores logarithmic factors, is it not? At least its correct usage.
    • kaba0 3y ago
      I guess I don’t understand what you mean by a logarithmic factor.
• moritzwarhier 3y ago
  Is locating the memory address a significant part of the time being spent on RAM access?
  • tsimionescu 3y ago
    Not in practice, but this is a theoretical argument about scaling to infinity.
• oivey 3y ago
  I think you’re confusing some variables here. If you say mergesort is O(N log N), N is the number of elements in the collection. The size of the address space is orthogonal to the limit being expressed. If a memory look up is O(log(M)) where M is the size of the address space, then it is constant time or O(1) with respect to N.
  • tsimionescu 3y ago
    It's easy to show that an N element array requires at least O(N) bits of memory. If we call the memory size M, then an obvious condition is M >= N. And if M >= N, then O(log(M)) as N tends to infinity is emphatically NOT O(1).
    • oivey 3y ago
      Fair enough that perhaps you can allow M to be a function of N. It feels like this sort of model might run into other issues, though. If you treat a memory look up as an operation on an infinitely long bit string that therefore takes non-constant time, then why wouldn’t you select integer addition to act on unbounded numbers and have similar asymptotic behavior? Obviously in practice M >> N, M is not a function of N, and/or M is constant, but we’re essentially discussing how to define the axioms underlying the complexity analysis.
      • tsimionescu 3y ago
        The model is ultimately a choice, and you chose one that models important aspects of your domain. People very very often work with data that doesn't fit into the fastest available memory, so modeling that fact that memory accesses taking O(foo(N)) time makes a lot of sense if you want to compare the performance of algorithms with different amounts of memory accesses. The performance differences predicted by a model that adds this complexity compared to a model that doesn't will be better. For example, traditional complexity analysis predicts that linear search in a linked list should be about as fast as in an array up to some constant factor. If you instead model memory access as taking longer the larger the data structure you seek to access, you'll predict that linked list search is in fact worse and worse compared to array search as the size of each increases. This second prediction will more closely match the actual performance on real hardware. In contrast, people very rarely work on problems where fixed, small size integers (i32, i64) are not good enough. Those that do also typically model addition as an O(foo(N)) operation. There is of course some interesting overlap where you'd perhaps want to model the actual address calculation using large integers, but since in practice that will almost always be much faster than the actual memory access itself, it's rarely useful to account for it inatead of the memory access cost.
• JohnBooty 3y ago
  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).
• mikewarot 3y ago
  Memory access can still be O(1) if you pipeline everything, instead of making everything wait for all of the RAM at the same time. Lots of things get wickedly faster, if you can ditch the Von Neuman model of computation.