Bug 490149

Description Stefan Xenos 2016-03-21 22:48:32 EDT

This is a proposal for a new change processing algorithm for Eclipse Databinding.

Problems in Eclipse Databinding:

- It is currently susceptible to performance degradation when there are multiple paths to the same observable. One representative pattern where performance degrades is the repeated diamond shape, where performance degrades to O(2^r) for r repetitions.

- It performs a lot of memory allocation during change processing.

- Some observables fire change events even though they haven't changed.

- Some observables recompute the observable eagerly in order to suppress redundant change notifications, but as a consequence recompute the observable once every time an input changes, which much more often than their dependencies would care about such changes.

- Calling getters or processing change events hits a lot of memory barriers and performs unnecessary thread synchronization due to heavy use of thread locals.

- All Observables currently leak memory unless they are explicitly disposed. However, internal nodes - like ComputedValue - could support disposal as an optional operation and could clean themselves up automatically once there are no further incoming references. This would simplify the programming model.


This proposal should address all these issues.

How it works:

All the ThreadLocals in ObservableTracker will become private attributes of Realm. Each Realm is associated with a thread, so the end effect is the same (actually, the functionality of the existing threadlocals will be preserved but they will be represented differently, as described below.)

Each Realm will get a DependencyGraph. DependencyGraph looks like this:

class DependencyGraph {
  long tickCounter;
  WeakKeyMap<Object, DataBindingNode> mapObservableOrSideEffectOntoDataBindingNode;
}

class DataBindingNode {
  // Time at which the node was last visited to determine if it changed.
  long tickLastVisited = -1;
  // Time at which the node was last known to be changed.
  long tickLastChanged = -1;
  // True iff the node is scheduled to be re-evaluated on the next tick.
  boolean dirty = true;
  // True iff the node will never fire another change event
  boolean isInvariant = false;
  // True iff this node is currently being recomputed
  boolean isComputing = false;
  // True iff this node needs to be visited on the next update pass
  boolean scheduledForUpdate = false;
  // List of nodes which depend upon this node (weak references)
  WeakSet<DataBindingNode> dependents;
  // Keys are nodes which this node depends on (strong references). Values have two states: 
  // "Used" or "Unused"
  HashMap<DataBindingNode, NodeState> dependencies
}


Operations on DataBindingNode:

getTickOfLastChange() {
  Recomputes the node if necessary then return tickLastChanged.
}

getTickOfLastChangedDependency() {
  find the maximum of the getTickOfLastChanged among all dependencies
}

recomputeIfNecessary() {
  Throws an exception if isComputing is true when invoked (this represents a circular dependency)
  if (dirty or graph.tickCounter > tickLastVisited) {
    dirty = false
    
    if (dirty || getTickOfLastChangedDependency() > tickLastVisited) {
      set isComputing to true, so we can detect recursion
      set all dependencies to the "Unused" state
      boolean changed = recompute()
      search through all dependencies and delete any that are still in the "Unused" state. Remove
      "this" as a dependent at the same time. Use copy-on-write to avoid creating a CME.
      set isComputing back to false
    }

    if (changed) {
      tickLastChanged = graph.tickCounter;
    }
  }
  tickLastVisited = graph.tickCounter
}

markDirty() {
  dirty = true;
  do nothing if this node is already scheduled for validation
  this.scheduledForUpdate = true
  
  schedule this node for processing on the next update if it hasn't already been done. Then recursively iterate over all of its dependents and schedule them, too.

  if graph.tickCounter == this.tickLastVisited then increment graph.tickCounter
  
  add this node (but not its dependents) to a queue in the dependency graph for validation on the next
  update pass.

  The dependency graph should schedule its own update() method to run asynchronously at the earliest opportunity.
}

// This is invoked asynchronously during an update pass on all nodes that were explicitly marked as dirty
update() {
  if (this node has public listeners attached or is an ISideEffect) {
    recomputeIfNecessary();
  }
  scheduledForUpdate = false;
  recursively call update() on all dependents
}



There would be different recompute() methods for different observable types. For SettableValue, it would look like this:

bool WritableValueNode.recompute() {
  Object oldValue = currentValue;
  this.currentValue = newValue;

  return (!Objects.equal(oldValue, newValue);
}

WritableValue.getValue() would look something like this:

getValue() {
  getterCalled();
  myDataBindingNode.recomputeIfNecessary();
  return currentValue;
}

...and WritableValue.setValue(...) would look like:

setValue(T newValue) {
  this.newValue = newValue;
  myDataBindingNode.markDirty();
}

There would be three types of ReactiveNodes -- for WritableValue, ComputedValue, and SideEffect. All other observable types would be reimplemented behind the scenes using some combination of the above, and none of them would attach listeners to one another.


The dependency graph itself has an update() method. It is scheduled to run asynchronously whenever anything in the graph is marked as dirty. It looks like this:

update() {
  for every node in update queue (the queue that was filled in by markDirty), call update() on that node.
  clear the update queue
}

The implementation of runAndMonitor would change. Rather than remembering a bunch of threadlocals, it only needs to remember the current DataBindingNode. When someone invokes getterCalled, it finds the matching DataBindingNode and connects the two nodes as a dependent/dependency. Dependencies are a map. The newly-discovered dependency is set always set to the "Used" state.