[LLVMdev] Efficient implementation of closures?

[Jon Harrop]

On Sunday 28 December 2008 05:53:55 Talin wrote:
> The second solution is that when calling via a pointer, we always call
> with the closure protocol, i.e. we include the hidden parameter.
> However, when taking the address of a non-closure function, we actually
> point to a stub function which strips off the hidden parameter before
> calling the real function. This solution is better in that it means that
> the extra cost is only paid when calling a non-closure function via a
> pointer. However, it means that we essentially pay the cost of
> marshalling the calling arguments twice.

I have been thinking about this myself recently and there is another 
specialization that can completely remove the performance hit of functional 
abstraction in some important cases and, in particular, it is made feasible 
by JIT compilation.

It may be instructive to consider a concrete example such as summing the 
elements of a float array by passing the add function to the higher-order 
fold function:

  let sum xs = Array.fold_left ( + ) 0.0 xs

Previous generation languages like OCaml compile this into a completely 
generic representation where polymorphism is handled at run-time. 
Consequently, even though the polymorphism is buried in the fold function 
(not visible at all in our "sum" function) it still incurs massive 
performance degradation.

JIT compilation makes it easy to avoid the cost of polymorphism by generating 
code for each permutation of type variables that a definition is used with. 
That immediately removes the cost of polymorphism because we get a version of 
fold specialized for float arrays.

However, there is still the overhead of the call to "+" which is obviously 
gratuitous in this case even if the function call is statically optimized 
from a closure into a function pointer. Inlining the higher-order fold 
function completely removes this cost as well and recovers the performance of 
hand-written C code.

JIT compilation makes a lot of interesting optimizations feasible...

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e