4 ms·
This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of mem
by gpm 8y ago
This seems like a good time to bring up one of my pet peeves about big O notation.
Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible:
- The pointer you need to read is log(n) bits.
- The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) because we build on flat planes (once you start talking about petabytes of data anyways).
Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.
- briankelly 8y agoThere's a nice series of articles on this here: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- gpm 8y agoOh cool, hadn't seen that!
- deathanatos 8y agoThere was a decent article exploring the timing between memory accesses, and when they started taking longer b/c you hit L2 cache, L3 cache, main RAM, swap, etc., and eventually showed how if you really graphed the access times, the overarching "curve" they followed was square/cube root¹; that is, real world hardware obeys the laws of physics. My googling dug up [1], but I'm not sure if that's it or not. My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about. > 16/32 bit pointers for small arrays? It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out. [1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html ¹I'm a software engineer, not a physicist.
- heinrich5991 8y agoIn academia, you usually see O(log n) for addressing. Since it doesn't really seem to matter for real-world performance, we just assume it's O(1) in practice.
- gpm 8y agoYou're probably seeing a different part of academia than I am. The portions of CS academia I'm familiar with don't do O(log n) addressing.
- anon946 8y agoWell, it's "wrong", but there's the saying that all models are wrong, but some are useful. If time complexity analysis had to include physical distance, then it would perhaps be less wrong, but also much less useful. That said, "time complexity" is a bit of a misnomer anyway. It's often implied, but underneath, there is a specific operation. For example, when we say that merge sort is O(N lg N), we mean in number of comparison operations.
- mwfunk 8y agoPart of it is that there's very casual, conversational usages of Big O vs. much more formal usages when trying to actually quantify performance. Conversational Big O tends to include a lot of spherical cows (https://en.wikipedia.org/wiki/Spherical_cow https://en.wikipedia.org/wiki/Spherical_cow), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive in that context. When someone is actually trying to quantify and predict performance of an algorithm, then the other extreme becomes desirable- the more detailed and specific the function, the better.
- gpm 8y agoYa, I'm directly addressing non-conversational use of Big O notation here, including the areas of academia I'm familiar with and know people in.
- jhanschoo 8y agoIn industry there is indeed a hand-waving of the size of addressing. IMO for industry this is not too important since a lg n multiplicative factor is peanuts. With respect to the space problem, for some problems researchers don't care about it so much because it only means that it is a polynomial factor slower. For problems where the degree of the polynomial is important, theorists typically work with variants of Turing machines and need to specify which variant they are using, which typically do not allow random access, so this does not become important. Of course, random-access Turing machines are also studied that violate the physical constraint you mentioned.
- umanwizard 8y agoActually the size of indices can be important in real life. For example, on Nvidia GPUs, a kernel that indexes data with 64-bit indices will usually be much slower than one that uses 32-bit indices. (Hard to argue that this is related to big-O since there are only two data points, but I'm just pointing out that index size is in fact a real-world concern).
- giucal 8y agoI think they don't matter because: 1. they are all fixed or bounded quantities; 2. all algorithms are subject to them. On the other hand, in practice, the input size is also bounded. You deal not with arbitrarily long arrays, for example, since memory is not infinite. So, I think, asymptotic time complexity is meaningful as long as the inputs we are considering can grow so much -- while remaining bounded -- that a linearithmic algorithm indeed outperforms, say, a quadratic one for a large and relevant class of inputs. And that may be why computational models make those assumptions; but I'm not remotely sure.