4 ms·
What's interesting is the implicit assumption that mutating memory is O(1). Unfortunately for real memory (caches, DIMMs, swap etc) that's not true. It's O(lo
by rwmj 15y ago
What's interesting is the implicit assumption that mutating memory is O(1).
Unfortunately for real memory (caches, DIMMs, swap etc) that's not true. It's O(log n) for any non-trivial size of memory, and can have bad (constant?) factors for mutating memory that is shared between processors.
Of course functional languages have hidden and not-so-hidden costs too, starting with the garbage collector, but including the time taken to get the larger working set into cache.
I'm interested in any studies that look at these total costs in real systems.
- colanderman 15y agoI can't upvote you enough. Too often programmers conflate "functional programming" with "availability of an O(1) array data type". The former does not imply lack of the latter, and (as you stated) lack of the latter does not imply the former. The important takeaway I think, is that O(log n) approaches O(1) for all practical values of n. To the downvoters: gee golly, would it hurt you to reply to my comment? If you think I'm wrong then say why!
- SamReidHughes 15y agoEdit: O(log n) is clearly worse than O(1) if you just considered an O(log n) array-replacement data structure or hash table-replacement data structure and considered what its performance would be. I mean, how is this even a question? Also if memory is O(log n) then arrays are O(log n) but BSTs are O((log n)^2). (Edit II: Let's be clear that BSTs are already (log n)^2 if you're counting CPU cycles with O(1) memory access. They're O(log n) if you count cache misses or comparisons, or you might say they're O((log n)^2) but the first log is base <2 and the second is the logarithm base 2 to the 256th power, so only one really counts. (The second manifests as a cache line miss if your key comparison walks past the first 32 bytes of your key.)) (Actually memory access is at best O(n^(1/3)) thanks to space being three dimensional, but really worse thanks to cooling concerns, and uh, for sufficiently large n, worse because of gravity.)
- btilly 15y agoO(log n) is clearly worse than O(1) if you just considered an O(log n) array-replacement data structure or hash table-replacement data structure and considered what its performance would be. I mean, how is this even a question? Why yes, it is worse in some theoretical manner. But if you think it is necessarily worse as a practical manner, you have failed to understand the math fully. Suppose that n is 1000 in some toy problem. Then you scale it up to a huge data set, a billion items! The log(n) factor only got worse by a factor of 3. Maybe we didn't go high enough. Perhaps we can take a large data set. Let's see, how about all of the data that is produced at CERN's Large Hadron Collider in a year? That's 15 petabytes. Now the log(n) factor is a whopping 5.39. In other words while log(n) represents unbounded possible growth, it gets worse in practice by at most a fairly small constant factor. How about O(1)? O(1) does not mean fast. It just means constant relative to the data size. It can be a bad constant, but as long as it is a constant it qualifies as O(1). Let's take a practical example. Wavelets are cool in lots of ways, but one of the properties people noticed quickly is that doing a basic wavelet transform on a data set with n elements takes time O(n). Doing a FFT (Fast Fourier Transform) on the same data set takes time O(n log(n)). Yay, we're faster! But hold on a minute. The interesting wavelets that we like to use are O(n) with a worse constant than the FFT. So the FFT tends to be faster on practical data sets. (There are lots of reasons why one would prefer wavelets over the FFT, but speed of calculation is not generally one of them.)
- SamReidHughes 15y ago> But if you think it is necessarily worse as a practical manner, you have failed to understand the math fully. Congratulations, I don't think one algorithm is necessarily worse, your entire post was a waste of effort. I mean seriously you just made a post teaching about how logarithmic constants can be low enough that they don't matter in reply to my post which provided an example of that very thing.
- btilly 15y agoI was just explaining the comment that O(log(n)) approaches O(1) for all practical values of n. If you understood this, then why did you start off your post arguing that O(log(n)) was worse than O(1)? Incidentally comparing a logarithmic lookup to a hash lookup, a lot of nosql solutions use hash tables because O(1) is good, right? For instance look at Apache's Cassandra. By contrast Google's BigTable uses an ordered data structure which is logarithmic. Guess what, if you've used both, BigTable is better. Because the extra log cost is irrelevant for the normal use case, and being ordered reduces the operational cost of things like range searches.
- dan00 15y ago"I can't upvote you enough. Too often programmers conflate "functional programming" with "availability of an O(1) array data type". The former does not imply lack of the latter, and (as you stated) lack of the latter does not imply the former." Yes, even the pure Haskell has unboxed, mutable O(1) arrays. They're just a bit hidden for the beginner.
- mickeyp 15y agoYou raise a valid point, and one that a lot of algorithm and data structure textbooks neglect to mention at all; seen purely from a practical perspective, things like locality of data with respect to CPU caches are probably more important than picking a slightly cleverer algorithm/data structure on any modern-day CPU. This once again raises the more subdued or neglected aspect of "premature optimisation": blindly picking an algorithm that looks better on paper may in reality be much slower than a naive algorithm that better matches the characteristics of a computer. Some algorithms are O(1) and you could easily be fooled into believing that they are, indeed, always better than their counterparts that're asymptotically worse than a constant-time; that may not be so, though, if the "constant-time" computations required for non-trivial inputs take longer than say a linear one.
- mjn 15y agoEven the "on-paper" analyses can take some of this into account, with algorithm analysis models that take into account cache and NUMA architectures. But, people do tend to just look at the classic big-O analyses, which may not be right. In a way that kind of dependence isn't new. If you look at old versions of Knuth's TAOCP, for many algorithms he has separate analyses for the in-RAM case and the on-tape case, using two different memory models, and in some cases which algorithm is better differs a lot between the two cases. But it may be that algorithms reference books are doing a worse job keeping up now than they used to.
- mickeyp 15y agoKnuth is probably the only (major) author that I can think of off-hand who took the application of his algorithms and data structures so seriously (going so far as to invent his own little RISC instruction set, MIX (later MMIX.) in a book that concerned itself with the theory as aswell as the practical aspects. Most books focus almost exclusively on one or the other. I think aside from things like cache coherency, memory models and things like SIMD, computer scientists will have to think of their algorithms (or at least cover it when they write books for undergrads or professionals) in terms of commutativity and associativity so people can see how parallelisable an algorithm is or can be.
- 15y ago
- adrianN 15y agoTo my knowledge, mutating memory is asymptotically the same as just reading it. Hence any asymptotic slowdown purely functional language have will translate, regardless of how long memory operations take.
- deleted 15y ago[deleted]
- rwmj 15y agoAre you sure? Writing to memory that might be shared between processors certainly isn't the same as reading, and so a parallel algorithm (and what isn't, these days?) should do better sharing lots of read-only data, rather than mutating shared state.
- scott_s 15y agoBjarne Stroustrup hit a similar point in his recent Going Native keynote (skip to 45 minutes in): http://www.youtube.com/watch?v=OB-bdWKwXsU http://www.youtube.com/watch?v=OB-bdWKwXsU
- brazzy 15y agoActually, memory access is O(n^1/3) if you want to get really real...