Dotty's parser has scaling issues in parallel execution

[gkossakowski]

Benchmarking shows that dotty's parser scales reasonably (near linearly) just up to two threads. The throughput doesn't improve much when more than two threads are added that share the same context object.

See the exact numbers here:

one thread
----------

[info] Benchmark                                                 (filePath)   Mode  Cnt    Score   Error  Units
[info] ParseBenchmark.parseTyper  ../src/dotty/tools/dotc/typer/Typer.scala  thrpt   60  159.786 ± 3.272  ops/s

two threads
-----------

[info] Benchmark                                                 (filePath)   Mode  Cnt    Score   Error  Units
[info] ParseBenchmark.parseTyper  ../src/dotty/tools/dotc/typer/Typer.scala  thrpt   60  259.886 ± 5.944  ops/s

four threads
------------

[info] Benchmark                                                 (filePath)   Mode  Cnt    Score    Error  Units
[info] ParseBenchmark.parseTyper  ../src/dotty/tools/dotc/typer/Typer.scala  thrpt   60  296.626 ± 14.163  ops/s

As you can see, the increase in throughput between two and four threads is minuscule.

From the numbers above you can see that dotty's parser achieves the performance of 300k LoC/s in single threaded execution. (300k = 159*1890, the last number is lines of code of Typers.scala)

A quick dip into a profiler suggests that parsing threads are contended on Names.termName.

Another intriguing observation is that dotty's parsing performance decreases as JVM warms up:

[info] # Warmup Iteration   1: 102.741 ops/s
[info] # Warmup Iteration   2: 168.566 ops/s
[info] # Warmup Iteration   3: 209.503 ops/s
[info] # Warmup Iteration   4: 315.379 ops/s
[info] # Warmup Iteration   5: 439.984 ops/s
[info] # Warmup Iteration   6: 445.540 ops/s
[info] # Warmup Iteration   7: 447.955 ops/s
[info] # Warmup Iteration   8: 429.745 ops/s
[info] # Warmup Iteration   9: 474.859 ops/s
[info] # Warmup Iteration  10: 473.342 ops/s
[info] # Warmup Iteration  11: 439.681 ops/s
[info] # Warmup Iteration  12: 435.863 ops/s
[info] # Warmup Iteration  13: 393.850 ops/s
[info] # Warmup Iteration  14: 405.858 ops/s
[info] # Warmup Iteration  15: 414.373 ops/s
[info] # Warmup Iteration  16: 393.982 ops/s
[info] # Warmup Iteration  17: 388.191 ops/s
[info] # Warmup Iteration  18: 372.182 ops/s
[info] # Warmup Iteration  19: 367.328 ops/s
[info] # Warmup Iteration  20: 360.737 ops/s
[info] Iteration   1: 358.978 ops/s
[info] Iteration   2: 351.729 ops/s
[info] Iteration   3: 353.012 ops/s
[info] Iteration   4: 322.184 ops/s
[info] Iteration   5: 344.890 ops/s
[info] Iteration   6: 329.241 ops/s
[info] Iteration   7: 314.066 ops/s
[info] Iteration   8: 316.703 ops/s
[info] Iteration   9: 320.233 ops/s
[info] Iteration  10: 319.633 ops/s
[info] Iteration  11: 314.716 ops/s
[info] Iteration  12: 304.024 ops/s
[info] Iteration  13: 294.362 ops/s
[info] Iteration  14: 270.942 ops/s
[info] Iteration  15: 286.218 ops/s
[info] Iteration  16: 278.624 ops/s
[info] Iteration  17: 284.292 ops/s
[info] Iteration  18: 273.424 ops/s
[info] Iteration  19: 259.550 ops/s
[info] Iteration  20: 262.592 ops/s

I collected the numbers using JMH on MBP15 with 2.7GHz Intel Core i7 and Java 8 installed on it. The code is available at: https://github.com/lampepfl/dotty/compare/master...gkossakowski:parsing-perf?expand=1

[DarkDimius]

@gkossakowski is this because you have 2 memory channels and the benchmark is memory bound?

[gkossakowski]

Unfortunately, I don't understand the question. My guess is that dotty's parsing is contended on concurrent access to the name table (implemented as a custom hash table in dotty).

[DarkDimius]

@gkossakowski In some(heavily optimized) applications, the bottleneck isn't the cpu power. It's the speed at which they can consume\produce the data. This is because the contemporary cpu's commonly have less memory channels than cores.

Eg, in ScalaBlitz, Array.sum operations wasn't benefiting from increase of number of cores bigger then number of memory channels, as it was entirely saturating them and added cores would simply wait for data to be read from memory.

Here's an old intel article about it:
https://software.intel.com/en-us/articles/detecting-memory-bandwidth-saturation-in-threaded-applications in this article, they have 4 cores but 1 memory channel and 4 threads run without any locking but don't introduce any speedup over 1 thread.

[odersky]

On Tue, Sep 20, 2016 at 4:51 PM, Grzegorz Kossakowski <
notifications@github.com> wrote:

Unfortunately, I don't understand the question. My guess is that dotty's
parsing is contended on concurrent access to the name table (implemented as
a custom hash table in dotty).

Yes, that's probably right. But at ~300K lines per second per thread, it
does not really seem a bottleneck right now.

Cheers

• Martin

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#1527 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAwlVmQjPOtLCofexuxiwovwlasj6ly-ks5qr_MGgaJpZM4KBrjn
.
{"api_version":"1.0","publisher":{"api_key":"
05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":
{"external_key":"github/lampepfl/dotty","title":"
lampepfl/dotty","subtitle":"GitHub repository","main_image_url":"
https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-
11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://
cloud.githubusercontent.com/assets/143418/15842166/
7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in
GitHub","url":"https://github.com/lampepfl/dotty"}},"
updates":{"snippets":[{"icon":"PERSON","message":"@gkossakowski in #1527:
Unfortunately, I don't understand the question. My guess is that dotty's
parsing is contended on concurrent access to the name table (implemented as
a custom hash table in dotty)."}],"action":{"name":"View Issue","url":"
https://github.com/lampepfl/dotty/issues/1527#issuecomment-248325193"}}}

Prof. Martin Odersky
LAMP/IC, EPFL

[Blaisorblade]

To be sure, I'm trying this out on a 6-core 12-thread server, to check the contention doesn't get catastrophic and decrease performance from single-threaded execution, but it doesn't seem to be the case. But I'm using project dotty-bench-jmh and jmh:run -t N, is that correct?

> jmh:run -t 1
[...]
[info] Result "parse":
[info]   130.321 ±(99.9%) 1.212 ops/s [Average]
[info]   (min, avg, max) = (122.970, 130.321, 135.546), stdev = 2.711
[info]   CI (99.9%): [129.109, 131.533] (assumes normal distribution)
[info]
[info]
[info] # Run complete. Total time: 00:02:02
[info]
[info] Benchmark                                            (filePath)   Mode  Cnt    Score   Error  Units
[info] ParseBenchmark.parse  ../src/dotty/tools/dotc/typer/Typer.scala  thrpt   60  130.321 ± 1.212  ops/s

> jmh:run -t 12
[info] Result "parse":
[info]   209.586 ±(99.9%) 5.018 ops/s [Average]
[info]   (min, avg, max) = (187.629, 209.586, 231.761), stdev = 11.223
[info]   CI (99.9%): [204.569, 214.604] (assumes normal distribution)
[info]
[info]
[info] # Run complete. Total time: 00:02:12
[info]
[info] Benchmark                                            (filePath)   Mode  Cnt    Score   Error  Units
[info] ParseBenchmark.parse  ../src/dotty/tools/dotc/typer/Typer.scala  thrpt   60  209.586 ± 5.018  ops/s

[retronym]

I recently fixed a bug in GenBCode that was dooming any method with synchronized block (def termName is such a method) to a life of interpretation under the HotSpot JVM. Maybe dotty needs to update its dependency or fork of that.

Running with -J-Xprof and looking for interpreted methods is a good indication of the problem.

[retronym]

Actually that method is ACC_SYNCHRONIZED (of the form def foo = this.synchronized { ... }) in a non-trait), so it isn't subject to that bug.

[DarkDimius]

Hi Paolo,
Would you mind telling what cpu your server has?

If it has 4memory channels this would be an independent validation that the
scaling here is limited not due to synchronised block, but memory bandwidth.

On 10 October 2016 1:20:13 a.m. "Paolo G. Giarrusso"
notifications@github.com wrote:

To be sure, I'm trying this out on a 6-core 12-thread server, to check the
contention doesn't get catastrophic and decrease performance from
single-threaded execution, but it doesn't seem to be the case. But I'm
using project dotty-bench-jmh and jmh:run -t N, is that correct?

> jmh:run -t 1
[...]
[info] Result "parse":
[info]   130.321 ±(99.9%) 1.212 ops/s [Average]
[info]   (min, avg, max) = (122.970, 130.321, 135.546), stdev = 2.711
[info]   CI (99.9%): [129.109, 131.533] (assumes normal distribution)
[info]
[info]
[info] # Run complete. Total time: 00:02:02
[info]
[info] Benchmark                                            (filePath)   
Mode  Cnt    Score   Error  Units
[info] ParseBenchmark.parse  ../src/dotty/tools/dotc/typer/Typer.scala  
thrpt   60  130.321 ± 1.212  ops/s

> jmh:run -t 12
[info] Result "parse":
[info]   209.586 ±(99.9%) 5.018 ops/s [Average]
[info]   (min, avg, max) = (187.629, 209.586, 231.761), stdev = 11.223
[info]   CI (99.9%): [204.569, 214.604] (assumes normal distribution)
[info]
[info]
[info] # Run complete. Total time: 00:02:12
[info]
[info] Benchmark                                            (filePath)   
Mode  Cnt    Score   Error  Units
[info] ParseBenchmark.parse  ../src/dotty/tools/dotc/typer/Typer.scala  
thrpt   60  209.586 ± 5.018  ops/s

You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#1527 (comment)

[Blaisorblade]

@DarkDimius Sure, but no clue how many memory channels this has. Below's cpuinfo for one processor. But IIUC that's not "validation" but "nonrefutation".

And your ScalaBlitz example described a lock-less scenario, while the culprit here has a synchronized block in an object, hence a global lock, so "lock contention" seems the most likely scenario, no? In other words, the bottleneck should be a single cacheline (the one with the lock) moving around processors.
I mean, we know that in general that's not a good ConcurrentHashMap, the ones in the stdlib or by Cliff Click are optimized for that scenario and have no single lock.

Anyway, if this becomes a bottleneck (which, again, doesn't seem to be the case) one would probably use appropriate instrumentation to confirm it.

Finally, absolute single-threaded performance isn't affected by total core count: Absolute performance is slower on this server, but so is maximum clock (2.2GHz), and linearly scaling 130 ops/s by the frequency ratio 2.7/2.2 gives ~159 ops/s, exactly the performance reported by @gkossakowski. This seems too accurate to be plausible, but if true it would be easier to explain with a CPU-bound task on single CPUs.

$ cat /proc/cpuinfo
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 62
model name      : Intel(R) Xeon(R) CPU E5-2420 v2 @ 2.20GHz
stepping        : 4
microcode       : 0x427
cpu MHz         : 2200.229
cache size      : 15360 KB
physical id     : 0
siblings        : 12
core id         : 0
cpu cores       : 6
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm ida arat xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms
bogomips        : 4400.45
clflush size    : 64
cache_alignment : 64
address sizes   : 46 bits physical, 48 bits virtual
power management:

[... snip other processors ...]

[retronym]

I do find the design choice to use one big name table in Names.table for all instances of the compiler in a given classloader to be questionable.

Bikeshedding a little, I'd be tempted to store names as plain old String-s these days and rely on on http://openjdk.java.net/jeps/192 to keep the heap usage compact.

[odersky]

I don't have any new data, but I do remember that Neil Gafter tried this
for javac around 2005/06 ish. He got a 5% overall slowdown, so he reverted
the change.

Also, we have to see things in perspective: At 150K lines/sec/thread the
parser is certainly not a bottleneck.

On Mon, Oct 10, 2016 at 11:59 AM, Jason Zaugg notifications@github.com
wrote:

I do find the design choice to use one big name table in Names.table for
all instances of the compiler in a given classloader to be questionable.

Bikeshedding a little, I'd be tempted to store names as plain old String-s
these days and rely on on http://openjdk.java.net/jeps/192 to keep the
heap usage compact.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#1527 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAwlVkR_6B_OdFtyANi8LDTqQ1Co4WIqks5qygyPgaJpZM4KBrjn
.
{"api_version":"1.0","publisher":{"api_key":"
05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":
{"external_key":"github/lampepfl/dotty","title":"
lampepfl/dotty","subtitle":"GitHub repository","main_image_url":"
https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-
11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://
cloud.githubusercontent.com/assets/143418/15842166/
7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in
GitHub","url":"https://github.com/lampepfl/dotty"}},"
updates":{"snippets":[{"icon":"PERSON","message":"@retronym in #1527: I
do find the design choice to use one big name table in Names.table for
all instances of the compiler in a given classloader to be
questionable.\r\n\r\nBikeshedding a little, I'd be tempted to store names
as plain old String-s these days and rely on on
http://openjdk.java.net/jeps/192 to keep the heap usage
compact."}],"action":{"name":"View Issue","url":"https://github.
com//issues/1527#issuecomment-252576957"}}}

Prof. Martin Odersky
LAMP/IC, EPFL

[retronym]

My main objection to the shared name table is that it looks like a memory leak. In scalac, the entire name table is discarded when the Global instance is released.

Just to complete my bikeshed, the other recent relevant JVM change is http://openjdk.java.net/jeps/254, which reduces storage for UTF-8 strings. JEP-192 avoids the most of the contention of using String.intern while (eventually) sharing common strings.

Maybe you could even do away with TermName / TypeName by having separate scopes for types and terms.

[odersky]

Yes, the memory leak possibility is indeed the more worrying part. It would
be interesting to see whether it will become a problem in practice.

On Mon, Oct 10, 2016 at 12:24 PM, Jason Zaugg notifications@github.com
wrote:

My main objection to the shared name table is that it looks like a memory
leak. In scalac, the entire name table is discarded when the Global
instance is released.

Just to complete my bikeshed, the other recent relevant JVM change is
http://openjdk.java.net/jeps/254, which reduces storage for UTF-8
strings. JEP-192 avoids the most of the contention of using String.intern
while (eventually) sharing common strings.

Maybe you could even do away with TermName / TypeName by having separate
scopes for types and terms.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#1527 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAwlVnF7jU__7XVQmgG0LVkXJpULBmP5ks5qyhJSgaJpZM4KBrjn
.
{"api_version":"1.0","publisher":{"api_key":"
05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":
{"external_key":"github/lampepfl/dotty","title":"
lampepfl/dotty","subtitle":"GitHub repository","main_image_url":"
https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-
11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://
cloud.githubusercontent.com/assets/143418/15842166/
7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in
GitHub","url":"https://github.com/lampepfl/dotty"}},"
updates":{"snippets":[{"icon":"PERSON","message":"@retronym in #1527: My
main objection to the shared name table is that it looks like a memory
leak. In scalac, the entire name table is discarded when the Global
instance is released.\r\n\r\nJust to complete my bikeshed, the other recent
relevant JVM change is http://openjdk.java.net/jeps/254, which reduces
storage for UTF-8 strings. JEP-192 avoids the most of the contention of
using String.intern while (eventually) sharing common
strings.\r\n\r\nMaybe you could even do away with TermName / TypeName
by having separate scopes for types and terms."}],"action":{"name":"View
Issue","url":"https://github.com/lampepfl/dotty/issues/
1527#issuecomment-252581036"}}}

Prof. Martin Odersky
LAMP/IC, EPFL

[Blaisorblade]

Can't we just move the relevant hashtable to whatever the equivalent of Global is? Trying out the JEP changes would be more invasive and have a potential slowdown, so it'd be a separate change.

My main objection to the shared name table is that it looks like a memory leak. In scalac, the entire name table is discarded when the Global instance is released.

It would
be interesting to see whether it will become a problem in practice.

To show the bug matters we just need some long-running client that invokes Dotty multiple times in the same classloader (which should be reasonable). SBT might be an example, and it seems ScalaIDE and Ensime will be two others after #1523 (/cc @sschaef @fommil)? And isn't that enough to show it's an actual leak (however small)?

Unless Dotty starts requiring all clients manage a separate classloader for the compiler, making all such bugs impossible but complicating clients.

Since used strings change slowly in a single project, this would also be an insidious bug to debug. In other words, we should probably open a separate issue to track that, since debugging such a leak from symptoms would be far from trivial.

Finally, opening and closing different projects (with different strings) in ScalaIDE would probably trigger this more easily.

[fommil]

It would be good if we could avoid the classloader problems of scalac, I've had to go to some incredible lengths to bypass problems on windows. See https://github.com/fommil/class-monkey for gory details, and the monkeys folder in ensime-server