9 ms·

What is the asymptotic cost of purely functional programming?

151 points by lambda 15y ago

jerf 15y ago
In addition to the great answer mentioned there, it should also be mentioned that every language referred to as functional still has the ability to use mutable arrays in some manner. Yes, even Haskell, it just requires you to carefully control where the mutation is used.
- greiskul 15y ago
  Yes, I think the great lesson we can take from functional programming is not of being functional 100% of the time, but of not having mutable global state. Your inner loops, local variables, etc. can all be mutable and nobody will care, as long as your interface is functional.
  - fpgeek 15y ago
    Yes and no. It is true that what matters most of the time is a functional interface, not how that is achieved. That being said, it is much harder to successfully implement a functional interface if you are using side-effects willy-nilly inside.
chimeracoder 15y ago
Purely functional programming? I dunno, what's the asymptotic cost of flipping a switch on a box and watching it warm up[1]? Nobody advocates purely functional programming, at least not in the implementation of a language itself, but it can be an incredibly valuable model for a language interface. In the same way, a stack (or better yet, semi-infinite tape) can be an incredibly valuable model for a language interface at well. Functional programming is, by definition, just another way of saying that your model of computation is based on the lambda calculus instead of a Turing machine. You can just as easily ask what the asymptotic 'cost' of using a non-random access Turing machine is. If people really want a functional language with a purely functional implementation, then you have to say 'farewell' to even things like tail-recursion, since you can make the argument that converting recursion to a loop is anti-lambda calculus. EDIT: It seems there's some confusion over the distinction between implementing a purely functional algorithm in a language and implementing an language in a purely functional manner. My point is that, even if you implement your algorithm in a purely functional manner, if your compiler is simply converting it to a (well-optimized) imperative, destructive code behind-the-scenes and making it appear to be immutable, then this entire question is rather beside the point. [1] (With apologies to Simon Peyton Jones).
- aplusbi 15y ago
  If it were really purely functional it wouldn't even warm up. When you compile your code, referential transparency would result in your executable being nothing more than the final value produced by your code.
  - chimeracoder 15y ago
    I've had this debate before :-) http://twitter.theinfo.org/171745809686200320#id171799214685306883 http://twitter.theinfo.org/171745809686200320#id171799214685... If we want to get really pedantic, I guess we could say that we're using one Turing machine (our computer) to emulate another equivalent model of computation (the lambda calculus), so the computer warms up because the Turing Machine is an inefficient emulator of the instantaneously-evaluating lambda calculus evaluator. But the lambda calculus evaluator doesn't change state. ...so, what we really need is to wait for someone to invent a lambda calculus evaluator. Then we wouldn't need to emulate them with these silly Turing machines, and we could get instant evaluations of our programs based solely on ϐ-reductions, with no side-effects (thermal side-effects included). That would put an end to this debate! (Furthermore, who cares if P=NP if ϐ-reductions can be evaluated 'directly' instead of being emulated by these obsolete Turing machines? Even the hardest decidable problems would be solved instantaneously!)
    - skew 15y ago
      If you were really pedantic, you'd make a distinction between executing beta-reductions directly, and executing them in zero time. Here's hardware that does the first http://www.cs.york.ac.uk/fp/reduceron/ http://www.cs.york.ac.uk/fp/reduceron/
      - chimeracoder 15y ago
        Yeah, in case it wasn't clear, by my second reply I was just being facetious. Pedantry is infinitely recursive, with no base case in sight and no tail optimization - my tolerance/stack for these things overflows rather quickly. :-) But thanks for the link! I'll be sure to check it out later; it looks interesting.
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 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. 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 ago
    Edit: 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 ago
      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? 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.)
ww520 15y ago
Lazy evaluation probably adds more unintuitive cost. E.g. Haskell uses thunk to track yet-to-be-evaluated values. These thunks take up memory and take up CPU cost. For lazily evaluated function calls (or expression), each call has a thunk created and it will be evaluated later when needed. For deep recursive calls the thunk link can be very long. Lazy evaluation is great in that the actual computation might not needed at the end but there are non-trivial cost to track and evaluate all the thunks. It's an extra dimension to consider when comparing the cost of doing simple computation with strict evaluation vs utilizing lazy evaluation with the added thunking cost.
- lnmx 15y ago
  I learned a lot about this from Edward Z. Yang's blog: http://blog.ezyang.com/2011/06/pinpointing-space-leaks-in-big-programs/ http://blog.ezyang.com/2011/06/pinpointing-space-leaks-in-bi... http://blog.ezyang.com/2011/04/the-haskell-heap/ http://blog.ezyang.com/2011/04/the-haskell-heap/
debacle 15y ago
I don't understand the term 'asymptotic cost' in the context of functional programming - simply the difference in efficiency between functional and imperative programming?
- ww520 15y ago
  It's just a fancy word for the BigO notation. See https://en.wikipedia.org/w/index.php?title=Asymptotic_complexity&redirect=no https://en.wikipedia.org/w/index.php?title=Asymptotic_comple...
  - debacle 15y ago
    So it's simply the difference in efficiency between an imperative and a functional algorithm?
    - ww520 15y ago
      It is not a matter of imperative or functional. It's the difference between mutable and immutable style programming. You can have an immutable imperative program or a mutable functional program. Lots of algorithms maintain mutable states. When these algorithms are translated into immutable state style, their complexity (BigO) shoots up. The SO question is asking what's the increased complexity when moving to PURE functional programming style.
lmkg 15y ago
The top-voted answer mentions that the example O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not? I sort of view lazily-evaluated data structures (like generator expressions) as not data structures at all, but rather control flow constructs[1]. They control when, how, and if expressions are evaluated and results are returned. As a result, I feel that using lazy equivalents for your data structures qualifies as an algorithmic change. In fact, one could manually code lazy data access in an eager language, and the resulting algorithm would look very different from the original. On the other hand, the laziness is enabled by the purity of the algorithm, so... well, it depends on your perspective. You could say that laziness makes the functional equivalent just as fast, or you could say that the functional equivalent is slower, but there's a different functional algorithm that is just as fast. [1] Except they're still data structures. They're like, a quantum superposition of data structure and control-flow operator. Which one it is depends on how you look at it.
- eru 15y ago
  Yes. That's why in Haskell programming a common sentiment is that data structures are control structures. And why we need non-linear data structures for concurrent execution (http://vimeo.com/6624203 http://vimeo.com/6624203).
- agumonkey 15y ago
  I think of Data structures as extension, value sets. Function as intension. They are dual to each other, sort of, modulo `some` energy.
- jpendry 15y ago
  You're getting dangerously close to describing continuations. And I think it's important to remember that just because a programming language doesn't give you access to a data structure, it doesn't mean it's not using it under the covers. The call stack is a data structure in all programming languages, only a few provide you with easy access to it.
- nandemo 15y ago
  > O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not? I don't think anyone is claiming that it is the same algorithm. Rather, they're claiming that using lazy evaluation gives you more choice of algorithms; and one of these algorithms is faster than the best algorithm under strict evaluation. I haven't been able to download Bird et. al's paper, but I wouldn't assume it's simply "implementing the same algorithm in Haskell instead of strict ML".
colanderman 15y ago
Uhh… none, seeing as any imperative program can be translated directly into a purely functional one by threading an implicit global state parameter around everywhere. Then it's just a matter of your compiler recognizing this paradigm (for example, Mercury does this). Equivalently, I can write an x86 emulator in a functional language whose time per instruction is independent of the amount of memory used. Then I can just compile an imperative program and run it on my emulator without any asymptotic slowdown. How, you ask? Either (a) my language provides me O(1) functional arrays (e.g. Mercury does this), or (b) I use an O(log n) structure (such as a binary tree): since n is bounded by the size of physically addressable memory, this reduces to O(1). (See also rwmj's comment about memory access times. [1]) The real question to ask is, what is the asymptotic cost of programming in a language without an O(1) array structure? (A property which unfortunately has falsely come to be associated with purely functional programming, due to early functional languages being merely naïve interpreters of the lambda calculus.) The answer to this question of course is likely O(log n). [1] http://news.ycombinator.com/item?id=3828860 http://news.ycombinator.com/item?id=3828860
- cube13 15y ago
  >(b) I use an O(log n) structure (such as a binary tree): since n is bounded by the size of physically addressable memory, this reduces to O(1). (See also rwmj's comment about memory access times. [1]) Uh, no. By definition, a O(log n) structure takes, on average, log n operations to get to the node you want to get to. That never reduces down to constant time, because any given access will take log n reads to get to the correct place. Also, keep in mind that O(1) array lookup isn't really constant time. It's still variable, depending on where the information actually is stored(i.e. in the L2 cache, RAM, on HDD, etc.), the practical time can vary from double digit nanoseconds to several milliseconds. Cache misses can be hugely expensive.
  - colanderman 15y ago
    OK, here's a proof: O(f(n)) means that an operation takes less than k f(n) time to complete (where k is some constant) for all n. I predicated my assertion on bounded memory, hence n is constant. Therefore O(log n) means that the operation is bounded in time by k log n. But since n is also a constant, this is equal to some other constant k'. This is equivalent to saying that the operation is bounded by O(1). QED.
jacquesm 15y ago
There is a very large difference between what you write and what your computer actually does. Something may look like it is O(1) but in reality it may be much slower. The only way to find out is to put the program through its paces with various values for 'n', and to measure the time it took to compute the answer. Prepare to be surprised.
justincormack 15y ago
It is kind of sad that there are no real results since Okasaki 1996. I remember reading that while I was doing my startup-interrupted PhD in the late 1990s. A result that lazy eval was algorithmically equivalent to imperative would be very compelling.
jwatte 15y ago
I've had some whoppers in Erlang, where "garbage generated" ends up costing N-squared, even though the operations were just N. In fact, the garbage collection footprint turns out to be one of the most significant markers for functional performance in my experience. Erlang's per-process heaps help here, because each heap can typically be tiny, but it's still something that needs to be managed as closely as, say, stale pointers in C++.
- jamii 15y ago
  A copying gc helps with that somewhat. When the young generation gets copied you only pay for data that is still alive, not garbage generated. I believe erlang uses mark-and-sweep rather than copying though.
scscsc 15y ago
There seem to be a lot of people confusing complexity with practical issues. I think we can agree that: 1) you can write most software in a functional programming language without any (noticeable) loss of performance 2) there will always be software (video encoders, HPC stuff) that will always be done in Fortran/C :D However, I think the question is very interesting from a theoretical point of view: if you model imperative algorithm as programs for a RAM machine (good theoretical approximation of real single core computers) and purely functional algorithms as programs for a TBI machine (good theoretical approximation of a hypothetical machine executing pure algorithms), is there a problem for which a faster solution exists for a RAM than for a TBI? Note. RAM machines exist and are standard in literature; to my knowledge TBI (to-be-invented) machines do not (yet) exist.
- eru 15y ago
  I agree. > 2) there will always be software (video encoders, HPC stuff) that will always be done in Fortran/C :D Alas, yes. But there are efforts underway to challenge that. Theoretically, your compiler should be able to do a better job, if it knows more about your intent. I'm learning about some techniques for really high performance Haskell. E.g.: * Iteratee/Enumeratee: http://okmij.org/ftp/Streams.html http://okmij.org/ftp/Streams.html * Stream fusion: https://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/ https://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-... The C equivalent of stream fusion would be loop fusion: if you have to for loops one after another iterating over the same array, you could fuse them into one loop. That same trick works in Haskell, even more often and with more benefits.

151 points by lambda 15y ago

jerf 15y ago

In addition to the great answer mentioned there, it should also be mentioned that every language referred to as functional still has the ability to use mutable arrays in some manner. Yes, even Haskell, it just requires you to carefully control where the mutation is used.

greiskul 15y ago
Yes, I think the great lesson we can take from functional programming is not of being functional 100% of the time, but of not having mutable global state. Your inner loops, local variables, etc. can all be mutable and nobody will care, as long as your interface is functional.
- fpgeek 15y ago
  Yes and no. It is true that what matters most of the time is a functional interface, not how that is achieved. That being said, it is much harder to successfully implement a functional interface if you are using side-effects willy-nilly inside.

chimeracoder 15y ago

Purely functional programming? I dunno, what's the asymptotic cost of flipping a switch on a box and watching it warm up[1]? Nobody advocates purely functional programming, at least not in the implementation of a language itself, but it can be an incredibly valuable model for a language interface. In the same way, a stack (or better yet, semi-infinite tape) can be an incredibly valuable model for a language interface at well. Functional programming is, by definition, just another way of saying that your model of computation is based on the lambda calculus instead of a Turing machine. You can just as easily ask what the asymptotic 'cost' of using a non-random access Turing machine is. If people really want a functional language with a purely functional implementation, then you have to say 'farewell' to even things like tail-recursion, since you can make the argument that converting recursion to a loop is anti-lambda calculus. EDIT: It seems there's some confusion over the distinction between implementing a purely functional algorithm in a language and implementing an language in a purely functional manner. My point is that, even if you implement your algorithm in a purely functional manner, if your compiler is simply converting it to a (well-optimized) imperative, destructive code behind-the-scenes and making it appear to be immutable, then this entire question is rather beside the point. [1] (With apologies to Simon Peyton Jones).

aplusbi 15y ago
If it were really purely functional it wouldn't even warm up. When you compile your code, referential transparency would result in your executable being nothing more than the final value produced by your code.
- chimeracoder 15y ago
  I've had this debate before :-) http://twitter.theinfo.org/171745809686200320#id171799214685306883 http://twitter.theinfo.org/171745809686200320#id171799214685... If we want to get really pedantic, I guess we could say that we're using one Turing machine (our computer) to emulate another equivalent model of computation (the lambda calculus), so the computer warms up because the Turing Machine is an inefficient emulator of the instantaneously-evaluating lambda calculus evaluator. But the lambda calculus evaluator doesn't change state. ...so, what we really need is to wait for someone to invent a lambda calculus evaluator. Then we wouldn't need to emulate them with these silly Turing machines, and we could get instant evaluations of our programs based solely on ϐ-reductions, with no side-effects (thermal side-effects included). That would put an end to this debate! (Furthermore, who cares if P=NP if ϐ-reductions can be evaluated 'directly' instead of being emulated by these obsolete Turing machines? Even the hardest decidable problems would be solved instantaneously!)
  - skew 15y ago
    If you were really pedantic, you'd make a distinction between executing beta-reductions directly, and executing them in zero time. Here's hardware that does the first http://www.cs.york.ac.uk/fp/reduceron/ http://www.cs.york.ac.uk/fp/reduceron/
    - chimeracoder 15y ago
      Yeah, in case it wasn't clear, by my second reply I was just being facetious. Pedantry is infinitely recursive, with no base case in sight and no tail optimization - my tolerance/stack for these things overflows rather quickly. :-) But thanks for the link! I'll be sure to check it out later; it looks interesting.

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 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. 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 ago
  Edit: 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 ago
    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? 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.)

ww520 15y ago

Lazy evaluation probably adds more unintuitive cost. E.g. Haskell uses thunk to track yet-to-be-evaluated values. These thunks take up memory and take up CPU cost. For lazily evaluated function calls (or expression), each call has a thunk created and it will be evaluated later when needed. For deep recursive calls the thunk link can be very long. Lazy evaluation is great in that the actual computation might not needed at the end but there are non-trivial cost to track and evaluate all the thunks. It's an extra dimension to consider when comparing the cost of doing simple computation with strict evaluation vs utilizing lazy evaluation with the added thunking cost.

lnmx 15y ago
I learned a lot about this from Edward Z. Yang's blog: http://blog.ezyang.com/2011/06/pinpointing-space-leaks-in-big-programs/ http://blog.ezyang.com/2011/06/pinpointing-space-leaks-in-bi... http://blog.ezyang.com/2011/04/the-haskell-heap/ http://blog.ezyang.com/2011/04/the-haskell-heap/

debacle 15y ago

I don't understand the term 'asymptotic cost' in the context of functional programming - simply the difference in efficiency between functional and imperative programming?

ww520 15y ago
It's just a fancy word for the BigO notation. See https://en.wikipedia.org/w/index.php?title=Asymptotic_complexity&redirect=no https://en.wikipedia.org/w/index.php?title=Asymptotic_comple...
- debacle 15y ago
  So it's simply the difference in efficiency between an imperative and a functional algorithm?
  - ww520 15y ago
    It is not a matter of imperative or functional. It's the difference between mutable and immutable style programming. You can have an immutable imperative program or a mutable functional program. Lots of algorithms maintain mutable states. When these algorithms are translated into immutable state style, their complexity (BigO) shoots up. The SO question is asking what's the increased complexity when moving to PURE functional programming style.

lmkg 15y ago

The top-voted answer mentions that the example O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not? I sort of view lazily-evaluated data structures (like generator expressions) as not data structures at all, but rather control flow constructs[1]. They control when, how, and if expressions are evaluated and results are returned. As a result, I feel that using lazy equivalents for your data structures qualifies as an algorithmic change. In fact, one could manually code lazy data access in an eager language, and the resulting algorithm would look very different from the original. On the other hand, the laziness is enabled by the purity of the algorithm, so... well, it depends on your perspective. You could say that laziness makes the functional equivalent just as fast, or you could say that the functional equivalent is slower, but there's a different functional algorithm that is just as fast. [1] Except they're still data structures. They're like, a quantum superposition of data structure and control-flow operator. Which one it is depends on how you look at it.

eru 15y ago
Yes. That's why in Haskell programming a common sentiment is that data structures are control structures. And why we need non-linear data structures for concurrent execution (http://vimeo.com/6624203 http://vimeo.com/6624203).
agumonkey 15y ago
I think of Data structures as extension, value sets. Function as intension. They are dual to each other, sort of, modulo `some` energy.
jpendry 15y ago
You're getting dangerously close to describing continuations. And I think it's important to remember that just because a programming language doesn't give you access to a data structure, it doesn't mean it's not using it under the covers. The call stack is a data structure in all programming languages, only a few provide you with easy access to it.
nandemo 15y ago
> O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not? I don't think anyone is claiming that it is the same algorithm. Rather, they're claiming that using lazy evaluation gives you more choice of algorithms; and one of these algorithms is faster than the best algorithm under strict evaluation. I haven't been able to download Bird et. al's paper, but I wouldn't assume it's simply "implementing the same algorithm in Haskell instead of strict ML".

colanderman 15y ago

Uhh… none, seeing as any imperative program can be translated directly into a purely functional one by threading an implicit global state parameter around everywhere. Then it's just a matter of your compiler recognizing this paradigm (for example, Mercury does this). Equivalently, I can write an x86 emulator in a functional language whose time per instruction is independent of the amount of memory used. Then I can just compile an imperative program and run it on my emulator without any asymptotic slowdown. How, you ask? Either (a) my language provides me O(1) functional arrays (e.g. Mercury does this), or (b) I use an O(log n) structure (such as a binary tree): since n is bounded by the size of physically addressable memory, this reduces to O(1). (See also rwmj's comment about memory access times. [1]) The real question to ask is, what is the asymptotic cost of programming in a language without an O(1) array structure? (A property which unfortunately has falsely come to be associated with purely functional programming, due to early functional languages being merely naïve interpreters of the lambda calculus.) The answer to this question of course is likely O(log n). [1] http://news.ycombinator.com/item?id=3828860 http://news.ycombinator.com/item?id=3828860

cube13 15y ago
>(b) I use an O(log n) structure (such as a binary tree): since n is bounded by the size of physically addressable memory, this reduces to O(1). (See also rwmj's comment about memory access times. [1]) Uh, no. By definition, a O(log n) structure takes, on average, log n operations to get to the node you want to get to. That never reduces down to constant time, because any given access will take log n reads to get to the correct place. Also, keep in mind that O(1) array lookup isn't really constant time. It's still variable, depending on where the information actually is stored(i.e. in the L2 cache, RAM, on HDD, etc.), the practical time can vary from double digit nanoseconds to several milliseconds. Cache misses can be hugely expensive.
- colanderman 15y ago
  OK, here's a proof: O(f(n)) means that an operation takes less than k f(n) time to complete (where k is some constant) for all n. I predicated my assertion on bounded memory, hence n is constant. Therefore O(log n) means that the operation is bounded in time by k log n. But since n is also a constant, this is equal to some other constant k'. This is equivalent to saying that the operation is bounded by O(1). QED.

jacquesm 15y ago

There is a very large difference between what you write and what your computer actually does. Something may look like it is O(1) but in reality it may be much slower. The only way to find out is to put the program through its paces with various values for 'n', and to measure the time it took to compute the answer. Prepare to be surprised.

justincormack 15y ago

It is kind of sad that there are no real results since Okasaki 1996. I remember reading that while I was doing my startup-interrupted PhD in the late 1990s. A result that lazy eval was algorithmically equivalent to imperative would be very compelling.

jwatte 15y ago

I've had some whoppers in Erlang, where "garbage generated" ends up costing N-squared, even though the operations were just N. In fact, the garbage collection footprint turns out to be one of the most significant markers for functional performance in my experience. Erlang's per-process heaps help here, because each heap can typically be tiny, but it's still something that needs to be managed as closely as, say, stale pointers in C++.

jamii 15y ago
A copying gc helps with that somewhat. When the young generation gets copied you only pay for data that is still alive, not garbage generated. I believe erlang uses mark-and-sweep rather than copying though.

scscsc 15y ago

There seem to be a lot of people confusing complexity with practical issues. I think we can agree that: 1) you can write most software in a functional programming language without any (noticeable) loss of performance 2) there will always be software (video encoders, HPC stuff) that will always be done in Fortran/C :D However, I think the question is very interesting from a theoretical point of view: if you model imperative algorithm as programs for a RAM machine (good theoretical approximation of real single core computers) and purely functional algorithms as programs for a TBI machine (good theoretical approximation of a hypothetical machine executing pure algorithms), is there a problem for which a faster solution exists for a RAM than for a TBI? Note. RAM machines exist and are standard in literature; to my knowledge TBI (to-be-invented) machines do not (yet) exist.

eru 15y ago
I agree. > 2) there will always be software (video encoders, HPC stuff) that will always be done in Fortran/C :D Alas, yes. But there are efforts underway to challenge that. Theoretically, your compiler should be able to do a better job, if it knows more about your intent. I'm learning about some techniques for really high performance Haskell. E.g.: * Iteratee/Enumeratee: http://okmij.org/ftp/Streams.html http://okmij.org/ftp/Streams.html * Stream fusion: https://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/ https://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-... The C equivalent of stream fusion would be loop fusion: if you have to for loops one after another iterating over the same array, you could fuse them into one loop. That same trick works in Haskell, even more often and with more benefits.