From: Robert Varga Date: Thu, 17 Mar 2022 22:01:26 +0000 (+0100) Subject: Optimize AbstractCompositeRuntimeType storage X-Git-Tag: v9.0.0~4 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=mdsal.git;a=commitdiff_plain;h=72648dcb3a85ca7c49ca492cb54acd198cc1e0c9 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 --- 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 85ecec6148..2887813cf9 100644 --- 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> extends AbstractRuntimeType implements CompositeRuntimeType { + private static final RuntimeType[] EMPTY = new RuntimeType[0]; + private final ImmutableMap byClass; - private final ImmutableMap 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 children) { super(bindingType, statement); @@ -36,20 +43,44 @@ abstract class AbstractCompositeRuntimeType> .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.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> return byClass.get(requireNonNull(typeName)); } - final @NonNull ImmutableCollection schemaTreeChildren() { - return bySchemaTree.values(); + // Makes an assertion of all types being of specified type + @SuppressWarnings("unchecked") + final @NonNull List schemaTree(final Class 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) 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 e69bd390a3..3470b96f48 100644 --- 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 validCaseChildren() { - return (Collection) Collections2.filter(schemaTreeChildren(), CaseRuntimeType.class::isInstance); + public List 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 63fcb19bb3..b22a7e8dbc 100644 --- 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 validCaseChildren(); + @NonNull List validCaseChildren(); }