From e90e6e75f8f0b06a5b0c9c68d8d98b8f37b0d3e0 Mon Sep 17 00:00:00 2001 From: Than McIntosh Date: Wed, 30 Oct 2019 10:14:33 -0400 Subject: [PATCH] [dev.link] cmd/link/internal/loader: add 1-element object cache for use in toLocal MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit To speed up the loader.Loader.toLocal() method, cache the index of the most recently accessed object file and check that object's sym range in toLocal() before doing a full binary search over all object symbol ranges. This speeds up relink of kubernetes/hyperkube by about 2%, and improves compilebench (relative to the dev.link branch) by about 5%: name old time/op new time/op delta LinkCompiler 1.62s ± 8% 1.50s ± 9% -7.21% (p=0.000 n=20+19) LinkWithoutDebugCompiler 1.13s ± 8% 1.09s ±12% ~ (p=0.052 n=20+20) name old user-time/op new user-time/op delta LinkCompiler 1.94s ±18% 1.97s ±16% ~ (p=0.813 n=19+20) LinkWithoutDebugCompiler 1.15s ±16% 1.13s ±12% ~ (p=0.547 n=20+20) Change-Id: Id5a8a847b533858373c0462f03972d436eda6748 Reviewed-on: https://go-review.googlesource.com/c/go/+/204337 Reviewed-by: Jeremy Faller Reviewed-by: Cherry Zhang --- src/cmd/link/internal/loader/loader.go | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) diff --git a/src/cmd/link/internal/loader/loader.go b/src/cmd/link/internal/loader/loader.go index 52809c63da..95e3005af2 100644 --- a/src/cmd/link/internal/loader/loader.go +++ b/src/cmd/link/internal/loader/loader.go @@ -65,6 +65,7 @@ type oReader struct { type objIdx struct { r *oReader i Sym // start index + e Sym // end index } type nameVer struct { @@ -98,6 +99,7 @@ type Loader struct { extStart Sym // from this index on, the symbols are externally defined extSyms []nameVer // externally defined symbols builtinSyms []Sym // global index of builtin symbols + ocache int // index (into 'objs') of most recent lookup symsByName [2]map[string]Sym // map symbol name to index, two maps are for ABI0 and ABIInternal extStaticSyms map[nameVer]Sym // externally defined static symbols, keyed by name @@ -116,7 +118,7 @@ func NewLoader() *Loader { nbuiltin := goobj2.NBuiltin() return &Loader{ start: make(map[*oReader]Sym), - objs: []objIdx{{nil, 0}}, + objs: []objIdx{{nil, 0, 0}}, symsByName: [2]map[string]Sym{make(map[string]Sym), make(map[string]Sym)}, objByPkg: make(map[string]*oReader), overwrite: make(map[Sym]Sym), @@ -143,7 +145,7 @@ func (l *Loader) addObj(pkg string, r *oReader) Sym { n := r.NSym() + r.NNonpkgdef() i := l.max + 1 l.start[r] = i - l.objs = append(l.objs, objIdx{r, i}) + l.objs = append(l.objs, objIdx{r, i, i + Sym(n) - 1}) l.max += Sym(n) return i } @@ -249,12 +251,17 @@ func (l *Loader) toLocal(i Sym) (*oReader, int) { if l.isExternal(i) { return nil, int(i - l.extStart) } + oc := l.ocache + if oc != 0 && i >= l.objs[oc].i && i <= l.objs[oc].e { + return l.objs[oc].r, int(i - l.objs[oc].i) + } // Search for the local object holding index i. // Below k is the first one that has its start index > i, // so k-1 is the one we want. k := sort.Search(len(l.objs), func(k int) bool { return l.objs[k].i > i }) + l.ocache = k - 1 return l.objs[k-1].r, int(i - l.objs[k-1].i) } -- 2.48.1