In the earlier posts on dynamic operations I talked about dynamic binders and rules. Then, rule was two things combined - test and target, both represented as expression trees. Test would determine whether arguments of the dynamic operations 'fit the target' and target would then perform the operation.

These rules, I mentioned, were cached inside of DLR for later reuse (so that DLR didn't have to ask the language binder over and over for the same rule). Today we will explore these caches and also changes that happened in the DLR since those posts. I will base this post off of the latest published sources on CodePlex, and in few places I will point out what it is that you have to look forward to in the near future as we publish next version of the sources. I am trying to find the way to publish our sources more frequently.

As the language binder produces the rule for performing a given dynamic operations, DLR will add it to the caches. DLR maintains 3 levels of caches so let's dive in and see what and where they are.

Level 0

When the dynamic operation is happening, DLR calls into the dynamic site which will in turn immediately call a delegate stored on the dynamic site. The delegate is a level 0 cache. if we were to disassemble the delegate, we would see the cache lookup expressed directly as code below.

// Level 0 cache lookup

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

    // Trying to match the cache entry for strings

    if ((obj1 is string) && (obj2 is string)) {

        // Cache hit on strings

        string str = ((string)obj1) + ((string)obj2);
        return str;
    }

 

    // Trying to match the cache entry for doubles

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

        // Cache hit on doubles

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

 

    // Level 0 cache miss, call for help

    return ((CallSite<DynamicSiteTarget<object, object, object>>)site).Update(
        site, context, obj1, obj2
    );
}

One idea that will apply to all of the cache levels is most visible here ... the cache lookup happens by executing the code, or in other words, by executing the rules in the level 0 cache.

Each dynamic site has its own Level 0 cache and the idea here is that well behaved programs generally only work with small set of types at a given call site and for such programs the level 0 cache will rarely experience a cache miss.

Level 1

However, a level 0 cache miss can happen. And when it does, the delegate cries for help by calling back into DLR. If you study the code above carefully and compare it to some of the older examples, you notice that the "cry for help" code has changed a little. Not to worry, it still serves the same purpose.

In general, the ultimate receiver of the 'cry for help' is a method "UpdateSiteAndExecute<T>" in ActionBinder.cs. It is the place where the Level 1 and Level 2 cache lookup happens. But where is the level 1 cache stored? Each call site has its own level 1 cache. If you look in CallSite.cs and find CallSite<T>, its first field:

    /// <summary>
    /// Dynamic site
    /// </summary>
    public sealed class CallSite<T> : CallSite {
        /// <summary>
        /// RuleSet - keeps history of the dynamic site
        /// </summary>

        private RuleSet<T> _rules;

        ...

    }

 

is the level 1 cache.

While Level 0 stores the rules compiled into an executable code, the Level 1 cache is just a read only (read only is important because it allows us to do cache lookups without holding locks) list of rules that the dynamic site has seen throughout its life. The delegate which is the level 0 cache is formed from (some of) the is the rules from this level 1 cache. Often from all of them, but not necessarily always.

Now we can go back to the cache lookup code in ActionBinder.UpdateSiteAndExecute<T>. The code we care about is starts here:

//
// Look in the site's local cache first, if we have rules, run those.
// If we find match, the site is polymorphic. Update the delegate in that
// case and keep running.
//

IList<Rule<T>> history = siteRules.GetRules();

 

if (history != null) {
    count = history.Count;
    for (index = 0; index < count; index ++) {
        rule = history[index];

        ...

    }
}

In short, we pull out all the rules from the level 1 cache as a list, iterate through them and the code I replaced with "..." is executing one rule at a time. Again, just like with the level 0 cache, the cache lookup happens by executing the rules.

Here also we run compiled code, but of a slightly different kind. This time they are individual delegates formed by the code pertinent to that one rule only. Good thing about those is that once the rule is created, this delegate never changes so we don't have to re-generate it on future Level 1 (and as we'll see, also level 2) cache lookups.

If we get level 1 cache hit, we update the Level 0 cache by including the rule we just found in the delegate and since we just performed the operation (remember, we executed the rule), we have result of the operation at hand so we are done and can go back to whatever the program was doing. The 'interrupt' (cache miss handling) is over.

Level 2

While level 0 and level 1 caches are stored on the dynamic site itself (as a delegate or as a read only list of rules respectively), the level 2 cache is bigger and is stored on the ActionBinder itself. Its purpose is to span many dynamic sites and allow for rule which was created by cache miss on one dynamic site to propagate to a different dynamic site, thus avoiding need to recreate the rule.

The level 2 cache lookup happens right beneath the Level 1 cache lookup. The code starts here:

//
// Look for applicable rules in the caches
//

Type[] argTypes = CompilerHelpers.GetTypes(args);
applicable = _ruleCache.FindApplicableRules<T>(site.Action, argTypes);

//
// Do we have rules? If so, run those
//

if (applicable != null) {
    count = applicable.Length;
    for (index = 0; index < count; index ++) {
        rule = applicable[index];

        ...

    }
}

Now that is awfully similar to the level 1 cache lookup, isn't it? Get list of applicable rules (granted, this time they come from _ruleCache - the Level 2 cache store), but other than that, we also iterate through the rules and ... no surprise ... execute them one by one until we find the match.

When we do find the match, we add the rule to the Level 1 cache and again, since we found the rule by executing it, the work has been done and we can return back to the program. Note that we don't regenerate the Level 0 cache in this case. There is good reason for it, but we'll talk about that in the future post.

Level 2 cache miss

If level 2 cache miss happens, we need to ask the language binder to create a new rule:

//
// No rule matched, we need to create one
//

for (; ; ) {

    rule = CreateNewRule<T>(context, site.Action, args);

    ...

}

Once the binder creates the new rule, we'll try to execute it. If all goes well we store the rule in the level 1 and 2 caches and since we already have the result of the operation (as we just executed the rule), we are done. However, it can happen that the rule we got from the language binder didn't work (due to an asynchronous update to the type system of the dynamic language that has invalidated the rule). If that happens, we try asking the language binder again...

Once we have matching rule, we store the rule in the caches, return the result and the program can continue executing until the next time it experiences a cache miss, and then we are back to square one (well, level 1 cache anyway).

For next time ...

In the future posts we'll explore:

  • Selection of rules from level 1 cache that form the level 0 cache delegate
  • Matchmakers (a mechanism we use for cache lookups)
  • Cache pruning
  • Changes in the Rule API
  • ...