tree 4c8dc381029c20056cc3fedbcaca0397b5fe2364
parent e4d6bfdbdf6037326633a7826293c848dc0d4228
author Cherry Zhang <cherryyz@google.com> 1591227269 -0400
committer Cherry Zhang <cherryyz@google.com> 1591298022 +0000

[dev.link] cmd/link: rewrite heap algorithm

Instead of using container/heap package, implement a simple
specialized heap algorithm for the work queue in the deadcode
pass, to avoid allocations and function pointer calls.

Linking cmd/compile,

name           old time/op    new time/op    delta
Deadcode_GC      59.8ms ± 4%    42.2ms ± 4%  -29.45%  (p=0.008 n=5+5)

name           old alloc/op   new alloc/op   delta
Deadcode_GC      3.53MB ± 0%    2.10MB ± 0%  -40.57%  (p=0.008 n=5+5)

name           old allocs/op  new allocs/op  delta
Deadcode_GC        187k ± 0%        8k ± 0%  -95.48%  (p=0.008 n=5+5)

Change-Id: Ibb21801d5b8e4a7eaf429856702e02720cd1772f
Reviewed-on: https://go-review.googlesource.com/c/go/+/236565
Run-TryBot: Cherry Zhang <cherryyz@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Jeremy Faller <jeremy@golang.org>
Reviewed-by: Than McIntosh <thanm@google.com>