prepack icon indicating copy to clipboard operation
prepack copied to clipboard

[Performance] Implement dependency tracking in visitor fixpoint computation

Open NTillmann opened this issue 6 years ago • 0 comments

In the ResidualHeapVisitor, there an interesting function called _enqueueWithUnrelatedScope. It really serves two purposes:

  1. Enqueueing an item to be processed in an (unrelated) scope, for which certain effects need to be applied which might not currently be applied.
  2. The processing of the item may be conditional on whether a particular value already was visited, and returning a Boolean indicating whether the item has processed everything it could possibly processes, or if it's still waiting on any particular values to be visited first (in which case it will have re-enqueued a new work item).

Then _visitUntilFixpoint takes those enqueued items, processes them all, checks if any of them made progress, and if so, repeat... Until no more progress is made.

Applying effects is expensive, so that's something to be minimized. A major inefficiency of the current fixpoint computation scheme is that it keeps reconsidering every single enqueued item.

Really, what should happen is that enqueueing an item presents a list of "dependencies", i.e. values that it might check whether they have been visited in the meantime. Only when such a value actually does get visited, then the whole applying-effects and re-running the item code needs to kick in.

(Dependencies can include other things besides values. In particular, whether bindings were visited, and there might be more. All conditions that guard re-queuing needs to be carefully inspected.)

To validate whether only declared dependencies are checked for, the function that process an item should not be allowed to directly call this.values.has (in fact, this.values should probably be renamed to this._values as part of the change), and instead go through a supplied helper function that blows up (fails an invariant) if a value is checked that wasn't a declared dependency.

NTillmann avatar Jun 11 '18 22:06 NTillmann