From add54f1ae94f38ec842ab6810d5da2369d05422d Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Fri, 9 Jun 2017 12:00:58 +0200 Subject: [PATCH] Optimize ModuleDependencySort This class can use some love to improve its performance: - eliminate unneeded String.format() calls - perform revision formatting only when needed - streamline getModuleByNameAndRevision() to eliminate duplicate lookups and checks Change-Id: Iac88e223bb108110a9081ce0e6edcdd748d5b52a Signed-off-by: Robert Varga --- .../parser/util/ModuleDependencySort.java | 126 +++++++----------- 1 file changed, 51 insertions(+), 75 deletions(-) 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 ebf6fe278d..cf3045f9ce 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 @@ -8,15 +8,12 @@ package org.opendaylight.yangtools.yang.parser.util; import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.Function; import com.google.common.collect.Lists; -import com.google.common.collect.Maps; -import com.google.common.collect.Sets; import java.net.URI; import java.util.Arrays; -import java.util.Collection; import java.util.Date; import java.util.HashMap; +import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Objects; @@ -25,7 +22,6 @@ import org.opendaylight.yangtools.yang.common.SimpleDateFormatUtil; import org.opendaylight.yangtools.yang.common.YangVersion; import org.opendaylight.yangtools.yang.model.api.Module; import org.opendaylight.yangtools.yang.model.api.ModuleImport; -import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.Node; import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.NodeImpl; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -39,13 +35,7 @@ import org.slf4j.LoggerFactory; public final class ModuleDependencySort { private static final Date DEFAULT_REVISION = SimpleDateFormatUtil.DEFAULT_DATE_REV; - private static final Logger LOGGER = LoggerFactory.getLogger(ModuleDependencySort.class); - private static final Function TOPOLOGY_FUNCTION = input -> { - if (input == null) { - return null; - } - return ((ModuleNodeImpl) input).getReference(); - }; + private static final Logger LOG = LoggerFactory.getLogger(ModuleDependencySort.class); /** * It is not desirable to instance this class @@ -74,17 +64,15 @@ public final class ModuleDependencySort { public static List sort(final Iterable modules) { final List sorted = sortInternal(modules); // Cast to Module from Node and return - return Lists.transform(sorted, TOPOLOGY_FUNCTION); + return Lists.transform(sorted, input -> input == null ? null : ((ModuleNodeImpl) input).getReference()); } private static List sortInternal(final Iterable modules) { final Map> moduleGraph = createModuleGraph(modules); - final Set nodes = Sets.newHashSet(); + final Set nodes = new HashSet<>(); for (final Map map : moduleGraph.values()) { - for (final ModuleNodeImpl node : map.values()) { - nodes.add(node); - } + nodes.addAll(map.values()); } return TopologicalSort.sort(nodes); @@ -92,7 +80,7 @@ public final class ModuleDependencySort { @VisibleForTesting static Map> createModuleGraph(final Iterable builders) { - final Map> moduleGraph = Maps.newHashMap(); + final Map> moduleGraph = new HashMap<>(); processModules(moduleGraph, builders); processDependencies(moduleGraph, builders); @@ -109,30 +97,19 @@ public final class ModuleDependencySort { // Create edges in graph for (final Module module : mmbs) { - final Map imported = Maps.newHashMap(); - - String fromName; - Date fromRevision; - Collection imports; - URI ns; - - fromName = module.getName(); - fromRevision = module.getRevision(); - imports = module.getImports(); - ns = module.getNamespace(); + final Map imported = new HashMap<>(); + final String fromName = module.getName(); + final URI ns = module.getNamespace(); + Date fromRevision = module.getRevision(); // check for existence of module with same namespace - if (allNS.containsKey(ns)) { - final Module mod = allNS.get(ns); - final String name = mod.getName(); - final Date revision = mod.getRevision(); + final Module prev = allNS.putIfAbsent(ns, module); + if (prev != null) { + final String name = prev.getName(); if (!fromName.equals(name)) { - LOGGER.warn( - "Error while sorting module [{}, {}]: module with same namespace ({}) already loaded: [{}, {}]", - fromName, fromRevision, ns, name, revision); + LOG.warn("Error while sorting module [{}, {}]: module with same namespace ({}) already loaded:" + + " [{}, {}]", fromName, fromRevision, ns, name, prev.getRevision()); } - } else { - allNS.put(ns, module); } // no need to check if other Type of object, check is performed in @@ -142,7 +119,7 @@ public final class ModuleDependencySort { fromRevision = DEFAULT_REVISION; } - for (final ModuleImport imprt : imports) { + for (final ModuleImport imprt : module.getImports()) { final String toName = imprt.getModuleName(); final Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION : imprt.getRevision(); @@ -154,11 +131,14 @@ public final class ModuleDependencySort { * If it is an yang 1 module, check imports: If module is imported twice with different * revisions then throw exception */ - if (YangVersion.VERSION_1.toString().equals(module.getYangVersion()) && imported.get(toName) != null - && !imported.get(toName).equals(toRevision) && !imported.get(toName).equals(DEFAULT_REVISION) - && !toRevision.equals(DEFAULT_REVISION)) { - ex(String.format("Module:%s imported twice with different revisions:%s, %s", toName, - formatRevDate(imported.get(toName)), formatRevDate(toRevision))); + if (YangVersion.VERSION_1.toString().equals(module.getYangVersion())) { + final Date impRevision = imported.get(toName); + if (impRevision != null && !impRevision.equals(toRevision) + && !DEFAULT_REVISION.equals(impRevision) && !DEFAULT_REVISION.equals(toRevision)) { + throw new YangValidationException(String.format( + "Module:%s imported twice with different revisions:%s, %s", toName, + formatRevDate(impRevision), formatRevDate(toRevision))); + } } imported.put(toName, toRevision); @@ -173,33 +153,31 @@ public final class ModuleDependencySort { */ 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)) { - // If revision is not specified in import, but module exists - // with different revisions, take first - if (moduleGraph.get(toName) != null && !moduleGraph.get(toName).isEmpty() - && toRevision.equals(DEFAULT_REVISION)) { - to = moduleGraph.get(toName).values().iterator().next(); - LOGGER.trace(String - .format("Import:%s:%s by module:%s:%s does not specify revision, using:%s:%s for module dependency sort", - toName, formatRevDate(toRevision), fromName, formatRevDate(fromRevision), to.getName(), - formatRevDate(to.getRevision()))); - } else { - LOGGER.warn(String.format("Not existing module imported:%s:%s by:%s:%s", toName, - formatRevDate(toRevision), fromName, formatRevDate(fromRevision))); - LOGGER.warn("Available models: {}", moduleGraph); - ex(String.format("Not existing module imported:%s:%s by:%s:%s", toName, formatRevDate(toRevision), - fromName, formatRevDate(fromRevision))); + + final Map modulerevs = moduleGraph.get(toName); + if (modulerevs != null) { + final ModuleNodeImpl exact = modulerevs.get(toRevision); + if (exact != null) { + return exact; + } + + // If revision is not specified in import, but module exists with different revisions, take first one + if (DEFAULT_REVISION.equals(toRevision) && !modulerevs.isEmpty()) { + final ModuleNodeImpl first = modulerevs.values().iterator().next(); + if (LOG.isTraceEnabled()) { + LOG.trace("Import:{}:{} by module:{}:{} does not specify revision, using:{}:{}" + + " for module dependency sort", toName, formatRevDate(toRevision), fromName, + formatRevDate(fromRevision), first.getName(), formatRevDate(first.getRevision())); + } + return first; } - } else { - to = moduleGraph.get(toName).get(toRevision); } - return to; - } - private static void ex(final String message) { - throw new YangValidationException(message); + LOG.warn("Not existing module imported:{}:{} by:{}:{}", toName, formatRevDate(toRevision), fromName, + formatRevDate(fromRevision)); + LOG.warn("Available models: {}", moduleGraph); + throw new YangValidationException(String.format("Not existing module imported:%s:%s by:%s:%s", toName, + formatRevDate(toRevision), fromName, formatRevDate(fromRevision))); } /** @@ -218,15 +196,13 @@ public final class ModuleDependencySort { rev = DEFAULT_REVISION; } - if (moduleGraph.get(name) == null) { - moduleGraph.put(name, Maps.newHashMap()); - } - - if (moduleGraph.get(name).get(rev) != null) { - ex(String.format("Module:%s with revision:%s declared twice", name, formatRevDate(rev))); + final Map revs = moduleGraph.computeIfAbsent(name, key -> new HashMap<>(2)); + if (revs.containsKey(rev)) { + throw new YangValidationException(String.format("Module:%s with revision:%s declared twice", name, + formatRevDate(rev))); } - moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev, momb)); + revs.put(rev, new ModuleNodeImpl(name, rev, momb)); } } -- 2.36.6