Parallel task evaluation - Please test

This branch experiments with parallel task execution in mill.
This PR is an implementation of https://github.com/lihaoyi/mill/issues/32. Please check out and give feedback! If you need a more recent mill version, just ping me (@lefou) and I'll re-sync the branch.
I try to update this description on the go, to reflect the current state. For details have a look at the commit messages. Everything is open for discussion, either here or on Gitter. Just ping me.
How to test
Checkout and build locally.
$ git clone -b par https://github.com/lefou/mill.git
Cloning into 'mill'...
$ cd mill
mill $ ./mill -i all __.publishLocal assembly
mill $ cp out/assembly/dest/mill ~/mill-par

The last line copies the mill executable to ~/mill-par, but you can freely choose a different location.
By default, mill uses as much build threads as available logical cpu cores. You can change it with --jobs or -j option. Use -j 1 to disable parallel execution at all.
Please note, that the all target enforces serial processing to ensure that calls like mill -i all clean __.compile will still work. In most cases (e.g. when you don't include a clean) you might want to use the new par target, which runs the following targets in parallel. For example: mill -i par __.compile __.testCached.
If you found issues, please report!
If it works for you, please report, too!
How to compare compile speeds
After a change of the mill version, various files need to be re-compiled (ammonite env, build.sc and possibly more). So, before you can compare build times with different mill versions you should run mill -i version, which ensures these things are done and wont foul your timings.
Also, if you want compare times side-by-side, you better clean your out directory with rm -f out.
For starters, if you just want to compare compile times, compare the outputs of:
rm -r out
time ~/mill-par -i __.compile

and
rm -r out
time ~/mill-jar -i -j 1 __.compile

Don't expect wonders! The more cores you have, the better the speedup. Many Laptops throttle their cpu frequencies when they are gooing too hot. Higher cpu usage means more heat, so after all the build times may even increase because you are running in parallel. Look at the ratio between real and user time.
Reporting bugs
If you think you found a bug, here are some infos that help me understanding and fixing it:

Output of mill-par --version
If possible a link to the public repository and steps to reproduce the error
The build output, esp. the error message, also out/evaluator.log is interesting (or run mill with -d)
Does the build succeed with mill-par -j 1 ?
Does the build succeed with mainline mill?

Pull Request Details
Task Evaluation
In this attempt, I use a Java ExecutionService for the job management, to avoid additional dependencies. It also allows some easy reasoning about job scheduling, as the control work and state handling is managed from the single self thread. Only Task execution happens in separate thread pool.
It uses a fixed thread pool with a configurable thread count. The thread pool is managed inside of Evaluator and created and shutdown for each evaluation phase (invokation of the evaluate def). That also means, that when running tasks which itself use an Evalutator instance, we end up with another thread pool. As an example mill all clean __.compile will run the all task in an outer Evaluator instance, which will block until an inner Evaluator instance completes the other tasks. Thus, I plan to redesign it to manage parallelism outside of Evaluator and increase the pool size for each new Evaluator instance, to gracefully adapt to the more or less blocking threads, that wait for the finish of the inner Evaluator instance.
Currently, we only parallelize whole terminal groups (which are most probably a collection of multiple tasks). All elements of a terminal group are by a high change depended on each other and also very fine grained, so that parallelization would not provide much gain; in contrary, it could produce more stress and overhead. But this is only an unverified assumption.
There is certainly a more elegant solution to calculate the task tree (which is a terminal group tree), but I just wanted to concentrate on the parallel processing for now.
Logging and output
Except for ticker message, I try to prefix all output that goes through the Logger with the current task name. Output going through the OutputStreams is currently not prefixed, as that does not work nicely when the streams use Ansi character control sequences, which e.g. is the case for zinc.
Caveats
Tasks that get an Evaluatorinstance are potentially sensitive to parallel execution. For example the built-in clean task will most probably not work as expected when given as an argument to the built-in all task. This will be fixed once #502 is addressed.

Thanks! Will take a look.
Some initial comments:

Currently, I use a hardcoded threadpool with 4 threads, but it is planned to make it configurable.

Sounds good; just a flag you pass similar to -w/--watch seems fine

That also means, that when running tasks which itself use an Evalutator instance, we end up with another thread pool. As an example mill all clean __.compile will run the all task in an outer Evaluator instance, which will block until a inner Evaluator instance completes the other tasks.

This is fine for now. I think long term the way forward is to remove the outer Evaluator from the top-level entry points like all that currently take an Evaluator as a parameter, so for now having an extra thread pool lying around is probably fine.

Currently, we only parallelize whole terminal groups (which are most probably a collection of multiple tasks). All elements of a terminal group are by a high change depended on each other and also very fine grained, so that parallelization would not provide much gain; in contrary, it could produce more stress and overhead. But this is only an unverified assumption.

Probably fine for now. Finer grained parallelism may or may not be better than terminal-group-level paralellism, but let's leave that for future follow-up investigation.
terminal-group-level parallelism also has the benefit that it is simpler for a user to understand, since most of the time they are interacting with terminal NamedTasks at the head of a terminal group, and not with individual tasks themselves

I suspect tasks, which get an Evaluator instance, are tricky to evaluate in parallel. As they can impact the whole tree, e.g. the clean task can be destructive, the work-to-do must be re-evaluated after those tasks complete.

Any update about this?

@nafg AFAIK, nobody reported any experiences with this branch yet. Looks like, there is not that much interest in this feature.

How could it be that there is not much interest :(

I merged  more recent changes, but stopped at the last commit in the 0.5.3 line. All master-commits after that point, introduce binary incompatibilies. I'd rather avoid merging newer versions until we fix #754, which is a blocker for large projects. Large projects are the best target to test this par branch.

Now that #754 is closed can this be rebased onto master?
I don't understand how it's possible to use Mill on large projects without this. I really want to switch to Mill but it's way too slow. :(

Now that #754 is closed can this be rebased onto master?

Sure.

I don't understand how it's possible to use Mill on large projects without this. I really want to switch to Mill but it's way too slow. :(

Do you already use(d) that branch? Have you any numbers for the change of build time?

Tested it on a reasonably complex build that contains plenty non-dependant modules that get cross-compiled to the trinity Jvm/Js/Native. There is a fair number of opportunities for parallelisation, but sadly the results are somewhat underwhelming.
Unfortunately, I cannot share the project's sources, but here are the numbers .
time mill -i all __.compile
real	4m52.666s
user	15m45.372s
sys	0m28.438s
time ~/mill-par -i all __.compile
real	4m34.847s
user	14m57.902s
sys	0m26.639s

I tried compiling a single module that depends on a bunch of others, the compilation of which could be parallelised. Got the following error :
oliviermelois:~/git/doss/baguette$ time ~/mill-par -i examples.jvm.compile
Compiling (synthetic)/ammonite/predef/interpBridge.sc
Compiling (synthetic)/ammonite/predef/sourceBridge.sc
Compiling (synthetic)/ammonite/predef/frontEndBridge.sc
Compiling /Users/oliviermelois/git/doss/baguette/build.sc
Using experimental parallel evaluator with 8 threads
[4/265] core.jvm.sources
[5/265] boilerplate.mainClass
[3/265] core.jvm.upstreamCompileOutput
[7/265] boilerplate.sources
[6/265] boilerplate.upstreamCompileOutput
[2/265] mill.scalalib.ZincWorkerModule.classpath
[190/265] examples.jvm.scalaCompilerClasspath FINISHED
boilerplate.compile: Compiling compiler interface...
[208/265] meta.compile
[info] Compiling 3 Scala sources to /Users/oliviermelois/git/doss/baguette/out/meta/compile/dest/classes ...
[error] ## Exception when compiling 3 sources to /Users/oliviermelois/git/doss/baguette/out/meta/compile/dest/classes
[error] xsbt.CompilerInterface
[error] java.net.URLClassLoader.findClass(URLClassLoader.java:381)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:424)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:357)
[error] java.lang.Class.forName0(Native Method)
[error] java.lang.Class.forName(Class.java:348)
[error] sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
[error] sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
[error] sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
[error] sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)
[error] sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
[error] scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
[error] sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
[error] sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
[error] sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)
[error] sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
[error] sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
[error] sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
[error] sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)
[error] sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
[error] sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)
[error] sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
[error] sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
[error] mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)
[error] mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)
[error] mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)
[error] mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)
[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
[error] mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
[error] mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
[error] mill.define.Task$MappedDest.evaluate(Task.scala:379)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$17(Evaluator.scala:361)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
[error] scala.Console$.withErr(Console.scala:196)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$16(Evaluator.scala:361)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
[error] scala.Console$.withOut(Console.scala:167)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$15(Evaluator.scala:360)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
[error] scala.Console$.withIn(Console.scala:230)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$11(Evaluator.scala:359)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$11$adapted(Evaluator.scala:313)
[error] scala.collection.Iterator.foreach(Iterator.scala:941)
[error] scala.collection.Iterator.foreach$(Iterator.scala:941)
[error] scala.collection.AbstractIterator.foreach(Iterator.scala:1429)
[error] scala.collection.IterableLike.foreach(IterableLike.scala:74)
[error] scala.collection.IterableLike.foreach$(IterableLike.scala:73)
[error] scala.collection.AbstractIterable.foreach(Iterable.scala:56)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$2(Evaluator.scala:313)
[error] mill.util.PrintLogger$.withContext(Loggers.scala:141)
[error] mill.eval.Evaluator.evaluateGroup(Evaluator.scala:282)
[error] mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:213)
[error] mill.eval.Evaluator.$anonfun$evaluateParallel$5(Evaluator.scala:525)
[error] java.util.concurrent.FutureTask.run(FutureTask.java:266)
[error] java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
[error] java.util.concurrent.FutureTask.run(FutureTask.java:266)
[error] java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
[error] java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
[error] java.lang.Thread.run(Thread.java:748)
[error]
[208/265] meta.compile FINISHED
error: java.lang.InterruptedException
	at scala.tools.nsc.io.SourceReader.read(SourceReader.scala:50)
	at scala.tools.nsc.io.SourceReader.read(SourceReader.scala:60)
	at scala.tools.nsc.Global.getSourceFile(Global.scala:367)
	at scala.tools.nsc.Global.getSourceFile(Global.scala:373)
	at scala.tools.nsc.Global$Run.$anonfun$compile$2(Global.scala:1603)
	at scala.tools.nsc.Global$Run.compile(Global.scala:1603)
	at scala.tools.nsc.Driver.doCompile(Driver.scala:47)
	at scala.tools.nsc.MainClass.doCompile(Main.scala:32)
	at scala.tools.nsc.Driver.process(Driver.scala:67)
	at scala.tools.nsc.Main.process(Main.scala)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at mill.scalalib.worker.ZincWorkerImpl.compileZincBridge(ZincWorkerImpl.scala:147)
	at mill.scalalib.worker.ZincWorkerImpl.compileBridgeIfNeeded(ZincWorkerImpl.scala:172)
	at mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:312)
	at mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
	at mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
	at mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
	at mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
	at mill.define.Task$MappedDest.evaluate(Task.scala:379)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$17(Evaluator.scala:361)
	at scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
	at scala.Console$.withErr(Console.scala:196)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$16(Evaluator.scala:361)
	at scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
	at scala.Console$.withOut(Console.scala:167)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$15(Evaluator.scala:360)
	at scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
	at scala.Console$.withIn(Console.scala:230)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$11(Evaluator.scala:359)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$11$adapted(Evaluator.scala:313)
	at scala.collection.Iterator.foreach(Iterator.scala:941)
	at scala.collection.Iterator.foreach$(Iterator.scala:941)
	at scala.collection.AbstractIterator.foreach(Iterator.scala:1429)
	at scala.collection.IterableLike.foreach(IterableLike.scala:74)
	at scala.collection.IterableLike.foreach$(IterableLike.scala:73)
	at scala.collection.AbstractIterable.foreach(Iterable.scala:56)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$2(Evaluator.scala:313)
	at mill.util.PrintLogger$.withContext(Loggers.scala:141)
	at mill.eval.Evaluator.evaluateGroup(Evaluator.scala:282)
	at mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:213)
	at mill.eval.Evaluator.$anonfun$evaluateParallel$5(Evaluator.scala:525)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
	at java.lang.Thread.run(Thread.java:748)
[207/265] boilerplate.compile FINISHED
2 targets failed
boilerplate.compile java.lang.reflect.InvocationTargetException
    sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    java.lang.reflect.Method.invoke(Method.java:498)
    mill.scalalib.worker.ZincWorkerImpl.compileZincBridge(ZincWorkerImpl.scala:147)
    mill.scalalib.worker.ZincWorkerImpl.compileBridgeIfNeeded(ZincWorkerImpl.scala:172)
    mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:312)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
    mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
    mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
    mill.define.Task$MappedDest.evaluate(Task.scala:379)
java.lang.InterruptedException
    scala.tools.nsc.io.SourceReader.read(SourceReader.scala:50)
    scala.tools.nsc.io.SourceReader.read(SourceReader.scala:60)
    scala.tools.nsc.Global.getSourceFile(Global.scala:367)
    scala.tools.nsc.Global.getSourceFile(Global.scala:373)
    scala.tools.nsc.Global$Run.$anonfun$compile$2(Global.scala:1603)
    scala.tools.nsc.Global$Run.compile(Global.scala:1603)
    scala.tools.nsc.Driver.doCompile(Driver.scala:47)
    scala.tools.nsc.MainClass.doCompile(Main.scala:32)
    scala.tools.nsc.Driver.process(Driver.scala:67)
    scala.tools.nsc.Main.process(Main.scala)
    sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    java.lang.reflect.Method.invoke(Method.java:498)
    mill.scalalib.worker.ZincWorkerImpl.compileZincBridge(ZincWorkerImpl.scala:147)
    mill.scalalib.worker.ZincWorkerImpl.compileBridgeIfNeeded(ZincWorkerImpl.scala:172)
    mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:312)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
    mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
    mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
    mill.define.Task$MappedDest.evaluate(Task.scala:379)
meta.compile java.lang.ClassNotFoundException: xsbt.CompilerInterface
    java.net.URLClassLoader.findClass(URLClassLoader.java:381)
    java.lang.ClassLoader.loadClass(ClassLoader.java:424)
    java.lang.ClassLoader.loadClass(ClassLoader.java:357)
    java.lang.Class.forName0(Native Method)
    java.lang.Class.forName(Class.java:348)
    sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
    sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
    sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
    sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
    sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
    sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)
    sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
    scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
    sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
    sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
    sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)
    sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
    sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
    sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
    sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
    sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
    sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)
    sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
    sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
    sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)
    sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
    sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
    sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
    mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)
    mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)
    mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)
    mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
    mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
    mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
    mill.define.Task$MappedDest.evaluate(Task.scala:379)

real	0m29.928s
user	1m53.683s
sys	0m3.355s

Tested it on a reasonably complex build that contains plenty non-dependant modules that get cross-compiled to the trinity Jvm/Js/Native. There is a fair number of opportunities for parallelisation, but sadly the results are somewhat underwhelming.
Unfortunately, I cannot share the project's sources, but here are the numbers .
time mill -i all __.compile
real 4m52.666s
user 15m45.372s
sys 0m28.438s
time ~/mill-par -i all __.compile
real 4m34.847s
user 14m57.902s
sys 0m26.639s

Do these numbers include compilation of mills ammonite env and the build.sc?
All targets that receive an Evaluator are sensitive to parallel processing. The all target is one of them. That's why this branch by defaults set the thread count to 1 in the all target, which retains the old sequential semantics. That means, you will not run in parallel at all.
But there is also a new par target, which runs all tasks in parallel.
But in your case it is best to omit the all completely:
mill -i __.compile

I guess, the initial compilation of the compiler interface needs to be better checked to avoid parallel initialization.

Do these numbers include compilation of mills ammonite env and the build.sc

They do not (in each case, I made sure to precompile the build before testing)

mill -i __.compile

Tried this, gave me roughly the same numbers :
real	4m39.929s
user	18m29.825s
sys	0m35.451s

I'm also getting this if I re-run the same command :
Exception in thread "main" java.util.concurrent.ExecutionException: java.nio.file.NoSuchFileException: /Users/oliviermelois/git/doss/baguette/out/mill/scalalib/ZincWorkerModule/worker/log
	at java.util.concurrent.FutureTask.report(FutureTask.java:122)
	at java.util.concurrent.FutureTask.get(FutureTask.java:192)
	at mill.eval.Evaluator.evaluateParallel(Evaluator.scala:560)
	at mill.eval.Evaluator.evaluate(Evaluator.scala:63)
	at mill.main.RunScript$.evaluate(RunScript.scala:209)
	at mill.main.RunScript$.$anonfun$evaluateTasks$1(RunScript.scala:195)
	at scala.util.Either.map(Either.scala:353)
	at mill.main.RunScript$.evaluateTasks(RunScript.scala:194)
	at mill.main.RunScript$.$anonfun$runScript$4(RunScript.scala:68)
	at ammonite.util.Res$Success.flatMap(Res.scala:62)
	at mill.main.RunScript$.runScript(RunScript.scala:67)
	at mill.main.MainRunner.$anonfun$runScript$1(MainRunner.scala:96)
	at mill.main.MainRunner.watchLoop2(MainRunner.scala:58)
	at mill.main.MainRunner.runScript(MainRunner.scala:72)
	at mill.MillMain$.main0(MillMain.scala:226)
	at mill.MillMain$.main(MillMain.scala:30)
	at mill.MillMain.main(MillMain.scala)
Caused by: java.nio.file.NoSuchFileException: /Users/oliviermelois/git/doss/baguette/out/mill/scalalib/ZincWorkerModule/worker/log
	at sun.nio.fs.UnixException.translateToIOException(UnixException.java:86)
	at sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:102)
	at sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:107)
	at sun.nio.fs.UnixFileSystemProvider.implDelete(UnixFileSystemProvider.java:244)
	at sun.nio.fs.AbstractFileSystemProvider.delete(AbstractFileSystemProvider.java:103)
	at java.nio.file.Files.delete(Files.java:1126)
	at os.remove$all$.apply(FileOps.scala:229)
	at mill.util.FileLogger.outputStream$lzycompute(Loggers.scala:155)
	at mill.util.FileLogger.outputStream(Loggers.scala:154)
	at mill.util.FileLogger.errorStream$lzycompute(Loggers.scala:161)
	at mill.util.FileLogger.errorStream(Loggers.scala:161)
	at mill.util.MultiLogger.errorStream$lzycompute(Loggers.scala:204)
	at mill.util.MultiLogger.errorStream(Loggers.scala:204)
	at mill.util.ProxyLogger.errorStream$lzycompute(Loggers.scala:243)
	at mill.util.ProxyLogger.errorStream(Loggers.scala:243)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$11(Evaluator.scala:356)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$11$adapted(Evaluator.scala:313)
	at scala.collection.Iterator.foreach(Iterator.scala:941)
	at scala.collection.Iterator.foreach$(Iterator.scala:941)
	at scala.collection.AbstractIterator.foreach(Iterator.scala:1429)
	at scala.collection.IterableLike.foreach(IterableLike.scala:74)
	at scala.collection.IterableLike.foreach$(IterableLike.scala:73)
	at scala.collection.AbstractIterable.foreach(Iterable.scala:56)
	at mill.eval.Evaluator.$anonfun$evaluateGroup$2(Evaluator.scala:313)
	at mill.util.PrintLogger$.withContext(Loggers.scala:141)
	at mill.eval.Evaluator.evaluateGroup(Evaluator.scala:282)
	at mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:213)
	at mill.eval.Evaluator.$anonfun$evaluateParallel$5(Evaluator.scala:525)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
	at java.lang.Thread.run(Thread.java:748)

I'm pretty sure I fixed this missing log file issue. Must be some change introduced between the merges with master.

@Baccata Thanks for your feedback.
I think, I have now fixed the two issues. If you want to re-try...
Some thoughts, why you see not much speed improvements

mill is quite IO heavy, it permantly reads and writes files, so small single threaded tasks will not profit much because of the concurrent IO
Zinc is (at least on my laptop) already using many thread. Could also be the JVM that is clever, but one single compile task utilizes my 4 logical core machine between 60 - 95 %

Good point, mill ain't gonna magically make the compiler use less resources ...
So far so good, didn't get the exceptions :+1:

I don't think there's any inherent parallelism limit on the ZincWorker; we re-use Mill's ZincWorker for our Bazel build at work, and quite comfortably huge speedups if you give it the necessary resources. A lot of us use 16-core m5.4xlarge machines on AWS, so it could be worth renting one for a few hours to play around with this PR (they cost 0.7USD/hr). You could even get one with ephemeral disks (m5d.4xlarge) and raid them together to try and reduce IO contention, or get a monster 96 core machine (m5.24xlarge) if you want to go all out (5USD/hr on AWS)
Regarding disk IO, that's definitely something within the scope of this PR: our goal is to make things faster after all, not just to use more CPUs. I had a prototype PR a while back that swaps out the flat files in favor of a SQLite database https://github.com/lihaoyi/mill/pull/297, could be worth experimenting with that (or something similar, like LevelDB/RocksDB) to see if such an approach is able to mitigate the tons-of-tiny-files bottleneck and get us the parallelism speedups we want

@lihaoyi Thanks for pointing out. I didn't know that. I added a commit that configures the cache size according to the --jobs parameter. I have no idea, whether that's the correct way to configure the cache, though.

With the latest commit :
time ~/mill-par -i __.compile
real	2m35.980s
user	14m37.463s
sys	0m32.181s
It basically shaves 2 minutes of non-incremental build time on my project 👍

I have no idea, whether that's the correct way to configure the cache, though.

Hah neither do I. Concurrency issues are always a bit heuristic. You can take a look at the cache source code to see what it does:

https://github.com/lihaoyi/mill/blob/master/main/api/src/mill/api/KeyedLockedCache.scala

It basically keeps a cache of compiler instances that it loans out to who-ever calls withCachedValue. The key is necessary because the different compiler instances may have different configuration. It basically acts as a random-eviction-cache, factory, and a lock/mutex combined together: producing new compiler instances where necessary, re-using them where possible, and ensuring every instance is only used in a single-threaded fashion.

I guess going with a cache size equal to the expected parallel job n count is a good tradeoff then. It ensures that we can always run n compiler instances concurrently. Worst thing that can happen is, that non of the instances is going to be reused.

@lihaoyi Regarding the embedded database idea, I would recommend H2. It's pure java and super-easy to embed, and it's fully-featured, unlike SQLite. In addition, I believe it's trivial to store arbitrary Java objects in it, should that be desired.

Out of curiosity, tested this branch against the mill codebase: __.compile takes roughly 2min30 with standard mill, 1min30 with this branch (8 cores 2.2GHz i7 processor)
@lefou might be worth advertising on social media (twitter/reddit) that you're looking for guinea pigs to test this work and give feedback.

@Baccata  one interesting point of reference would be: what would the time be taken with theoretically-ideal parallelism? Running Mill single-threaded gets you a out/mill-profile.json file telling you how long every step took, and you can dump the task graph using mill visualize.
From there, it should be straightforward to compute the how much time your build should take in an idealized scenario with infinite parallelism, and that can serve as a benchmark to consider how well we think Mill is doing in comparison (and if we need to make it do better)

I'd rather not extend to scope of this PR. It is already open for more than a year. It provides significant build time improvements (although I can't provide good numbers, as I have currently some cpu frequency scaling issue on my machine, so thank you @Baccata for your numbers). What I'm looking for is the question: Is it stable enough to merge?
Also a code review of the change and some input on how to handle evalutator-targets like all, which I changed in this PR, would be great.
I really like to finalize this PR.

@Baccata Do you have also numbers on how long it takes to compile with bloop in the same machine?

@lefou sounds good. I think if it shows significant speedups on @Baccata’s
repo, that’s enough for me to be happy merging
On Wed, 4 Mar 2020 at 6:53 PM, Tobias Roeser<EMAIL_ADDRESS>wrote:

@Baccata https://github.com/Baccata Do you have also numbers on how
long it takes to compile with bloop in the same machine?
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/lihaoyi/mill/pull/480?email_source=notifications&email_token=AE5HBDAAEW6KRSV6LKEKMBLRFYXL5A5CNFSM4GBXTFZKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOENXKBYQ#issuecomment-594452706,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AE5HBDBVDX2DMB42X6ZNEDDRFYXL5ANCNFSM4GBXTFZA
.

(significant speedups vs the single threaded case)
On Wed, 4 Mar 2020 at 7:03 PM, Ammonite-Bot<EMAIL_ADDRESS>wrote:

@lefou sounds good. I think if it shows significant speedups on @Baccata’s
repo, that’s enough for me to be happy merging
On Wed, 4 Mar 2020 at 6:53 PM, Tobias Roeser<EMAIL_ADDRESS>wrote:

@Baccata https://github.com/Baccata Do you have also numbers on how
long it takes to compile with bloop in the same machine?
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<
https://github.com/lihaoyi/mill/pull/480?email_source=notifications&email_token=AE5HBDAAEW6KRSV6LKEKMBLRFYXL5A5CNFSM4GBXTFZKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOENXKBYQ#issuecomment-594452706
,
or unsubscribe
<
https://github.com/notifications/unsubscribe-auth/AE5HBDBVDX2DMB42X6ZNEDDRFYXL5ANCNFSM4GBXTFZA
.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/lihaoyi/mill/pull/480?email_source=notifications&email_token=AAHEB7EETXHFXRCONS5BMZDRFYYPLA5CNFSM4GBXTFZKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOENXLHGQ#issuecomment-594457498,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AAHEB7HREUR2MBMF3FWJ2GTRFYYPLANCNFSM4GBXTFZA
.

From there, it should be straightforward to compute the how much time your build should take in an idealized scenario with infinite parallelism, and that can serve as a benchmark to consider how well we think Mill is doing in comparison (and if we need to make it do better)

That's cool. Medium term we could/should embed such benchmarking logic directly in mill, and have it output an out/mill-benchmark.json, something like :
{
    "naive": ...,
    "real": ...
    "utopic": ...
}

In the meantime I'll try to find the time and write a dirty script to compute the same thing from the output files you pointed to.

@lefou sounds good. I think if it shows significant speedups on @Baccata’s
repo, that’s enough for me to be happy merging

Glad to hear, however It'd be good to gather more feedback than just mine, especially considering the most significant test I've made is on a codebase I can't disclose.

@Baccata Do you have also numbers on how long it takes to compile with bloop in the same machine?

It's not an accurate comparison considering bloop ain't a build tool and doesn't support a compile all command. The closest, most performant command I can do is :
time bloop compile --pipeline --cascade main.api
```,

which takes 41 seconds (vs 1min30 using your branch).

* main.api is the most upstream module I can find in the hierachy, using `mill vizualise __.compile`
* --cascade tells bloop to compile all downstream modules, recursively
* --pipeline means bloop can start compilation of downstream modules after a module's type-checking phase ends, but before it's been fully compiled (and bytecode was emitted). Pipelining isn't currently possible for incremental compilation, so it does a full recompile of the modules involved.

NB : above comparison is against the mill codebase, not against the other codebase I was using to test.
Can't provide a comparison between mill and bloop on that other codebase because the build has some complex logic with running one module to generate sources that are compiled in another module, which bloop can't do because it ain't a build tool and can't express such complex dependencies on its own.

One easy repo to benchmark would be the Ammonite repo. That one cross builds onto a dozen different Scala versions, all of which should be able to run prettymuch independently. That should hopefully show significant speedups

@lihaoyi Shouldn't it be possible to tag the branch (e.g. as 0.6.1-par-M1), so that we get an automatic release for easier consumption? And would it be ok for you?

@lefou sure, that could work. Although I would honestly prefer if you just verified the speedup yourself on a few repos, wrote up your findings, and we merge it.
There are enough OSS mill repos out there that we should be able to get good numbers even without any community help. Ammonite, Mill, Fastparse, etc all have tons of cross builds and should benefit a lot from parallelization

Although I would honestly prefer if you just verified the speedup yourself on a few repos, wrote up your findings, and we merge it.

It's not the speedups I'm interested in, but the stability. And to test it in other environments means currently, I need to build it there first, which make a difference in required time. Also, my current machine has some cpu scaling issues making it a bad env for benchmarking.

One easy repo to benchmark would be the Ammonite repo. That one cross builds onto a dozen different Scala versions, all of which should be able to run prettymuch independently. That should hopefully show significant speedups

Did try it, stopped after 10 minutes and 1/3rd of the steps being completed : my CPU was melting 😅. I'll retry later and maybe build only one module against all possible scala versions

FYI, tried this on our wacky build and had no problems; it shaved about a minute and a half off of our time:
With -j 1:
real    7m49.820s
user    23m31.204s
sys     0m43.949s

With 12 threads:
real    6m7.505s
user    32m2.856s
sys     1m3.090s

I'm getting some weird errors trying to run this PR's artifact on one of my private repos:
future [java.util.concurrent.FutureTask@52ff99cd[Completed exceptionally: java.nio.channels.ClosedByInterruptException]] of task [chapter[1].color.htmlBodyAndPreview] failed: java.util.concurrent.ExecutionException: java.nio.channels.ClosedByInterruptException
        at java.base/java.util.concurrent.FutureTask.report(FutureTask.java:122)
        at java.base/java.util.concurrent.FutureTask.get(FutureTask.java:191)
        at mill.eval.Evaluator.evaluateParallel(Evaluator.scala:562)
        at mill.eval.Evaluator.evaluate(Evaluator.scala:63)
        at mill.main.RunScript$.evaluate(RunScript.scala:209)
        at mill.main.RunScript$.$anonfun$evaluateTasks$1(RunScript.scala:195)
        at scala.util.Either.map(Either.scala:353)
        at mill.main.RunScript$.evaluateTasks(RunScript.scala:194)
        at mill.main.RunScript$.$anonfun$runScript$4(RunScript.scala:68)
        at ammonite.util.Res$Success.flatMap(Res.scala:62)
        at mill.main.RunScript$.runScript(RunScript.scala:67)
        at mill.main.MainRunner.$anonfun$runScript$1(MainRunner.scala:96)
        at mill.main.MainRunner.watchLoop2(MainRunner.scala:58)
        at mill.main.MainRunner.runScript(MainRunner.scala:72)
        at mill.MillMain$.main0(MillMain.scala:226)
        at mill.MillMain$.main(MillMain.scala:30)
        at mill.MillMain.main(MillMain.scala)
Caused by: java.nio.channels.ClosedByInterruptException
        at java.base/java.nio.channels.spi.AbstractInterruptibleChannel.end(AbstractInterruptibleChannel.java:199)
        at java.base/sun.nio.ch.FileChannelImpl.endBlocking(FileChannelImpl.java:162)
        at java.base/sun.nio.ch.FileChannelImpl.position(FileChannelImpl.java:366)
        at java.base/sun.nio.ch.FileChannelImpl.position(FileChannelImpl.java:52)
        at os.write$.write(ReadWriteOps.scala:63)
        at os.write$over$.apply(ReadWriteOps.scala:132)
        at mill.eval.Evaluator.$anonfun$handleTaskResult$3(Evaluator.scala:261)
        at mill.eval.Evaluator.$anonfun$handleTaskResult$3$adapted(Evaluator.scala:260)
        at scala.Option$WithFilter.foreach(Option.scala:274)
        at mill.eval.Evaluator.handleTaskResult(Evaluator.scala:260)
        at mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:221)
        at mill.eval.Evaluator.$anonfun$evaluateParallel$5(Evaluator.scala:527)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
        at java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:515)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
        at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
        at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
        at java.base/java.lang.Thread.run(Thread.java:834)

Execption caught: java.util.concurrent.ExecutionException: java.nio.channels.ClosedByInterruptException
        at java.base/java.util.concurrent.FutureTask.report(FutureTask.java:122)
        at java.base/java.util.concurrent.FutureTask.get(FutureTask.java:191)
        at mill.eval.Evaluator.evaluateParallel(Evaluator.scala:562)
        at mill.eval.Evaluator.evaluate(Evaluator.scala:63)
        at mill.main.RunScript$.evaluate(RunScript.scala:209)
        at mill.main.RunScript$.$anonfun$evaluateTasks$1(RunScript.scala:195)
        at scala.util.Either.map(Either.scala:353)
        at mill.main.RunScript$.evaluateTasks(RunScript.scala:194)
        at mill.main.RunScript$.$anonfun$runScript$4(RunScript.scala:68)
        at ammonite.util.Res$Success.flatMap(Res.scala:62)
        at mill.main.RunScript$.runScript(RunScript.scala:67)
        at mill.main.MainRunner.$anonfun$runScript$1(MainRunner.scala:96)
        at mill.main.MainRunner.watchLoop2(MainRunner.scala:58)
        at mill.main.MainRunner.runScript(MainRunner.scala:72)
        at mill.MillMain$.main0(MillMain.scala:226)
        at mill.MillMain$.main(MillMain.scala:30)
        at mill.MillMain.main(MillMain.scala)
Caused by: java.nio.channels.ClosedByInterruptException
        at java.base/java.nio.channels.spi.AbstractInterruptibleChannel.end(AbstractInterruptibleChannel.java:199)
        at java.base/sun.nio.ch.FileChannelImpl.endBlocking(FileChannelImpl.java:162)
        at java.base/sun.nio.ch.FileChannelImpl.position(FileChannelImpl.java:366)
        at java.base/sun.nio.ch.FileChannelImpl.position(FileChannelImpl.java:52)
        at os.write$.write(ReadWriteOps.scala:63)
        at os.write$over$.apply(ReadWriteOps.scala:132)
        at mill.eval.Evaluator.$anonfun$handleTaskResult$3(Evaluator.scala:261)
        at mill.eval.Evaluator.$anonfun$handleTaskResult$3$adapted(Evaluator.scala:260)
        at scala.Option$WithFilter.foreach(Option.scala:274)
        at mill.eval.Evaluator.handleTaskResult(Evaluator.scala:260)
        at mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:221)
        at mill.eval.Evaluator.$anonfun$evaluateParallel$5(Evaluator.scala:527)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
        at java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:515)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
        at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
        at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
        at java.base/java.lang.Thread.run(Thread.java:834)

Exception in thread "main" java.util.concurrent.ExecutionException: java.nio.channels.ClosedByInterruptException
        at java.base/java.util.concurrent.FutureTask.report(FutureTask.java:122)
        at java.base/java.util.concurrent.FutureTask.get(FutureTask.java:191)
        at mill.eval.Evaluator.evaluateParallel(Evaluator.scala:562)
        at mill.eval.Evaluator.evaluate(Evaluator.scala:63)
        at mill.main.RunScript$.evaluate(RunScript.scala:209)
        at mill.main.RunScript$.$anonfun$evaluateTasks$1(RunScript.scala:195)
        at scala.util.Either.map(Either.scala:353)
        at mill.main.RunScript$.evaluateTasks(RunScript.scala:194)
        at mill.main.RunScript$.$anonfun$runScript$4(RunScript.scala:68)
        at ammonite.util.Res$Success.flatMap(Res.scala:62)
        at mill.main.RunScript$.runScript(RunScript.scala:67)
        at mill.main.MainRunner.$anonfun$runScript$1(MainRunner.scala:96)
        at mill.main.MainRunner.watchLoop2(MainRunner.scala:58)
        at mill.main.MainRunner.runScript(MainRunner.scala:72)
        at mill.MillMain$.main0(MillMain.scala:226)
        at mill.MillMain$.main(MillMain.scala:30)
        at mill.MillMain.main(MillMain.scala)
Caused by: java.nio.channels.ClosedByInterruptException
        at java.base/java.nio.channels.spi.AbstractInterruptibleChannel.end(AbstractInterruptibleChannel.java:199)
        at java.base/sun.nio.ch.FileChannelImpl.endBlocking(FileChannelImpl.java:162)
        at java.base/sun.nio.ch.FileChannelImpl.position(FileChannelImpl.java:366)
        at java.base/sun.nio.ch.FileChannelImpl.position(FileChannelImpl.java:52)
        at os.write$.write(ReadWriteOps.scala:63)
        at os.write$over$.apply(ReadWriteOps.scala:132)
        at mill.eval.Evaluator.$anonfun$handleTaskResult$3(Evaluator.scala:261)
        at mill.eval.Evaluator.$anonfun$handleTaskResult$3$adapted(Evaluator.scala:260)
        at scala.Option$WithFilter.foreach(Option.scala:274)
        at mill.eval.Evaluator.handleTaskResult(Evaluator.scala:260)
        at mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:221)
        at mill.eval.Evaluator.$anonfun$evaluateParallel$5(Evaluator.scala:527)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
        at java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:515)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
        at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
        at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
        at java.base/java.lang.Thread.run(Thread.java:834)

Not sure what this is about... also not sure if the problem is in my build config, or the problem is elsewhere

Time to fully compile the Ammonite Repo, on my 4-core 16GB RAM Macbook Pro
$  time ~/mill-par -i __.compile

real	11m25.701s
user	65m18.218s
sys	1m4.644s

$ time ~/mill-par -i -j 1 __.compile
real	20m4.318s
user	73m33.483s
sys	1m18.391s

Not sure what this is about... also not sure if the problem is in my build config, or the problem is in the PR. As far as I can tell the failure is nondeterministic, but it seems to blow up every time at some point before finishing this build

@lihaoyi Can't tell without seeing the project. You can inspect the out/evaluator.log (or run with -d)  to get a clue what tasks ran in parallel.

Time to fully compile the Ammonite Repo, on my 4-core 16GB RAM 2015 Macbook Pro
$  time ~/mill-par -i __.compile

real	11m25.701s
user	65m18.218s
sys	1m4.644s

$ time ~/mill-par -i -j 1 __.compile
real	20m4.318s
user	73m33.483s
sys	1m18.391s

Having a smaller user time is a bit unexpected, but after all benchmarks with time on laptops is always a bit delicate. But the numbers look really nice.
So, IMHO, whats needed before a merge:

your approval
probably change the default to -j 1
Document new par task

@lefou here's the evaluator log from the earlier run on Ammonite:
evaluator.log
Not sure how to read it; it seems pretty verbose. Does it mean anything to you?

Time to fully compile the Ammonite Repo, on an m5d.24xlarge EC2 instance with 96 cores, 384GB of RAM, and RAID0-ed ephemeral disks for maximal filesystem performance
$  time ./mill __.compile # this is using the default version of Mill in the Ammonite repo

real	13m29.293s
user	0m16.655s
sys	0m17.968s

$ time ~/mill-par -i -j 1 __.compile
real	14m18.692s
user	79m27.849s
sys	3m13.173s

$ time ~/mill-par -i __.compile
real	3m50.820s
user	39m51.076s
sys	1m42.965s

A reasonable speedup. Not as much as I had hoped for given 96 cores and a ridiculous amount of memory and IO performance, but clearly we are getting some parallelism.

@lefou what you propose sounds good to me.
If we want to merge this, we need to get this code into shape and make sure we fully understand the runtime characteristics of this PR. I have run some basic tests on my laptop and on a beefy EC2 instance, and posted the results above. Honestly I'm not terribly happy with the amount of speedup I'm getting, and the evaluator.log file seems pretty useless w.r.t. figuring out what's going on in the course of the build.
I have done one code review pass over the PR to try and get it into shape; the current code is pretty rough, and may need 1 or 2 more review passes after. But we'll get there
For runtime characteristics, perhaps we could set up some way to track how much parallelism we're actually getting in the build? e.g. a simplified evaluator.log file that simply prints out START task and END task for every task, in chronological order, would be enough to tell us exactly how much parallelism we are getting at various points in the build. That would help tell us whether the 3x speedup on 96 cores is a reasonable amount of parallelism to expect given the shape of the build graph, or whether we are hitting other obvious bottlenecks that if resolved would unlock even more parallelism and performance

@lihaoyi Thanks for the review.

@lefou maybe we can spit out the profiling information in the chrome tracing format? https://aras-p.info/blog/2017/01/23/Chrome-Tracing-as-Profiler-Frontend/ That looks like a relatively simple JSON structure and would give us a nice UI to visualize and explore the profiles for free

I reworked result and exception handling a bit. We should now always see the failed targets. There is one issue with started sub-processes, which don't stop when the thread is stopped, e.g. long running test cases. But that's probably something that must be handled in the process handling code (os-lib) e.g. with some kind of shutdown hock or something like that. This is also nothing new, and also happens sometime in non-parallel mode though. I have seen it with run targets, especially.
There is now a out/tasks-par.log which shows only the evaluator start and the start and stop of each task. I also like the idea of the json format @lihaoyi proposed, but haven't it implemented it yet.
Next step is refactoring the code...

Mill does not remove duplicate targets. E.g. if you run mill __.test this will probably result in running all tests twice, as the pattern matches the test target as well as the test project, which expands then to the test target again.
In parallel mode these duplicates will run most likely run in parallel. This can cause issues, also spurios NoSuchFileExceptions and FileAlreadyExistsExceptions. Also it may be a reason, why parallel build was less faster that it could be (haven't checked that claim).
As running the same target make no sense, I will change the par-mode to eliminate duplicates.

Here is a graphical representation of ~/mill-par -i __.complie.

Thread 0 is scheduling work (find targets with no unresolved deps)
Thread 1 to 4 are my worker threads (aka --jobs 4)

Now is a good time to re-test this branch. It now properly handles duplicate goals in the sense that it avoids to run them concurrently. If we should run them at all is another question.
As suggested by Haoyi I added a tracing log as out/mill-par-profile.json. You can open with with Google Chrome by entering the url chrome://tracing and then click on "Load".

And here is the same run when everything is cached.

As you can see, we do almost nothing as we wait for scheduling.
I thinks, that's a good basis the fine-tune scheduling and prioritization.

And here is one of my other projects, mostly Java and AspectJ compiler, also some code generators and tests.
~/mill-par -i -d "{__.compile,__.testCached}"

IMHO, it's pretty well using the threads.

Thanks @lefou, will find a time to re-run my Ammonite build on a variety of hardware

Getting an error trying to run this on the current Ammonite repo:
lihaoyi Ammonite$ rm -rf out/

lihaoyi Ammonite$ rm -rf ~/.mill/

lihaoyi Ammonite$ rm -rf ~/.ammonite/

lihaoyi Ammonite$ time ~/mill-par -i __.compile
Preparing Java 11.0.2 runtime; this may take a minute or two ...
Compiling (synthetic)/ammonite/predef/interpBridge.sc
Compiling (synthetic)/ammonite/predef/sourceBridge.sc
Compiling (synthetic)/ammonite/predef/frontEndBridge.sc
Compiling (synthetic)/ammonite/predef/DefaultPredef.sc
Compiling /Users/lihaoyi/Github/Ammonite/ci/upload.sc
Compiling /Users/lihaoyi/Github/Ammonite/build.sc
Using experimental parallel evaluator with 8 threads
[2/4405] mill.scalalib.ZincWorkerModule.classpath
[7/4405] ops[2.12.10].transitiveLocalClasspath
[8/4405] ops[2.12.10].resources
[3/4405] ops[2.12.10].upstreamCompileOutput
[4/4405] ops[2.12.10].scalaVersion
[5/4405] ops[2.12.10].sources.overriden.mill.scalalib.MavenModule.sources
[1/4405] mill.scalalib.ZincWorkerModule.compilerInterfaceClasspath
[302/4405] amm.repl.api[2.12.1].sources.overriden.mill.scalalib.MavenModule.sources
Writing Constants.scala
[364/4405] amm.repl.api[2.12.2].generatedSources
Writing Constants.scala
[375/4405] amm.interp[2.12.1].scalacPluginClasspath
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.1/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[420/4405] mill.scalalib.ZincWorkerModule.worker
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.2/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[458/4405] amm.repl.api[2.12.3].sources.overriden.mill.scalalib.MavenModule.sources
Writing Constants.scala
[509/4405] amm.interp[2.12.3].scalacPluginIvyDeps FINISHED
ops[2.12.10].compile: Compiling compiler interface...
[515/4405] amm.interp[2.12.3].sources FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.3/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[522/4405] amm.repl.api[2.12.4].generatedSources
Writing Constants.scala
[552/4405] amm.runtime[2.12.4].sources.overriden.mill.scalalib.CrossSbtModule.sources FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.4/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[548/4405] amm.repl.api[2.12.4].dependencyFileResources FINISHED
[587/4405] amm.repl.api[2.12.6].generatedSources
Writing Constants.scala
[617/4405] amm.runtime[2.12.6].scalaOrganization FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.6/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[651/4405] amm.repl.api[2.12.7].generatedSources
Writing Constants.scala
[705/4405] amm.repl.api[2.12.7].allSourceFiles
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.7/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[717/4405] amm.repl.api[2.12.8].generatedSources
Writing Constants.scala
[759/4405] amm.runtime[2.12.8].scalacPluginClasspath FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.8/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[781/4405] amm.repl.api[2.12.9].generatedSources
Writing Constants.scala
[829/4405] amm.interp[2.12.9].compileIvyDeps FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.9/dependencyFileResources/dest/extra-resources/amm-dependencies.txt

[844/4405] amm.repl.api[2.12.10].sources.overriden.mill.scalalib.MavenModule.sources
Writing Constants.scala
[888/4405] amm.runtime[2.12.10].scalacPluginClasspath FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.12.10/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[823/4405] amm.runtime[2.12.9].scalaCompilerClasspath FINISHED
Writing Constants.scala
[964/4405] amm.interp[2.13.0].sources.overriden.mill.scalalib.CrossSbtModule.sources FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.13.0/dependencyFileResources/dest/extra-resources/amm-dependencies.txt
[973/4405] amm.repl.api[2.13.1].generatedSources
Writing Constants.scala
[1042/4405] amm.interp[2.13.1].sources FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/api/2.13.1/dependencyFileResources/dest/extra-resources/amm-dependencies.txt

[1140/4405] amm.repl[2.12.2].test.ivyDeps FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.1/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1123/4405] amm.repl[2.12.1].test.dependencyFileResources FINISHED
[1213/4405] amm.repl[2.12.4].test.compileIvyDeps FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.2/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1226/4405] amm.repl[2.12.4].test.scalaOrganization FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.3/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt

[1260/4405] amm.repl[2.12.6].test.sources.overriden.mill.scalalib.MavenTests.sources
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.4/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1335/4405] amm.repl[2.12.7].test.scalacPluginClasspath
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.6/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1367/4405] amm.repl[2.12.8].test.scalaCompilerClasspath
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.7/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1350/4405] amm.repl[2.12.8].scalaCompilerClasspath FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.8/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1436/4405] amm.repl[2.12.10].test.resources.overriden.mill.scalalib.MavenTests.resources
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.9/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1510/4405] amm.repl[2.13.0].scalacPluginClasspath FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.12.10/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[1548/4405] amm.repl[2.13.1].test.generatedSources FINISHED
terminal[2.13.1].compile: Compiling compiler interface...
[1568/4405] amm.test-runner.resources FINISHED
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.13.0/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt

[1611/4405] amm[2.12.1].test.sources.overriden.mill.scalalib.MavenTests.sources
Writing /Users/lihaoyi/Github/Ammonite/out/amm/repl/2.13.1/test/dependencyFileResources/dest/extra-resources/amm-test-dependencies.txt
[2038/4405] amm[2.13.0].scalaCompilerClasspath FINISHED
[info] Compiling 13 Scala sources to /Users/lihaoyi/Github/Ammonite/out/terminal/2.12.10/compile/dest/classes ...
[2074/4405] amm[2.13.1].scalaOrganization FINISHED
[error] ## Exception when compiling 13 sources to /Users/lihaoyi/Github/Ammonite/out/terminal/2.12.10/compile/dest/classes

[2075/4405] amm[2.13.1].ivyDeps
[error] xsbt.CompilerInterface
[error] java.base/java.net.URLClassLoader.findClass(URLClassLoader.java:471)
[error] java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:588)
[error] java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:521)
[error] java.base/java.lang.Class.forName0(Native Method)
[error] java.base/java.lang.Class.forName(Class.java:398)

[2075/4405] amm[2.13.1].ivyDeps FINISHED
[error] sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
[error] sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
[error] sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
[error] sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)
[error] sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
[error] scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
[error] sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
[error] sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
[error] sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)

[2076/4405] amm[2.13.1].javacOptions
[error] sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
[error] sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
[error] sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
[error] sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)

[2076/4405] amm[2.13.1].javacOptions FINISHED
[error] sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
[error] sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)
[error] sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
[error] sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
[error] mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)
[error] mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)
[error] mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)
[error] mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)
[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
[error] mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
[error] mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
[error] mill.define.Task$MappedDest.evaluate(Task.scala:379)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$18(Evaluator.scala:364)

[2077/4405] amm[2.13.1].scalacOptions [error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)

[error] scala.Console$.withErr(Console.scala:196)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$17(Evaluator.scala:364)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
[error] scala.Console$.withOut(Console.scala:167)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$16(Evaluator.scala:363)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
[error] scala.Console$.withIn(Console.scala:230)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$13(Evaluator.scala:362)

[2077/4405] amm[2.13.1].scalacOptions FINISHED
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$13$adapted(Evaluator.scala:314)
[error] scala.collection.Iterator.foreach(Iterator.scala:941)
[error] scala.collection.Iterator.foreach$(Iterator.scala:941)
[error] scala.collection.AbstractIterator.foreach(Iterator.scala:1429)
[error] scala.collection.IterableLike.foreach(IterableLike.scala:74)
[error] scala.collection.IterableLike.foreach$(IterableLike.scala:73)
[error] scala.collection.AbstractIterable.foreach(Iterable.scala:56)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$2(Evaluator.scala:314)
[error] mill.util.PrintLogger$.withContext(Loggers.scala:141)
[error] mill.eval.Evaluator.evaluateGroup(Evaluator.scala:282)
[error] mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:213)
[error] mill.eval.Evaluator$ParallelEvaluator.$anonfun$scheduleWork$7(Evaluator.scala:684)
[error] java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
[error] java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:515)
[error] java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
[error] java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
[error] java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
[error] java.base/java.lang.Thread.run(Thread.java:834)
[error]            [2078/4405] amm[2.13.1].scalacPluginIvyDeps
[2081/4405] amm[2.13.0].test.allSourceFiles FINISHED
1 targets failed
terminal[2.12.10].compile java.lang.ClassNotFoundException: xsbt.CompilerInterface
    java.base/java.net.URLClassLoader.findClass(URLClassLoader.java:471)
    java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:588)
    java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:521)
    java.base/java.lang.Class.forName0(Native Method)
    java.base/java.lang.Class.forName(Class.java:398)
    sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
    sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
    sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
    sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
    sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
    sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)
    sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
    scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
    sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
    sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
    sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)
    sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
    sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
    sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
    sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
    sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
    sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)
    sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
    sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
    sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)
    sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
    sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
    sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
    mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)
    mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)
    mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)
    mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
    mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
    mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
    mill.define.Task$MappedDest.evaluate(Task.scala:379)

real	0m50.280s
user	2m28.524s
sys	0m6.133s

lihaoyi Ammonite$ git rev-parse HEAD
ef64cbe6a568aacf1c8a10afde698942ca4a2bb2

Tested this on a m5.4xlarge EC2 machine (16core, 64gb)
16 cores
real	2m15.186s
user	18m9.767s
sys	0m19.981s

4 cores
real	1m22.091s
user	10m58.353s
sys	0m11.508s

1 core
real	1m50.712s
user	8m28.904s
sys	0m9.131s

Compiling the Ammonite repo on a m5.4xlarge EC2 machine (16core, 64gb)
16 cores
[info] Compiling 13 Scala sources to /home/lihaoyi/Ammonite/out/terminal/2.12.10/compile/dest/classes ...[info] Compiling 13 Scala sources to /home/lihaoyi/Ammonite/out/terminal/2.13.1/compile/dest/classes ...

[error] ## Exception when compiling 13 sources to /home/lihaoyi/Ammonite/out/terminal/2.12.10/compile/dest/classes[error] ## Exception when compiling 13 sources to /home/lihaoyi/Ammonite/out/terminal/2.13.1/compile/dest/classes

[error] xsbt.CompilerInterface[error] xsbt.CompilerInterface

[error] java.net.URLClassLoader.findClass(URLClassLoader.java:382)[error] java.net.URLClassLoader.findClass(URLClassLoader.java:382)

[error] java.lang.ClassLoader.loadClass(ClassLoader.java:419)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:419)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:352)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:352)[error] java.lang.Class.forName0(Native Method)
[error] java.lang.Class.forName0(Native Method)
[error] java.lang.Class.forName(Class.java:348)
[error] sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
[error] sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
[error] sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
[error] sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)
[error] sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
[error] scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
[error] sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
[error] sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
[error] sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)

[error] java.lang.Class.forName(Class.java:348)
[error] sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
[error] sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
[error] sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
[error] sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)[error] sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)

[error] sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
[error] sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
[error] scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
[error] sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)[error] sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)

[error] sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)[error] sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)

[error] sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)[error] sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)

[error] sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)

[error] sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
[error] sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)
[error] sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
[error] sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
[error] mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)
[error] mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)
[error] mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)
[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)
[error] sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
[error] sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
[error] sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
[error] sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
[error] mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)[error] sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)

[error] sbt.internal.inc.Incremental$.compile(Incremental.scala:80)[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)

[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)[error] sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)

[error] sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)[error] mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)

[error] mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)[error] sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)

[error] sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
[error] mill.define.Task$MappedDest.evaluate(Task.scala:379)
[error] sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$18(Evaluator.scala:364)
[error] sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)[error] mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)

[error] mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)[error] scala.Console$.withErr(Console.scala:196)

[error] mill.eval.Evaluator.$anonfun$evaluateGroup$17(Evaluator.scala:364)[error] mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)

[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)[error] mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)

[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
[error] scala.Console$.withOut(Console.scala:167)[error] mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
[error] mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)

[error] mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$16(Evaluator.scala:363)
[error] mill.define.Task$MappedDest.evaluate(Task.scala:379)
[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)[error] mill.eval.Evaluator.$anonfun$evaluateGroup$18(Evaluator.scala:364)

[error] scala.Console$.withIn(Console.scala:230)[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)

[error] scala.Console$.withErr(Console.scala:196)[error] mill.eval.Evaluator.$anonfun$evaluateGroup$13(Evaluator.scala:362)

[error] mill.eval.Evaluator.$anonfun$evaluateGroup$13$adapted(Evaluator.scala:314)[error] mill.eval.Evaluator.$anonfun$evaluateGroup$17(Evaluator.scala:364)

[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)
[error] scala.collection.Iterator.foreach(Iterator.scala:941)[error] scala.Console$.withOut(Console.scala:167)
[error] mill.eval.Evaluator.$anonfun$evaluateGroup$16(Evaluator.scala:363)

[error] scala.util.DynamicVariable.withValue(DynamicVariable.scala:62)[error] scala.collection.Iterator.foreach$(Iterator.scala:941)

[error] scala.collection.AbstractIterator.foreach(Iterator.scala:1429)
[error] scala.Console$.withIn(Console.scala:230)
[error] scala.collection.IterableLike.foreach(IterableLike.scala:74)[error] mill.eval.Evaluator.$anonfun$evaluateGroup$13(Evaluator.scala:362)

[error] mill.eval.Evaluator.$anonfun$evaluateGroup$13$adapted(Evaluator.scala:314)
[error] scala.collection.IterableLike.foreach$(IterableLike.scala:73)[error] scala.collection.Iterator.foreach(Iterator.scala:941)
[error] scala.collection.Iterator.foreach$(Iterator.scala:941)

[error] scala.collection.AbstractIterable.foreach(Iterable.scala:56)
[error] scala.collection.AbstractIterator.foreach(Iterator.scala:1429)[error] mill.eval.Evaluator.$anonfun$evaluateGroup$2(Evaluator.scala:314)

[error] mill.util.PrintLogger$.withContext(Loggers.scala:141)
[error] scala.collection.IterableLike.foreach(IterableLike.scala:74)
[error] mill.eval.Evaluator.evaluateGroup(Evaluator.scala:282)
[error] scala.collection.IterableLike.foreach$(IterableLike.scala:73)[error] mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:213)

[error] mill.eval.Evaluator$ParallelEvaluator.$anonfun$scheduleWork$7(Evaluator.scala:684)[error] scala.collection.AbstractIterable.foreach(Iterable.scala:56)

[error] mill.eval.Evaluator.$anonfun$evaluateGroup$2(Evaluator.scala:314)
[error] java.util.concurrent.FutureTask.run(FutureTask.java:266)
[error] mill.util.PrintLogger$.withContext(Loggers.scala:141)
[error] java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
[error] mill.eval.Evaluator.evaluateGroup(Evaluator.scala:282)
[error] java.util.concurrent.FutureTask.run(FutureTask.java:266)[error] mill.eval.Evaluator.evaluateGroupCached(Evaluator.scala:213)

[error] mill.eval.Evaluator$ParallelEvaluator.$anonfun$scheduleWork$7(Evaluator.scala:684)[error] java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)

[error] java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)[error] java.util.concurrent.FutureTask.run(FutureTask.java:266)

[error] java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
[error] java.lang.Thread.run(Thread.java:748)[error] java.util.concurrent.FutureTask.run(FutureTask.java:266)

[error]            [error] java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)

[error] java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
[error] java.lang.Thread.run(Thread.java:748)
[error]
[1216/4405] terminal[2.12.10].compile FINISHED
[1601/4405] terminal[2.13.1].compile FINISHED
no errors found
1 targets failed
terminal[2.12.10].compile java.lang.ClassNotFoundException: xsbt.CompilerInterface
    java.net.URLClassLoader.findClass(URLClassLoader.java:382)
    java.lang.ClassLoader.loadClass(ClassLoader.java:419)
    java.lang.ClassLoader.loadClass(ClassLoader.java:352)
    java.lang.Class.forName0(Native Method)
    java.lang.Class.forName(Class.java:348)
    sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
    sbt.internal.inc.AnalyzingCompiler.call(AnalyzingCompiler.scala:234)
    sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:134)
    sbt.internal.inc.AnalyzingCompiler.newCachedCompiler(AnalyzingCompiler.scala:121)
    sbt.internal.inc.FreshCompilerCache.apply(CompilerCache.scala:78)
    sbt.internal.inc.AnalyzingCompiler.compile(AnalyzingCompiler.scala:88)
    sbt.internal.inc.MixedAnalyzingCompiler.$anonfun$compile$3(MixedAnalyzingCompiler.scala:82)
    scala.runtime.java8.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:23)
    sbt.internal.inc.MixedAnalyzingCompiler.timed(MixedAnalyzingCompiler.scala:133)
    sbt.internal.inc.MixedAnalyzingCompiler.compileScala$1(MixedAnalyzingCompiler.scala:73)
    sbt.internal.inc.MixedAnalyzingCompiler.compile(MixedAnalyzingCompiler.scala:116)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1(IncrementalCompilerImpl.scala:307)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileInternal$1$adapted(IncrementalCompilerImpl.scala:307)
    sbt.internal.inc.Incremental$.doCompile(Incremental.scala:106)
    sbt.internal.inc.Incremental$.$anonfun$compile$4(Incremental.scala:87)
    sbt.internal.inc.IncrementalCommon.recompileClasses(IncrementalCommon.scala:116)
    sbt.internal.inc.IncrementalCommon.cycle(IncrementalCommon.scala:63)
    sbt.internal.inc.Incremental$.$anonfun$compile$3(Incremental.scala:89)
    sbt.internal.inc.Incremental$.manageClassfiles(Incremental.scala:134)
    sbt.internal.inc.Incremental$.compile(Incremental.scala:80)
    sbt.internal.inc.IncrementalCompile$.apply(Compile.scala:67)
    sbt.internal.inc.IncrementalCompilerImpl.compileInternal(IncrementalCompilerImpl.scala:311)
    sbt.internal.inc.IncrementalCompilerImpl.$anonfun$compileIncrementally$1(IncrementalCompilerImpl.scala:269)
    sbt.internal.inc.IncrementalCompilerImpl.handleCompilationError(IncrementalCompilerImpl.scala:159)
    sbt.internal.inc.IncrementalCompilerImpl.compileIncrementally(IncrementalCompilerImpl.scala:238)
    sbt.internal.inc.IncrementalCompilerImpl.compile(IncrementalCompilerImpl.scala:69)
    mill.scalalib.worker.ZincWorkerImpl.compileInternal(ZincWorkerImpl.scala:433)
    mill.scalalib.worker.ZincWorkerImpl.$anonfun$compileMixed0$1(ZincWorkerImpl.scala:270)
    mill.api.KeyedLockedCache$RandomBoundedCache.withCachedValue(KeyedLockedCache.scala:31)
    mill.scalalib.worker.ZincWorkerImpl.withCompilers(ZincWorkerImpl.scala:341)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed0(ZincWorkerImpl.scala:269)
    mill.scalalib.worker.ZincWorkerImpl.compileMixed(ZincWorkerImpl.scala:239)
    mill.scalalib.ScalaModule.$anonfun$compile$2(ScalaModule.scala:143)
    mill.define.ApplyerGenerated.$anonfun$zipMap$9(ApplicativeGenerated.scala:21)
    mill.define.Task$MappedDest.evaluate(Task.scala:379)

4 cores
real	7m7.346s
user	66m13.748s
sys	1m3.782s

1 core
real	16m12.676s
user	82m41.582s
sys	1m17.297s

Note that the above benchmarks were run using the following patch:
$ cat out.diff
diff --git a/main/api/src/mill/api/KeyedLockedCache.scala b/main/api/src/mill/api/KeyedLockedCache.scala
index 47fdd888..a320b49c 100644
--- a/main/api/src/mill/api/KeyedLockedCache.scala
+++ b/main/api/src/mill/api/KeyedLockedCache.scala
@@ -42,3 +42,84 @@ object KeyedLockedCache{
     }
   }
 }
+
+import java.io._
+import java.net.InetAddress
+import java.net.{ServerSocket, Socket}
+import java.text.SimpleDateFormat
+import java.util.concurrent.{ConcurrentHashMap, Semaphore}
+import java.util.zip.{ZipEntry, ZipOutputStream}
+
+import scala.util.{Try, Success, Failure}
+import scala.util.control.NonFatal
+
+import mill.api.{KeyedLockedCache, Result}
+import os.Path
+/**
+ * Simple fixed size cache with the following properties
+ * - Elements are lazily initialized upon first access
+ * - Cached element ordering is preserved. The earliest available compiler will always be returned
+ *   first, and it will always be put back in the cache in the same position. This is important
+ *   because each compiler instance is JITed independently. So with a stable ordering so we can bias
+ *   towards reusing an already warm compiler.
+ *
+ * @param perKeySize Cache Size per unique key
+ */
+class FixSizedCache[T](perKeySize: Int) extends KeyedLockedCache[T] {
+
+  // Cache Key -> (Semaphore, Array of cached elements)
+  private[this] val keyToCache: ConcurrentHashMap[Long, (Semaphore, Array[(Boolean, Option[T])])] =
+    new ConcurrentHashMap
+
+  override def withCachedValue[V](key: Long)(f: => T)(f2: T => V): V = {
+    var cacheEntry = keyToCache.get(key)
+    // null if we haven't seen this key before
+    if (cacheEntry == null) {
+      val newSemaphore = new Semaphore(perKeySize, true /* fair */)
+      val newCache = Array.fill[(Boolean, Option[T])](perKeySize)((false, None))
+      // Important that we use putIfAbsent, ensuring we are thread-safe
+      keyToCache.putIfAbsent(key, (newSemaphore, newCache))
+      // Need to call another get, because another thread may have beat us to putting the semaphore
+      // and cache in the map
+      cacheEntry = keyToCache.get(key)
+    }
+    val perKeySemaphore: Semaphore = cacheEntry._1
+    val perKeyCache: Array[(Boolean, Option[T])] = cacheEntry._2
+
+    perKeySemaphore.acquire()
+
+    val (usableCompilerSlot, compilerOpt) = perKeyCache.synchronized {
+      // This will always return a valid value (ie, positive and within the array bounds) because
+      // our guarding semaphore is the same size as our cache.
+      val usableCompilerSlot = perKeyCache.indexWhere { case (compilerInUse, _) => !compilerInUse }
+      require(usableCompilerSlot >= 0,
+        s"Invariant violated: usableCompilerSlot must be >= 0. Found $usableCompilerSlot")
+      val (inUse, compilerOpt) = perKeyCache(usableCompilerSlot)
+      require(!inUse, "Invariant violated: Compiler must not be in use")
+      // Set the `compilerInUse` flag to true
+      perKeyCache(usableCompilerSlot) = (true, compilerOpt)
+      (usableCompilerSlot, compilerOpt)
+    }
+
+    // The compiler may not be initialized yet. If it's None we need to initialize it
+    val compiler = try {
+      compilerOpt.getOrElse(f)
+    } catch {
+      case t: Throwable =>
+        // If we fail to initialize a compiler, print the error and exit the process
+        t.printStackTrace()
+        sys.exit(1)
+    }
+
+    val result = try {
+      f2(compiler)
+    } finally {
+      perKeyCache.synchronized {
+        perKeyCache(usableCompilerSlot) = (false, Some(compiler))
+      }
+      perKeySemaphore.release()
+    }
+
+    result
+  }
+}
diff --git a/scalalib/src/ZincWorkerModule.scala b/scalalib/src/ZincWorkerModule.scala
index a9e0e88e..8746e75a 100644
--- a/scalalib/src/ZincWorkerModule.scala
+++ b/scalalib/src/ZincWorkerModule.scala
@@ -4,7 +4,7 @@ package mill.scalalib
 import coursier.maven.MavenRepository
 import mill.Agg
 import mill.T
-import mill.api.{Ctx, KeyedLockedCache, Loose}
+import mill.api.{Ctx, KeyedLockedCache, Loose, FixSizedCache}
 import mill.define.{Discover, Worker}
 import mill.scalalib.Lib.resolveDependencies
 import mill.scalalib.api.Util.{isBinaryBridgeAvailable, isDotty}
@@ -68,7 +68,7 @@ trait ZincWorkerModule extends mill.Module {
         )),
         mill.scalalib.api.Util.grepJar(_, "scala-library", _, sources = false),
         mill.scalalib.api.Util.grepJar(_, "scala-compiler", _, sources = false),
-        new KeyedLockedCache.RandomBoundedCache(jobs, jobs),
+        new FixSizedCache(jobs),
         false.asInstanceOf[AnyRef]
       )
     instance.asInstanceOf[mill.scalalib.api.ZincWorkerApi]

This is a new KeyedLockedCache implementation that we've been using at databricks, and seems to be simpler and be more stable than the one currently in the Mill codebase. Without this patch, I can't get the Ammonite build to work at all at any level of parallelism above 4, whereas with this patch it seems to work reliably at 8 and work some of the time at 16.

@lefou I'd like 3 things before we merge this PR: performance, stability, and simplicity.

Performance numbers: these I have attempted to provide. My last few tests on the Ammonite repo demonstrate a reasonable speedup for a range of thread counts.

Stability: we should be able to build the Ammonite repo reliably at 16x parallel without hitting any nondeterministic crashes (e.g. those stack traces above). You can spin up an m5.4xlarge EC2 instance for 70c an hour if you want to reproduce what I was doing.

Simplicity: I'm still not convinced that managing our own work queue and dispatch system is a better option than running everything on Futures on a scala.concurrent.ExecutionContext. Unless there is some reason that Futures cannot work, scala.concurrent.ExecutionContext seems like a more reliable and battle-tested implementation of the ad-hoc work-dispatch thread that this PR currently implements.

I saw the xsbt exceptions too, as did others. But haven't located their cause. As you said, I think we need to better isolate the compiler interface creation.
I just wanted to start to reorganize / refactor the parallel code to encapsulate the state and ensure it still works. Now, after that preparationm we can change to Scala's Future and ExecutionContext. Sorry, If I let you belief that I don't want that change.
Can I assume the project license for your patch? I'd like to integrate it.

@lefou yes take it as MIT licensed. Integrating it upstream will also help reduce our maintenance burden.

1 core
real	16m12.676s
user	82m41.582s
sys	1m17.297s

You can clearly see, that some parallelism is already there. Of course that depends heavily on the project and the machine.

Yeah I'm quite happy with the wall-clock speedup, now we just need to nail the stability and simplicity of implementation and I think we're done!

@lefou you should also rigorously review FixSizedCache. It was written in haste, and seems to work, but could definitely use another pair of eyes going over it carefully to make sure it does what  we want it to do. I have not properly reviewed it myself.

FWIW, I hit that strange ClassNotFoundException: xsbt.CompilerInterface when trying it, but afterwards I hit it with regular Mill, and later with SBT as well. The common denominator was that it was in a freshly git cloned directory. Based on https://github.com/sbt/sbt/issues/3124 I suspected it has something to do with the zinc compiler bridge. I tried deleting stuff from places it might have been cached. I think that worked eventually. Or else it's just nondeterministic and the patterns were coincidence and red herrings (tiny sample size)... Not sure if that theory even makes any sense, someone that knows mill internals might have a better idea.
I guess the proper way to debug it would be to attach a debugger and set it to suspend on such exceptions.

@nafg I already found the issue, but haven't finished a proper solution. I can elaborate later...

The xsbt classloading issue should be fixed now. Scheduling now also avoids running worker targets concurrently.

@lefou I just ran PR a few times at 4/8/16x parallelism on my 16core devboxes with no patches applied, seems stable, with performance numbers similar to what I reported earlier

@lefou one thing I've noticed about that logs is that we only apply the task name prefix to the things we log explicitly via log.info, but not things that get streamed to stdout.
We could apply the task name prefix to the streams too, but that might get very noisy.
One idea I had was maybe we could shorten the prefix to just the task number: e.g. [2403/4405] or even just [2403]. I believe every task gets a unique number even under parallelism, and that number is guaranteed to be printed out when the task starts executing. I think consistently tagging every single log line with the task from which it came from will help greatly in making the console logs during parallel execution much more digestible to the reader

@lihaoyi Yeah, I had that implemented very early, but it didn't work very well. Sometimes the prefix ended up as suffix, especially in zinc output. Either I did something work or zinc messes with escape characters to put its stuff into the beginning of the line. That's why I disabled it again (for now). If someone gets it to work, I'm all for it.

I would first go with the prefix, as that is much easier to grasp. We should definitely truncate output of overridden targets though.

I have to slow down my work on this branch a bit for some days. So, if you're eager to start migrating Java Future stuff to Scala Futures, go on. But please hook me in before you merge this branch.

My last change should speed up the initialization phase a lot. The method findInterGroupDeps had an awful complexity.
Let me show the log lines before/after that change in Ammonite build:
# before
28995 [main] finding 4405 inter-group dependencies took 27191 msec
# after
1075 [main] finding 4405 inter-group dependencies took 55 msec

@lihaoyi Would you please review this PR again. I tried to address all your concerns. I hope I haven't missed any. But I'd like to move the change from Java to Scala Futures to after this PR gets merged. Mostly because of a lack of time on my side.

@lefou thanks, will find time to take another look

I'm using the mill-par exclusively for a while now. No issues at all for me. Nice speedup, especially when running tests.

Travis-CI is now green, jay!

I am seeing an exception that looks like we might be trying to start compilation before the compiler interface has been built.  It tries to compile these two modules (trace.projections and domains.everstore) in parallel, but the compiler interface isn't built yet, and one of the two modules proceeds without waiting for it to be available:
[636/671] trace.projections.jvm.compile.overriden.ammonite.$file.sys.proj.base.BaseModule.compile
trace.projections.jvm.compile.overriden.ammonite.$file.sys.proj.base.BaseModule.compile: Compiling compiler interface...
[646/671] domains.everstore.compile.overriden.ammonite.$file.sys.proj.base.BaseModule.compile
[info] Compiling 2 Scala sources to /Users/geh/milltest2/out/foreign-modules/sys/domains/everstore/compilerOutputDir/dest/classes ...
[error] ## Exception when compiling 2 sources to /Users/geh/milltest2/out/foreign-modules/sys/domains/everstore/compilerOutputDir/dest/classes
[error] xsbt.CompilerInterface
[error] java.net.URLClassLoader.findClass(URLClassLoader.java:381)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:424)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:357)
[error] java.lang.Class.forName0(Native Method)
[error] java.lang.Class.forName(Class.java:348)
[error] sbt.internal.inc.AnalyzingCompiler.getInterfaceClass(AnalyzingCompiler.scala:267)
...

This only happens the first time, when the compiler interface hasn't yet been built.  It's a shame, because usually dependencies haven't yet been fetched either at that stage, and dependency fetching happens a lot faster with this branch.

So out of curiosity, what's the plan regarding this branch ?

Not sure about Tobias’ plans, but my last ask is to port the custom thread
scheduler to use Futures before merging. Whether he does it, or someone
else does it, or I end up doing it is immaterial, but I do think it’s a
significant enough win in code cleanliness that I’d like it to happen
before merging
On Sat, 11 Apr 2020 at 11:08 PM, Olivier Mélois<EMAIL_ADDRESS>wrote:

So out of curiosity, what's the plan regarding this branch ?
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/lihaoyi/mill/pull/480#issuecomment-612442086, or
unsubscribe
https://github.com/notifications/unsubscribe-auth/AE5HBDE53JZDSXPN45UEYVDRMCBXJANCNFSM4GBXTFZA
.

@Baccata, glad you asked. The branch itself is pretty stable for me. I'm using it almost on a daily basis. I'm eager to merge it, but asked @lihaoyi  for a second review a month ago.
He already demanded a change to Scala Futures (initially, I choose Java Futures because they are cancelable, but it isn't really required and less readable). But we agreed to defer that to after the merge in another PR, mostly because of lack of time and this PR is already pretty big.
What I ask myself: Should we make the parallel evaluation the default (as it is now in the branch), or should we default to --jobs/-j 1? If we do that (which means no change in mill behavior by default), than it is pretty safe to merge as-is, I think. We can mark the feature "experimental" a release round or two, and ask for feedback. There was not much feedback IMHO, and I can't tell if it's because nobody tried or because all who tried are happy.

Oh, looks like Haoyi already answered (concurrently) and we took different conclusions regarding the Futures change.

I’d say default to non parallel for now. For me at least I have quite a
number of workers which are not thread safe, and passing in a flag for
parallelism is no real hardship.
On Sun, 12 Apr 2020 at 3:58 AM, Tobias Roeser<EMAIL_ADDRESS>wrote:

Oh, looks like Haoyi already answered (concurrently) and we took different
conclusions regarding the Futures change.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/lihaoyi/mill/pull/480#issuecomment-612502108, or
unsubscribe
https://github.com/notifications/unsubscribe-auth/AAHEB7HE2BQLF4XQHKOIINDRMDDWVANCNFSM4GBXTFZA
.

Yeah I still would like the implementation to use Scala futures. For simple
things I don’t mind a little redundancy or reimplementation, but the
future/thread scheduler we have hand rolled here is gnarly and complicated
and seems like a maintenance headache going forward.
Concurrency/parallelism-related code in particular is always something I
would try extra hard to keep simple.
If we discover a reason Scala futures don’t work that’s fine, but we should
have a good reason before committing to our hand-rolled scheduler.
On Sun, 12 Apr 2020 at 4:05 AM, Li Haoyi<EMAIL_ADDRESS>wrote:

I’d say default to non parallel for now. For me at least I have quite a
number of workers which are not thread safe, and passing in a flag for
parallelism is no real hardship.
On Sun, 12 Apr 2020 at 3:58 AM, Tobias Roeser<EMAIL_ADDRESS>wrote:

Oh, looks like Haoyi already answered (concurrently) and we took
different
conclusions regarding the Futures change.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/lihaoyi/mill/pull/480#issuecomment-612502108, or
unsubscribe
<
https://github.com/notifications/unsubscribe-auth/AAHEB7HE2BQLF4XQHKOIINDRMDDWVANCNFSM4GBXTFZA
.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/lihaoyi/mill/pull/480#issuecomment-612503261, or
unsubscribe
https://github.com/notifications/unsubscribe-auth/AE5HBDCF2Y3XLIGJHJEZGNLRMDEPZANCNFSM4GBXTFZA
.

The thing is, we won't get rid of the hand rolled scheduling just by changing from Java Futures to Scala Futures. As we plug-in the multithreading on a high level, we need to handle some concurrency constraints.
When creating the futures, we have no idea if a target is cached before we actually start the future. And we need to make sure that only one target with the same name runs at the same time.  This is not only the case when the user requests the same target twice (e.g. __.test, which resolves to modulex.test.test and modulex.test with default command modulex.test.test) but also each compile task depends on different versions of ZincModule.worker, and we can't run these concurrently before we know it is cached properly. That's something that wasn't obvious to me before, and which I only learned by battle testing and adapting the scheduling.
I think to get rid of the hand roled scheduling would mean, we also need to refactor the evaluateGroup* methods, split it up and be more specific with inputs and output. Currently, these do not hand-over concrete results to each other, but simply fill and use some mutable state. Also we might want to invesitage why there are multiple instances of the (from my naive understanding) same workers. Of course we can improve those things, and I'm sure, mill would greatly improve from these changes, and we should do that sooner or later, but it's still additional non-trivial work.
And that's a bitter pill to me, especially as I've already investent a great amount of time to make the current branch ready to work properly with all projects I know.
So my request is to reconsider adding the current branch as an experimental feature right now. It's disabled by default and easy to remove or improve too. But adding it now allows me and many others to profit from the huge speedups when running compiles and tests right now. Also the additional merge overhead with each change in master was not fun in the past and will not be in the future. It's the reason why I was no longer able to rebase this branch, but needed to merge with master now and then.
As an alternative, we could prepare the Evaluator to have an injectable sheduling strategy and some mechanism to let the user to configure it.

What you say makes sense. Let's merge this as is then! If I want to try a different evaluation strategy, or if there remain issues, we can do that in a later PR.
Looks good to me!

Thank you! I will polish a bit more and merge. I think tagging mill afterwards as 0.7.0 is a good idea.

@lefou give me a few days before tagging 0.7.0, I also want to try and squeeze in a Scala 2.13 upgrade now that https://github.com/sbt/zinc/pull/754 has landed :)

@lihaoyi Sure.