commit 21c2fdd91c1c5885990663a054c66bddfa4986fc
author Cherry Mui <cherryyz@google.com> Thu Apr 20 23:33:42 2023 -0400
committer Cherry Mui <cherryyz@google.com> Mon Apr 24 14:00:39 2023 +0000
tree d29511a64fbddf40d505525070aa05794901917e
parent 2c70690451f1484607a9172a4c24f78ae832dcb0

cmd/link: use slice and bitmap for some attributes

Currently, a symbol's outer symbol, the "special" attribute, and
whether a symbol is a generator symbol are represented as maps,
and are accessed in some loops over nearly all reachable symbols.
The map lookups are a bit expensive.

For outer symbol, a non-trivial portion of the symbols have outer
symbol set (e.g. type symbols, which we put into container symbols
like "type:*"). Using a slice to access more efficiently.

For the special and generator symbol attributes, use a bitmap.
There are not many symbols have those attributes, so the bitmap is
quite sparse. The bitmap is not too large anyway, so use it for
now. If we want to further reduce memory usage we could consider
some other data structure like a Bloom filter.

Linking cmd/compile in external linking mode (on macOS/amd64)

Symtab   12.9ms ± 9%     6.4ms ± 5%   -50.08%  (p=0.000 n=19+18)
Dodata   64.9ms ±12%    57.1ms ±12%   -11.90%  (p=0.000 n=20+20)
Asmb     36.7ms ±11%    32.8ms ± 9%   -10.61%  (p=0.000 n=20+18)
Asmb2    26.6ms ±15%    21.9ms ±12%   -17.75%  (p=0.000 n=20+18)

There is some increase of memory usage

Munmap_GC   40.9M ± 1%     43.2M ± 0%    +5.54%  (p=0.000 n=20+19)

The next CL will bring the memory usage back.

Change-Id: Ie4347eb96c51f008b9284270de37fc880bb52d2c
Reviewed-on: https://go-review.googlesource.com/c/go/+/487415
Run-TryBot: Cherry Mui <cherryyz@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>