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>

0 files changed, 0 insertions, 0 deletions