Efficient function composition with Truffle

[Boris Spasojevic]

Hi Timothy,

You might want to take a look at the entire contents of the 
https://github.com/oracle/graal/blob/master/truffle/docs/splitting as it 
describes the direction we are taking splitting. The current splitting 
heuristic is bad for a multitude of reasons and we are (hopefully soon) 
moving to the new approach described in the linked documentation.

The short version is that we are giving the language implementor the 
option to decide which nodes are likely to benefit from being split, and 
annotate them (@ ReportPolymorphism 
http://www.graalvm.org/truffle/javadoc/com/oracle/truffle/api/dsl/ReportPolymorphism.html). 
Such nodes will inform the runtime when they turn polymorphic, allowing 
the runtime to attempt to "monomorphize" that node through splitting.

BoriS


On 01/20/2019 10:32 PM, Chris Seaton wrote:
> 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)