Efficient function composition with Truffle

[Chris Seaton]

Truffle automatically splits methods that have become megamorphic.

Splitting means that multiple copies are made which can specialise independently with independent inline caches. Splitting can be recursive. It happens based on heuristics that looks at how many specialisation your node are actually using and similar properties, and can be tweaked by the language implementor if needed, or forced or disabled.

This is a major advantage over implementing languages on the JVM in the conventional way, where, as you say, higher order methods quickly become megamorphic. The effect is particularly strong in languages like Ruby where many control structures are method calls.

Are you not seeing splitting working automatically already? You should see references to ’split’ in -Dgraal.TraceTruffleCompilation=true.

Chris

> On 20 Jan 2019, at 20:52, Timothy Baldridge <tbaldridge at gmail.com> wrote:
> 
> Something that I haven't figured out yet in my studies of Truffle, is the
> best way to deal with higher-order functions in a Truffle language. Let's
> say we have a function like comp from Clojure:
> 
> (defn comp [a b]
>  (fn inner [x]
>    (a (b x))))
> 
> The semantics here are fairly simple, comp takes two functions and composes
> them. A problem in on the JVM (and I think in Truffle) is that these call
> sites quickly become megamorphic. There may be thousands of functions in a
> runtime, and so if comp is used a lot, the callsites in the inner function
> (calls to a and b) have to become indirect.
> 
> This problem exists in may situations, for example with reduce:
> 
> (defn sum [coll]
>  (reduce + 0 coll))
> 
> Reduce may be called in many places in the runtime, but in this specific
> case, the callsite that invokes + can be monomorphic.
> 
> So what's the best way to code this sort of thing? Do I manually clone AST
> trees that use higher-order-functions? Is there some sort of feature in
> Truffle that allows me to say "duplicate this entire AST whenever this node
> changes?"
> 
> Thanks,
> 
> Timothy Baldridge