Function Overhead in Functional Languages like Haskell or in Hybrids like Scala [closed]

Question

Coming from imperative languages like Python, Javascript and Java, I was very often reading about function overhead and why to avoid map from a performance perspective. Obviously these are no functional languages and foreign concepts usually tend to be less optimised and less idiomatic. I understand that calling functions is pushing values from the registers back to the stack which is expensive.

So with the recent buzz about FP concept and languages I'm really wondering how does Haskell solve this Problem? Is it just that the compilers are inlining a whole lot? In addition to that how do FP-Languages (Clojure/ Scala) on the JVM solve this Problem? Not even having a decent Tail-Call optimisation tells quite a bit about JVMs capabilities in terms of optimising FP Code.

Thank you!

Answer 1

I can't provide a comprehensive answer for Haskell, but for Scala the answer is pretty simple: it performs transformations on the bytecode so that, for example, a (simple) tail call is implemented as a loop with variables instead. This is inherently what any language has to do to achieve good performance since computers are mutable (RAM, not WORM!).

Turning a method into something that can be passed around involves creating an object, but object creation is cheap on the JVM, and both the JVM and Scala have or will have tricks to avoid creating that object at all unless it's really necessary.

Then there's the issue of re-use of memory vs. use of new memory. That one is hard to get around entirely, but the JVM is very good at rapidly reclaiming memory, so you pay a relatively modest penalty for e.g. recreating your list each time instead of mutating the values in it. (If no references to the old list remain, you could just mutate the values and call it a new list--I don't know whether GHC plays tricks like this.) The worst situation is when you need a local update, where you can have log(n) work instead of constant-time work in some cases.

When you add all of these things together, the (single-threaded) performance penalty is often modest or negligible.