Terrible Golang performance

[movelazar]

Stackoverflow: https://stackoverflow.com/questions/72266899/golang-performance-issues

Google group: https://groups.google.com/g/antlr-discussion/c/OdhAIsy2GfI

Example code: https://github.com/movelazar/perf-repro

A simple rule such as:

1 EQ 2 OR
1 EQ 2 OR
1 EQ 2 OR
1 EQ 2 OR
1 EQ 2

takes exponentially longer to parse the more 1 EQ 2 OR clauses there are. This does not happen in python (by my testing) or CSharp, Dart, Java (by stackoverflow comment).

On my machine, # of lines vs parse time:

11: 0.5s
12: 1.2s
13: 3.2s
14: 8.1s
15: 21.9s
16: 57.5s

Given that Python doesn't face this issue I can't imagine I'm doing something terrible in my grammar.

Issue goes away if I put parens on things but that's not a real solution.

On 4.10.1, first noticed with 4.9.1.

Any help is greatly appreciated. Surprised I can't find others with this issue.

[movelazar]

Copying an insightful comment from Stackoverflow:

profiling your bench it appears that this package spends a great amount of time within some internals github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).closureWork:1091. Doing that, it allocates a lot, then it does it again. Somtimes it adds a node to its tree. You can easily observe that by yourself running the trace utility pkg.go.dev/runtime/trace

[kaby76]

Copying an insightful comment from Stackoverflow:

profiling your bench it appears that this package spends a great amount of time within some internals github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).closureWork:1091. Doing that, it allocates a lot, then it does it again. Somtimes it adds a node to its tree. You can easily observe that by yourself running the trace utility pkg.go.dev/runtime/trace

Does anyone know how to use the ggprof utility? The instructions referenced are some of the worse I've ever seen in 40 years. It took me hours to read past the incomplete instructions, syntactically invalid code given, and improper use of standard software engineering terminology, to construct a working parser driver program that sets up a server and turns on "profiling". And even then, "top10" shows diddly squat:

(pprof) top10
Showing nodes accounting for 10ms, 100% of 10ms total
      flat  flat%   sum%        cum   cum%
      10ms   100%   100%       10ms   100%  runtime.stdcall6
         0     0%   100%       10ms   100%  runtime.findrunnable
         0     0%   100%       10ms   100%  runtime.mcall
         0     0%   100%       10ms   100%  runtime.netpoll
         0     0%   100%       10ms   100%  runtime.park_m
         0     0%   100%       10ms   100%  runtime.schedule
(pprof)

I still cannot determine if ggprof is a profiling tool or a tracing tool or both. I still cannot understand why the program actually needs to be modified at all in order to perform profiling aka "sampling" at fixed intervals and recording a stack trace.

[kaby76]

I changed test to use a larger example boolean expression, and redid the run--which gives wildly different results every time--and only this one run outputted more useful results:

(pprof) top111
Showing nodes accounting for 9.50s, 87.16% of 10.90s total
Dropped 134 nodes (cum <= 0.05s)
Showing top 111 nodes out of 115
      flat  flat%   sum%        cum   cum%
     2.06s 18.90% 18.90%      2.06s 18.90%  runtime.stdcall2
     1.27s 11.65% 30.55%      6.20s 56.88%  github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).closureWork
     0.69s  6.33% 36.88%      0.69s  6.33%  runtime.stdcall1
     0.56s  5.14% 42.02%      2.03s 18.62%  runtime.mallocgc
     0.51s  4.68% 46.70%      0.71s  6.51%  runtime.heapBitsSetType
     0.36s  3.30% 50.00%      2.52s 23.12%  github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).getEpsilonTarget
     0.27s  2.48% 52.48%      0.27s  2.48%  runtime.nextFreeFast (inline)
     0.22s  2.02% 54.50%      0.27s  2.48%  runtime.mapaccess1_fast64
     0.20s  1.83% 56.33%      1.67s 15.32%  github.com/antlr/antlr4/runtime/Go/antlr.NewBaseATNConfig
     0.17s  1.56% 57.89%      6.20s 56.88%  github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).closureCheckingStopState
     0.16s  1.47% 59.36%      0.57s  5.23%  runtime.scanobject
     0.15s  1.38% 60.73%      0.15s  1.38%  runtime.memclrNoHeapPointers
     0.15s  1.38% 62.11%      0.15s  1.38%  runtime.stdcall3
     0.14s  1.28% 63.39%      0.21s  1.93%  runtime.heapBitsForAddr (inline)
     0.14s  1.28% 64.68%      0.14s  1.28%  runtime.markBits.isMarked (inline)
     0.13s  1.19% 65.87%      0.13s  1.19%  runtime.(*itabTableType).find
     0.13s  1.19% 67.06%      0.13s  1.19%  runtime.stdcall6
     0.12s  1.10% 68.17%      1.74s 15.96%  github.com/antlr/antlr4/runtime/Go/antlr.(*BaseATNConfigSet).Add
     0.11s  1.01% 69.17%      0.13s  1.19%  github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).canDropLoopEntryEdgeInLeftRecursiveRule
     0.10s  0.92% 70.09%      0.12s  1.10%  runtime.findObject
     0.10s  0.92% 71.01%      0.26s  2.39%  runtime.greyobject
     0.09s  0.83% 71.83%      0.09s  0.83%  github.com/antlr/antlr4/runtime/Go/antlr.(*BaseATNState).GetTransitions
     0.08s  0.73% 72.57%      0.21s  1.93%  runtime.getitab
     0.07s  0.64% 73.21%      0.08s  0.73%  github.com/antlr/antlr4/runtime/Go/antlr.(*BaseATNConfig).GetState
     0.07s  0.64% 73.85%      0.07s  0.64%  github.com/antlr/antlr4/runtime/Go/antlr.(*BaseTransition).getSerializationType
     0.07s  0.64% 74.50%      0.52s  4.77%  github.com/antlr/antlr4/runtime/Go/antlr.(*array2DHashSet).innerAdd
     0.07s  0.64% 75.14%      0.20s  1.83%  github.com/antlr/antlr4/runtime/Go/antlr.equalATNConfigs
     0.07s  0.64% 75.78%      0.07s  0.64%  runtime._ExternalCode
     0.07s  0.64% 76.42%      2.56s 23.49%  runtime.gcDrain
     0.07s  0.64% 77.06%      0.08s  0.73%  runtime.ifaceeq
     0.07s  0.64% 77.71%      2.09s 19.17%  runtime.newobject
     0.06s  0.55% 78.26%      0.06s  0.55%  github.com/antlr/antlr4/runtime/Go/antlr.murmurFinish (inline)
     0.06s  0.55% 78.81%      0.06s  0.55%  runtime.(*lfstack).pop (inline)
     0.06s  0.55% 79.36%      0.06s  0.55%  runtime.(*sweepLocker).tryAcquire (inline)
     0.06s  0.55% 79.91%      0.21s  1.93%  runtime.assertE2I
     0.06s  0.55% 80.46%      0.96s  8.81%  runtime.findrunnable
     0.05s  0.46% 80.92%      1.62s 14.86%  github.com/antlr/antlr4/runtime/Go/antlr.NewBaseATNConfig4
     0.05s  0.46% 81.38%      0.22s  2.02%  github.com/antlr/antlr4/runtime/Go/antlr.hashATNConfig
     0.05s  0.46% 81.83%      0.08s  0.73%  runtime.gcWriteBarrier
     0.04s  0.37% 82.20%      1.80s 16.51%  runtime.lock2
     0.04s  0.37% 82.57%      0.48s  4.40%  runtime.stealWork
     0.04s  0.37% 82.94%      0.09s  0.83%  runtime.unlock2
     0.03s  0.28% 83.21%      0.25s  2.29%  github.com/antlr/antlr4/runtime/Go/antlr.(*array2DHashSet).getBuckets (inline)
     0.03s  0.28% 83.49%      0.25s  2.29%  github.com/antlr/antlr4/runtime/Go/antlr.NewArrayPredictionContext
     0.03s  0.28% 83.76%      0.91s  8.35%  github.com/antlr/antlr4/runtime/Go/antlr.merge
     0.03s  0.28% 84.04%      0.11s  1.01%  runtime.(*mheap).allocSpan
     0.03s  0.28% 84.31%      0.60s  5.50%  runtime.notewakeup
     0.03s  0.28% 84.59%      1.27s 11.65%  runtime.schedule
     0.02s  0.18% 84.77%      0.64s  5.87%  github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).precedenceTransition
     0.02s  0.18% 84.95%      0.27s  2.48%  github.com/antlr/antlr4/runtime/Go/antlr.SingletonBasePredictionContextCreate (inline)
     0.02s  0.18% 85.14%      0.50s  4.59%  runtime.checkTimers
     0.02s  0.18% 85.32%      0.15s  1.38%  runtime.netpoll
     0.01s 0.092% 85.41%      0.27s  2.48%  github.com/antlr/antlr4/runtime/Go/antlr.(*DoubleDict).Get (inline)
     0.01s 0.092% 85.50%      0.42s  3.85%  github.com/antlr/antlr4/runtime/Go/antlr.(*ParserATNSimulator).ruleTransition
     0.01s 0.092% 85.60%      0.07s  0.64%  github.com/antlr/antlr4/runtime/Go/antlr.(*Predicate).hash
     0.01s 0.092% 85.69%      0.53s  4.86%  github.com/antlr/antlr4/runtime/Go/antlr.(*array2DHashSet).Add
     0.01s 0.092% 85.78%      0.12s  1.10%  github.com/antlr/antlr4/runtime/Go/antlr.NewBaseATNConfig5 (inline)
     0.01s 0.092% 85.87%      0.25s  2.29%  github.com/antlr/antlr4/runtime/Go/antlr.NewBaseSingletonPredictionContext
     0.01s 0.092% 85.96%      0.21s  1.93%  github.com/antlr/antlr4/runtime/Go/antlr.mergeArrays
     0.01s 0.092% 86.06%      1.91s 17.52%  runtime.(*gcWork).balance
     0.01s 0.092% 86.15%      0.26s  2.39%  runtime.(*mcache).nextFree
     0.01s 0.092% 86.24%      0.07s  0.64%  runtime.(*sweepLocked).sweep
     0.01s 0.092% 86.33%      0.07s  0.64%  runtime.gcWriteBarrierCX
     0.01s 0.092% 86.42%      0.37s  3.39%  runtime.injectglist
     0.01s 0.092% 86.51%      1.81s 16.61%  runtime.lock (inline)
     0.01s 0.092% 86.61%      0.17s  1.56%  runtime.newstack
     0.01s 0.092% 86.70%      1.93s 17.71%  runtime.preemptM
     0.01s 0.092% 86.79%      0.06s  0.55%  runtime.resettimer (inline)
     0.01s 0.092% 86.88%      0.44s  4.04%  runtime.runtimer
     0.01s 0.092% 86.97%      0.17s  1.56%  runtime.sweepone
     0.01s 0.092% 87.06%      0.16s  1.47%  runtime.sysUnused
     0.01s 0.092% 87.16%      3.12s 28.62%  runtime.systemstack
         0     0% 87.16%      0.13s  1.19%  github.com/antlr/antlr4/runtime/Go/antlr.NewBaseATNConfig1
         0     0% 87.16%      0.08s  0.73%  github.com/antlr/antlr4/runtime/Go/antlr.NewBasePredictionContext (inline)
         0     0% 87.16%      0.18s  1.65%  github.com/antlr/antlr4/runtime/Go/antlr.mergeSingletons
         0     0% 87.16%      1.85s 16.97%  runtime.(*gcControllerState).enlistWorker
         0     0% 87.16%      0.25s  2.29%  runtime.(*mcache).refill
         0     0% 87.16%      0.21s  1.93%  runtime.(*mcentral).cacheSpan
         0     0% 87.16%      0.15s  1.38%  runtime.(*mcentral).grow
         0     0% 87.16%      0.15s  1.38%  runtime.(*mheap).alloc
         0     0% 87.16%      0.11s  1.01%  runtime.(*mheap).alloc.func1
         0     0% 87.16%      0.18s  1.65%  runtime.(*pageAlloc).scavenge
         0     0% 87.16%      0.17s  1.56%  runtime.(*pageAlloc).scavengeOne
         0     0% 87.16%      0.16s  1.47%  runtime.(*pageAlloc).scavengeRangeLocked
         0     0% 87.16%      0.07s  0.64%  runtime._System
         0     0% 87.16%      0.06s  0.55%  runtime.assertE2I2
         0     0% 87.16%      0.15s  1.38%  runtime.bgscavenge
         0     0% 87.16%      0.39s  3.58%  runtime.bgscavenge.func1
         0     0% 87.16%      0.19s  1.74%  runtime.bgscavenge.func2
         0     0% 87.16%      0.17s  1.56%  runtime.bgsweep
         0     0% 87.16%      0.06s  0.55%  runtime.gcAssistAlloc.func1
         0     0% 87.16%      0.06s  0.55%  runtime.gcAssistAlloc1
         0     0% 87.16%      0.81s  7.43%  runtime.gcBgMarkWorker
         0     0% 87.16%      2.57s 23.58%  runtime.gcBgMarkWorker.func2
         0     0% 87.16%      0.06s  0.55%  runtime.gcDrainN
         0     0% 87.16%      0.16s  1.47%  runtime.gopreempt_m
         0     0% 87.16%      0.21s  1.93%  runtime.goschedImpl
         0     0% 87.16%      0.36s  3.30%  runtime.injectglist.func1 (inline)
         0     0% 87.16%      1.80s 16.51%  runtime.lockWithRank (inline)
         0     0% 87.16%      1.21s 11.10%  runtime.mcall
         0     0% 87.16%      0.15s  1.38%  runtime.morestack
         0     0% 87.16%      1.16s 10.64%  runtime.park_m
         0     0% 87.16%      0.07s  0.64%  runtime.preemptall
         0     0% 87.16%      1.92s 17.61%  runtime.preemptone
         0     0% 87.16%      0.24s  2.20%  runtime.resetspinning
         0     0% 87.16%      0.40s  3.67%  runtime.runOneTimer
         0     0% 87.16%      0.11s  1.01%  runtime.scavengeSleep
         0     0% 87.16%      1.74s 15.96%  runtime.semasleep
         0     0% 87.16%      0.62s  5.69%  runtime.semawakeup
         0     0% 87.16%      0.60s  5.50%  runtime.startm
         0     0% 87.16%      0.09s  0.83%  runtime.unlock (inline)
(pprof) Time: 15.072 s

It's not clear how one changes the sampling interval.

[kaby76]

I think the problem is that the there is excessive pressure on the heap and stack. This is because the definitions for many of the Antlr data structures are actually incorrect. Most fields of structs are structs themselves, whereas they should be pointers. Go is very much like C++, and one must explicitly use pointers, e.g., this is a struct, not a pointer to a struct. Contrast that with the Cpp target, where it is explicitly a pointer. The erroneous confusion of struct vs pointer to struct manifests in another problem that I mentioned here. Yes, this is just conjecture on my part. I'll try at some point to modify the code to redo the data structures to see if that fixes the performance, but it's low priority for me.

[parrt]

I was just going to say that wildly different times could indicate an issue with garbage collection. I also noticed that the go target who is kind of walkie when I tried it once. @jcking is taking a look at the target at the moment I think.

[kaby76]

I should note, for strings of (1 EQ 2 OR)* 1 EQ 2, the runtime climbs exponentially per each "1 EQ 2 OR" sub-string added, just as what @movelazar says. But, process memory is pretty much constant! And, it's only 10 or 20 MB! You can't get more than 15 pairs of "1 EQ 2" before it starts to hang. I attached a debugger to the process on Windows, and whenever I did a break, it would be in a lock routine in the OS, likely to keep memory allocation/GC re-entrant or to single thread the runtime.

[parrt]

zoiks!!! @jcking here's a good used case for testing and upgraded Go target.

[kylege]

Same issue here.

[parrt]

Yeah, somebody needs to take a serious look at rebuilding the Go target. I might take a walk at it but it's lower on my priority list. sorry!

[jimidle]

Did anyone look in to this more? If not, then I may do this myself. Go should be about the fastest target, assuming that it has implemented the various algorithms in the runtime as well as any other target.

[kaby76]

It's likely caused by a bug in the Go Antlr runtime. Turning on debug for the runtime (and cleaning out the Go runtime where we get a core dump because atn_config printing is passed a nil pointer), we see that the edges in the dfas are not correct.

See https://github.com/kaby76/issue-3718 for a complete side-by-side exact run comparison, driver code that was generated by my trgen program--handles all targets except "Swift".

CSharp here:

SLL altSubSets=[{1, 2}, {1, 2}, {1, 2}, {1, 2}, {1, 2}], configs=[(10,1,[52 $]), (14,1,[52 $]), (16,1,[52 $]), (56,1,[24 52 $]), (22,1,[52 $]), (10,2,[52 $],up=8), (14,2,[52 $],up=8), (16,2,[52 $],up=8), (56,2,[24 52 $],up=8), (22,2,[52 $],up=8)],dipsIntoOuterContext, predict=0, allSubsetsConflict=True, conflictingAlts={1, 2}
EDGE 0:[(26,1,[$]), (29,1,[$]), (32,1,[$]), (35,1,[$]), (38,1,[$]), (45,1,[$]), (7,2,[$],up=1), (12,2,[$],up=1), (26,2,[$],up=8), (29,2,[$],up=8), (32,2,[$],up=8), (35,2,[$],up=8), (38,2,[$],up=8), (45,2,[$],up=8), (19,2,[$],up=2), (40,2,[$],up=3), (47,2,[$],up=7)],dipsIntoOuterContext -> -1:[(10,1,[52 $]), (14,1,[52 $]), (16,1,[52 $]), (56,1,[24 52 $]), (22,1,[52 $]), (10,2,[52 $],up=8), (14,2,[52 $],up=8), (16,2,[52 $],up=8), (56,2,[24 52 $],up=8), (22,2,[52 $],up=8)],conflictingAlts={1, 2},dipsIntoOuterContext=>1 upon OR<2>
adding new DFA state: 4:[(10,1,[52 $]), (14,1,[52 $]), (16,1,[52 $]), (56,1,[24 52 $]), (22,1,[52 $]), (10,2,[52 $],up=8), (14,2,[52 $],up=8), (16,2,[52 $],up=8), (56,2,[24 52 $],up=8), (22,2,[52 $],up=8)],conflictingAlts={1, 2},dipsIntoOuterContext=>1
DFA=
s0-OR->:s4^=>1
s0-EQ->:s1^=>1
s2-OR->:s3=>2

Go here:

SLL altSubSets=[{1, 2} {1, 2} {1, 2} {1, 2} {1, 2}], previous=[(26,1,[$]), (29,1,[$]), (32,1,[$]), (35,1,[$]), (38,1,[$]), (45,1,[$]), (7,2,[$],up=1), (12,2,[$],up=1), (26,2,[$],up=8), (29,2,[$],up=8), (32,2,[$],up=8), (35,2,[$],up=8), (38,2,[$],up=8), (45,2,[$],up=8), (19,2,[$],up=2), (40,2,[$],up=3), (47,2,[$],up=7)],dipsIntoOuterContext, configs=[(10,1,[52 $]), (14,1,[52 $]), (16,1,[52 $]), (56,1,[24 52 $]), (22,1,[52 $]), (10,2,[52 $],up=8), (14,2,[52 $],up=8), (16,2,[52 $],up=8), (56,2,[24 52 $],up=8), (22,2,[52 $],up=8)],dipsIntoOuterContext, predict=0, allSubsetsConflict=true, conflictingAlts={1, 2}
EDGE 0:[(26,1,[$]), (29,1,[$]), (32,1,[$]), (35,1,[$]), (38,1,[$]), (45,1,[$]), (7,2,[$],up=1), (12,2,[$],up=1), (26,2,[$],up=8), (29,2,[$],up=8), (32,2,[$],up=8), (35,2,[$],up=8), (38,2,[$],up=8), (45,2,[$],up=8), (19,2,[$],up=2), (40,2,[$],up=3), (47,2,[$],up=7)],dipsIntoOuterContext -> -1:[(10,1,[52 $]), (14,1,[52 $]), (16,1,[52 $]), (56,1,[24 52 $]), (22,1,[52 $]), (10,2,[52 $],up=8), (14,2,[52 $],up=8), (16,2,[52 $],up=8), (56,2,[24 52 $],up=8), (22,2,[52 $],up=8)],conflictingAlts={1, 2},dipsIntoOuterContext=>1 upon <2>
DFA=
s0-->:s1^=>1
s0-->:s1^=>1
s2-->:s3=>2

Most of the debug output has a 1 to 1 correspondence between the Go and CSharp runtimes (although, it would really really help to be consistent in debug output formatted strings to make life easier). The major diff occurs where a DFA is added in CSharp but not in Go. Note, the Go runtime does print out new DFA creation, but after a few, this is the first where it's not recorded. There are 11 DFA states created in the CSharp target, 9 DFA states created in the Go target.

(And, anticipating the argument "But Java code is the gold standard!", I also did it for that target. There are 11 new DFA states added, just as with CSharp, and the with this important add also in the Java debug output.)

Unless this bug is fixed, it's unlikely to know for sure whether this is the "performance issue". I have been programming for ~50 years. There is lttle sense in tracking down a "performance issue" when the basic behavior of the software is not working.

[kaby76]

The problem is here and it goes to how DFAState objects are kept in a hash table.

Let's compare the CSharp and Go target code side by side:

CSharp	Go
AddDFAState(dfa, to)	p.addDFAState(dfa, to)
dfa.states.Get(D)	dfa.getState(hash)
dictionary.TryGetValue(key, out value)	no equality compare

Hashing is never perfect. In this case, there is a collision between two dfa states, one that exists in a table, and another which should be entered into the table. After computing the hash value of the DFAState to enter, you have to perform an equality check to verify that the state you want to enter is already in the table, i.e., has an identical hash but are equality different.

Note here in C#, "states" is a map from DFAState to DFAState. The C# runtime actually performs an equality comparison and notices the hash is identical with something that is already in the table, but the value of the new DFAState is equality compare different than the one that is already in the table. So, a new state is created.

But, in Go, it is a map from int to DFAState. Collisions in hash values are never checked because it's a mapping of hash value to DFAState not DFAState to DFAState. So, a new state is not created.

@parrt This is a serious problem.

[parrt]

Thanks, @kaby76 for tracking this down! yeah, I was under impression Go target was kinda screwed up.

Does anybody know Go well enough to fix this hash issue?

[KvanTTT]

@kaby76 nice investigation, thanks. I think we must include tests on hashing into runtime testsuite.

[jcking]

The Go runtime does hashing poorly and in the case where kaby76 points out it assumes hashes are unique, which is just wrong. I believe the Go runtime uses a 32-bit hash even on 64-bit platforms. The top 32 bits are simply ignored and chopped off. In general, most of the Go runtime needs to be re-written. I had partially done it, but I do not have the free time and will likely not have it for quite some time.

Additionally the hierarchy of the structs needs to have another look taken at it. There is lots of embedding by pointer. It may make more sense to dereference so that there is only a single allocation. However I am not familiar enough with Golang GC to know if that helps.

[jimidle]

Thanks, @kaby76 for tracking this down! yeah, I was under impression Go target was kinda screwed up.

Does anybody know Go well enough to fix this hash issue?

I am pretty sure I do :). Now, do I have the time? Hmmm - I did the C runtime for v3 because nobody else had the time... It sounds like the consensus is that the Go runtime may need either a rewrite or some serious work.

What would those with an interest in the Go runtime vote for? A new runtime, or a revamp.

I can look at the hashing anyway - though this looks more like an oversight in how go and hashing works (that's a guess - I have not looked at the problem that @kaby76 describes, but that description looks sound to me).
I also agree with earlier comments that the structs and embedded structs may not be organized as well as they might - but that probably is better taken care of with a rewrite.

[jimidle]

The problem is here and it goes to how DFAState objects are kept in a hash table.

Let's compare the CSharp and Go target code side by side:

CSharp Go
AddDFAState(dfa, to) p.addDFAState(dfa, to)
dfa.states.Get(D) dfa.getState(hash)
dictionary.TryGetValue(key, out value) no equality compare
Hashing is never perfect. In this case, there is a collision between two dfa states, one that exists in a table, and another which should be entered into the table. After computing the hash value of the DFAState to enter, you have to perform an equality check to verify that the state you want to enter is already in the table, i.e., has an identical hash but are equality different.

Note here in C#, "states" is a map from DFAState to DFAState. The C# runtime actually performs an equality comparison and notices the hash is identical with something that is already in the table, but the value of the new DFAState is equality compare different than the one that is already in the table. So, a new state is created.

But, in Go, it is a map from int to DFAState. Collisions in hash values are never checked because it's a mapping of hash value to DFAState not DFAState to DFAState. So, a new state is not created.

@parrt This is a serious problem.

OK - so, reminding myself how Java and C# work since I switched to go, C# Dictionary and Java Map<> allow the key to be objects. Just looking at Java any object that supplies consistent/conformant hashCode() and equals() can be a key. As stated above, we can see that because both calls have to be true, there won't be a clash in the map if hashCode() is equal for two objects but equals() is not. So, the DFAState object itself can be used as the map key.

In the go runtime, the use of only the hashCode() equivalent is guaranteed to generate hash clashes (eventually). Hence it doesn't work. I think I can come up with a better way of modeling the dfa.states for go and will probably have to look at all other collections.

Does anyone object to using an external dependency to replace Go builtin maps with something more sane for this case? The dev branch seems to have already been converted to modules, so this isn't really a big deal in my book.

[jimidle]

One question here is whether the Go runtime is supposed to allow invocations from multiple go routines at the same time? In its current form, without too much inspection, it would seem that it isn't, even if it was supposed to be a design goal.

[kaby76]

The Dictionary<> implementation for C# is here. I think it's actually being used more like a HashSet because the state number is not used in the hash computation, but that's how it's coded in Java.

I made a crude, freshman-oriented implementation of a hash table for *DFAState using hash buckets, replaced the definition for "states", and tried it out. It could all be wrong, but took me a couple of hours of fumbling around with Go--which I cannot stand because ':=' assignments don't tell me what the type of a variable is, and the forced "one true brace style" style. The hack fixes the problem in collisions, invalid configs/DFAStates--and the performance issue. The runtimes are on par with the other runtimes. The hack is here. P.S.: someone updated the serialization/deserialization of some tables, and didn't update the tests--"go test" does not work.

[parrt]

Hi @jimidle !! Yep, fork then cut new branch for a PR from dev branch (not master). Maybe we start by using @kaby76 awesome fix.

Yep, multiple threads should be able to use the DFAState stuff but likely it ain't right. Very tricky.

[jimidle]

Right Ter. I have a fix. However, it is literally designed to fix this before I look to a revamp. I’m not convinced it needs a complete restart yet. This doesn’t fix hashing or anything else. Just to prove that this is a fix. After that, I will start to analyze the code. I would be surprised if GC was an issue these days. With a large grammar and a set of large programs, how many DFAstates are we talking around. 1000s? 100,000s, 1,000,000? Jim

…

On Thu, Aug 11, 2022 at 09:13 Terence Parr ***@***.***> wrote: Hi @jimidle <https://github.com/jimidle> !! Yep, fork then cut new branch for a PR from dev branch (not master). Maybe we start by using @kaby76 <https://github.com/kaby76> awesome fix. Yep, multiple threads should be able to use the DFAState stuff but likely it ain't right. Very tricky. — Reply to this email directly, view it on GitHub <#3718 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMDXHZWW35NQQCBAHOLVYRHSFANCNFSM5WGGAXKQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[jimidle]

Hi @jimidle !! Yep, fork then cut new branch for a PR from dev branch (not master). Maybe we start by using @kaby76 awesome fix.

Yep, multiple threads should be able to use the DFAState stuff but likely it ain't right. Very tricky.

Up to you which fix to take mate. I will make the PR anyway so you guys can take a look - I don't mind which path is taken.

My fix is very simple and just uses a look aside slice in the hash bucket. It is a very safe change and does not involve new data structures., outside go builtins. Hash collisions are fairly rare - a tiny look aside table won't add much overhead - probably not measurable. Anyway, I will test against the original grammar mentioned above.

The fix is in the same place as @kaby76 but the changes are probably smaller as I did not write a replacement table system etc - internally, go maps are a HashTable anyway, but the current code tries to do the hashing itself. I just made a few tweak changes such that the actual values are compared on any hash collision and any search. The comparison mirrors the Java implementation.

My change is only for that specific map - the whole code set probably needs a full inspection - but at the moment I don't think it is so terrible that it needs a rewrite - a lot of it is sound.

I would like to volunteer to take on a bit of a revamp of the runtime, unless anyone already working on this runtime wants to take that on before me and has the time? I don't want to step on anyone's toes of course.

I was looking at the last time I was involved with ANTLR - yikes - how did that many years go by?

[jimidle]

here

@kaby76 - So, in your collection implementation, are you not using the Equals() in atn_config_set.go? The reason I ask is that, my hack just adds a bucket in to the states map, and then instead of only using the hash, it looks to see if they are equal by value. I discovered that the go implementation of Equals in atn_config_set.go is quite different from the java version in that it does not actually compare the configs - I don't see how that can work. In go, we just have:

	// configs is the added elements.
	configs []ATNConfig

And the Equals() does this:

func (b *BaseATNConfigSet) Equals(other interface{}) bool {
	if b == other {
		return true
	} else if _, ok := other.(*BaseATNConfigSet); !ok {
		return false
	}

	other2 := other.(*BaseATNConfigSet)

	return b.configs != nil &&
		// TODO: b.configs.equals(other2.configs) && // TODO: Is b necessary?
		...

So the set of configs are not actually compared. Whereas in Java, there is a custom comparator class for the declaration:

/** Track the elements as they are added to the set; supports get(i) */
	public final ArrayList<ATNConfig> configs = new ArrayList<ATNConfig>(7);

...
		@Override
		public boolean equals(ATNConfig a, ATNConfig b) {
			if ( a==b ) return true;
			if ( a==null || b==null ) return false;
			return a.state.stateNumber==b.state.stateNumber
				&& a.alt==b.alt
				&& a.semanticContext.equals(b.semanticContext);
		}
...

And the equals() for ATNConfigSet.java is then:

...
		boolean same = configs!=null &&
			configs.equals(other.configs) &&  // includes stack context
			this.fullCtx == other.fullCtx &&
			this.uniqueAlt == other.uniqueAlt &&
			this.conflictingAlts == other.conflictingAlts &&
			this.hasSemanticContext == other.hasSemanticContext &&
			this.dipsIntoOuterContext == other.dipsIntoOuterContext;
...

So, my simple solution to equality, will not work unless I also fix the Equals() for BaseATNConfigSet.

So, if your hack fix gets around this in some way, then I am disinclined to pursue my hack fix further - if the go runtime is to mirror the way the Java runtime works, I think that there are quite a few of these TODOs that will need addressing - and it is going to take more than either of us hacking at this issue to make it work correctly. I will pursue this more though as it will be useful to understand what the current runtime is up to!

[kaby76]

So, in your collection implementation, are you not using the Equals() in atn_config_set.go?

@jimidle I think I just call the DFAState equals comparison, which is defined in DFAState. That code calls the ATNConfigSet Equals() method, which is similar to that in the C# code. But, to check, a side-by-side debug session between Java and Go should be done (at the DFAState compare methods in both targets). The code "works", but you know how assumptions can go.

Note, I looked everywhere to see if map in golang could be defined as states map[*DFAState]*DFAState instead of states map[int]*DFAState. I think I tried, and almost got there, but I didn't know how to override the equals() method that is apparently called in the map code here, and didn't try the obvious definition func (p *DFAState) equals(other *DFAState) bool. It probably can, but I'm probably the worst "go to guy" for Go--and certainly for Antlr interals. I just cannot understand Go's syntax.

[jimidle]

here

@kaby76 - both my local hack and your hack seem to fix the collisions, but neither seem to fix the performance problems. The provided sample repo at the start of this issue takes 71.9 seconds to run with your hack and 69.4 seconds with mine. Basically the same.

What numbers did you get on the repo above with your hack? I definitely know that I am running your version - perhaps I am missing something here?

The performance problem on the face of it is because closureCheckingStopState and it's call tree create 285,782,265 objects. and closureWork creates 211,925,408 objects. NOw, I suggest that it should not be creating that many and something else is very wrong here.

But I just wanted to check to see whether your hack fixes the performance problems locally for you?

[jimidle]

So, in your collection implementation, are you not using the Equals() in atn_config_set.go?

@jimidle I think I just call the DFAState equals comparison, which is defined in DFAState. That code calls the ATNConfigSet Equals() method, which is similar to that in the C# code. But, to check, a side-by-side debug session between Java and Go should be done (at the DFAState compare methods in both targets). The code "works", but you know how assumptions can go.

Note, I looked everywhere to see if map in golang could be defined as states map[*DFAState]*DFAState instead of states map[int]*DFAState. I think I tried, and almost got there, but I didn't know how to override the equals() method that is apparently called in the map code here, and didn't try the obvious definition func (p *DFAState) equals(other *DFAState) bool. It probably can, but I'm probably the worst "go to guy" for Go--and certainly for Antlr internals. I just cannot understand Go's syntax.

You cannot override the equals method for map - the key must implement in the built in comparable interface - it is low level. You either do what you did, which is make a hashtable that works for this case, or change the storage. All I did was change the map to be [int][]*DFAState and then expand the slice upon a collision where value comparison via equals shows that it is hash collision. Similarly on search, just chase the slice - because there won't be millions of clashes.

I am a big fan of go - I can see why some people are not though ;)

If you can confirm that your hack runtime also does not fix the performance issue, then I will find out why those routines are allocating so many objects. The answer might mean just starting again - maybe reusing some of the logic that seems sound. I don't quite trust the comparators (equals() etc), but I have them working.

[jimidle]

I am going to build the Java version of everything and debug step through side by side - that should tell us where the go runtime is going wrong. There are more bugs here than just that map ignoring hash collisions. This will take some time.

[KvanTTT]

Yes - that is what i was running, then it gets to the test runnner, which creates a blank go.mod and sets GOROOT in an environment, which is then looking for a test/parser, which is nowhere to be found. That runner is totally wrong - mostly you never set GOROOT at all, but definitely not for finding packages.

Please fix it if you know how without degrading performance. I changed it some time ago to get rid of excess cloning of go runtime files in every test, see #3365 I didn't find a better solution.

[jimidle]

Yes - that is what i was running, then it gets to the test runner, which creates a blank go.mod and sets GOROOT in an environment, which is then looking for a test/parser, which is nowhere to be found. That runner is totally wrong - mostly you never set GOROOT at all, but definitely not for finding packages.

Please fix it if you know how without degrading performance. I changed it some time ago to get rid of excess cloning of go runtime files in every test, see #3365 I didn't find a better solution.

No worries @KvanTTT - I see what you did and I see why. With newer go compilers, we have better options. It is a bit convoluted in there because of the maven test runner etc. But I will neaten it up and take advantage of modules etc etc

I removed the GOROOT stuff and now rely on a replace in the go.mod for a test. Also, there is no longer a need to change the generated code.

[jimidle]

A simple indexing error in the Lexer ATN simulator because of my change to use new collection code is now fixed.
The go test runner in the test suite has been revamped to use go modules and no longer tries to build its own go installation. This avoids a huge copy of GOROOT to a temporary location, and so the tests are faster for not having to make that large copy.

All tests pass. There do not seem to be any performance tests per se, but the test grammar in this thread now runs in milliseconds on my system:

/usr/local/opt/go/libexec/bin/go build -o /private/var/folders/h7/r6kmfvb50_9cncx1bpqlhbqc0000gn/T/GoLand/___go_build_main_go /Users/jim/tmp/perf-repro/main.go #gosetup
/private/var/folders/h7/r6kmfvb50_9cncx1bpqlhbqc0000gn/T/GoLand/___go_build_main_go
Success: compile

Success: run

Took 2 milliseconds to compile, 615 nanoseconds to run.

I believe that I can get this time down a little and also reduce memory allocations. Because Github only lets you have one PR outstanding at a time, I have to wait until this one is accepted before pushing any more changes for those improvements. It could also be the case that there is no point pursuing improvements in this code base, and maybe time is better spent on a revamp.

@parrt - I think that the PR is now ready mate.

[jimidle]

The next thing that could perhaps give a major improvement in allocations is the go implementation of array2DHashSet, which seems to be a naïve implementation of the Java version, it causes about 17,900 allocations, which is the vast majority of the allocations to run the grammar at the top of this thread. I am also not sure if it is using the correct hash and comparator (this is buried in the generic implementation in Java).

@parrt Without me trawling all the way through the code, does the Java implementation of this use the hashCode() and equals() of the object type it is storing? Or is it overridden somewhere? The go version is using a hash() and compare() that do not match the hashCode() and equals() of ATNConfig in Java.

Never mind Ter - I see it has its own hashCode and comparator, which checks to see if the object is an ATNConfig. I can fix the go version to use the same hash and comparator. See if that cuts down the allocations.

[jimidle]

The go version of array2DHashSet is preallocating buckets and bucket capacity, even though it won't need them - it is treating the buckets as arrays instead of slices but then the algorithm is expecting a bucket to be initialized. Because there are lots of these allocated, every new allocation for this causes tons of empty buckets to be allocated.

It needs a rethink to do lazy allocation - I will need to study how the Java version is doing this. I assume it isn't allocating all those buckets if it does not need them.

[jimidle]

The functionality provided by that collection is already provided by my new generic container, which does not make any allocations unless they are needed, so I will carefully go through the code and replace its use with the generic store.

[parrt]

@parrt Without me trawling all the way through the code, does the Java implementation of this use the hashCode() and equals() of the object type it is storing? Or is it overridden somewhere?

It should use standard code hashCode() and equals():

	@Override
	public int hashCode() {
		int hash = MurmurHash.initialize(7);
		hash = MurmurHash.update(hash, configs.hashCode());
		hash = MurmurHash.finish(hash, 1);
		return hash;
	}

	/**
	 * Two {@link DFAState} instances are equal if their ATN configuration sets
	 * are the same. This method is used to see if a state already exists.
	 *
	 * <p>Because the number of alternatives and number of ATN configurations are
	 * finite, there is a finite number of DFA states that can be processed.
	 * This is necessary to show that the algorithm terminates.</p>
	 *
	 * <p>Cannot test the DFA state numbers here because in
	 * {@link ParserATNSimulator#addDFAState} we need to know if any other state
	 * exists that has this exact set of ATN configurations. The
	 * {@link #stateNumber} is irrelevant.</p>
	 */
	@Override
	public boolean equals(Object o) {
		// compare set of ATN configurations in this set with other
		if ( this==o ) return true;

		if (!(o instanceof DFAState)) {
			return false;
		}

		DFAState other = (DFAState)o;
		// TODO (sam): what to do when configs==null?
		boolean sameSet = this.configs.equals(other.configs);
//		System.out.println("DFAState.equals: "+configs+(sameSet?"==":"!=")+other.configs);
		return sameSet;
	}

[parrt]

@movelazar a PR fixing got merged into dev branch. can you test?

[jimidle]

@movelazar a PR fixing got merged into dev branch. can you test?

Excellent - I will now fix the 2darray thing to bring down the allocations, then I think I will check to see if there are any other bugs that I could fix quickly. Then let's move to a redo.

@parrt - Do you delete the incoming branch after merging it to dev? I use git flow on my end, so I will pull from the repo, then delete my feature branch.

[parrt]

You can delete if you'd like...it's just in your fork so doesnt' affect main repo. :)

[parrt]

It looks like your merge into dev is all green for github CI :) https://github.com/antlr/antlr4/actions/runs/2862709143

[jimidle]

It looks like your merge into dev is all green for github CI :) https://github.com/antlr/antlr4/actions/runs/2862709143

Excellent.

Ter - I am going to now take a little time to reorganize all this hashing and collections and so on. Because it was a bit of a mess before, it has ended up being more of a mess. So, I will keep my newhash branch alive and send another PR that does this:

• Implements all the custom comparators that Java has - there are a number of places where go is replacing Array2DHashMap where this has got very convoluted
• Verifies that hash() and equals() for each of the structs that are equivalent to Java objects are using the same algorithms as the Java classes - I am pretty sure that this is correct now, but I want to do a full review of them all
• get rid of the go implementation of Array2DHashMap - it is basically a copy of the Java implementation without using go and so is responsible for something like 75% of all memory allocations in a run of a recognizer

This is all related to this performance issue, so I think we can keep this issue open and I will use the same branch to track the changes.

I should be able to finish this today my time and then we can be assured that all the hashing and collection stuff is hunk dory.

[parrt]

Great!

[jimidle]

Great!

Sorry for the delay in submitting the latest PR. Unfortunately COVID got in the way!

However, the latest PR replaces most of the collection related code with new generic based collections that behave
the same way as the Java versions, though they don't always use the same algorithms for collections. This reduces
memory allocations and therefore requires less memory and less work by the GC.

There are still improvements that I can see will help both performance and memory, but I think this PR is enough of a change at one go. From here, PRs should be smaller. I am now thinking that there might not be any reason to start again on the go runtime. It is work to improve what we have, but most of the logic is intact and if there are structural changes required, we can implement them in the existing code base. I will gradually improve documentation and doc comments, some code can be redone with newer Go language support etc. I am willing to be talked out of this viewpoint, but right now, I don't think a complete redo is necessary. i will spend more time on this though and see if I change my mind.

Also - I think we can close this issue now @parrt

[parrt]

Hi Jim! Sorry to hear about the Covid!!

Good news on the performance improvements and glad we can keep the same runtime. Does your PR keep the same interface? I want to make sure I don't break a bunch of projects inside Google.

Closing this via #3829

[jimidle]

No change to the external interface Ter. This is all just internal collections.

…

On Sun, Aug 21, 2022 at 00:15 Terence Parr ***@***.***> wrote: Closed #3718 <#3718> as completed. — Reply to this email directly, view it on GitHub <#3718 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMBNHAHMBB3TGHFMFU3V2EAA3ANCNFSM5WGGAXKQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>