From c0fe96104139bb605f200fbe84d8631729825561 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Fri, 23 May 2014 23:28:12 +0200 Subject: [PATCH] BUG-582: Optimize SchemaContextImpl.findModuleByNamespace() This is by far the hottest method, taking full 10 seconds from the startup. Optimizing it looks simple enough: just create a SetMultimap and precompute the URI->Module mappings. Change-Id: Icf9b42424a083f665911c5b3a8853c38662b1e87 Signed-off-by: Robert Varga --- .../yang/parser/impl/SchemaContextImpl.java | 72 ++++++++++++------- .../parser/util/ModuleDependencySort.java | 52 +++++++------- 2 files changed, 74 insertions(+), 50 deletions(-) diff --git a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/impl/SchemaContextImpl.java b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/impl/SchemaContextImpl.java index 6f81e7adaf..c689fa9011 100644 --- a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/impl/SchemaContextImpl.java +++ b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/impl/SchemaContextImpl.java @@ -7,7 +7,18 @@ */ package org.opendaylight.yangtools.yang.parser.impl; -import com.google.common.base.Optional; +import java.net.URI; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Date; +import java.util.HashSet; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.TreeMap; + import org.opendaylight.yangtools.yang.common.QName; import org.opendaylight.yangtools.yang.model.api.AugmentationSchema; import org.opendaylight.yangtools.yang.model.api.ConstraintDefinition; @@ -26,24 +37,39 @@ import org.opendaylight.yangtools.yang.model.api.UnknownSchemaNode; import org.opendaylight.yangtools.yang.model.api.UsesNode; import org.opendaylight.yangtools.yang.parser.util.ModuleDependencySort; -import java.net.URI; -import java.util.ArrayList; -import java.util.Collections; -import java.util.Date; -import java.util.HashSet; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; -import java.util.TreeMap; +import com.google.common.base.Optional; +import com.google.common.base.Supplier; +import com.google.common.collect.ImmutableSetMultimap; +import com.google.common.collect.Multimaps; +import com.google.common.collect.SetMultimap; final class SchemaContextImpl implements SchemaContext { - private final Set modules; + private static final Supplier> URI_SET_SUPPLIER = new Supplier>() { + @Override + public HashSet get() { + return new HashSet<>(); + } + }; + private final Map identifiersToSources; + private final SetMultimap namespaceToModules; + private final Set modules; - SchemaContextImpl(final Set modules, Map identifiersToSources) { + SchemaContextImpl(final Set modules, final Map identifiersToSources) { this.modules = modules; this.identifiersToSources = identifiersToSources; + + /* + * The most common lookup is from Namespace->Module. Invest some quality time in + * building that up. + */ + final SetMultimap multimap = Multimaps.newSetMultimap( + new TreeMap>(), URI_SET_SUPPLIER); + for (Module m : modules) { + multimap.put(m.getNamespace(), m); + } + + namespaceToModules = ImmutableSetMultimap.copyOf(multimap); } @Override @@ -57,6 +83,7 @@ final class SchemaContextImpl implements SchemaContext { @Override public Set getModules() { + // FIXME: can we pre-compute this in the constructor? List sorted = ModuleDependencySort.sort(modules.toArray(new Module[modules.size()])); return new LinkedHashSet(sorted); } @@ -106,19 +133,12 @@ final class SchemaContextImpl implements SchemaContext { @Override public Set findModuleByNamespace(final URI namespace) { - final Set ret = new HashSet(); - if (namespace != null) { - for (final Module module : modules) { - if (module.getNamespace().equals(namespace)) { - ret.add(module); - } - } - } - return ret; + final Set ret = namespaceToModules.get(namespace); + return ret == null ? Collections.emptySet() : ret; } @Override - public Module findModuleByNamespaceAndRevision(URI namespace, Date revision) { + public Module findModuleByNamespaceAndRevision(final URI namespace, final Date revision) { if (namespace != null) { Set modules = findModuleByNamespace(namespace); @@ -224,7 +244,7 @@ final class SchemaContextImpl implements SchemaContext { } @Override - public DataSchemaNode getDataChildByName(QName name) { + public DataSchemaNode getDataChildByName(final QName name) { DataSchemaNode result = null; for (Module module : modules) { result = module.getDataChildByName(name); @@ -236,7 +256,7 @@ final class SchemaContextImpl implements SchemaContext { } @Override - public DataSchemaNode getDataChildByName(String name) { + public DataSchemaNode getDataChildByName(final String name) { DataSchemaNode result = null; for (Module module : modules) { result = module.getDataChildByName(name); @@ -269,7 +289,7 @@ final class SchemaContextImpl implements SchemaContext { } @Override - public Optional getModuleSource(ModuleIdentifier moduleIdentifier) { + public Optional getModuleSource(final ModuleIdentifier moduleIdentifier) { String maybeSource = identifiersToSources.get(moduleIdentifier); return Optional.fromNullable(maybeSource); } diff --git a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java index 4c4b64a37c..ea304d4f10 100644 --- a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java +++ b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java @@ -51,31 +51,35 @@ public final class ModuleDependencySort { private ModuleDependencySort() { } + /** + * Extracts {@link ModuleBuilder} from a {@link ModuleNodeImpl}. + */ + private static final Function NODE_TO_MODULEBUILDER = new Function() { + @Override + public ModuleBuilder apply(final Node input) { + // Cast to ModuleBuilder from Node and return + return (ModuleBuilder) ((ModuleNodeImpl) input).getReference(); + } + }; + /** * Topological sort of module builder dependency graph. * * @return Sorted list of Module builders. Modules can be further processed * in returned order. */ - public static List sort(ModuleBuilder... builders) { + public static List sort(final ModuleBuilder... builders) { List sorted = sortInternal(Arrays.asList(builders)); - // Cast to ModuleBuilder from Node and return - return Lists.transform(sorted, new Function() { - - @Override - public ModuleBuilder apply(Node input) { - return (ModuleBuilder) ((ModuleNodeImpl) input).getReference(); - } - }); + return Lists.transform(sorted, NODE_TO_MODULEBUILDER); } - public static List sort(Collection builders) { + public static List sort(final Collection builders) { ModuleBuilder[] array = new ModuleBuilder[builders.size()]; builders.toArray(array); return sort(array); } - public static List sortWithContext(SchemaContext context, ModuleBuilder... builders) { + public static List sortWithContext(final SchemaContext context, final ModuleBuilder... builders) { List modules = new ArrayList(); Collections.addAll(modules, builders); modules.addAll(context.getModules()); @@ -85,7 +89,7 @@ public final class ModuleDependencySort { return Lists.transform(sorted, new Function() { @Override - public ModuleBuilder apply(Node input) { + public ModuleBuilder apply(final Node input) { if (((ModuleNodeImpl) input).getReference() instanceof ModuleBuilder) { return (ModuleBuilder) ((ModuleNodeImpl) input).getReference(); } else { @@ -101,19 +105,19 @@ public final class ModuleDependencySort { * @return Sorted list of Modules. Modules can be further processed in * returned order. */ - public static List sort(Module... modules) { + public static List sort(final Module... modules) { List sorted = sortInternal(Arrays.asList(modules)); // Cast to Module from Node and return return Lists.transform(sorted, new Function() { @Override - public Module apply(Node input) { + public Module apply(final Node input) { return (Module) ((ModuleNodeImpl) input).getReference(); } }); } - private static List sortInternal(List modules) { + private static List sortInternal(final List modules) { Map> moduleGraph = createModuleGraph(modules); Set nodes = Sets.newHashSet(); @@ -127,7 +131,7 @@ public final class ModuleDependencySort { } @VisibleForTesting - static Map> createModuleGraph(List builders) { + static Map> createModuleGraph(final List builders) { Map> moduleGraph = Maps.newHashMap(); processModules(moduleGraph, builders); @@ -139,7 +143,7 @@ public final class ModuleDependencySort { /** * Extract module:revision from module builders */ - private static void processDependencies(Map> moduleGraph, List builders) { + private static void processDependencies(final Map> moduleGraph, final List builders) { Map allNS = new HashMap<>(); // Create edges in graph @@ -219,8 +223,8 @@ public final class ModuleDependencySort { /** * Get imported module by its name and revision from moduleGraph */ - private static ModuleNodeImpl getModuleByNameAndRevision(Map> moduleGraph, - String fromName, Date fromRevision, String toName, Date toRevision) { + private static ModuleNodeImpl getModuleByNameAndRevision(final Map> moduleGraph, + final String fromName, final Date fromRevision, final String toName, final Date toRevision) { ModuleNodeImpl to = null; if (moduleGraph.get(toName) == null || !moduleGraph.get(toName).containsKey(toRevision)) { @@ -246,7 +250,7 @@ public final class ModuleDependencySort { return to; } - private static void ex(String message) { + private static void ex(final String message) { throw new YangValidationException(message); } @@ -254,7 +258,7 @@ public final class ModuleDependencySort { * Extract dependencies from module builders or modules to fill dependency * graph */ - private static void processModules(Map> moduleGraph, List builders) { + private static void processModules(final Map> moduleGraph, final List builders) { // Process nodes for (Object mb : builders) { @@ -290,7 +294,7 @@ public final class ModuleDependencySort { } } - private static String formatRevDate(Date rev) { + private static String formatRevDate(final Date rev) { return rev.equals(DEFAULT_REVISION) ? "default" : new SimpleDateFormat("yyyy-MM-dd").format(rev); } @@ -300,7 +304,7 @@ public final class ModuleDependencySort { private final Date revision; private final Object originalObject; - public ModuleNodeImpl(String name, Date revision, Object builder) { + public ModuleNodeImpl(final String name, final Date revision, final Object builder) { this.name = name; this.revision = revision; this.originalObject = builder; @@ -324,7 +328,7 @@ public final class ModuleDependencySort { } @Override - public boolean equals(Object obj) { + public boolean equals(final Object obj) { if (this == obj) { return true; } -- 2.36.6