Optimize AbstractCompositeRuntimeType storage

Storage on schema tree does not allow for duplicates. Rather than
allocating a full Map, let's use arrays and associated binary search.
This allows us to drop the storage requirements, especially for choices,
which would end up allocating an object to contain Map.values()
representation.

This results in O(log2(N)) lookups instead of O(1), plus some additional
code, but the lookups are one-off and so well worth the reduced
footprint. A further improvement is that we relax type safety down to
Object, which allows us to not allocate singleton arrays.

Change-Id: Ice6f07a7f853bd68c614a42eda6cc1d3fd2c184e
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/AbstractCompositeRuntimeType.java b/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/AbstractCompositeRuntimeType.java
index 85ecec6148b4279d5a04ee97cda338b8ae2ca89b..2887813cf96bea200ad2fea89dc137ea1dd4d8dc 100644 (file)
--- a/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/AbstractCompositeRuntimeType.java
+++ b/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/AbstractCompositeRuntimeType.java
@@ -7,11 +7,14 @@
  */
 package org.opendaylight.mdsal.binding.generator.impl.rt;
 
+import static com.google.common.base.Verify.verify;
 import static java.util.Objects.requireNonNull;
 
 import com.google.common.base.Functions;
-import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableMap;
+import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
+import java.util.Arrays;
+import java.util.Collections;
 import java.util.List;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.mdsal.binding.model.api.GeneratedType;
@@ -25,9 +28,13 @@ import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeEffectiveStateme
 
 abstract class AbstractCompositeRuntimeType<S extends EffectiveStatement<?, ?>>
         extends AbstractRuntimeType<S, GeneratedType> implements CompositeRuntimeType {
+    private static final RuntimeType[] EMPTY = new RuntimeType[0];
+
     private final ImmutableMap<JavaTypeName, GeneratedRuntimeType> byClass;
-    private final ImmutableMap<QName, RuntimeType> bySchemaTree;
+    private final Object bySchemaTree;
 
+    @SuppressFBWarnings(value = "SE_COMPARATOR_SHOULD_BE_SERIALIZABLE",
+        justification = "https://github.com/spotbugs/spotbugs/issues/1985")
     AbstractCompositeRuntimeType(final GeneratedType bindingType, final S statement, final List<RuntimeType> children) {
         super(bindingType, statement);
 
@@ -36,20 +43,44 @@ abstract class AbstractCompositeRuntimeType<S extends EffectiveStatement<?, ?>>
             .map(GeneratedRuntimeType.class::cast)
             .collect(ImmutableMap.toImmutableMap(GeneratedRuntimeType::getIdentifier, Functions.identity()));
 
-        // Note: this may be over-sized, but we typically deal with schema tree statements, hence it is kind of accurate
-        final var builder = ImmutableMap.<QName, RuntimeType>builderWithExpectedSize(children.size());
-        for (var child : children) {
-            final var stmt = child.statement();
-            if (stmt instanceof SchemaTreeEffectiveStatement) {
-                builder.put(((SchemaTreeEffectiveStatement<?>)stmt).argument(), child);
-            }
+        final var tmp = children.stream()
+            .filter(child -> child.statement() instanceof SchemaTreeEffectiveStatement)
+            .toArray(RuntimeType[]::new);
+        switch (tmp.length) {
+            case 0:
+                bySchemaTree = EMPTY;
+                break;
+            case 1:
+                bySchemaTree = tmp[0];
+                break;
+            default:
+                Arrays.sort(tmp, (o1, o2) -> {
+                    final int cmp = extractQName(o1).compareTo(extractQName(o2));
+                    verify(cmp != 0, "Type %s conflicts with %s on schema tree", o1, o2);
+                    return cmp;
+                });
+                bySchemaTree = tmp;
         }
-        bySchemaTree = builder.build();
     }
 
     @Override
     public final RuntimeType schemaTreeChild(final QName qname) {
-        return bySchemaTree.get(requireNonNull(qname));
+        if (bySchemaTree instanceof RuntimeType) {
+            final var tmp = (RuntimeType) bySchemaTree;
+            return qname.equals(tmp.statement().argument()) ? tmp : null;
+        }
+
+        final var tmp = (RuntimeType[]) bySchemaTree;
+        @SuppressFBWarnings(value = "SE_COMPARATOR_SHOULD_BE_SERIALIZABLE",
+            justification = "https://github.com/spotbugs/spotbugs/issues/1985")
+        final int offset = Arrays.binarySearch(tmp, null, (o1, o2) -> {
+            // We make assumptions about how Arrays.binarySearch() is implemented: o2 is expected to be the provided
+            // key -- which is null. This helps CHA by not introducing a fake RuntimeType class and the
+            // corresponding instanceof checks.
+            verify(o2 == null, "Unexpected key %s", o2);
+            return extractQName(o1).compareTo(qname);
+        });
+        return offset < 0 ? null : tmp[offset];
     }
 
     @Override
@@ -57,7 +88,23 @@ abstract class AbstractCompositeRuntimeType<S extends EffectiveStatement<?, ?>>
         return byClass.get(requireNonNull(typeName));
     }
 
-    final @NonNull ImmutableCollection<RuntimeType> schemaTreeChildren() {
-        return bySchemaTree.values();
+    // Makes an assertion of all types being of specified type
+    @SuppressWarnings("unchecked")
+    final <T extends RuntimeType> @NonNull List<T> schemaTree(final Class<T> expectedType) {
+        if (expectedType.isInstance(bySchemaTree)) {
+            return List.of(expectedType.cast(bySchemaTree));
+        }
+
+        final var tmp = (RuntimeType[]) bySchemaTree;
+        for (var item : tmp) {
+            verify(expectedType.isInstance(item), "Unexpected schema tree child %s", item);
+        }
+        return (List<T>) Collections.unmodifiableList(Arrays.asList(tmp));
+    }
+
+    private static @NonNull QName extractQName(final RuntimeType type) {
+        final var stmt = type.statement();
+        verify(stmt instanceof SchemaTreeEffectiveStatement, "Unexpected statement %s in %s", stmt, type);
+        return ((SchemaTreeEffectiveStatement<?>) stmt).argument();
     }
-}
+}
\ No newline at end of file

diff --git a/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/DefaultChoiceRuntimeType.java b/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/DefaultChoiceRuntimeType.java
index e69bd390a3136e2c4586e843bd00369b4d47fad4..3470b96f489b3fa923f7152682c9e8a121662b3a 100644 (file)
--- a/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/DefaultChoiceRuntimeType.java
+++ b/binding/mdsal-binding-generator/src/main/java/org/opendaylight/mdsal/binding/generator/impl/rt/DefaultChoiceRuntimeType.java
@@ -8,8 +8,6 @@
 package org.opendaylight.mdsal.binding.generator.impl.rt;
 
 import com.google.common.annotations.Beta;
-import com.google.common.collect.Collections2;
-import java.util.Collection;
 import java.util.List;
 import org.opendaylight.mdsal.binding.model.api.GeneratedType;
 import org.opendaylight.mdsal.binding.model.api.JavaTypeName;
@@ -27,8 +25,8 @@ public final class DefaultChoiceRuntimeType extends AbstractCompositeRuntimeType
     }
 
     @Override
-    public Collection<CaseRuntimeType> validCaseChildren() {
-        return (Collection) Collections2.filter(schemaTreeChildren(), CaseRuntimeType.class::isInstance);
+    public List<CaseRuntimeType> validCaseChildren() {
+        return schemaTree(CaseRuntimeType.class);
     }
 
     @Override

diff --git a/binding/mdsal-binding-runtime-api/src/main/java/org/opendaylight/mdsal/binding/runtime/api/ChoiceRuntimeType.java b/binding/mdsal-binding-runtime-api/src/main/java/org/opendaylight/mdsal/binding/runtime/api/ChoiceRuntimeType.java
index 63fcb19bb32b8152b7f92896f9c8b2b034629d58..b22a7e8dbc61b2f10adb9f3730011f3babbf7d8d 100644 (file)
--- a/binding/mdsal-binding-runtime-api/src/main/java/org/opendaylight/mdsal/binding/runtime/api/ChoiceRuntimeType.java
+++ b/binding/mdsal-binding-runtime-api/src/main/java/org/opendaylight/mdsal/binding/runtime/api/ChoiceRuntimeType.java
@@ -8,7 +8,7 @@
 package org.opendaylight.mdsal.binding.runtime.api;
 
 import com.google.common.annotations.Beta;
-import java.util.Collection;
+import java.util.List;
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
 import org.opendaylight.mdsal.binding.model.api.JavaTypeName;
@@ -38,5 +38,5 @@ public interface ChoiceRuntimeType extends CompositeRuntimeType, DataRuntimeType
      *
      * @return Valid {@link CaseRuntimeType}s
      */
-    @NonNull Collection<CaseRuntimeType> validCaseChildren();
+    @NonNull List<CaseRuntimeType> validCaseChildren();
 }