Go: proposal: reflect: add Named() bool to Type interface

[mvdan]

Right now, the only way to tell if a reflect.Type is a named type is to do t.Name() != "". This is quite common:

$ git grep -n '\.Name() [!=]= ""'
src/encoding/gob/type.go:844:   if rt.Name() == "" {
src/encoding/gob/type.go:866:   if rt.Name() != "" {
src/encoding/json/encode.go:1148:                               if ft.Name() == "" && ft.Kind() == reflect.Ptr {
src/encoding/xml/marshal.go:638:        } else if typ.Name() != "" {
src/encoding/xml/read.go:188:   if t.Name() != "" {
src/reflect/type.go:1575:       if T.Name() != "" && V.Name() != "" || T.Kind() != V.Kind() {
src/reflect/value.go:2323:      if dst.Kind() == Ptr && dst.Name() == "" &&
src/reflect/value.go:2324:              src.Kind() == Ptr && src.Name() == "" &&

However, the function implementation is quite complex:

func (t *rtype) Name() string {
        if t.tflag&tflagNamed == 0 {
                return ""
        }
        s := t.String()
        i := len(s) - 1
        for i >= 0 {
                if s[i] == '.' {
                        break
                }
                i--
        }
        return s[i+1:]
}

I don't think it would ever be possible for the compiler to know that we just care about the first branch, since it's possible that t.String would return a string like foo., in which case s[i+1:] at the end would also be the empty string.

I propose that we add a method like Named() bool to the interface, implemented like:

func (t *rtype) Named() bool {
        return t.tflag&tflagNamed != 0
}

A call to this function would be inlineable and not require string handling, so it would be massively cheaper than the original t.Name() != "". As proof, here's what happens if we implement it and use it in JSON decoding:

diff --git a/src/encoding/json/decode.go b/src/encoding/json/decode.go
index 2e734fb39e..97d44d4639 100644
--- a/src/encoding/json/decode.go
+++ b/src/encoding/json/decode.go
@@ -451,7 +451,7 @@ func indirect(v reflect.Value, decodingNull bool) (Unmarshaler, encoding.TextUnm
    // If v is a named type and is addressable,
    // start with its address, so that if the type has pointer methods,
    // we find them.
-   if v.Kind() != reflect.Ptr && v.Type().Name() != "" && v.CanAddr() {
+   if v.Kind() != reflect.Ptr && v.Type().Named() && v.CanAddr() {
        haveAddr = true
        v = v.Addr()
    }

name           old time/op    new time/op    delta
CodeDecoder-4    27.3ms ± 1%    26.5ms ± 1%  -2.80%  (p=0.002 n=6+6)

name           old speed      new speed      delta
CodeDecoder-4  71.1MB/s ± 1%  73.1MB/s ± 1%  +2.89%  (p=0.002 n=6+6)

One can imagine that the gob and xml packages would also see many-percent speedups, on top of the reflect package itself getting faster.

I realise that this is a case of adding extra API just for the sake of performance. However, I fail to see another way to cheaply see if a reflect.Type is named, which is a common operation that should be trivial. If anyone has any ideas on how to make Name() != "" just as fast somehow, please do speak up.

On the plus side, there aren't any other flag bits that would be interesting to export, so this shouldn't lead to adding a countless number of boolean methods.

cc @josharian @randall77 @ianlancetaylor @Quasilyte

[mvdan]

Here's a possible alternative - somehow help the compiler realise that we just care about t.tflag&tflagNamed in the Name implementation. For example:

func (t *rtype) Name() string {
        if t.tflag&tflagNamed == 0 {
                return ""
        }
        // statically, we can know that the return below will use a non-empty string.
        s := t.String()
        i := len(s) - 1
        for i >= 0 {
                if s[i] == '.' {
                        break
                }
                i--
        }
        name := s[i+1:]
        if name == "" {
                panic("impossible") // or perhaps return "BADNAME"
        }
        return name        
}

[mvdan]

One counter-point to the JSON case is that we could instead do the reflect work ahead of time for structs; see #16212.

Still, this seems like a common reflection operation that should be way cheaper. And reflection is used in many more places than just encoding/json.

[as]

Is adding Named a backward-compatible change?

[cespare]

@as yes, because Type has unexported methods.

[CAFxX]

While I understand that adding Named() would be much simpler from an implementation perspective, it sets a bad precedent (as correctly noted in the first comment) and doesn't solve the same problem elsewhere. It would be better to actually have some (even restricted) form of partial inlining, and let the compiler do the right thing.

[quasilyte]

@CAFxX do you have implementation ideas of this partial inlining?
Ones come to my mind either require more memory consumption per inlining candidate and/or more computations to analyze the call site, which would probably result in wasted cycles for 90% of places. This can be optimized from the toolchain speed point of view, but changing the inliner is complicated since it's hard to determine whether inlining something will make things better or not (at least on architectures like x86).

I've tried several changes to make Go inliner more "dynamic" and make decisions with some caller context. It made some benchmarks faster, some slower. This might be the reason why we still have current cost model, for example. It's trivial to make it worse, but hard to make it universally better (it may actually require profile-guided optimization, since guessing statically is non-trivial).

[mvdan]

@CAFxX of course it would be best if this was fast with no changes to the API - but the hard problem is figuring out how that would work. Make the compiler smarter? Special-case the reflect package in the compiler? Somehow rewrite the method to do less work?

I haven't come up with a way to do it, and I'm not even sure it's possible, hence this proposal.

[rsc]

<3% in one case does not seem worth the extra API here.
As others noted, the code could cache the result if needed.
Or we could arrange for it to be faster if needed.
Neither of those requires new API.
New API is much more costly than 3%.

[mvdan]

As others noted, the code could cache the result if needed.

Sorry, I don't know what you're referring to.

Or we could arrange for it to be faster if needed.

I opened this proposal precisely because I didn't see an easy way to do this :) I could make the reflect struct heavier to then cache the name string, but I don't know if that's a tradeoff we want to make.

[mvdan]

@rsc sorry to comment on a frozen issue, but I'm still confused about the arguments to close this proposal. Like I said in the comment above, I don't see a way to make reflect.rtype.String significantly faster, or to cache its result in encoding/json. If anyone has a specific idea, I'll gladly use that instead of adding new API.

I completely forgot to follow up on this and the thread got locked. Unlocking for now.

[andybons]

Additional context: @mvdan asked if it was alright to unlock and follow up. I said yes.

[ianlancetaylor]

If we think it's worth it, and if it's faster, we could use a sync.Map to cache (*rtype).String in the reflect package. Or in the encoding/json package.

The current rtype format is optimized for space. We could change that.

We could implement partial inlining as suggested above.

The encoding/json code should check CanAddr first, although I don't know how often that is false. CanAddr is simple.

There are quite a few areas we could explore rather than adding new API. New API seems like a lot, and the performance improvement doesn't seem like all that much in the larger scheme of things.

[mvdan]

Thanks, @ianlancetaylor. Next time I'm in the mood for some encoding/json performance tuning I'll try your ideas and report back. I'm not sure why I hadn't noticed your reply until now, I must have read the notification and forgotten about it.