More intelligent stratification

[neilconway]

We currently place temporal rules (<+, <-, <~) in the final stratum. This is not unnecessary: it should be sufficient to just follow the normal stratification logic for such rules. In the new runtime, pushing rules into higher strata unnecessarily comes at an additional performance cost because it triggers the accumulate_tick_deltas logic.

[sriram-srinivasan]

The design is indeed as you suggest: the temporal operator does not dictate the stratum, and the results are temporally stratified anyway because of the queues into which the tuples are merged (pending_adds/deletes etc.)

However, one can't avoid the notion of two different kinds of deltas: there is \delta, accumulated during one fixpoint iteration, and \Delta, which we call tick_delta, which is all the small \deltas put together. The former is used in recursive rules to identify the new tuples from that iteration, and the latter is used by all dependent rules downstream to identify all tuples introduced in the source collection since the last tick. Clearly, this distinction needs to be made only for collections under recursion.

[neilconway]

The design is not as I suggest: rules with temporal operators are placed into an extra additional stratum (see bud_meta.rb circa line 25). I'm suggesting we get rid of that special case and stop treating temporal rules specially with respect to stratification.

A further improvement is possible: we can evaluate a rule as soon as we know that all of its dependencies (body relations and their transitive dependencies) will not shrink for the remainder of the tick. If there are two rules with relation r in the lhs, we currently place both rules in the maximum of the strata required for either rule independently. We could improve this by placing the two rules in different strata, according to their respective dependencies.

[sriram-srinivasan]

The design is not as I suggest: rules with temporal operators are placed into an extra additional stratum (see bud_meta.rb circa line 25). I'm suggesting we get rid of that special case and stop treating temporal rules specially with respect to stratification.

Sorry, I wasn't clear. I meant to say that the new design is as you suggest. I agree with you that we give special treatment to temporal ops in the present incarnation of bud, but isn't that way in the evolving runtime.

A further improvement is possible: we can evaluate a rule as soon as we know that all of its dependencies (body relations and their transitive dependencies) will not shrink for the remainder of the tick. If there are two rules with relation r in the lhs, we currently place both rules in the maximum of the strata required for either rule independently. We could improve this by placing the two rules in different strata, according to their respective dependencies.

I thought about it, and I have avoided it doing this way for the following reasons. Since the head relations are where the updates happen, they are potential concurrent hotspots when we start evaluation in parallel. Evaluating all rules with the same head in a single thread is a simple way to eliminate write contention. Since collections are topologically ordered, and all code to do with a particular head is bunched together, it is cache-friendly. It also simplifies the generated code (two threads don't have to worry about whether a head is being rebuilt after negation), permits deterministic scheduling, which is good for debuggability and maintainability.

[neilconway]

Re: new runtime design, ah -- makes sense :)

Re: tweaking stratification, those are fair points (although I don't see the connection between the more conservative stratification approach and deterministic scheduling). Counter-points:

• More aggressive stratification (evaluating rules "early" when possible as I suggested) allows more work to be done earlier by eliminating needless waiting, which might improve efficiency.
• If the goal is to eliminate write contention, you can just evaluate all rules in a given stratum with the same head in a single thread -- i.e., I'm not sure the situation is too different.
• If we're serious about enabling efficient parallel evaluation, there is likely a ton more work to do; this issue might be in the noise anyway. e.g., the best approach might be picking a stratification that (a) is legal (b) is predicted to match the available machine resources (e.g., try to run four separate rule "partitions" in each stratum if the machine has four cores).

[neilconway]

Note that this is partially fixed in 92771a276c4592af2c2b46e4539d0612f21350c7 -- not the temporal operator behavior, but we now assign a rule to the lowest legal strata based on the rule's body relations.