Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Inspired by a question from SO: http://stackoverflow.com/questions/6623391/how-to-gain-control-of-a-5gb-heap-in-haskell

It can be a long debate about FP's numerous advantages and disadvantages, but for now, I'd like to narrow the scope to principal efficiency of FP on modern hardware.

Thesis:

Functional paradigm implies immutability and statelessness (?), but the hardware we run functional programs on are stateful finite automata. Translation of 'pure functional' program to a 'stateful hardware' representation leaves little control to programmer, brings overhead (?) and limits the use of hardware capabilities (?).

Am I right or wrong in the questioned statements?

Can it be proven that FP does / doesn't imply principal performance penalties on modern general-purpose computer architecture?

EDIT: As I've already stated in response to some comments, the question isn't about implementation performance and details. It is about presence or absence of principal overhead, which running FP on stateful automata may bring.

share|improve this question
2  
Have you ever really looked at how modern hardware works at a low level? If you care about efficiency at all, it doesn't resemble everyday imperative programming either. –  C. A. McCann Jul 8 '11 at 15:44
    
Believe it or not, but the computer scientists who have designed functional programming languages and compilers also know a little bit about optimizing for performance. That isn't the goal of every functional language product but is for the serious production platforms. –  Jeremy Jul 8 '11 at 15:56
    
@camccann, @Jeremy: C# and Java, for example, use virtual machines. No matter how optimal it is, no matter how efficient C# and Java programs are for production, there is a principal source of inefficiency, and it is the VM. The question isn't about implementation performance, but running FP on stateful automata. –  vines Jul 9 '11 at 7:12
1  
see my question here- programmers.stackexchange.com/q/71391/963 –  Gulshan Jul 9 '11 at 9:24
1  
@vines: You realize that modern VMs with fancy JITing can actually outperform native code in some cases, right? And that the whole purpose of a compiler is to convert a program to a representation matching the underlying architecture, which is unlike any modern language? Your question doesn't make any sense. –  C. A. McCann Jul 9 '11 at 15:00

4 Answers 4

up vote 5 down vote accepted

There is a huge misunderstanding in immutability.

The immutability is a feature of the semantics, but it does not imply immutability in implementation.

A simple example is the implementation of laziness.

When computations are lazy, the result of an expression is conceptually a value, but the underlying implementation is a thunk that contains the arguments to be evaluated and a function to create the value, as well as a slot to store the value in.

The first time you will ask (in the language) for the value, the computation will actually be performed, its result evaluated, and the value given back to you (or a handle).

This is transparent in the language semantics, and all you know is that this variable has been bound to a value (or a future value) and that once it's done you cannot change the value that will be returned. The underlying memory representation will change, but you won't know about it.

The same semantic/implementation difference exist in about any language, and is in fact at the heart of optimization. Whatever the language, the semantics guarantee some things, but leave others unspecified to leave room for optimization.

Now, it is true that practically functional languages are not as fast as C++, for example. However, Go (which is quite the hype still) is slower than Haskell or Lisp, and so is C# Mono (source).

When you see how unreliable C++ or C can be to get you those performances, you might wish to let go a bit.

When you realize that Haskell is growing fast today, and there is still much room for optimization in its compiler/runtime (GHC just switched recently to LLVM for example, Microsoft Research is actively funding the runtime improvements), you might be willing to bet that it's going to improve soon.

Fun: A Play on Regular Expressions or how a Haskell team created a regular expression matcher that outperforms re2, the C library from Google, in a number of scenarios.

share|improve this answer
    
Sounds optimistic :) –  vines Jul 9 '11 at 18:29

Functional paradigm is useful to split up thing in a narrow scope. This is a really good thing considering how computer evolve.

Multicore CPU have big problems dealing with shared resources and synchronization cost are really exepensive. Functional paradigm allows a natural way to express programs that doesn't have thoses issues. This is really good for parallelism.

In addition, we are using servers farms more and more with SaaS and cloud computing. Thus, the same application has to run on several machines. In this position, synchronization costs are even more costly. Google has done some work and publish some research papers about functionnal programming and algorithm you can write in. This is a key thing for them because they have a scallability issue.

Moreover, you can easily do a stack in the heap of the computer, and even a non continuous one using linked lists. This is aloready done to generate stack trace in many programmation languages. So this is not an issue.

OK, functionnal programming implies some limitations. But it also brings natural way to express problematics we have in modern computering, that are extremely hard to handle in paradigms wa are used to. Scalability is one of them, and it's becoming a real deal.

Everyone that already deal with a complex parallel system know what I'm talking about.

So I would nuance the answer. Yes, functional has issue with modern hardware, but plain old programming has some too. Like always, you'll find advantages and drawbacks. The point is to know what they are so you can make the apropriate choice when you have to.

share|improve this answer

It's true that the functional paradigm implies immutability and statelessness, but we don't have any completely pure programming languages. Even the purest, Haskell, allows side effects.

That said, to answer your question about efficiency, I've used both Haskell and Clojure, and haven't noticed any performance issues with either.

share|improve this answer
1  
Issues are relative to requirements... What about performance-critical areas? High parallelism is valuable there, but what's the overall score? –  vines Jul 8 '11 at 14:30
1  
@vines: I haven't used either language for a performance-critical application, so I can't really speak to that. –  Larry Coleman Jul 8 '11 at 14:47
1  
Not much fun with no side effects, as you would not be able to save the result anywhere. –  user1249 Jul 8 '11 at 15:04
    
@Thorbjørn Ravn Andersen: ...in a way other than returning it to the caller, which is allowed. –  vines Jul 8 '11 at 15:24

I don't really have an answer, as I don't know the current state or even how difficult it would be, but just because the compiler would ensure those things from the input, doesn't necessarily mean that the output would have them. In theory, a sufficiently smart compiler could by pass all these problems, but in practice, it probably will always exist.

However, another way to look at it is to look at the history of the Lisp machine. If I recall correctly, they were originally designed to over come the same problems Lisp had with it's difference from the machines at the time. Development of these machines eventually stopped, as desktop became fast enough to make the inefficiencies cheaper to live with than to support another machine.

Generally, except for the most performance critical application, FP languages are still fast enough. Choices any higher level language, you will be willing to lower the priority on fine tune control and performance for safer, easier, more maintainable, or some other priority.

End in the end, programming is all about trade offs, so one just needs to choose what matters more for the project on hand.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.