This is an automated email from the ASF dual-hosted git repository. gnodet pushed a commit to branch gnodet/conflict-resolver-memory-improvements in repository https://gitbox.apache.org/repos/asf/maven-resolver.git
commit 7db826a7c17c247eedf50bb1509bc8b175509486 Author: Guillaume Nodet <[email protected]> AuthorDate: Sun Jun 28 06:59:50 2026 +0000 Reduce PathConflictResolver memory and auto-select resolver Three improvements to reduce OOM risk on large dependency graphs: 1. Auto-selection heuristic (new default): estimates Path tree memory cost from the conflict-ID map size and falls back to ClassicConflictResolver if the parallel tree would exceed 25% of available heap. 2. Lazy right-sized children lists: Path.children starts as null (not an empty ArrayList) and is initialized to exactly the right capacity in addChildren(). Leaves (~60-70% of nodes) never allocate a list, saving ~40 bytes per leaf. 3. outOfScope flag replaces LinkedHashSet partition entries: moveOutOfScope() sets a boolean instead of removing from a LinkedHashSet, eliminating the HashMap.Node overhead (~48 bytes per Path). Active paths are filtered at query time with a simple boolean check. Co-Authored-By: Claude Opus 4.6 <[email protected]> --- .../util/graph/transformer/ConflictResolver.java | 50 +++++++- .../graph/transformer/PathConflictResolver.java | 131 +++++++++++++-------- 2 files changed, 127 insertions(+), 54 deletions(-) diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/ConflictResolver.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/ConflictResolver.java index 0b7df0856..0b3bdec54 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/ConflictResolver.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/ConflictResolver.java @@ -20,6 +20,7 @@ package org.eclipse.aether.util.graph.transformer; import java.util.Arrays; import java.util.Collection; +import java.util.Map; import org.eclipse.aether.ConfigurationProperties; import org.eclipse.aether.RepositoryException; @@ -129,7 +130,11 @@ public class ConflictResolver implements DependencyGraphTransformer { public static final String CONFIG_PROP_VERBOSE = ConfigurationProperties.PREFIX_AETHER + "conflictResolver.verbose"; /** - * The name of the conflict resolver implementation to use: "path" (default) or "classic" (same as Maven 3). + * The name of the conflict resolver implementation to use: "auto" (default), "path", or "classic" (same as Maven 3). + * <p> + * When set to "auto", the resolver estimates whether the Path tree would fit in available heap memory. + * If it would consume more than 25% of available heap, the classic (in-place) resolver is used instead + * to avoid OutOfMemoryErrors on very large dependency graphs. * * @since 2.0.11 * @configurationSource {@link RepositorySystemSession#getConfigProperties()} @@ -141,8 +146,9 @@ public class ConflictResolver implements DependencyGraphTransformer { public static final String CLASSIC_CONFLICT_RESOLVER = "classic"; public static final String PATH_CONFLICT_RESOLVER = "path"; + public static final String AUTO_CONFLICT_RESOLVER = "auto"; - public static final String DEFAULT_CONFLICT_RESOLVER_IMPL = PATH_CONFLICT_RESOLVER; + public static final String DEFAULT_CONFLICT_RESOLVER_IMPL = AUTO_CONFLICT_RESOLVER; /** * The enum representing verbosity levels of conflict resolver. @@ -258,22 +264,58 @@ public class ConflictResolver implements DependencyGraphTransformer { } @Override + @SuppressWarnings("unchecked") public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context) throws RepositoryException { String cf = ConfigUtils.getString( context.getSession(), DEFAULT_CONFLICT_RESOLVER_IMPL, CONFIG_PROP_CONFLICT_RESOLVER_IMPL); ConflictResolver delegate; - if (PATH_CONFLICT_RESOLVER.equals(cf)) { + if (AUTO_CONFLICT_RESOLVER.equals(cf)) { + delegate = selectConflictResolver(node, context); + } else if (PATH_CONFLICT_RESOLVER.equals(cf)) { delegate = new PathConflictResolver(versionSelector, scopeSelector, optionalitySelector, scopeDeriver); } else if (CLASSIC_CONFLICT_RESOLVER.equals(cf)) { delegate = new ClassicConflictResolver(versionSelector, scopeSelector, optionalitySelector, scopeDeriver); } else { throw new IllegalArgumentException("Unknown conflict resolver: " + cf + "; known are " - + Arrays.asList(PATH_CONFLICT_RESOLVER, CLASSIC_CONFLICT_RESOLVER)); + + Arrays.asList(AUTO_CONFLICT_RESOLVER, PATH_CONFLICT_RESOLVER, CLASSIC_CONFLICT_RESOLVER)); } return delegate.transformGraph(node, context); } + /** + * Selects the most appropriate conflict resolver based on graph size and available memory. + * <p> + * PathConflictResolver builds a parallel tree of Path objects that costs ~200 bytes per node. + * For very large dependency graphs (millions of nodes), this can exhaust the heap. + * In such cases, ClassicConflictResolver is used instead — it works in-place with no parallel + * structure, trading O(N²) worst-case time for O(1) extra space. + */ + @SuppressWarnings("unchecked") + private ConflictResolver selectConflictResolver(DependencyNode node, DependencyGraphTransformationContext context) + throws RepositoryException { + // Ensure conflict IDs are computed — both implementations need this anyway + if (context.get(TransformationContextKeys.SORTED_CONFLICT_IDS) == null) { + new ConflictIdSorter().transformGraph(node, context); + } + + Map<DependencyNode, String> conflictIds = + (Map<DependencyNode, String>) context.get(TransformationContextKeys.CONFLICT_IDS); + int nodeCount = conflictIds != null ? conflictIds.size() : 0; + + // Estimate Path tree memory: ~200 bytes per Path (object + right-sized children list + partition entry) + long pathTreeEstimate = (long) nodeCount * 200; + Runtime rt = Runtime.getRuntime(); + long available = rt.maxMemory() - (rt.totalMemory() - rt.freeMemory()); + + // Use PathConflictResolver only if the parallel tree fits within 25% of available heap + if (pathTreeEstimate < available / 4) { + return new PathConflictResolver(versionSelector, scopeSelector, optionalitySelector, scopeDeriver); + } else { + return new ClassicConflictResolver(versionSelector, scopeSelector, optionalitySelector, scopeDeriver); + } + } + /** * A context used to hold information that is relevant for deriving the scope of a child dependency. * diff --git a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java index 20b1b6f9a..3e9dfff7d 100644 --- a/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java +++ b/maven-resolver-util/src/main/java/org/eclipse/aether/util/graph/transformer/PathConflictResolver.java @@ -22,12 +22,9 @@ import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.HashMap; -import java.util.LinkedHashSet; import java.util.List; import java.util.Map; import java.util.Objects; -import java.util.Set; -import java.util.stream.Collectors; import org.eclipse.aether.ConfigurationProperties; import org.eclipse.aether.RepositoryException; @@ -174,24 +171,28 @@ public final class PathConflictResolver extends ConflictResolver { // loop over topographically sorted conflictIds for (String conflictId : sortedConflictIds) { - // paths in given conflict group to consider - Set<Path> paths = state.partitions.get(conflictId); - if (paths.isEmpty()) { + // paths in given conflict group to consider; filter out those moved out of scope + List<Path> allPaths = state.partitions.get(conflictId); + List<Path> activePaths = new ArrayList<>(); + List<ConflictItem> items = new ArrayList<>(); + for (Path p : allPaths) { + if (!p.outOfScope) { + activePaths.add(p); + items.add(new ConflictItem(p)); + } + } + if (activePaths.isEmpty()) { // this means that whole group "fall out of scope" (are all on loser branches); skip continue; } // create conflict context for given conflictId - ConflictContext ctx = new ConflictContext( - node, - state.conflictIds, - paths.stream().map(ConflictItem::new).collect(Collectors.toList()), - conflictId); + ConflictContext ctx = new ConflictContext(node, state.conflictIds, items, conflictId); // select winner (is done by VersionSelector) state.versionSelector.selectVersion(ctx); if (ctx.winner == null) { - throw new RepositoryException("conflict resolver did not select winner among " + ctx.items); + throw new RepositoryException("conflict resolver did not select winner among " + items); } // select scope (no side effect between this and above operations) state.scopeSelector.selectScope(ctx); @@ -208,8 +209,8 @@ public final class PathConflictResolver extends ConflictResolver { } state.resolvedIds.put(conflictId, winnerPath); - // loop over considered paths and apply selection results; note: node may remove itself from iterated set - for (Path path : new ArrayList<>(paths)) { + // loop over considered paths and apply selection results + for (Path path : activePaths) { // apply selected properties scope/optional to winner (winner carries version; others are losers) if (path == winnerPath) { path.scope = ctx.scope; @@ -217,7 +218,11 @@ public final class PathConflictResolver extends ConflictResolver { } // reset children as inheritance may be affected by this node scope/optionality change - path.children.forEach(c -> c.pull(0)); + if (path.children != null) { + for (Path c : path.children) { + c.pull(0); + } + } // derive with new values from this to children only; observe winner flag path.derive(1, path == winnerPath); // push this node full level changes to DN graph @@ -228,9 +233,15 @@ public final class PathConflictResolver extends ConflictResolver { if (stats != null) { long time2 = System.nanoTime(); stats.put("ConflictResolver.totalTime", time2 - time1); - stats.put( - "ConflictResolver.conflictItemCount", - state.partitions.values().stream().map(Set::size).reduce(0, Integer::sum)); + int conflictItemCount = 0; + for (List<Path> paths : state.partitions.values()) { + for (Path p : paths) { + if (!p.outOfScope) { + conflictItemCount++; + } + } + } + stats.put("ConflictResolver.conflictItemCount", conflictItemCount); } return node; @@ -279,9 +290,10 @@ public final class PathConflictResolver extends ConflictResolver { /** * A mapping from conflictId to paths represented as {@link Path}s that exist for each conflictId. In other * words all paths to each {@link DependencyNode} that are member of same conflictId group. - * Uses {@link LinkedHashSet} for O(1) removal in {@link Path#moveOutOfScope()} while preserving insertion order. + * Uses {@link ArrayList} per partition; out-of-scope paths are marked via {@link Path#outOfScope} flag + * and filtered at query time, avoiding the per-entry overhead of LinkedHashSet/HashMap.Node. */ - private final Map<String, Set<Path>> partitions; + private final Map<String, List<Path>> partitions; /** * A mapping from conflictIds to winner {@link Path}, hence {@link DependencyNode} for given conflictId. @@ -379,10 +391,15 @@ public final class PathConflictResolver extends ConflictResolver { private final Path parent; // derived private final int depth; - private final List<Path> children; + // Lazy: null for leaf nodes (never populated by addChildren), right-sized for non-leaves. + // This avoids allocating an ArrayList + backing array for every leaf node in the tree + // (typically 60-70% of all nodes), saving ~40 bytes per leaf. + private List<Path> children; // mutated private String scope; private boolean optional; + // Flag used instead of removing from partition sets; avoids LinkedHashSet overhead (~48 bytes/entry) + private boolean outOfScope; private Path(State state, DependencyNode dn, String conflictId, Path parent) { this.state = state; @@ -390,12 +407,11 @@ public final class PathConflictResolver extends ConflictResolver { this.conflictId = conflictId; this.parent = parent; this.depth = parent != null ? parent.depth + 1 : 0; - this.children = new ArrayList<>(); pull(0); this.state .partitions - .computeIfAbsent(this.conflictId, k -> new LinkedHashSet<>()) + .computeIfAbsent(this.conflictId, k -> new ArrayList<>()) .add(this); } @@ -429,7 +445,7 @@ public final class PathConflictResolver extends ConflictResolver { this.optional = false; } int newLevels = levels - 1; - if (newLevels >= 0) { + if (newLevels >= 0 && this.children != null) { for (Path child : this.children) { child.pull(newLevels); } @@ -459,8 +475,8 @@ public final class PathConflictResolver extends ConflictResolver { } } int newLevels = levels - 1; - if (newLevels >= 0) { - for (Path child : children) { + if (newLevels >= 0 && this.children != null) { + for (Path child : this.children) { child.derive(newLevels, false); } } @@ -503,10 +519,12 @@ public final class PathConflictResolver extends ConflictResolver { switch (state.verbosity) { case NONE: // remove loser dn - this.parent.children.remove(this); + if (this.parent.children != null) { + this.parent.children.remove(this); + } this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren())); this.parent.dn.getChildren().remove(this.dn); - this.children.clear(); + this.children = null; break; case STANDARD: String artifactId = ArtifactIdUtils.toId(this.dn.getArtifact()); @@ -522,10 +540,12 @@ public final class PathConflictResolver extends ConflictResolver { } if (isRedundant) { // is redundant dn; remove dn - this.parent.children.remove(this); + if (this.parent.children != null) { + this.parent.children.remove(this); + } this.parent.dn.setChildren(new ArrayList<>(this.parent.dn.getChildren())); this.parent.dn.getChildren().remove(this.dn); - this.children.clear(); + this.children = null; } else { // copy loser dn; without children DependencyNode dnCopy = new DefaultDependencyNode(this.dn); @@ -538,7 +558,7 @@ public final class PathConflictResolver extends ConflictResolver { } this.dn = dnCopy; - this.children.clear(); + this.children = null; markLoser = true; } break; @@ -574,9 +594,9 @@ public final class PathConflictResolver extends ConflictResolver { } int newLevels = levels - 1; - if (newLevels >= 0 && !this.children.isEmpty()) { + if (newLevels >= 0 && this.children != null && !this.children.isEmpty()) { // child may remove itself from iterated list - for (Path child : new ArrayList<>(children)) { + for (Path child : new ArrayList<>(this.children)) { child.push(newLevels); } } @@ -610,43 +630,52 @@ public final class PathConflictResolver extends ConflictResolver { * verbosity mode we remove "redundant" nodes (of a range) leaving only "winner equal" loser, that have same GACEV as winner. */ private int relatedSiblingsCount(Artifact artifact, Path parent) { + if (parent.children == null) { + return 0; + } String ga = artifact.getGroupId() + ":" + artifact.getArtifactId(); - return Math.toIntExact(parent.children.stream() - .map(n -> n.dn.getArtifact()) - .filter(a -> ga.equals(a.getGroupId() + ":" + a.getArtifactId())) - .count()); + int count = 0; + for (Path n : parent.children) { + Artifact a = n.dn.getArtifact(); + if (ga.equals(a.getGroupId() + ":" + a.getArtifactId())) { + count++; + } + } + return count; } /** - * Removes this and all child {@link Path} nodes from winner selection scope; essentially marks whole subtree + * Marks this and all child {@link Path} nodes as out of scope; essentially marks whole subtree * from "this and below" as loser, to not be considered in subsequent winner selections. - * Uses {@link LinkedHashSet} for O(1) removal instead of the previous O(N) ArrayList.remove. + * Uses a boolean flag instead of removing from partition collections, avoiding the per-entry + * overhead of LinkedHashSet (~48 bytes/entry). Out-of-scope paths are filtered at query time. */ private void moveOutOfScope() { - this.state.partitions.get(this.conflictId).remove(this); - for (Path child : this.children) { - child.moveOutOfScope(); + this.outOfScope = true; + if (this.children != null) { + for (Path child : this.children) { + child.moveOutOfScope(); + } } } /** * Adds node children: this method should be "batch" used, as all (potential) children should be added at once. * Method will return really added {@link Path} instances, as this class avoids cycles. Those forming a cycle - * are added to {@link Path} structure but are not recursed (not returned in list), keeping {@link Path} cycle - * free. Cycle detection is performed by walking up the parent chain via + * are not recursed (not returned in list), keeping {@link Path} cycle free. + * <p> + * Cycle detection is performed by walking up the parent chain via * {@link #hasConflictIdOnPathToRoot(String)} instead of maintaining a per-node set, trading O(depth) per * check for dramatically reduced memory allocation on large dependency graphs. * This implies that this conflict resolver, by its nature "redoes" the * {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} calculated by {@link ConflictIdSorter}. */ private List<Path> addChildren(List<DependencyNode> children) throws RepositoryException { + // Right-size the children list to avoid ArrayList default capacity waste + this.children = new ArrayList<>(children.size()); ArrayList<Path> added = new ArrayList<>(children.size()); for (DependencyNode child : children) { String childConflictId = this.state.conflictIds.get(child); - // Detect cycles by walking up the parent chain instead of copying a HashSet per child. - // This trades O(depth) per check for eliminating the dominant memory consumer: - // previously, each Path copied its parent's entire conflict-ID set, creating millions - // of HashMap.Node objects for large graphs. boolean cycle = hasConflictIdOnPathToRoot(childConflictId); Path c = new Path(this.state, child, childConflictId, this); this.children.add(c); @@ -663,8 +692,10 @@ public final class PathConflictResolver extends ConflictResolver { */ private void dump(String padding) { System.out.println(padding + this.dn + ": " + this.scope + "/" + this.optional); - for (Path child : children) { - child.dump(padding + " "); + if (this.children != null) { + for (Path child : this.children) { + child.dump(padding + " "); + } } }
