[dev.link] cmd/link: use min-heap for work queue for better locality
In the deadcode pass, we use a work queue for the flood algorithm.
Currently this is a simple LIFO queue. In this order, there is
poor locality in accessing object files.
Since the global indices are assigned in package DAG order, edges
are mostly either within a package or from a smaller index to a
larger one. (With named symbols, there can be backward edges, but
shouldn't be too many.) Using a min-heap for the work queue, we
access all symbols in one object, then move to next one. It
rarely needs to revisit an object that is already visted. This
should result in better locality.
Benchmark result from Than (thanks!):
name old time/op new time/op delta
LinkCompiler 1.74s ±11% 1.61s ± 9% -7.80% (p=0.000 n=20+19)
LinkWithoutDebugCompiler 1.27s ±11% 1.15s ± 9% -9.02% (p=0.000 n=20+20)
Currently this uses the container/heap package, which uses
interface elements. If this allocates too much, we may consider
to hand-code the min heap.
Change-Id: I216d5291c432fe1f40b0b8f4f1b9d388807bf6c5
Reviewed-on: https://go-review.googlesource.com/c/go/+/204438 Reviewed-by: Jeremy Faller <jeremy@golang.org>