BUG-650: optimize subtree listener collection

[controller.git] / opendaylight / md-sal / sal-inmemory-datastore / src / main / java / org / opendaylight / controller / md / sal / dom / store / impl / ResolveDataChangeState.java

diff --git a/opendaylight/md-sal/sal-inmemory-datastore/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/ResolveDataChangeState.java b/opendaylight/md-sal/sal-inmemory-datastore/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/ResolveDataChangeState.java
index d3c5a7cb70e8013734f64619b456e74ed18ee0e2..e18b632275b88f51e713468f1bf1ca7de6c24dfb 100644 (file)
--- a/opendaylight/md-sal/sal-inmemory-datastore/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/ResolveDataChangeState.java
+++ b/opendaylight/md-sal/sal-inmemory-datastore/src/main/java/org/opendaylight/controller/md/sal/dom/store/impl/ResolveDataChangeState.java
@@ -47,16 +47,16 @@ final class ResolveDataChangeState {
     /**
      * Inherited from immediate parent
      */
-    private final Iterable<Builder> inheritedOne;
+    private final Collection<Builder> inheritedOne;
     private final YangInstanceIdentifier nodeId;
     private final Collection<Node> nodes;
 
-    private final Map<DataChangeListenerRegistration<?>, Builder> subBuilders = new HashMap<>();
-    private final Map<DataChangeListenerRegistration<?>, Builder> oneBuilders = new HashMap<>();
-    private final Map<DataChangeListenerRegistration<?>, Builder> baseBuilders = new HashMap<>();
+    private final Map<DataChangeListenerRegistration<?>, Builder> subBuilders;
+    private final Map<DataChangeListenerRegistration<?>, Builder> oneBuilders;
+    private final Map<DataChangeListenerRegistration<?>, Builder> baseBuilders;
 
     private ResolveDataChangeState(final YangInstanceIdentifier nodeId,
-            final Iterable<Builder> inheritedSub, final Iterable<Builder> inheritedOne,
+            final Iterable<Builder> inheritedSub, final Collection<Builder> inheritedOne,
             final Collection<Node> nodes) {
         this.nodeId = Preconditions.checkNotNull(nodeId);
         this.nodes = Preconditions.checkNotNull(nodes);
@@ -66,22 +66,36 @@ final class ResolveDataChangeState {
         /*
          * Collect the nodes which need to be propagated from us to the child.
          */
+        final Map<DataChangeListenerRegistration<?>, Builder> sub = new HashMap<>();
+        final Map<DataChangeListenerRegistration<?>, Builder> one = new HashMap<>();
+        final Map<DataChangeListenerRegistration<?>, Builder> base = new HashMap<>();
         for (Node n : nodes) {
             for (DataChangeListenerRegistration<?> l : n.getListeners()) {
                 final Builder b = DOMImmutableDataChangeEvent.builder(DataChangeScope.BASE);
                 switch (l.getScope()) {
                 case BASE:
-                    baseBuilders.put(l, b);
+                    base.put(l, b);
                     break;
                 case ONE:
-                    oneBuilders.put(l, b);
+                    one.put(l, b);
                     break;
                 case SUBTREE:
-                    subBuilders.put(l, b);
+                    sub.put(l, b);
                     break;
                 }
             }
         }
+
+        baseBuilders = maybeEmpty(base);
+        oneBuilders = maybeEmpty(one);
+        subBuilders = maybeEmpty(sub);
+    }
+
+    private static <K, V> Map<K, V> maybeEmpty(final Map<K, V> map) {
+        if (map.isEmpty()) {
+            return Collections.emptyMap();
+        }
+        return map;
     }
 
     /**
@@ -103,8 +117,38 @@ final class ResolveDataChangeState {
      * @return State handle
      */
     public ResolveDataChangeState child(final PathArgument childId) {
-        return new ResolveDataChangeState(nodeId.node(childId),
-            Iterables.concat(inheritedSub, subBuilders.values()),
+        /*
+         * We instantiate a concatenation only when needed:
+         *
+         * 1) If our collection is empty, we reuse the parent's. This is typically the case
+         *    for intermediate node, which should be the vast majority.
+         * 2) If the parent's iterable is a Collection and it is empty, reuse our collection.
+         *    This is the case for the first node which defines a subtree listener in a
+         *    particular subtree.
+         * 3) Concatenate the two collections. This happens when we already have some
+         *    subtree listeners and we encounter a node which adds a few more.
+         *
+         * This allows us to lower number of objects allocated and also
+         * speeds up Iterables.isEmpty() in needsProcessing().
+         *
+         * Note that the check for Collection in 2) relies on precisely this logic, which
+         * ensures that we simply cannot see an empty concatenation, but rather start off with
+         * an empty collection, then switch to a non-empty collection and finally switch to
+         * a concatenation. This saves us from instantiating iterators, which a trivial
+         * Iterables.isEmpty() would do as soon as we cross case 3).
+         */
+        final Iterable<Builder> sb;
+        if (!subBuilders.isEmpty()) {
+            if (inheritedSub instanceof Collection && ((Collection<?>) inheritedSub).isEmpty()) {
+                sb = subBuilders.values();
+            } else {
+                sb = Iterables.concat(inheritedSub, subBuilders.values());
+            }
+        } else {
+            sb = inheritedSub;
+        }
+
+        return new ResolveDataChangeState(nodeId.node(childId), sb,
             oneBuilders.values(), getListenerChildrenWildcarded(nodes, childId));
     }
 
@@ -127,12 +171,12 @@ final class ResolveDataChangeState {
         if (!nodes.isEmpty()) {
             return true;
         }
-        // Have SUBTREE listeners
-        if (!Iterables.isEmpty(inheritedSub)) {
+        // Have ONE listeners
+        if (!inheritedOne.isEmpty()) {
             return true;
         }
-        // Have ONE listeners
-        if (!Iterables.isEmpty(inheritedOne)) {
+        // Have SUBTREE listeners
+        if (!Iterables.isEmpty(inheritedSub)) {
             return true;
         }