After a month break (a month which I spent deep in the guts of the DLR compiler so I wasn't really slacking off) I am back and notice several questions, and since they are good ones (Diky moc, Alesi!), let me address those questions here.
First question was, why do we have the seemingly dual nodes in the DLR Tree and how are they different? One can express operation either using the 'static' nodes, with which one would construct binary addition node as:
Ast.Add(left, right)
And the other is using the dynamic (action) nodes, in which case dynamic addition would be expressed as:
Ast.Action.Operator(Operators.Add, left, right)
How are those two nodes different, which one do I use when, and what are their trade-offs?
Static Nodes
Let's start with the simple one, the static node. Unfortunately, they are hard to come by in dynamic languages so we'll have to use some tricks here and there to really see what's going on. The goal is to write a function that adds integers. Should be pretty simple. Below is the code which does just that in the language of DLR trees (in addition to also setting up the few tricks).
using Microsoft.Scripting;
using Microsoft.Scripting.Runtime;
using Microsoft.Scripting.Generation;
using Microsoft.Scripting.Ast;
namespace Tree {
public class Program {
// Delegate type for our "Add two integers" function
public delegate int AddInt(int l, int r);
public static void Main() {
// Setting DLR options to see the emitted code
ScriptDomainManager.Options.DebugMode = true;
Snippets.Shared.SaveSnippets = true;
// Create parameters for the function
Variable left = Variable.Parameter(SymbolTable.StringToId("left"), typeof(int));
Variable right = Variable.Parameter(SymbolTable.StringToId("right"), typeof(int));
// Create function itself
CodeBlock add = Ast.CodeBlock(
"Add", // Name
typeof(int), // Return Type
Ast.Return( // Body... it is return result of
Ast.Add( // adding
Ast.Read(left), // left argument
Ast.Read(right) // and right argument
)
),
new Variable[] { left, right }, // Parameters of the function
new Variable[0] // These would be local variables
);
// Compile and get delegate back
AddInt ai = TreeCompiler.CompileBlock<AddInt>(add);
// Call it
int r = ai(1, 2);
// Save the generated code
Snippets.Shared.Dump();
}
}
}
Ok, so what's going on here...
The function we are defining will be adding two integers, and ideally we would compile it into a delegate which we can later call, so AddInt is the delegate of choice, function taking two ints and returning int also. Let's fast forward to the lines which define Variable left and Variable right. They are the parameters to our function. in DLR, parameters and variables differ very little so they are, as of right now, represented simply as Variable. To create a variable/parameter, we provide name (currently as the interned SymbolId) and type, in our case typeof(int).
As for the function itself, we need to give it name ("Add"), return type (int) body, array of parameters (left, right) and local variables (no locals for this one). Let's go back to the body:
Ast.Return( // Body... it is return result of
Ast.Add( // adding
Ast.Read(left), // left argument
Ast.Read(right) // and right argument
)
)
This code creates the static "Add" node, an instance of BinaryExpression, give it left and right as children and package it all up in a return for the function. Before we look at the generated code itself, let's poke around in a debugger for a little bit. I'll save the sub-tree into a temp and bring up a watch window:
One thing to notice is that the type of the addExpression is System.Int32, as are the types of the left and right (which we created as such), in other words, the tree is completely statically typed. And now to the tricks I used to get DLR to save the code...
The code that DLR generates goes to various places. In ideal case, it goes into dynamic methods, which are pieces of code which get garbage collected as soon as nobody uses them anymore. Problem is, they can' be saved and later inspected (which makes it really fun to debug cases where one emits unverifiable code ... another reason to use the DLR trees and let us do the code generation :) The debug flag and setting a "Save" flag on snippets (set of assemblies DLR keeps around to generate code - and especially types - into if needed) and later calling Snippets.Shared.Dump() will ensure that after our program exits, we'll get to inspect the generated assembly (called Snippets.dll in this case), so let's drill into it:
Looking at the IL view, we see a function with 3 parameters, the 2nd and 3rd are our two ints, left and right (let's ignore the first one for now), and the IL is very simple. Load left, load right, add, return. As for the last two instructions, DLR always adds them so because it doesn't yet do code flow analysis to determine whether all function's branches terminate with return.
So the function itself is pretty tight IL, and that's due to the fact that the input tree was statically typed, using the BinaryExpression node.
As for the first argument ... We'll see it play bigger role in the future posts, but for now let's just say that the DLR compiler may face situations in which it needs to pass data from compilation to runtime. After the compiler is done with the delegate, it will put all such data into the "Closure" and bind it to the delegate so that it is available to the delegate wherever life takes it. I would love to take detour and tell you all about it, but you'll just have to wait for another post as we'd never get to the dynamic nodes ...
The conclusion of this experiment is that using the static nodes will produce statically typed trees (the binary expression was also typed as int) and the generated code is very much static, and as a result, it is also faster.
Where would one use these nodes? Obviously, where compiler knows for sure the types of the operands and the full runtime semantic of the operation at compile time (when generating the trees). There's another place where these nodes are useful, and we'll get to it in a minute.
Dynamic nodes
Dynamic nodes are much easier to bring to life. All we need to do, just like in the previous posts, is write little Python script (or ToyScript script). This is in fact what we discussed few posts back. ToyScript, or Python, when facing a dynamic operation (which are pretty much all of them), will generate the dynamic "Add" node. Unlike the statically typed expression node, the dynamic node's arguments are, in general sense, typed as object. That's why the tree dump of our little toy function:
def f(a,b) {
return a + b;
}
Looks like this:
.codeblock Object f ()(
.arg Object a (Parameter,InParameterArray)
.arg Object b (Parameter,InParameterArray)
) {
{
.return .action (Object) Do Add( // DoOperation Add
(.bound a)
(.bound b)
);
}
}
Where as far as you can see, everything is an object. So really what one expresses when using the dynamic "add" node is: "I really have no idea what exactly is going to happen here, all I know is that the operation is binary addition." And we already discussed that this node will create what we call DynamicSite, and when, at runtime, the operation gets invoked, only then can the language produce the rule as to what to do in a given case.
And here's where the static nodes come into play again. In a way, using the dynamic nodes means postponing certain decisions until runtime. But no matter how hard you try, nobody can add two instances of object. At some point we get the actual values, the language gets to examine them in the binder and will produce a rule. When it does so, the language implementation has the advantage of knowing the types of the values that are, in this precise moment, being operands to a given operation. And to express the actual operation that needs to be performed, the language uses ... the static nodes.
Let me add call to the above function f, taking two integers, and let's have DLR run wild with it and produce dump of all trees that it encounters, by running:
ts.exe -X:ShowASTs -X:ShowRules x.ts
The rule that DLR produced for the addition when presented with 2 doubles (ToyScript doesn't deal with integers, only doubles), is:
//
// AST Rule.Test
//
((((.bound $arg0) != .null) && (((.bound $arg0)).(Object.GetType)() == ((Type)Double))) &&
(((.bound $arg1) != .null) && (((.bound $arg1)).(Object.GetType)() == ((Type)Double))))
//
// AST Rule.Target
//
.return .comma {
(.bound $retVal) = ((Double)(.bound $arg0) + (Double)(.bound $arg1))
(Object)(.bound $retVal)
}
The rule says that if we are dealing with two doubles, this is how you add them ... and here it produces code which is using the statically typed BinaryExpression with two children, both of type double. And if we were to look at the generated code in the reflector (save it using -X:SaveAssemblies -X:StaticMethods), we'd find the compiled code to be very similar to the tree dump above:
and in IL, the actual addition of doubles is here:
So again, the statically compiled addition operator in the form of a very tight IL. Notice that in this case the parameters are both of type object so the code must cast them to double first by un-boxing them.
Summary
It turns out that the dynamic operation nodes postpone certain decisions until runtime. When the actual operands are known, the language decides what needs to be done, expresses it via the static nodes (which compile into very nice IL) and that's the code that runs from then on. To answer the actual question, the static nodes are faster. The dynamic ones are slow the first time around, but from then on they are very fast too. There's some overhead in the tests present in the dynamic site, but it is hardly anything compared to what runtime lookup on each call would do.
The second question Ales asked will have to wait until next time. For now, I am back to coding...