• Cherry Zhang's avatar
    [dev.link] cmd/link: use min-heap for work queue for better locality · 36dbdbe9
    Cherry Zhang authored
    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/+/204438Reviewed-by: default avatarJeremy Faller <jeremy@golang.org>
    36dbdbe9
deadcode2.go 13.4 KB