reflect: sort exported methods first
By moving exported methods to the front of method lists, filtering
down to only the exported methods just needs a count of how many
exported methods exist, which the compiler can statically
provide. This allows getting rid of the exported method cache.
For #22075.
Change-Id: I8eeb274563a2940e1347c34d673f843ae2569064
Reviewed-on: https://go-review.googlesource.com/100846
Reviewed-by: Ian Lance Taylor <iant@golang.org>
diff --git a/src/cmd/compile/internal/gc/reflect.go b/src/cmd/compile/internal/gc/reflect.go
index eeb74c6..3cb6930 100644
--- a/src/cmd/compile/internal/gc/reflect.go
+++ b/src/cmd/compile/internal/gc/reflect.go
@@ -51,21 +51,19 @@
offset int32
}
-// siglt sorts method signatures by name, then package path.
+// siglt sorts method signatures by name with exported methods first,
+// and then non-exported methods by their package path.
func siglt(a, b *Sig) bool {
+ if (a.pkg == nil) != (b.pkg == nil) {
+ return a.pkg == nil
+ }
if a.name != b.name {
return a.name < b.name
}
- if a.pkg == b.pkg {
- return false
+ if a.pkg != nil && a.pkg != b.pkg {
+ return a.pkg.Path < b.pkg.Path
}
- if a.pkg == nil {
- return true
- }
- if b.pkg == nil {
- return false
- }
- return a.pkg.Path < b.pkg.Path
+ return false
}
// Builds a type representing a Bucket structure for
@@ -403,7 +401,7 @@
method := f.Sym
if method == nil {
- continue
+ break
}
// get receiver type for this particular method.
@@ -683,12 +681,13 @@
if mcount != int(uint16(mcount)) {
Fatalf("too many methods on %v: %d", t, mcount)
}
+ xcount := sort.Search(mcount, func(i int) bool { return m[i].pkg != nil })
if dataAdd != int(uint32(dataAdd)) {
Fatalf("methods are too far away on %v: %d", t, dataAdd)
}
ot = duint16(lsym, ot, uint16(mcount))
- ot = duint16(lsym, ot, 0)
+ ot = duint16(lsym, ot, uint16(xcount))
ot = duint32(lsym, ot, uint32(dataAdd))
ot = duint32(lsym, ot, 0)
return ot
diff --git a/src/cmd/compile/internal/gc/reflect_test.go b/src/cmd/compile/internal/gc/reflect_test.go
index fe6dcf0..1e280c2 100644
--- a/src/cmd/compile/internal/gc/reflect_test.go
+++ b/src/cmd/compile/internal/gc/reflect_test.go
@@ -14,23 +14,27 @@
func TestSortingBySigLT(t *testing.T) {
data := []*Sig{
&Sig{name: "b", pkg: &types.Pkg{Path: "abc"}},
- &Sig{name: "b", pkg: nil},
- &Sig{name: "c", pkg: nil},
+ &Sig{name: "B", pkg: nil},
+ &Sig{name: "C", pkg: nil},
&Sig{name: "c", pkg: &types.Pkg{Path: "uvw"}},
- &Sig{name: "c", pkg: nil},
+ &Sig{name: "C", pkg: nil},
+ &Sig{name: "φ", pkg: &types.Pkg{Path: "gr"}},
+ &Sig{name: "Φ", pkg: nil},
&Sig{name: "b", pkg: &types.Pkg{Path: "xyz"}},
&Sig{name: "a", pkg: &types.Pkg{Path: "abc"}},
- &Sig{name: "b", pkg: nil},
+ &Sig{name: "B", pkg: nil},
}
want := []*Sig{
+ &Sig{name: "B", pkg: nil},
+ &Sig{name: "B", pkg: nil},
+ &Sig{name: "C", pkg: nil},
+ &Sig{name: "C", pkg: nil},
+ &Sig{name: "Φ", pkg: nil},
&Sig{name: "a", pkg: &types.Pkg{Path: "abc"}},
- &Sig{name: "b", pkg: nil},
- &Sig{name: "b", pkg: nil},
&Sig{name: "b", pkg: &types.Pkg{Path: "abc"}},
&Sig{name: "b", pkg: &types.Pkg{Path: "xyz"}},
- &Sig{name: "c", pkg: nil},
- &Sig{name: "c", pkg: nil},
&Sig{name: "c", pkg: &types.Pkg{Path: "uvw"}},
+ &Sig{name: "φ", pkg: &types.Pkg{Path: "gr"}},
}
if len(data) != len(want) {
t.Fatal("want and data must match")
diff --git a/src/cmd/compile/internal/gc/subr.go b/src/cmd/compile/internal/gc/subr.go
index 91e99fc..b9bf1d3 100644
--- a/src/cmd/compile/internal/gc/subr.go
+++ b/src/cmd/compile/internal/gc/subr.go
@@ -373,7 +373,8 @@
n.Orig = norig
}
-// methcmp sorts by symbol, then by package path for unexported symbols.
+// methcmp sorts methods by name with exported methods first,
+// and then non-exported methods by their package path.
type methcmp []*types.Field
func (x methcmp) Len() int { return len(x) }
@@ -381,22 +382,31 @@
func (x methcmp) Less(i, j int) bool {
a := x[i]
b := x[j]
- if a.Sym == nil && b.Sym == nil {
+ if a.Sym == b.Sym {
return false
}
+
+ // Blank methods to the end.
if a.Sym == nil {
- return true
+ return false
}
if b.Sym == nil {
- return false
+ return true
}
+
+ // Exported methods to the front.
+ ea := exportname(a.Sym.Name)
+ eb := exportname(b.Sym.Name)
+ if ea != eb {
+ return ea
+ }
+
+ // Sort by name and then package.
if a.Sym.Name != b.Sym.Name {
return a.Sym.Name < b.Sym.Name
}
- if !exportname(a.Sym.Name) {
- if a.Sym.Pkg.Path != b.Sym.Pkg.Path {
- return a.Sym.Pkg.Path < b.Sym.Pkg.Path
- }
+ if !ea && a.Sym.Pkg.Path != b.Sym.Pkg.Path {
+ return a.Sym.Pkg.Path < b.Sym.Pkg.Path
}
return false
diff --git a/src/reflect/type.go b/src/reflect/type.go
index 716ab0c..021258e 100644
--- a/src/reflect/type.go
+++ b/src/reflect/type.go
@@ -333,7 +333,7 @@
type uncommonType struct {
pkgPath nameOff // import path; empty for built-in types like int, string
mcount uint16 // number of methods
- _ uint16 // unused
+ xcount uint16 // number of exported methods
moff uint32 // offset from this uncommontype to [mcount]method
_ uint32 // unused
}
@@ -639,6 +639,13 @@
return (*[1 << 16]method)(add(unsafe.Pointer(t), uintptr(t.moff), "t.mcount > 0"))[:t.mcount:t.mcount]
}
+func (t *uncommonType) exportedMethods() []method {
+ if t.xcount == 0 {
+ return nil
+ }
+ return (*[1 << 16]method)(add(unsafe.Pointer(t), uintptr(t.moff), "t.xcount > 0"))[:t.xcount:t.xcount]
+}
+
// resolveNameOff resolves a name offset from a base pointer.
// The (*rtype).nameOff method is a convenience wrapper for this function.
// Implemented in the runtime package.
@@ -783,43 +790,12 @@
func (t *rtype) common() *rtype { return t }
-var methodCache sync.Map // map[*rtype][]method
-
func (t *rtype) exportedMethods() []method {
- methodsi, found := methodCache.Load(t)
- if found {
- return methodsi.([]method)
- }
-
ut := t.uncommon()
if ut == nil {
return nil
}
- allm := ut.methods()
- allExported := true
- for _, m := range allm {
- name := t.nameOff(m.name)
- if !name.isExported() {
- allExported = false
- break
- }
- }
- var methods []method
- if allExported {
- methods = allm
- } else {
- methods = make([]method, 0, len(allm))
- for _, m := range allm {
- name := t.nameOff(m.name)
- if name.isExported() {
- methods = append(methods, m)
- }
- }
- methods = methods[:len(methods):len(methods)]
- }
-
- methodsi, _ = methodCache.LoadOrStore(t, methods)
- return methodsi.([]method)
+ return ut.exportedMethods()
}
func (t *rtype) NumMethod() int {
@@ -827,9 +803,6 @@
tt := (*interfaceType)(unsafe.Pointer(t))
return tt.NumMethod()
}
- if t.tflag&tflagUncommon == 0 {
- return 0 // avoid methodCache synchronization
- }
return len(t.exportedMethods())
}
@@ -876,16 +849,10 @@
if ut == nil {
return Method{}, false
}
- utmethods := ut.methods()
- var eidx int
- for i := 0; i < int(ut.mcount); i++ {
- p := utmethods[i]
- pname := t.nameOff(p.name)
- if pname.isExported() {
- if pname.name() == name {
- return t.Method(eidx), true
- }
- eidx++
+ // TODO(mdempsky): Binary search.
+ for i, p := range ut.exportedMethods() {
+ if t.nameOff(p.name).name() == name {
+ return t.Method(i), true
}
}
return Method{}, false
@@ -2627,7 +2594,12 @@
default:
panic("reflect.StructOf: too many methods")
}
+ // TODO(sbinet): Once we allow embedding multiple types,
+ // methods will need to be sorted like the compiler does.
+ // TODO(sbinet): Once we allow non-exported methods, we will
+ // need to compute xcount as the number of exported methods.
ut.mcount = uint16(len(methods))
+ ut.xcount = ut.mcount
ut.moff = uint32(unsafe.Sizeof(uncommonType{}))
if len(fs) > 0 {
diff --git a/src/runtime/type.go b/src/runtime/type.go
index b3df335..b72f5c0 100644
--- a/src/runtime/type.go
+++ b/src/runtime/type.go
@@ -329,7 +329,7 @@
type uncommontype struct {
pkgpath nameOff
mcount uint16 // number of methods
- _ uint16 // unused
+ xcount uint16 // number of exported methods
moff uint32 // offset from this uncommontype to [mcount]method
_ uint32 // unused
}
