You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@maven.apache.org by GitBox <gi...@apache.org> on 2021/09/09 14:13:12 UTC
[GitHub] [maven] gnodet opened a new pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
gnodet opened a new pull request #530:
URL: https://github.com/apache/maven/pull/530
Following this checklist to help us incorporate your
contribution quickly and easily:
- [ ] Make sure there is a [JIRA issue](https://issues.apache.org/jira/browse/MNG) filed
for the change (usually before you start working on it). Trivial changes like typos do not
require a JIRA issue. Your pull request should address just this issue, without
pulling in other changes.
- [ ] Each commit in the pull request should have a meaningful subject line and body.
- [ ] Format the pull request title like `[MNG-XXX] - Fixes bug in ApproximateQuantiles`,
where you replace `MNG-XXX` with the appropriate JIRA issue. Best practice
is to use the JIRA issue title in the pull request title and in the first line of the
commit message.
- [ ] Write a pull request description that is detailed enough to understand what the pull request does, how, and why.
- [ ] Run `mvn clean verify` to make sure basic checks pass. A more thorough check will
be performed on your pull request automatically.
- [ ] You have run the [Core IT][core-its] successfully.
If your pull request is about ~20 lines of code you don't need to sign an
[Individual Contributor License Agreement](https://www.apache.org/licenses/icla.pdf) if you are unsure
please ask on the developers list.
To make clear that you license your contribution under
the [Apache License Version 2.0, January 2004](http://www.apache.org/licenses/LICENSE-2.0)
you have to acknowledge this by using the following check-box.
- [ ] I hereby declare this contribution to be licenced under the [Apache License Version 2.0, January 2004](http://www.apache.org/licenses/LICENSE-2.0)
- [ ] In any other case, please file an [Apache Individual Contributor License Agreement](https://www.apache.org/licenses/icla.pdf).
[core-its]: https://maven.apache.org/core-its/core-it-suite/
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on pull request #530:
URL: https://github.com/apache/maven/pull/530#issuecomment-919434406
> I will try to review and understand your change this week.
@michael-o Let me give you a few details.
I performed a time analysis on the quite big project (1300 modules or so) with a `mvnd help:evaluate -Dexpression=project.version` run. `mvnd` does compute the whole graph at the beginning.
This leads to a call to `getDownstreamProjects()` for each project in the build.
Currently, this means for each call, going through all projects and calling `projectIds.contains( ProjectSorter.getId( mavenProject ) )`. The new version caches a few things (the order of the projects so that the dependent projects can be sorted without iterating through the whole list of projects), and a mapping of `ProjectSorter.getId(x) -> x` to avoid recomputing the ids.
In addition to those two caches, the loop is changed so that we retrieve the projects and sort them.
So, if `N` is the number of projects, this brings down the number of iteration from `N * N` to `a * N`, where `a` is the mean number of downstream projects. And `a` is usually very small (especially in my case where we only get the first level of dependencies between modules and not the transitive ones). In addition, the number of `getId()` calls is down to `N`, which was the critical spot.
Hopes this helps.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716543177
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -59,6 +66,16 @@ public DefaultProjectDependencyGraph( Collection<MavenProject> projects )
super();
this.allProjects = Collections.unmodifiableList( new ArrayList<>( projects ) );
this.sorter = new ProjectSorter( projects );
+ this.order = new HashMap<>();
+ this.projects = new HashMap<>();
+ List<MavenProject> sorted = this.sorter.getSortedProjects();
+ for ( int index = 0; index < sorted.size(); index++ )
+ {
+ MavenProject project = sorted.get( index );
Review comment:
This should rather use an iterator style (for each loop) and a separately incremended index. Generally, this will incur `O(n)` and is antipattern.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716911948
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
Here's a test:
```
package org.apache.maven.graph;
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.TimeUnit;
import org.junit.Test;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(1)
@State(Scope.Thread)
public class PerfTest {
static final int nmask = 1024*1024 - 1;
static final double[] random_values = new double[nmask + 1];
static {
Random r = new Random();
int[] pows = new int[] { 1, 10, 100, 1000, 10000, 100000, 1000000 };
for( int i = 0; i < random_values.length; ++i ) {
random_values[i] = r.nextDouble();
}
}
@Benchmark
public Collection<Double> test_list() {
List<Double> list = new ArrayList<>( random_values.length );
for ( double d : random_values )
{
list.add( d );
}
Collections.sort(list, new Comparator<Double>() {
@Override
public int compare(Double o1, Double o2) {
return Double.compare(o1, o2);
}
});
return list;
}
@Benchmark
public Collection<Double> test_treeset() {
Set<Double> set = new TreeSet<Double>( new Comparator<Double>() {
@Override
public int compare(Double o1, Double o2) {
return Double.compare(o1, o2);
}
} );
for ( double d : random_values )
{
set.add( d );
}
return set;
}
@Test
public void test() throws Exception {
main(null);
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(".*" + PerfTest.class.getSimpleName() + ".*")
.warmupIterations(20)
.measurementIterations(20)
.forks(1)
.build();
new Runner(opt).run();
}
}
```
and the output:
```
/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/bin/java -ea -Xmx256m -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=61882:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar:/Applications/IntelliJ IDEA CE.app/Contents/plugins/junit/lib/junit5-rt.jar:/Applications/IntelliJ IDEA CE.app/Contents/plugins/junit/lib/junit-rt.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/adoptopenj
dk-8.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/H
ome/lib/dt.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/lib/tools.jar:/Users/gnodet/work/git/maven/maven-core/target/test-classes:/Users/gnodet/work/git/maven/maven-core/target/classes:/Users/gnodet/work/git/maven/maven-model/target/classes:/Users/gnodet/work/git/maven/maven-settings/target/classes:/Users/gnodet/work/git/maven/maven-settings-builder/target/classes:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-interpolation/1.26/plexus-interpolation-1.26.jar:/Users/gnodet/.m2/repository/org/sonatype/plexus/plexus-sec-dispatcher/1.4/plexus-sec-dispatcher-1.4.jar:/Users/gnodet/work/git/maven/maven-builder-support/target/classes:/Users/gnodet/work/git/maven/maven-repository-metadata/target/classes:/Users/gnodet/work/git/maven/maven-artifact/target/classes:/Users/gnodet/work/git/maven/mave
n-plugin-api/target/classes:/Users/gnodet/work/git/maven/maven-model-builder/target/classes:/Users/gnodet/work/git/maven/maven-resolver-provider/target/classes:/Users/gnodet/.m2/repository/org/slf4j/slf4j-api/1.7.32/slf4j-api-1.7.32.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-impl/1.6.3/maven-resolver-impl-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-api/1.6.3/maven-resolver-api-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-spi/1.6.3/maven-resolver-spi-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-util/1.6.3/maven-resolver-util-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/shared/maven-shared-utils/3.3.4/maven-shared-utils-3.3.4.jar:/Users/gnodet/.m2/repository/commons-io/commons-io/2.6/commons-io-2.6.jar:/Users/gnodet/.m2/repository/org/eclipse/sisu/org.eclipse.sisu.plexus/0.3.4/org.eclipse.sisu.plexus-0.3.4.jar:/Users/gnodet/.m2/repository/
javax/enterprise/cdi-api/1.0/cdi-api-1.0.jar:/Users/gnodet/.m2/repository/javax/annotation/jsr250-api/1.0/jsr250-api-1.0.jar:/Users/gnodet/.m2/repository/org/eclipse/sisu/org.eclipse.sisu.inject/0.3.4/org.eclipse.sisu.inject-0.3.4.jar:/Users/gnodet/.m2/repository/com/google/inject/guice/4.2.2/guice-4.2.2-no_aop.jar:/Users/gnodet/.m2/repository/aopalliance/aopalliance/1.0/aopalliance-1.0.jar:/Users/gnodet/.m2/repository/com/google/guava/guava/25.1-android/guava-25.1-android.jar:/Users/gnodet/.m2/repository/com/google/code/findbugs/jsr305/3.0.2/jsr305-3.0.2.jar:/Users/gnodet/.m2/repository/org/checkerframework/checker-compat-qual/2.0.0/checker-compat-qual-2.0.0.jar:/Users/gnodet/.m2/repository/com/google/errorprone/error_prone_annotations/2.1.3/error_prone_annotations-2.1.3.jar:/Users/gnodet/.m2/repository/com/google/j2objc/j2objc-annotations/1.1/j2objc-annotations-1.1.jar:/Users/gnodet/.m2/repository/org/codehaus/mojo/animal-sniffer-annotations/1.14/animal-sniffer-annotations-1.14.ja
r:/Users/gnodet/.m2/repository/javax/inject/javax.inject/1/javax.inject-1.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-utils/3.3.0/plexus-utils-3.3.0.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-classworlds/2.6.0/plexus-classworlds-2.6.0.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-component-annotations/2.1.0/plexus-component-annotations-2.1.0.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-cipher/1.8/plexus-cipher-1.8.jar:/Users/gnodet/.m2/repository/org/apache/commons/commons-lang3/3.8.1/commons-lang3-3.8.1.jar:/Users/gnodet/.m2/repository/commons-jxpath/commons-jxpath/1.3/commons-jxpath-1.3.jar:/Users/gnodet/.m2/repository/org/mockito/mockito-core/2.21.0/mockito-core-2.21.0.jar:/Users/gnodet/.m2/repository/net/bytebuddy/byte-buddy/1.8.15/byte-buddy-1.8.15.jar:/Users/gnodet/.m2/repository/net/bytebuddy/byte-buddy-agent/1.8.15/byte-buddy-agent-1.8.15.jar:/Users/gnodet/.m2/repository/org/objenesis/objenesis/2.6/objenesis-2.6.j
ar:/Users/gnodet/.m2/repository/org/hamcrest/hamcrest-library/1.3/hamcrest-library-1.3.jar:/Users/gnodet/.m2/repository/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar:/Users/gnodet/.m2/repository/org/openjdk/jmh/jmh-core/1.32/jmh-core-1.32.jar:/Users/gnodet/.m2/repository/net/sf/jopt-simple/jopt-simple/4.6/jopt-simple-4.6.jar:/Users/gnodet/.m2/repository/org/apache/commons/commons-math3/3.2/commons-math3-3.2.jar:/Users/gnodet/.m2/repository/junit/junit/4.12/junit-4.12.jar com.intellij.rt.junit.JUnitStarter -ideVersion5 -junit4 org.apache.maven.graph.PerfTest,test
# JMH version: 1.32
# VM version: JDK 1.8.0_292, OpenJDK 64-Bit Server VM, 25.292-b10
# VM invoker: /Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/bin/java
# VM options: -ea -Xmx256m -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=61882:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8
# Blackhole mode: full + dont-inline hint
# Warmup: 20 iterations, 1 s each
# Measurement: 20 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Average time, time/op
# Benchmark: org.apache.maven.graph.PerfTest.test_list
# Run progress: 0.00% complete, ETA 00:01:20
# Fork: 1 of 1
# Warmup Iteration 1: 369628532.333 ns/op
# Warmup Iteration 2: 335057040.000 ns/op
# Warmup Iteration 3: 286127027.250 ns/op
# Warmup Iteration 4: 377216394.333 ns/op
# Warmup Iteration 5: 297273231.500 ns/op
# Warmup Iteration 6: 296754056.250 ns/op
# Warmup Iteration 7: 302441702.500 ns/op
# Warmup Iteration 8: 295685397.750 ns/op
# Warmup Iteration 9: 304160248.750 ns/op
# Warmup Iteration 10: 291609306.750 ns/op
# Warmup Iteration 11: 299350773.750 ns/op
# Warmup Iteration 12: 296379928.500 ns/op
# Warmup Iteration 13: 289805099.500 ns/op
# Warmup Iteration 14: 363609976.667 ns/op
# Warmup Iteration 15: 297788170.000 ns/op
# Warmup Iteration 16: 290522436.250 ns/op
# Warmup Iteration 17: 299326935.500 ns/op
# Warmup Iteration 18: 313127877.000 ns/op
# Warmup Iteration 19: 323881028.250 ns/op
# Warmup Iteration 20: 285531507.000 ns/op
Iteration 1: 301504768.250 ns/op
Iteration 2: 298018122.500 ns/op
Iteration 3: 300425164.750 ns/op
Iteration 4: 369989915.667 ns/op
Iteration 5: 299958799.750 ns/op
Iteration 6: 299201220.500 ns/op
Iteration 7: 298340072.750 ns/op
Iteration 8: 297962777.500 ns/op
Iteration 9: 293935264.750 ns/op
Iteration 10: 294291176.500 ns/op
Iteration 11: 301389877.000 ns/op
Iteration 12: 307207136.000 ns/op
Iteration 13: 296464749.500 ns/op
Iteration 14: 367193909.000 ns/op
Iteration 15: 331991575.250 ns/op
Iteration 16: 293078236.000 ns/op
Iteration 17: 295787907.750 ns/op
Iteration 18: 292366315.250 ns/op
Iteration 19: 296645362.000 ns/op
Iteration 20: 299472610.500 ns/op
Result "org.apache.maven.graph.PerfTest.test_list":
306761248.058 ±(99.9%) 19729179.331 ns/op [Average]
(min, avg, max) = (292366315.250, 306761248.058, 369989915.667), stdev = 22720152.257
CI (99.9%): [287032068.728, 326490427.389] (assumes normal distribution)
# JMH version: 1.32
# VM version: JDK 1.8.0_292, OpenJDK 64-Bit Server VM, 25.292-b10
# VM invoker: /Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/bin/java
# VM options: -ea -Xmx256m -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=61882:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8
# Blackhole mode: full + dont-inline hint
# Warmup: 20 iterations, 1 s each
# Measurement: 20 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Average time, time/op
# Benchmark: org.apache.maven.graph.PerfTest.test_treeset
# Run progress: 50.00% complete, ETA 00:00:48
# Fork: 1 of 1
# Warmup Iteration 1: 728575052.500 ns/op
# Warmup Iteration 2: 697615447.500 ns/op
# Warmup Iteration 3: 714500606.500 ns/op
# Warmup Iteration 4: 704115292.000 ns/op
# Warmup Iteration 5: 652757373.000 ns/op
# Warmup Iteration 6: 660579469.000 ns/op
# Warmup Iteration 7: 642177484.000 ns/op
# Warmup Iteration 8: 680201986.000 ns/op
# Warmup Iteration 9: 650914439.500 ns/op
# Warmup Iteration 10: 642703043.000 ns/op
# Warmup Iteration 11: 680210051.500 ns/op
# Warmup Iteration 12: 623427813.500 ns/op
# Warmup Iteration 13: 692796563.000 ns/op
# Warmup Iteration 14: 666650813.500 ns/op
# Warmup Iteration 15: 730136792.500 ns/op
# Warmup Iteration 16: 685890335.000 ns/op
# Warmup Iteration 17: 669761864.500 ns/op
# Warmup Iteration 18: 702372229.500 ns/op
# Warmup Iteration 19: 622794157.000 ns/op
# Warmup Iteration 20: 707023768.000 ns/op
Iteration 1: 676860694.500 ns/op
Iteration 2: 642499918.000 ns/op
Iteration 3: 697423059.500 ns/op
Iteration 4: 657877062.500 ns/op
Iteration 5: 683425746.500 ns/op
Iteration 6: 652071902.500 ns/op
Iteration 7: 662835988.000 ns/op
Iteration 8: 663524244.000 ns/op
Iteration 9: 752266449.500 ns/op
Iteration 10: 681924793.000 ns/op
Iteration 11: 652598390.000 ns/op
Iteration 12: 697151458.000 ns/op
Iteration 13: 667009518.000 ns/op
Iteration 14: 664859193.500 ns/op
Iteration 15: 705290734.500 ns/op
Iteration 16: 654008780.500 ns/op
Iteration 17: 713168541.000 ns/op
Iteration 18: 667416055.500 ns/op
Iteration 19: 660016529.500 ns/op
Iteration 20: 725536066.000 ns/op
Result "org.apache.maven.graph.PerfTest.test_treeset":
678888256.225 ±(99.9%) 24607512.517 ns/op [Average]
(min, avg, max) = (642499918.000, 678888256.225, 752266449.500), stdev = 28338048.010
CI (99.9%): [654280743.708, 703495768.742] (assumes normal distribution)
# Run complete. Total time: 00:01:43
REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
experiments, perform baseline and negative tests that provide experimental control, make sure
the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
Do not assume the numbers tell you what you want them to tell.
Benchmark Mode Cnt Score Error Units
PerfTest.test_list avgt 20 306761248.058 ± 19729179.331 ns/op
PerfTest.test_treeset avgt 20 678888256.225 ± 24607512.517 ns/op
Process finished with exit code 0
```
The result is that using a `TreeSet` is more than twice the time than `ArrayList` + `sort` ...
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716916762
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
Very nice!
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716543177
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -59,6 +66,16 @@ public DefaultProjectDependencyGraph( Collection<MavenProject> projects )
super();
this.allProjects = Collections.unmodifiableList( new ArrayList<>( projects ) );
this.sorter = new ProjectSorter( projects );
+ this.order = new HashMap<>();
+ this.projects = new HashMap<>();
+ List<MavenProject> sorted = this.sorter.getSortedProjects();
+ for ( int index = 0; index < sorted.size(); index++ )
+ {
+ MavenProject project = sorted.get( index );
Review comment:
This should rather use an iterator style and a separately incremended index. Generally, this will incur `O(n)` and is antipattern.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716911948
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
Here's a test:
```
package org.apache.maven.graph;
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.TimeUnit;
import org.junit.Test;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(1)
@State(Scope.Thread)
public class PerfTest {
static final int nmask = 1024*1024 - 1;
static final double[] random_values = new double[nmask + 1];
static {
Random r = new Random();
int[] pows = new int[] { 1, 10, 100, 1000, 10000, 100000, 1000000 };
for( int i = 0; i < random_values.length; ++i ) {
random_values[i] = r.nextDouble();
}
}
@Benchmark
public Collection<Double> test_list() {
List<Double> list = new ArrayList<>( random_values.length );
for ( double d : random_values )
{
list.add( d );
}
Collections.sort(list, new Comparator<Double>() {
@Override
public int compare(Double o1, Double o2) {
return Double.compare(o1, o2);
}
});
return list;
}
@Benchmark
public Collection<Double> test_treeset() {
Set<Double> set = new TreeSet<Double>( new Comparator<Double>() {
@Override
public int compare(Double o1, Double o2) {
return Double.compare(o1, o2);
}
} );
for ( double d : random_values )
{
set.add( d );
}
return set;
}
@Test
public void test() throws Exception {
main(null);
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(".*" + PerfTest.class.getSimpleName() + ".*")
.warmupIterations(20)
.measurementIterations(20)
.forks(1)
.build();
new Runner(opt).run();
}
}
```
and the output:
```
/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/bin/java -ea -Xmx256m -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=61882:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar:/Applications/IntelliJ IDEA CE.app/Contents/plugins/junit/lib/junit5-rt.jar:/Applications/IntelliJ IDEA CE.app/Contents/plugins/junit/lib/junit-rt.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/adoptopenj
dk-8.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/H
ome/lib/dt.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/lib/tools.jar:/Users/gnodet/work/git/maven/maven-core/target/test-classes:/Users/gnodet/work/git/maven/maven-core/target/classes:/Users/gnodet/work/git/maven/maven-model/target/classes:/Users/gnodet/work/git/maven/maven-settings/target/classes:/Users/gnodet/work/git/maven/maven-settings-builder/target/classes:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-interpolation/1.26/plexus-interpolation-1.26.jar:/Users/gnodet/.m2/repository/org/sonatype/plexus/plexus-sec-dispatcher/1.4/plexus-sec-dispatcher-1.4.jar:/Users/gnodet/work/git/maven/maven-builder-support/target/classes:/Users/gnodet/work/git/maven/maven-repository-metadata/target/classes:/Users/gnodet/work/git/maven/maven-artifact/target/classes:/Users/gnodet/work/git/maven/mave
n-plugin-api/target/classes:/Users/gnodet/work/git/maven/maven-model-builder/target/classes:/Users/gnodet/work/git/maven/maven-resolver-provider/target/classes:/Users/gnodet/.m2/repository/org/slf4j/slf4j-api/1.7.32/slf4j-api-1.7.32.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-impl/1.6.3/maven-resolver-impl-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-api/1.6.3/maven-resolver-api-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-spi/1.6.3/maven-resolver-spi-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/resolver/maven-resolver-util/1.6.3/maven-resolver-util-1.6.3.jar:/Users/gnodet/.m2/repository/org/apache/maven/shared/maven-shared-utils/3.3.4/maven-shared-utils-3.3.4.jar:/Users/gnodet/.m2/repository/commons-io/commons-io/2.6/commons-io-2.6.jar:/Users/gnodet/.m2/repository/org/eclipse/sisu/org.eclipse.sisu.plexus/0.3.4/org.eclipse.sisu.plexus-0.3.4.jar:/Users/gnodet/.m2/repository/
javax/enterprise/cdi-api/1.0/cdi-api-1.0.jar:/Users/gnodet/.m2/repository/javax/annotation/jsr250-api/1.0/jsr250-api-1.0.jar:/Users/gnodet/.m2/repository/org/eclipse/sisu/org.eclipse.sisu.inject/0.3.4/org.eclipse.sisu.inject-0.3.4.jar:/Users/gnodet/.m2/repository/com/google/inject/guice/4.2.2/guice-4.2.2-no_aop.jar:/Users/gnodet/.m2/repository/aopalliance/aopalliance/1.0/aopalliance-1.0.jar:/Users/gnodet/.m2/repository/com/google/guava/guava/25.1-android/guava-25.1-android.jar:/Users/gnodet/.m2/repository/com/google/code/findbugs/jsr305/3.0.2/jsr305-3.0.2.jar:/Users/gnodet/.m2/repository/org/checkerframework/checker-compat-qual/2.0.0/checker-compat-qual-2.0.0.jar:/Users/gnodet/.m2/repository/com/google/errorprone/error_prone_annotations/2.1.3/error_prone_annotations-2.1.3.jar:/Users/gnodet/.m2/repository/com/google/j2objc/j2objc-annotations/1.1/j2objc-annotations-1.1.jar:/Users/gnodet/.m2/repository/org/codehaus/mojo/animal-sniffer-annotations/1.14/animal-sniffer-annotations-1.14.ja
r:/Users/gnodet/.m2/repository/javax/inject/javax.inject/1/javax.inject-1.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-utils/3.3.0/plexus-utils-3.3.0.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-classworlds/2.6.0/plexus-classworlds-2.6.0.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-component-annotations/2.1.0/plexus-component-annotations-2.1.0.jar:/Users/gnodet/.m2/repository/org/codehaus/plexus/plexus-cipher/1.8/plexus-cipher-1.8.jar:/Users/gnodet/.m2/repository/org/apache/commons/commons-lang3/3.8.1/commons-lang3-3.8.1.jar:/Users/gnodet/.m2/repository/commons-jxpath/commons-jxpath/1.3/commons-jxpath-1.3.jar:/Users/gnodet/.m2/repository/org/mockito/mockito-core/2.21.0/mockito-core-2.21.0.jar:/Users/gnodet/.m2/repository/net/bytebuddy/byte-buddy/1.8.15/byte-buddy-1.8.15.jar:/Users/gnodet/.m2/repository/net/bytebuddy/byte-buddy-agent/1.8.15/byte-buddy-agent-1.8.15.jar:/Users/gnodet/.m2/repository/org/objenesis/objenesis/2.6/objenesis-2.6.j
ar:/Users/gnodet/.m2/repository/org/hamcrest/hamcrest-library/1.3/hamcrest-library-1.3.jar:/Users/gnodet/.m2/repository/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar:/Users/gnodet/.m2/repository/org/openjdk/jmh/jmh-core/1.32/jmh-core-1.32.jar:/Users/gnodet/.m2/repository/net/sf/jopt-simple/jopt-simple/4.6/jopt-simple-4.6.jar:/Users/gnodet/.m2/repository/org/apache/commons/commons-math3/3.2/commons-math3-3.2.jar:/Users/gnodet/.m2/repository/junit/junit/4.12/junit-4.12.jar com.intellij.rt.junit.JUnitStarter -ideVersion5 -junit4 org.apache.maven.graph.PerfTest,test
# JMH version: 1.32
# VM version: JDK 1.8.0_292, OpenJDK 64-Bit Server VM, 25.292-b10
# VM invoker: /Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/bin/java
# VM options: -ea -Xmx256m -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=61882:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8
# Blackhole mode: full + dont-inline hint
# Warmup: 20 iterations, 1 s each
# Measurement: 20 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Average time, time/op
# Benchmark: org.apache.maven.graph.PerfTest.test_list
# Run progress: 0.00% complete, ETA 00:01:20
# Fork: 1 of 1
# Warmup Iteration 1: 369628532.333 ns/op
# Warmup Iteration 2: 335057040.000 ns/op
# Warmup Iteration 3: 286127027.250 ns/op
# Warmup Iteration 4: 377216394.333 ns/op
# Warmup Iteration 5: 297273231.500 ns/op
# Warmup Iteration 6: 296754056.250 ns/op
# Warmup Iteration 7: 302441702.500 ns/op
# Warmup Iteration 8: 295685397.750 ns/op
# Warmup Iteration 9: 304160248.750 ns/op
# Warmup Iteration 10: 291609306.750 ns/op
# Warmup Iteration 11: 299350773.750 ns/op
# Warmup Iteration 12: 296379928.500 ns/op
# Warmup Iteration 13: 289805099.500 ns/op
# Warmup Iteration 14: 363609976.667 ns/op
# Warmup Iteration 15: 297788170.000 ns/op
# Warmup Iteration 16: 290522436.250 ns/op
# Warmup Iteration 17: 299326935.500 ns/op
# Warmup Iteration 18: 313127877.000 ns/op
# Warmup Iteration 19: 323881028.250 ns/op
# Warmup Iteration 20: 285531507.000 ns/op
Iteration 1: 301504768.250 ns/op
Iteration 2: 298018122.500 ns/op
Iteration 3: 300425164.750 ns/op
Iteration 4: 369989915.667 ns/op
Iteration 5: 299958799.750 ns/op
Iteration 6: 299201220.500 ns/op
Iteration 7: 298340072.750 ns/op
Iteration 8: 297962777.500 ns/op
Iteration 9: 293935264.750 ns/op
Iteration 10: 294291176.500 ns/op
Iteration 11: 301389877.000 ns/op
Iteration 12: 307207136.000 ns/op
Iteration 13: 296464749.500 ns/op
Iteration 14: 367193909.000 ns/op
Iteration 15: 331991575.250 ns/op
Iteration 16: 293078236.000 ns/op
Iteration 17: 295787907.750 ns/op
Iteration 18: 292366315.250 ns/op
Iteration 19: 296645362.000 ns/op
Iteration 20: 299472610.500 ns/op
Result "org.apache.maven.graph.PerfTest.test_list":
306761248.058 ±(99.9%) 19729179.331 ns/op [Average]
(min, avg, max) = (292366315.250, 306761248.058, 369989915.667), stdev = 22720152.257
CI (99.9%): [287032068.728, 326490427.389] (assumes normal distribution)
# JMH version: 1.32
# VM version: JDK 1.8.0_292, OpenJDK 64-Bit Server VM, 25.292-b10
# VM invoker: /Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/jre/bin/java
# VM options: -ea -Xmx256m -Didea.test.cyclic.buffer.size=1048576 -javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=61882:/Applications/IntelliJ IDEA CE.app/Contents/bin -Dfile.encoding=UTF-8
# Blackhole mode: full + dont-inline hint
# Warmup: 20 iterations, 1 s each
# Measurement: 20 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Average time, time/op
# Benchmark: org.apache.maven.graph.PerfTest.test_treeset
# Run progress: 50.00% complete, ETA 00:00:48
# Fork: 1 of 1
# Warmup Iteration 1: 728575052.500 ns/op
# Warmup Iteration 2: 697615447.500 ns/op
# Warmup Iteration 3: 714500606.500 ns/op
# Warmup Iteration 4: 704115292.000 ns/op
# Warmup Iteration 5: 652757373.000 ns/op
# Warmup Iteration 6: 660579469.000 ns/op
# Warmup Iteration 7: 642177484.000 ns/op
# Warmup Iteration 8: 680201986.000 ns/op
# Warmup Iteration 9: 650914439.500 ns/op
# Warmup Iteration 10: 642703043.000 ns/op
# Warmup Iteration 11: 680210051.500 ns/op
# Warmup Iteration 12: 623427813.500 ns/op
# Warmup Iteration 13: 692796563.000 ns/op
# Warmup Iteration 14: 666650813.500 ns/op
# Warmup Iteration 15: 730136792.500 ns/op
# Warmup Iteration 16: 685890335.000 ns/op
# Warmup Iteration 17: 669761864.500 ns/op
# Warmup Iteration 18: 702372229.500 ns/op
# Warmup Iteration 19: 622794157.000 ns/op
# Warmup Iteration 20: 707023768.000 ns/op
Iteration 1: 676860694.500 ns/op
Iteration 2: 642499918.000 ns/op
Iteration 3: 697423059.500 ns/op
Iteration 4: 657877062.500 ns/op
Iteration 5: 683425746.500 ns/op
Iteration 6: 652071902.500 ns/op
Iteration 7: 662835988.000 ns/op
Iteration 8: 663524244.000 ns/op
Iteration 9: 752266449.500 ns/op
Iteration 10: 681924793.000 ns/op
Iteration 11: 652598390.000 ns/op
Iteration 12: 697151458.000 ns/op
Iteration 13: 667009518.000 ns/op
Iteration 14: 664859193.500 ns/op
Iteration 15: 705290734.500 ns/op
Iteration 16: 654008780.500 ns/op
Iteration 17: 713168541.000 ns/op
Iteration 18: 667416055.500 ns/op
Iteration 19: 660016529.500 ns/op
Iteration 20: 725536066.000 ns/op
Result "org.apache.maven.graph.PerfTest.test_treeset":
678888256.225 ±(99.9%) 24607512.517 ns/op [Average]
(min, avg, max) = (642499918.000, 678888256.225, 752266449.500), stdev = 28338048.010
CI (99.9%): [654280743.708, 703495768.742] (assumes normal distribution)
# Run complete. Total time: 00:01:43
REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
experiments, perform baseline and negative tests that provide experimental control, make sure
the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
Do not assume the numbers tell you what you want them to tell.
Benchmark Mode Cnt Score Error Units
PerfTest.test_list avgt 20 306761248.058 ± 19729179.331 ns/op
PerfTest.test_treeset avgt 20 678888256.225 ± 24607512.517 ns/op
Process finished with exit code 0
```
The result is that using a `TreeSet` is more than twice the time than `ArrayList` + `sort` ...
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716549709
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -158,4 +183,12 @@ public String toString()
return sorter.getSortedProjects().toString();
}
+ private class MavenProjectComparator implements Comparator<MavenProject>
+ {
+ @Override
+ public int compare( MavenProject o1, MavenProject o2 )
+ {
+ return order.get( o1 ) - order.get( o2 );
Review comment:
This involves boxing, is is cheaper to get the `intValue()` from the `Integer` instance?
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet edited a comment on pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet edited a comment on pull request #530:
URL: https://github.com/apache/maven/pull/530#issuecomment-919434406
> I will try to review and understand your change this week.
@michael-o Let me give you a few details.
I performed a time analysis on the quite big project (1300 modules or so) with a `mvnd help:evaluate -Dexpression=project.version` run. `mvnd` does compute the whole graph at the beginning.
This leads to a call to `getDownstreamProjects()` for each project in the build.
Currently, this means for each call, going through all projects and calling `projectIds.contains( ProjectSorter.getId( mavenProject ) )`. The new version caches a few things (the order of the projects so that the dependent projects can be sorted without iterating through the whole list of projects), and a mapping of `ProjectSorter.getId(x) -> x` to avoid recomputing the ids. In addition to those two caches, the loop is changed so that we retrieve the projects using a lookup and sort them (instead of iterating through the whole list of sorted projects and adding the matching ones).
So, if `N` is the number of projects, this brings down the number of iteration from `N * N` to `a * N`, where `a` is the mean number of downstream projects. And `a` is usually very small (especially in my case where we only get the first level of dependencies between modules and not the transitive ones). In addition, the number of `getId()` calls is down to `N`, which was the critical spot.
Hopes this helps.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716841840
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
I think for this usage, an `ArrayList` followed by a `sort` is better, as the cost of the underlying `TreeSet` structure is quite high. I can do some measurements.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716544057
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -78,6 +95,16 @@ public DefaultProjectDependencyGraph( final List<MavenProject> allProjects,
super();
this.allProjects = Collections.unmodifiableList( new ArrayList<>( allProjects ) );
this.sorter = new ProjectSorter( projects );
+ this.order = new HashMap<>();
+ this.projects = new HashMap<>();
+ List<MavenProject> sorted = this.sorter.getSortedProjects();
+ for ( int index = 0; index < sorted.size(); index++ )
+ {
+ MavenProject project = sorted.get( index );
Review comment:
Same here...
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
Woud it be cheaper to have a `TreeSet` which a comparator which sorts on insertion directly?
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
+
return result;
Review comment:
So your optimization resolves around here to get `result` faster? (Means precomputing)
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716843859
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -59,6 +66,16 @@ public DefaultProjectDependencyGraph( Collection<MavenProject> projects )
super();
this.allProjects = Collections.unmodifiableList( new ArrayList<>( projects ) );
this.sorter = new ProjectSorter( projects );
+ this.order = new HashMap<>();
+ this.projects = new HashMap<>();
+ List<MavenProject> sorted = this.sorter.getSortedProjects();
+ for ( int index = 0; index < sorted.size(); index++ )
+ {
+ MavenProject project = sorted.get( index );
Review comment:
Yeah, well, the list is backed by an `ArrayList` in this case and not a `LinkedList`, but the change is ok.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716846770
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
Would be awesome, let me plase know.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716849797
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
+
return result;
Review comment:
Precomputing the project ids and their respective order to avoid iterating through the list multiple times.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] gnodet commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
gnodet commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716848022
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -158,4 +183,12 @@ public String toString()
return sorter.getSortedProjects().toString();
}
+ private class MavenProjectComparator implements Comparator<MavenProject>
+ {
+ @Override
+ public int compare( MavenProject o1, MavenProject o2 )
+ {
+ return order.get( o1 ) - order.get( o2 );
Review comment:
I don't think there's any performance difference between unboxing and calling `intValue()`...
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on pull request #530:
URL: https://github.com/apache/maven/pull/530#issuecomment-928156441
Merged.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o closed pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o closed pull request #530:
URL: https://github.com/apache/maven/pull/530
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716846415
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -59,6 +66,16 @@ public DefaultProjectDependencyGraph( Collection<MavenProject> projects )
super();
this.allProjects = Collections.unmodifiableList( new ArrayList<>( projects ) );
this.sorter = new ProjectSorter( projects );
+ this.order = new HashMap<>();
+ this.projects = new HashMap<>();
+ List<MavenProject> sorted = this.sorter.getSortedProjects();
+ for ( int index = 0; index < sorted.size(); index++ )
+ {
+ MavenProject project = sorted.get( index );
Review comment:
That is likely true, but the `ArrayList` is an implementation detail and shouldn't really matter. So don't make this assumption.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o closed pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o closed pull request #530:
URL: https://github.com/apache/maven/pull/530
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on pull request #530:
URL: https://github.com/apache/maven/pull/530#issuecomment-928156441
Merged.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on a change in pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on a change in pull request #530:
URL: https://github.com/apache/maven/pull/530#discussion_r716916762
##########
File path: maven-core/src/main/java/org/apache/maven/graph/DefaultProjectDependencyGraph.java
##########
@@ -140,15 +167,13 @@ private void getUpstreamProjects( String projectId, Collection<String> projectId
private List<MavenProject> getSortedProjects( Set<String> projectIds )
{
List<MavenProject> result = new ArrayList<>( projectIds.size() );
-
- for ( MavenProject mavenProject : sorter.getSortedProjects() )
+ for ( String projectId : projectIds )
{
- if ( projectIds.contains( ProjectSorter.getId( mavenProject ) ) )
- {
- result.add( mavenProject );
- }
+ result.add( projects.get( projectId ) );
}
+ Collections.sort( result, new MavenProjectComparator() );
Review comment:
Very nice!
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [maven] michael-o commented on pull request #530: [MNG-7235] Speed improvements when calculating the sorted project graph
Posted by GitBox <gi...@apache.org>.
michael-o commented on pull request #530:
URL: https://github.com/apache/maven/pull/530#issuecomment-919413894
I will try to review and understand your change this week.
--
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: issues-unsubscribe@maven.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org