gnodet commented on PR #1908:
URL: https://github.com/apache/maven-resolver/pull/1908#issuecomment-4652055593
Nice benchmark! A few observations and a suggestion for a more
representative topology.
## Minor issues in the current code
1. **`makeDependencyNode(String, String, String, String scope)` silently
drops `scope`** — it delegates to the 3-arg overload which then calls the 5-arg
one with `null` classifier and hardcoded `"compile"`. The `scope` parameter is
never used. Either remove that overload or fix the delegation chain.
2. **`DUMPER_SOUT` is declared but never used** — leftover from debugging.
3. **Assertions in `@Benchmark` hot path** — `assertSame`, `assertEquals`,
`assertNotNull` in `uniqueSnake`/`uniqueSnakeWithRootCycle` add overhead to
every benchmark invocation. Fine for correctness validation but they do inflate
the measurements slightly.
## The "diamond" topology would better stress conflict resolution
The current `uniqueSnake` topology has **zero real conflicts** — every
artifact is unique, so both resolvers spend most of their time on bookkeeping
with nothing to actually resolve. This actually understates PCR's advantage:
PCR's O(N) vs CCR's O(N²) comes from CCR re-walking the whole graph once per
conflict group, so real conflicts are needed to expose the difference.
A diamond (or wide diamond fan) is the classic Maven conflict topology — the
same artifact pulled in at different versions via two or more paths:
```
root
/ \
left right
| \ / |
| \/ |
| shared-1.0
| \
| shared-2.0 ← conflict! classic "nearest wins" scenario
...
```
Here's a `diamondFan(depth, width)` topology to add — `width` independent
chains all pulling in the same shared artifact at conflicting versions:
```java
/**
* A "diamond fan": {@code width} independent chains of length {@code
depth}, all converging
* on the same shared artifact at two different versions (simulating a real
version conflict).
* This is the topology where CCR's O(N²) re-walk per conflict group shows
up most clearly.
*
* Graph shape (width=3, depth=2):
* root
* ├── chain-0-0 → chain-0-1 → shared:1.0
* ├── chain-1-0 → chain-1-1 → shared:2.0 (conflict: 1.0 vs 2.0)
* └── chain-2-0 → chain-2-1 → shared:1.0
*/
private static void diamondFan(ConflictResolver conflictResolver, int depth,
int width)
throws RepositoryException {
DependencyNode root = makeDependencyNode("group-id", "root", "1.0");
List<DependencyNode> chains = new ArrayList<>(width);
for (int w = 0; w < width; w++) {
DependencyNode chainHead = makeDependencyNode("group-id", "chain-" +
w + "-0", "1.0");
DependencyNode last = chainHead;
for (int d = 1; d < depth; d++) {
DependencyNode dep = makeDependencyNode("group-id", "chain-" + w
+ "-" + d, "1.0");
last.setChildren(mutableList(dep));
last = dep;
}
// All chains converge on the same artifact at alternating versions
— real conflict
String version = (w % 2 == 0) ? "1.0" : "2.0";
DependencyNode shared = makeDependencyNode("group-id", "shared",
version);
last.setChildren(mutableList(shared));
chains.add(chainHead);
}
root.setChildren(chains);
DependencyNode result = transform(conflictResolver, root);
assertNotNull(result);
// After conflict resolution, all paths to "shared" must agree on one
version
assertEquals(1, countDistinctVersions(result, "shared"));
}
private static int countDistinctVersions(DependencyNode node, String
artifactId) {
// BFS/DFS to count distinct versions of the given artifactId in the
resolved graph
java.util.Set<String> versions = new java.util.HashSet<>();
collectVersions(node, artifactId, versions);
return versions.size();
}
private static void collectVersions(DependencyNode node, String artifactId,
java.util.Set<String> versions) {
if (node.getArtifact() != null &&
artifactId.equals(node.getArtifact().getArtifactId())
&& node.getData().get(ConflictResolver.NODE_DATA_WINNER) ==
null) {
versions.add(node.getArtifact().getVersion());
}
for (DependencyNode child : node.getChildren()) {
collectVersions(child, artifactId, versions);
}
}
```
Then add benchmark methods:
```java
@Benchmark
public void diamondFan_10x5_path() throws RepositoryException {
diamondFan(path, 5, 10);
}
@Benchmark
public void diamondFan_10x5_classic() throws RepositoryException {
diamondFan(classic, 5, 10);
}
@Benchmark
public void diamondFan_20x10_path() throws RepositoryException {
diamondFan(path, 10, 20);
}
@Benchmark
public void diamondFan_20x10_classic() throws RepositoryException {
diamondFan(classic, 10, 20);
}
```
My expectation is that `diamondFan` will show a **larger** PCR advantage
than `uniqueSnake`, because CCR re-walks the entire graph for the `shared`
conflict group (finding it at the tip of every chain), while PCR already has it
pre-indexed in its partition map from the initial build pass.
Would be interesting to see your numbers on this one!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
