Go: exponentially bad/absymal performance as of ...

[kirides]

• target information: Go go get -u github.com/antlr/antlr4/runtime/Go/antlr/v4@d5dd253 (same with plain /v4)
• smallest possible grammar and code that reproduces the behavior

Expected

Parsing 19 files should take around 0.2s

Actual

Parsing 19 files takes more than 11s, and exponentially more the more files there are

Happens as of f19dc0e (~5.5s)
Got worse with 56df72c (~10s)

See example in attached zip: (includes sample files and grammar)
issue.zip

To test old and new behaviour, just toggle the commented lines in go.mod and run
go mod tidy && go test -timeout 30s -run ^TestParsing$ issue -count=1

EDIT: after removing all leading conditional values (summary comments) and putting them into a hidden channel, performance was still a bit lower (~20%) but much, MUCH better than whatever that issue is

[kaby76]

The grammar has one big ambiguity, but it's probably not the problem. statement can derive funcCall and expression, but expression can derive value, which can also derive funcCall. It reads the entire statement just to decide which one to pick of funcCall vs expression.

[kirides]

removing funcCall from Statement and nameNode from expression didn't really do anything

[kaby76]

I added code to separate the parse from the tree walker, since this has nothing to do with tree walking, and added code to time the parse call. I then ran the code with all 19 files in data/ vs only one file in data/, data/EngineAdr_G1.d, and compared the time performing the one parse of that file versus the parse of that file in an aggregate of 19 different parses. In the 19-file parse run, EngineAdr_G1.d ran in 3.500 s. When run alone, it ran in 0.564 s. (I also ran this against my templated-generated driver with the grammar, which runs only one parse per process run, and the parse for EngineAdr_G1.d was 0.5s--the same result.) That's a pretty significant difference. If anything, cached data from previous parses should improve the performance of subsequent parses. This says for Go, it's actually hurting. My conclusion is that either there is significant pressure on the memory allocator, or that cached parse data alters the parse for the Go target when compared to another target. I haven't checked internally the actual closure computations side-by-side between Go and CSharp or Java, but I will check that next. BTW folks, we really really need to get the debug output on ParserATNSimulator to look the same across targets. It is not currently. I mentioned this several times before. We need this fixed in order to trace identical operations across targets and to point out porting issues.

[kaby76]

I modified the trgen templates to create drivers for CSharp and Go that parse multiple files, then tested how previous parses affect the timing of subsequent parses. For a parse of Buffs.d then EngineAdr_G1.d in CSharp, the parse of EngineAdr_G1.d is 5x faster than if parsing EngineAdr_G1.d alone. That is complete expected. But, for a parse of Buffs.d then EngineAdr_G1.d in Go, the parse of EngineAdr_G1.d is 3x slower! That is completely unexpected. Somehow, warm-up caching is not working. This is serious.

[kaby76]

I turned on debugging for both CSharp and Go targets for Antlr 4.11.1, rebuilt the trgen-generated apps, and ran the application on the sequence of files "Buffs.d EngineAdr_G1.d", capturing the output. After extracting out key events from the output (such as "adaptivePredict ...", "testing ...", "DFA after predictATN ..."), and editing trivial strings out (sed 's/Const<34>/34/', ...), there are no differences in how the algorithms run.

It's likely that the data structures associated with caching are to blame, e.g., DoubleDict/map, etc., or Go memory management is to blame.

[kirides]

Inside the issues.zip are two profiling results, those can be analyzed using
go tool pprof -http=":8000" profile_xyz

it shows that a lot of the time is spend in equality checks.
Sadly i don't know if the behavior is to be expected.

Top VIew

Flat	Flat%	Sum%	Cum	Cum%	Name	Inlined?
1.07s	18.84%	18.84%	1.40s	24.65%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfig).Equals	
0.98s	17.25%	36.09%	1.15s	20.25%	runtime.(*itabTableType).find	
0.61s	10.74%	46.83%	4.16s	73.24%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfigSet).Compare	
0.39s	6.87%	53.70%	2.44s	42.96%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNConfig).Equals	
0.33s	5.81%	59.51%	1.48s	26.06%	runtime.getitab	
0.26s	4.58%	64.08%	0.65s	11.44%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerActionExecutor).Equals	
0.24s	4.23%	68.31%	4.96s	87.32%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*DFAState).Equals	
0.22s	3.87%	72.18%	0.39s	6.87%	golang.org/x/exp/slices.EqualFunc[...]	
0.20s	3.52%	75.70%	1.67s	29.40%	runtime.convI2I	
0.20s	3.52%	79.23%	4.36s	76.76%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfigSet).Equals	
0.18s	3.17%	82.39%	0.18s	3.17%	runtime.add	(inline)
0.14s	2.46%	84.86%	2.67s	47.01%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*JStore[...]).Get	
0.13s	2.29%	87.15%	5.09s	89.61%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ObjEqComparator[...]).Equals2	
0.13s	2.29%	89.44%	2.69s	47.36%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*JStore[...]).Put	
0.10s	1.76%	91.20%	0.17s	2.99%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerActionExecutor).Equals.func1	
0.06s	1.06%	92.25%	0.06s	1.06%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNState).GetStateNumber	
0.05s	0.88%	93.13%	0.05s	0.88%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerSkipAction).Equals	
0.04s	0.70%	93.84%	0.04s	0.70%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BasicState).GetStateNumber	
0.03s	0.53%	94.37%	0.03s	0.53%	runtime.stdcall1	
0.03s	0.53%	94.89%	0.03s	0.53%	runtime.heapBitsSetType	
0.02s	0.35%	95.25%	0.04s	0.70%	runtime/pprof.(*profMap).lookup	
0.01s	0.18%	95.42%	0.09s	1.58%	runtime.schedule	
0.01s	0.18%	95.60%	0.03s	0.53%	runtime.resetForSleep	
0.01s	0.18%	95.77%	0.03s	0.53%	runtime.checkTimers	
0.01s	0.18%	95.95%	5.37s	94.54%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).addDFAEdge	
0	0.00%	95.95%	0.06s	1.06%	runtime/pprof.profileWriter	
0	0.00%	95.95%	0.04s	0.70%	runtime/pprof.(*profileBuilder).addCPUData	
0	0.00%	95.95%	0.04s	0.70%	runtime.wakep	
0	0.00%	95.95%	0.03s	0.53%	runtime.systemstack	
0	0.00%	95.95%	0.04s	0.70%	runtime.startm	
0	0.00%	95.95%	0.03s	0.53%	runtime.semawakeup	
0	0.00%	95.95%	0.03s	0.53%	runtime.resetspinning	
0	0.00%	95.95%	0.11s	1.94%	runtime.park_m	
0	0.00%	95.95%	0.03s	0.53%	runtime.notewakeup	
0	0.00%	95.95%	0.03s	0.53%	runtime.newobject	
0	0.00%	95.95%	0.11s	1.94%	runtime.mcall	
0	0.00%	95.95%	0.05s	0.88%	runtime.mallocgc	
0	0.00%	95.95%	0.05s	0.88%	runtime.findRunnable	
0	0.00%	95.95%	0.03s	0.53%	runtime.(*mheap).allocSpan	
0	0.00%	95.95%	0.03s	0.53%	runtime.(*mheap).alloc.func1	
0	0.00%	95.95%	5.47s	96.30%	github.com/kirides/DaedalusLanguageServer/langserver.(*regularGrammarParser).NewDaedalusFile	
0	0.00%	95.95%	0.74s	13.03%	github.com/kirides/DaedalusLanguageServer/langserver.(*parseResultsManager).validateFiles.func1	
0	0.00%	95.95%	0.74s	13.03%	github.com/kirides/DaedalusLanguageServer/langserver.(*parseResultsManager).ValidateScript	
0	0.00%	95.95%	4.74s	83.45%	github.com/kirides/DaedalusLanguageServer/langserver.(*parseResultsManager).ParseSource.func1	
0	0.00%	95.95%	5.48s	96.48%	github.com/kirides/DaedalusLanguageServer/langserver.(*parseResultsManager).ParseScriptListener	(inline)
0	0.00%	95.95%	4.74s	83.45%	github.com/kirides/DaedalusLanguageServer/langserver.(*parseResultsManager).ParseScript	
0	0.00%	95.95%	5.48s	96.48%	github.com/kirides/DaedalusLanguageServer/langserver.(*RegularParser).Parse	
0	0.00%	95.95%	0.04s	0.70%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).expression	
0	0.00%	95.95%	2.52s	44.37%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).StatementBlock	
0	0.00%	95.95%	0.07s	1.23%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).Statement	
0	0.00%	95.95%	0.40s	7.04%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).InlineDef	
0	0.00%	95.95%	1.06s	18.66%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).IfBlockStatement	
0	0.00%	95.95%	0.88s	15.49%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).IfBlock	
0	0.00%	95.95%	2.52s	44.37%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).FunctionDef	
0	0.00%	95.95%	0.04s	0.70%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).ExpressionBlock	
0	0.00%	95.95%	0.22s	3.87%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).ElseIfBlock	
0	0.00%	95.95%	0.11s	1.94%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).ElseBlock	
0	0.00%	95.95%	5.47s	96.30%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).DaedalusFile	
0	0.00%	95.95%	0.41s	7.22%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).ClassDef	
0	0.00%	95.95%	4.91s	86.44%	github.com/kirides/DaedalusLanguageServer/daedalus/parser.(*DaedalusParser).BlockDef	
0	0.00%	95.95%	0.03s	0.53%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).execATN	
0	0.00%	95.95%	0.03s	0.53%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).AdaptivePredict	
0	0.00%	95.95%	5.42s	95.42%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).execATN	
0	0.00%	95.95%	5.40s	95.07%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).computeTargetState	
0	0.00%	95.95%	5.36s	94.37%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).addDFAState	
0	0.00%	95.95%	5.42s	95.42%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).Match	
0	0.00%	95.95%	0.16s	2.82%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).setup	
0	0.00%	95.95%	0.16s	2.82%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).lazyInit	(inline)
0	0.00%	95.95%	5.42s	95.42%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).fetch	
0	0.00%	95.95%	5.42s	95.42%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).Sync	
0	0.00%	95.95%	0.16s	2.82%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).LT	
0	0.00%	95.95%	5.26s	92.61%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).Consume	
0	0.00%	95.95%	5.23s	92.08%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseParser).Match	
0	0.00%	95.95%	0.18s	3.17%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseParser).EnterRule	
0	0.00%	95.95%	5.23s	92.08%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseParser).Consume	
0	0.00%	95.95%	5.42s	95.42%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseLexer).safeMatch	
0	0.00%	95.95%	5.42s	95.42%	github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseLexer).NextToken	

[kaby76]

That profiling data might come in handy. What tool did you use so I can understand what it means? [Never mind--I see now.]

I'm pretty confident the algorithms are now working the same between the Go target and CSharp for 4.11.1. That's great news because prior to 4.11.1, it was very very different. Many important bugs found.

So caching is working, but it's not well.

The peak working memory usage for the Go target is roughly 2x the peak memory usage for the CSharp target. But, it's only ~50MB, which is basically nothing in a modest 16GB, AMD Ryzen 7 2700 system. So, resources are not the problem.

[kirides]

to collect the data i used a the pprof endpoint of my language server, very simple:
main.go, just copy into the issues dir where go.mod is and run with go run main.go

EDIT: or just modify the test / create a new one, and execute go test -v -run=^TestParsing$ -timeout=30s -cpuprofile profile -count=1

package main

import (
	"net/http"
	_ "net/http/pprof"
)

func main() {
	// pprof url:             http://127.0.0.1:5000/debug/pprof
	// direct url to profile: http://127.0.0.1:5000/debug/pprof/profile?seconds=10 (default is 30)

	http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
		// Start your work here
		// start profile, then call http://127.0.0.1:5000/
	})

	http.ListenAndServe("127.0.0.1:5000", nil)
}

to analyze the profile data, run go tool pprof -http=":8000" profile

msedge_ZKYFux3UYf.mp4

[kaby76]

"To start tuning the Go program, we have to enable profiling. If the code used the Go testing package’s benchmarking support, we could use gotest’s standard -cpuprofile and -memprofile flags. In a standalone program like this one, we have to import runtime/pprof and add a few lines of code" https://go.dev/blog/pprof

Geezuz, doesn't Go have a stand-alone CPU sampling profiler of an executable program that doesn't require code modification of source code? I guess that's why this was written as a unit test application.

[kirides]

Geezuz, doesn't Go have a stand-alone CPU sampling profiler of an executable program that doesn't require code modification of source code? I guess that's why this was written as a unit test application

yes ^^'

EDIT: updated the post above and added "just modify the test / create a new one, and execute go test -v -run=^TestParsing$ -timeout=30s -cpuprofile profile -count=1"

[kaby76]

I modified the trgen driver to create cpu profiling, and it works--but you cannot call Exit(), otherwise you get a zero-length profiling output file.

$ ./Test.exe ../examples/*
HI THERE
Time: 0.044 s
Parse succeeded.
Time: 0.070 s
Parse succeeded.
Time: 0.134 s
Parse succeeded.
Time: 0.588 s
Parse succeeded.
Time: 0.090 s
Parse succeeded.
Time: 0.271 s
Parse succeeded.
Time: 1.190 s
Parse succeeded.
Time: 0.436 s
Parse succeeded.
Time: 1.052 s
Parse succeeded.
Time: 0.170 s
Parse succeeded.
Time: 0.173 s
Parse succeeded.
Time: 1.050 s
Parse succeeded.
Time: 4.091 s
Parse succeeded.
Time: 2.649 s
Parse succeeded.
Time: 0.363 s
Parse succeeded.
Time: 0.789 s
Parse succeeded.
Time: 1.791 s
Parse succeeded.
Time: 0.339 s
Parse succeeded.
Time: 0.216 s
Parse succeeded.
Total Time: 15.517 s

Kenne@DESKTOP-DL44R7B MINGW64 ~/issue-3934/Go/Generated
$ ls -lts
total 186215
    20 -rw-r--r-- 1 Kenne Kenne     18561 Oct 20 07:07 cpu.prof
  5492 -rwxr-xr-x 1 Kenne Kenne   5623808 Oct 20 07:06 Test.exe*
     8 -rw-r--r-- 1 Kenne Kenne      5751 Oct 20 07:06 Test.go
   240 -rw-r--r-- 1 Kenne Kenne    242780 Oct 20 04:15 s3.txt
  1608 -rw-r--r-- 1 Kenne Kenne   1645089 Oct 20 04:02 ss.txt
   152 -rw-r--r-- 1 Kenne Kenne    153644 Oct 20 03:49 s.txt
129652 -rw-r--r-- 1 Kenne Kenne 132760394 Oct 20 03:38 sequenced.txt
 49028 -rw-r--r-- 1 Kenne Kenne  50204596 Oct 20 03:37 single.txt
     4 drwxr-xr-x 1 Kenne Kenne         0 Oct 19 14:06 parser/
     1 -rw-r--r-- 1 Kenne Kenne       468 Oct 19 14:06 go.sum
     1 -rw-r--r-- 1 Kenne Kenne       207 Oct 19 14:06 go.mod
     4 -rw-r--r-- 1 Kenne Kenne      1587 Oct 19 14:06 tester.psm1
     1 -rw-r--r-- 1 Kenne Kenne       618 Oct 19 14:06 test.sh
     4 -rw-r--r-- 1 Kenne Kenne      1062 Oct 19 14:06 makefile

Kenne@DESKTOP-DL44R7B MINGW64 ~/issue-3934/Go/Generated
$ !go
go tool pprof cpu.prof
Type: cpu
Time: Oct 20, 2022 at 7:07am (EDT)
Duration: 15.64s, Total samples = 10.72s (68.53%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top100
Showing nodes accounting for 10s, 93.28% of 10.72s total
Dropped 117 nodes (cum <= 0.05s)
      flat  flat%   sum%        cum   cum%
     1.60s 14.93% 14.93%      2.32s 21.64%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfig).Equals
     1.57s 14.65% 29.57%      1.75s 16.32%  runtime.(*itabTableType).find
     1.21s 11.29% 40.86%      4.67s 43.56%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNConfig).Equals
     1.06s  9.89% 50.75%      7.42s 69.22%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfigSet).Compare
     0.74s  6.90% 57.65%      2.49s 23.23%  runtime.getitab
     0.53s  4.94% 62.59%      1.14s 10.63%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerActionExecutor).Equals
     0.48s  4.48% 67.07%      2.99s 27.89%  runtime.convI2I
     0.44s  4.10% 71.18%         9s 83.96%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*DFAState).Equals
     0.43s  4.01% 75.19%      7.85s 73.23%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfigSet).Equals
     0.40s  3.73% 78.92%      0.61s  5.69%  golang.org/x/exp/slices.EqualFunc[...]
     0.22s  2.05% 80.97%      5.02s 46.83%  github.com/antlr/antlr4/runtime/Go/antlr/v4..Get
     0.17s  1.59% 82.56%      4.56s 42.54%  github.com/antlr/antlr4/runtime/Go/antlr/v4..Put
     0.16s  1.49% 84.05%      0.16s  1.49%  runtime.stdcall1
     0.15s  1.40% 85.45%      0.15s  1.40%  runtime.add (inline)
     0.14s  1.31% 86.75%      0.30s  2.80%  runtime.scanobject
     0.12s  1.12% 87.87%      0.12s  1.12%  runtime.stdcall2
     0.09s  0.84% 88.71%      0.21s  1.96%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerActionExecutor).Equals.func1
     0.09s  0.84% 89.55%      9.10s 84.89%  github.com/antlr/antlr4/runtime/Go/antlr/v4..Equals2
     0.07s  0.65% 90.21%      0.07s  0.65%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNState).GetStateNumber
     0.06s  0.56% 90.76%      0.06s  0.56%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseLexerAction).Equals
     0.06s  0.56% 91.32%      0.06s  0.56%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerSkipAction).Equals
     0.05s  0.47% 91.79%      0.07s  0.65%  runtime.findObject
     0.05s  0.47% 92.26%      0.50s  4.66%  runtime.gcDrain
     0.02s  0.19% 92.44%      0.20s  1.87%  runtime.mallocgc
     0.02s  0.19% 92.63%      0.06s  0.56%  runtime.newstack
     0.01s 0.093% 92.72%      9.60s 89.55%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).fetch
     0.01s 0.093% 92.82%      0.07s  0.65%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).getReachableConfigSet
     0.01s 0.093% 92.91%      0.14s  1.31%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).closureCheckingStopState
     0.01s 0.093% 93.00%      0.13s  1.21%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).closureWork
     0.01s 0.093% 93.10%      0.17s  1.59%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).execATNWithFullContext
     0.01s 0.093% 93.19%      0.06s  0.56%  runtime.mapassign_fast64
     0.01s 0.093% 93.28%      0.06s  0.56%  runtime/pprof.(*profMap).lookup
         0     0% 93.28%      5.57s 51.96%  example.com/myparser/parser.(*DaedalusParser).BlockDef
         0     0% 93.28%      0.32s  2.99%  example.com/myparser/parser.(*DaedalusParser).ClassDef
         0     0% 93.28%      9.81s 91.51%  example.com/myparser/parser.(*DaedalusParser).DaedalusFile
         0     0% 93.28%      0.32s  2.99%  example.com/myparser/parser.(*DaedalusParser).ElseBlock
         0     0% 93.28%      0.39s  3.64%  example.com/myparser/parser.(*DaedalusParser).ElseIfBlock
         0     0% 93.28%      0.09s  0.84%  example.com/myparser/parser.(*DaedalusParser).ExpressionBlock
         0     0% 93.28%      0.06s  0.56%  example.com/myparser/parser.(*DaedalusParser).FuncArgExpression
         0     0% 93.28%      0.07s  0.65%  example.com/myparser/parser.(*DaedalusParser).FuncCall
         0     0% 93.28%      3.02s 28.17%  example.com/myparser/parser.(*DaedalusParser).FunctionDef
         0     0% 93.28%      1.54s 14.37%  example.com/myparser/parser.(*DaedalusParser).IfBlock
         0     0% 93.28%      1.76s 16.42%  example.com/myparser/parser.(*DaedalusParser).IfBlockStatement
         0     0% 93.28%      4.05s 37.78%  example.com/myparser/parser.(*DaedalusParser).InlineDef
         0     0% 93.28%      0.22s  2.05%  example.com/myparser/parser.(*DaedalusParser).Statement
         0     0% 93.28%      3.02s 28.17%  example.com/myparser/parser.(*DaedalusParser).StatementBlock
         0     0% 93.28%      0.08s  0.75%  example.com/myparser/parser.(*DaedalusParser).Value
         0     0% 93.28%      0.09s  0.84%  example.com/myparser/parser.(*DaedalusParser).expression
         0     0% 93.28%      0.08s  0.75%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseATNConfigSet).Add
         0     0% 93.28%      9.59s 89.46%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseLexer).NextToken
         0     0% 93.28%      9.59s 89.46%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseLexer).safeMatch
         0     0% 93.28%      9.40s 87.69%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseParser).Consume
         0     0% 93.28%      0.20s  1.87%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseParser).EnterRule
         0     0% 93.28%      9.40s 87.69%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*BaseParser).Match
         0     0% 93.28%      9.41s 87.78%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).Consume
         0     0% 93.28%      0.19s  1.77%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).LT
         0     0% 93.28%      9.60s 89.55%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).Sync
         0     0% 93.28%      0.19s  1.77%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).lazyInit (inline)
         0     0% 93.28%      0.19s  1.77%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*CommonTokenStream).setup
         0     0% 93.28%      9.59s 89.46%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).Match
         0     0% 93.28%      9.51s 88.71%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).addDFAEdge
         0     0% 93.28%      9.48s 88.43%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).addDFAState
         0     0% 93.28%      0.06s  0.56%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).closure
         0     0% 93.28%      9.58s 89.37%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).computeTargetState
         0     0% 93.28%      9.59s 89.46%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*LexerATNSimulator).execATN
         0     0% 93.28%      0.21s  1.96%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).AdaptivePredict
         0     0% 93.28%      0.14s  1.31%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).closure (inline)
         0     0% 93.28%      0.13s  1.21%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).computeReachSet
         0     0% 93.28%      0.21s  1.96%  github.com/antlr/antlr4/runtime/Go/antlr/v4.(*ParserATNSimulator).execATN
         0     0% 93.28%      9.81s 91.51%  main.DoParse
         0     0% 93.28%      9.81s 91.51%  main.ParseFilename
         0     0% 93.28%      9.81s 91.51%  main.main
         0     0% 93.28%      0.13s  1.21%  runtime.(*gcControllerState).enlistWorker
         0     0% 93.28%      0.14s  1.31%  runtime.(*gcWork).balance
         0     0% 93.28%      0.15s  1.40%  runtime.findRunnable
         0     0% 93.28%      0.37s  3.45%  runtime.gcBgMarkWorker
         0     0% 93.28%      0.50s  4.66%  runtime.gcBgMarkWorker.func2
         0     0% 93.28%      0.10s  0.93%  runtime.lock (inline)
         0     0% 93.28%      0.10s  0.93%  runtime.lock2
         0     0% 93.28%      0.10s  0.93%  runtime.lockWithRank (inline)
         0     0% 93.28%      9.81s 91.51%  runtime.main
         0     0% 93.28%      0.26s  2.43%  runtime.mcall
         0     0% 93.28%      0.11s  1.03%  runtime.newobject (partial-inline)
         0     0% 93.28%      0.14s  1.31%  runtime.notewakeup
         0     0% 93.28%      0.26s  2.43%  runtime.park_m
         0     0% 93.28%      0.13s  1.21%  runtime.preemptM
         0     0% 93.28%      0.13s  1.21%  runtime.preemptone
         0     0% 93.28%      0.12s  1.12%  runtime.resetspinning
         0     0% 93.28%      0.27s  2.52%  runtime.schedule
         0     0% 93.28%      0.10s  0.93%  runtime.semasleep
         0     0% 93.28%      0.14s  1.31%  runtime.semawakeup
         0     0% 93.28%      0.13s  1.21%  runtime.startm
         0     0% 93.28%      0.55s  5.13%  runtime.systemstack
         0     0% 93.28%      0.13s  1.21%  runtime.wakep
         0     0% 93.28%      0.06s  0.56%  runtime/pprof.(*profileBuilder).addCPUData
         0     0% 93.28%      0.07s  0.65%  runtime/pprof.profileWriter
(pprof)

[kaby76]

I think a Hash1() function for generics isn't quite right. I'm seeing that a Hash1() for an ATNConfig for generics is missing the addition of the hash value for "context" used in Hash() for a BaseATNConfig. I don't understand why it just doesn't returno.Hash() as that will call the hash function for object o. A similar argument could be made for other Hash1() functions, e.g., this and Equals2(), e.g., this. Why is it duplicating these functions--and apparently not even correctly?

If a hash value collides excessively, it will have to be resolved by Equals().

[kaby76]

Ah, it's a 2-level hash table. Not as simple as I thought.