Last time I talked about the 3 levels of DLR caches. Level 0 stored directly in a delegate, Level 1 on the dynamic site, and finally Level 2 which spans multiple sites. Language runtime binders (also called Dynamic- or Action- binders) produce rules that then end up in the DLR caches for future retrieval. We also briefly looked at the code which performs the lookup. In the code you are looking at this logic is still on ActionBinder, but as soon we upload the latest sources, the logic will move to the ultimate place - CallSite<T>.

The question we'll look at today is: How do we actually search in the caches? And the quick answer is that we use what we call "Matchmaker" to do that.

To DLR, the rule is just a piece of code which examines the argument values and if the arguments match the rule, it performs operation. If the rule is not applicable to the argument values, the execution falls off the end. In Level 0 cache where the rules are neatly emitted into a delegate this is clearly visible:

public static object _stub_(
    Closure closure, CallSite site, CodeContext context,
    object obj1, object obj2) {

    // Rule 1
    if ((obj1 is string) && (obj2 is string)) {
        return (((string)obj1) + ((string)obj2));
    }

    // Rule 2
    if (((obj1 != null) && (obj1.GetType() == typeof(double))) &&
        ((obj2 != null) && (obj2.GetType() == typeof(double)))) {

        return (((double)obj1) + ((double)obj2));
    }

    // Fall off the end into cache lookups
    return ((CallSite<DynamicSiteTarget<CodeContext, object, object, object>>)site)
        .Update(site, context, obj1, obj2);

}

If we fall of the end completely, the delegate will call into the cache lookup and update logic. It is the "Update" call above. The trick is that the Update is itself a delegate. For regular dynamic sites, this is always a delegate which packages up the arguments into an array and calls. We have predefined ones in "UpdateDelegates.Generated.cs" and if those are not enough, we use lightweight code generation to build a custom one.

And now to what the matchmaker is. Matchmaker is a dynamic site which has the update logic modified. Instead of calling into the cache lookup, it will only take note of the fact that the rule did not match (and hence didn't perform the operation) and the cache lookup logic can continue searching. You can check out the pre-build matchmaker logic in "Matchmaker.Generated.cs".

The actual cache lookup is easy. We build a matchmaker dynamic site, get the list of applicable rules (from Level 1 or Level 2 caches) and iterate though those. Each step we reset the matchmaker, run the rule and check for result. If the rule didn't match, the "update" delegate on the matchmaker was called, and it set a flag accordingly. If rule performed work, no such thing happened so we know we are done searching.

Lastly, to "run" the rule we simply call the Invoke method on the rule's own delegate. In DLR, each rule has its own delegate. It looks very much like the code above, except it only contains the work part from the one rule. Then it immediately falls to the update path.

Interesting trivia about these delegates - called also monomorphic delegates - is that if DLR detects badly behaved dynamic site it will stop generating the delegates consisting of multiple rules. Reason is that we would spend too much time generating the new delegates for the site that obviously doesn't benefit too much from them. With such sites we fall back to simply running these monomorphic delegates. Each time we call the dynamic site we fall back to the cache lookup and do the work there.

The code in question lives in CallSite<T>.UpdateAndExecute (the new version). The old version which is still the latest available on CodePlex has it in ActionBinder.UpdateSiteAndExecute<T>.