Efficient function composition with Truffle

[Chris Seaton]

There’s this file and others in the same directory

https://github.com/oracle/graal/blob/master/truffle/docs/splitting/MonomorphizationUseCases.md

We sometimes call splitting ‘monomorphization’, as that’s what it achieves, and we also sometimes call it ‘cloning’ as that’s how it’s achieved, sorry for all the names! I know I’ve covered it in some of my talks, but I haven’t particularly signposted it.

It’s not mentioned much in the API documentation as it’s supposed to be automatic. Here’s one reference

https://www.graalvm.org/truffle/javadoc/com/oracle/truffle/api/nodes/DirectCallNode.html#cloneCallTarget--

> On 20 Jan 2019, at 21:21, Timothy Baldridge <tbaldridge at gmail.com> wrote:
> 
> Thanks for the info! No, I simply wasn't seeing any information about this in the documentation. On that subject, how would I know this from the docs? Almost everything I can read on Truffle is either super high-level "Truffle merges Nodes, and look, you can be polyglot on the JVM!", or is something like the API docs that are so low level it's hard to know how it all fits together. 
> 
> On Sun, Jan 20, 2019 at 2:07 PM Chris Seaton <chris.seaton at oracle.com> wrote:
> 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
> 
> 
> 
> -- 
> “One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
> (Robert Firth)