cheaper reflect.Type equality check

[Ugorji]

While benchmarking my msgpack/binc encoder, I noticed that one of the bigger performance hits occurred when I had to do a map[reflect.Type]XXX check each time within a recursive call.

Just about all encoders do this too (encoding/gob, encoding/json, etc) and suffer from this performance hit.

The reason for being expensive is that reflect.Type is an interface, and interface equality check is more expensive than numbers or strings (ie. check for "identical" dynamic types and equal dynamic values). 

However, it doesn't have to be:

- reflect.Type is always a singleton within a process

- reflect.Type underlying value has a private hash field which is unique within the process

- Consequently, the equality check can be much faster (becoming just an integer comparison)

If we can optimize this (either generally or specifically for reflect.Type), then

- map access with reflect.Type keys (which is common for any framework/library built around reflection) is no longer a bottleneck

- even faster linear search and binary search can be possible

A different way of working around this, is to expose the hash value of reflect.Type (e.g. as an Id() int). With this exposed methods, users can map the Id() and maintain data structures that are performant (e.g. linear search, binary search, map[int]XXX). I'm not fond of this, because it exposes a field to workaround a performance issue.

Thoughts?

[Ugorji]

I got a reply in my inbox that: 

reflect.Type's are pointers stored in an interface. The comparison is only a comparison of two pointers, which is already cheap.

However, before the cheap pointer comparison happens, interface comparison involves a check for identical dynamic types. This is the more expensive part. Unfortunately, we can't get the reflect.Type pointer directly (since it's unexported) so have to pay the cost for the wrapping interface comparison. 

I ran some benchmarks that show it:

http://play.golang.org/p/dO1QEuQfpH

PASS

BenchmarkIntfEqual 100000000        15.3 ns/op

BenchmarkPtrEqual 2000000000         1.06 ns/op

[Russ Cox]

I am skeptical. In particular, the code you say is slow and the code you benchmarked are nearly unrelated, because you've cut out the map.

You can test your hypothesis by editing package reflect and rebuilding:

1. Add ID() uintptr to the type Type interface definition.

2. Add func(t *rtype) ID() uintptr { return uintptr(unsafe.Pointer(t)) }

and see how much your profile changes.

If it makes a significant difference, then that doesn't mean we are going to add this method, it just provides better evidence that the implementation of maps of interfaces needs to be made better.

Russ

[Ugorji]

I tried to distill down from map access to the underlying culprit, which was the interface equality check.

In other languages (like Java), users can define an implementation of equals(...), so they are in charge of making the equality check cheap (which is used internally by maps, etc). 

In Go, we don't have that, so the typical workaround (that I have used) is to keep map keys as 32-bit/64-bit numbers where possible, or strings (since these are optimized). Interface equality checks especially are real expensive, and this shows a lot in recursive functions which do a linear search(since an equality check is done every loop) or map access (since equality checks are done under the hood). 

I've updated the benchmark to show map access cost. It's clear that interface equality costs 14.6ns whereas pointer equality cost 1.07ns. Within the context of a map, the cost goes up to 64.6ns whereas if key is integer, the cost is 5.7ns or 19.1ns (if a map hit or miss respectively).

In my codebase, I do map checks for integer keys, string keys and reflect.Type keys. The reflect.Type keys map access increased encoding time by over 10-20%, even with a 2-element map. 

http://play.golang.org/p/1evwkTYYlB

BenchmarkIntfEqual 100000000        14.7 ns/op

BenchmarkReflectTypeEqual 100000000        14.7 ns/op

BenchmarkPtrEqual 2000000000         1.08 ns/op

BenchmarkIntEqual 2000000000         0.72 ns/op

BenchmarkIntMapAccess 500000000         5.74 ns/op

BenchmarkReflectTypeMapAccess 50000000        64.6 ns/op

BenchmarkIntMapAccessMiss 100000000        19.1 ns/op

BenchmarkReflectTypeMapAccessMiss 50000000        64.8 ns/op

I'm not sure what else testing using the ID() function will show, since I've tested and shown the underlying concerns. 

[Ugorji]

On Monday, June 10, 2013 2:48:29 PM UTC-4, rsc wrote:

I added the ID() method to the Type interface as you suggested, and used it in my comparison checks (rt1.ID() == rt2.ID()) as well as my maps (map[uintptr]XXX instead of map[reflect.Type]XXX). 

The results using benchcmp:

/opt/go-contrib/misc/benchcmp ~/bench-orig.txt ~/bench-after-changes.txt 

benchmark                     old ns/op    new ns/op    delta

Benchmark__Msgpack__Encode        77860        62882  -19.24%

Benchmark__Msgpack__Decode       130156       119486   -8.20%

Benchmark__Binc_____Encode        69968        65513   -6.37%

Benchmark__Binc_____Decode       126137       120672   -4.33%

At least for my codecs, the benefits are significant. I think the same will hold for others too (e.g. encoding/gob, encoding/json which use map[reflect.Type]XXX).

As I alluded to in the last message I sent, it boils down to the following:

- interface comparison is expensive compared to integer comparison (14.7 vs 0.7 ns)

- map access with interface key is expensive compared to integer key (64.6 ns vs 5.7ns)

- In a codec which depends on recursively calling itself many times, these numbers add up significantly.

Following up with this, it's weird that interface comparison is so expensive. If interface comparison just checks that type is same and value is same, why is that taking about 20X the time that just the value comparison is taking? Can someone point me to the part of the code that does this so I can look at it?

Thanks.

Russ

[minux]

On Thu, Jun 13, 2013 at 2:01 AM, Ugorji <ugo...@gmail.com> wrote:

Following up with this, it's weird that interface comparison is so expensive. If interface comparison just checks that type is same and value is same, why is that taking about 20X the time that just the value comparison is taking? Can someone point me to the part of the code that does this so I can look at it?

function runtime.ifaceeq and runtime.efaceeq in pkg/runtime/iface.c 

[Keith Randall]

Keep in mind that map access with integer keys is special-cased, so that's probably not a fair comparison.  A better comparison would be to the key struct{x,y int}.

--
 
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Ugorji]

Thanks. Looking at it now. 

[Ugorji]

On Wednesday, June 12, 2013 2:21:05 PM UTC-4, Keith Randall wrote:

Keep in mind that map access with integer keys is special-cased, so that's probably not a fair comparison.  A better comparison would be to the key struct{x,y int}.

Yes, the more apt comparison will be between interface wrapping a pointer, and pointer (which is 14.7 ns vs 1.08 ns, which is 14X). 

The issue I'm raising is not about map access. I believe that's a result of reflect.Type/interface comparisons being expensive (compared to pointer or integer comparison), even when the interface dynamic type and value are just pointer type and pointer respectively (as in reflect.Type). I would expect struct comparison to be potentially expensive (since it compares field by field).

[Ugorji]

PING.

Can we get this in? It provides a much faster check for identity and much better performant key in a map for reflect.Type, which can be a bottleneck in some fast-paths (e.g. encoding where functions are registered per type). 

Thanks.

[Ian Lance Taylor]

On Thu, Aug 8, 2013 at 7:52 AM, Ugorji <ugo...@gmail.com> wrote:
> PING.
>
> Can we get this in? It provides a much faster check for identity and much
> better performant key in a map for reflect.Type, which can be a bottleneck
> in some fast-paths (e.g. encoding where functions are registered per type).

Sorry, I'm not really clear on what it is that you want to get in.
You've mentioned an idea but there is no implementation. And I'm not
even quite clear on the idea. Is the idea is that we should speed up
maps with a key of interface type? Or is the idea that we should up
comparisons of interfaces for equality? And, whichever idea it is,
how exactly should we do it?

Ian

[Ugorji]

On Thursday, August 8, 2013 11:29:56 AM UTC-4, Ian Lance Taylor wrote:

On Thu, Aug 8, 2013 at 7:52 AM, Ugorji <ugo...@gmail.com> wrote:
> PING.
>
> Can we get this in? It provides a much faster check for identity and much
> better performant key in a map for reflect.Type, which can be a bottleneck
> in some fast-paths (e.g. encoding where functions are registered per type).

Sorry, I'm not really clear on what it is that you want to get in.
You've mentioned an idea but there is no implementation.  And I'm not
even quite clear on the idea.  Is the idea is that we should speed up
maps with a key of interface type?  Or is the idea that we should up
comparisons of interfaces for equality?  And, whichever idea it is,
how exactly should we do it?

Ian

Getting in the ID() method on reflect.Type, as Russ mentioned:

1. Add ID() uintptr to the type reflect.Type interface definition.

2. Add func(t *rtype) ID() uintptr { return uintptr(unsafe.Pointer(t)) }

This is low hanging fruit that is beneficial, even if future work speeds up equality check of interface types and map access with interface keys. 

I can prepare a CL.

[Brad Fitzpatrick]

We can't add a method to an interface type, per the Go 1 API promise.

Also, Russ didn't say that it was a good idea either.  He said:

"If it makes a significant difference, then that doesn't mean we are going to add this method, it just provides better evidence that the implementation of maps of interfaces needs to be made better."

[Russ Cox]

Gmail is hiding the most important part of Brad's mail, namely that I wrote: "If it makes a significant difference, then that doesn't mean we are going to add this method, it just provides better evidence that the implementation of maps of interfaces needs to be made better."

We can add methods to interfaces with unexported methods, such as reflect.Type. But that doesn't mean we're going to.

Russ

[Ugorji]

To be clear, let me list the reasons why I think this is a good API addition:

1. It is consistent with the spirit of reflect.Type. There is a single reflect.Type instance returned by TypeOf for any given type. Having an ID() method for comparison or identification is consistent with that.

2. It provides very fast equality check. No matter how fast we make interface comparison (which by definition is more involved), it cannot come close to integer comparison. In a deeply recursive function where you have to check if an interface type is one of a given set everytime the function is called, integer comparison is much faster. 

3. It affords very fast map access when needed. Integer map keys will always be the fastest and most performant map keys. When trying to extract performance in the fast path (e.g. encoders which run everytime data is read or written to memory or disk), this is very significant.

4. It's a 2-line addition (for gc compiler support at least). Very low cost, but very high reward.

In my codec (for binc/msgpack), I allow the user register an encoding and decoding function for any type. 

http://godoc.org/github.com/ugorji/go/codec#BincHandle.AddExt

Encode/Decode is a recursive function which calls itself while walking a struct, map, slice, array, etc. Each time, I look at current value and get the type. I then first check a list of builtin types in a loop to see if the type matches one of them, and if so, calls the builtin enc/dec function. If it doesn't match any of the builtin types, I then check a map for registered enc/dec functions, and if there, call the registered one. I do this each time the recursive function calls itself (e.g. walking a struct, map, slice, array). As you can imagine, the comparison checks and map access checks happening every entry into a recursive "en/decodeValue" function can get expensive. Doing integer comparisons and map access of integer keys improves performance significantly.

If JSON allows registering a function based on the type, I can see this becoming a problem that it would have to solve also. 

This is not just about maps with interface keys, or interface comparison. This is about reflect.Type which is pretty fundamental (as fundamental as java.lang.Class is to java programmers).

I think this API addition is very much worth its very low cost. 

[Russ Cox]

On Thu, Aug 8, 2013 at 2:23 PM, Ugorji <ugo...@gmail.com> wrote:

To be clear, let me list the reasons why I think this is a good API addition:

1. It is consistent with the spirit of reflect.Type. There is a single reflect.Type instance returned by TypeOf for any given type. Having an ID() method for comparison or identification is consistent with that.

The reflect.Type is already perfectly fine for comparison or identification. If we introduce ID then we will have some things using the ID and some things using the reflect.Type. Everything today uses reflect.Type; there is no confusion.

 

2. It provides very fast equality check. No matter how fast we make interface comparison (which by definition is more involved), it cannot come close to integer comparison. In a deeply recursive function where you have to check if an interface type is one of a given set everytime the function is called, integer comparison is much faster. 

An interface comparison here is two integer comparisons. That's good enough.

3. It affords very fast map access when needed. Integer map keys will always be the fastest and most performant map keys. When trying to extract performance in the fast path (e.g. encoders which run everytime data is read or written to memory or disk), this is very significant.

4. It's a 2-line addition (for gc compiler support at least). Very low cost, but very high reward.

It is a 2-line addition but it is an API we will have to support forever, and it causes the ambiguity I mentioned above. Even small things can have big costs.

There's no reward here, just opportunities to make operations on interfaces faster.

Russ

[Brad Fitzpatrick]

You can do this already in your own code.

Make two files:

typeid_safe.go

typeid_unsafe.go

Mark one as +build appengine, and one as +build !appengine.

In the unsafe one, use unsafe.

func TypeID(t reflect.Type) uintptr

func Type(id uintptr) reflect.Type

In the safe one, implement with:

var (

      mu sync.Mutex

      mt map[uintptr]reflect.Type

      mi map[reflect.Type]uintptr

)

etc

Now you run everywhere, and our API isn't any uglier.

[Ugorji]

Fair enough. If interface equality check is equivalent to a few integer comparisons, and maps with interface keys can perform considerably better, then that is definitely good enough. I had looked at runtime.ifaceeq and runtime.efaceeq to try to understand why interface equality check was much slower than integer equality check, but couldn't figure it out. 

I'd file an issue to track it, including the benchmarks I created previously.

 

Russ

[Ugorji]

On Thursday, August 8, 2013 2:32:03 PM UTC-4, Brad Fitzpatrick wrote:

You can do this already in your own code.

Make two files:

typeid_safe.go

typeid_unsafe.go

Mark one as +build appengine, and one as +build !appengine.

In the unsafe one, use unsafe.

func TypeID(t reflect.Type) uintptr

func Type(id uintptr) reflect.Type

In the safe one, implement with:

var (

      mu sync.Mutex

      mt map[uintptr]reflect.Type

      mi map[reflect.Type]uintptr

)

This doesn't help, as I am trying to bypass looking into a map with reflect.Type (interface) key. Your proposal includes another level of abstraction that involves a map with reflect.Type key. 

If interface comparison is as fast as 2'ish integer comparisons, and interface key in map is not much slower than integer keys, then that will be a good enough solution.

[Russ Cox]

If you need a stopgap, use 

var t reflect.Type

reflect.ValueOf(t).Pointer()

as your ID.

[Ugorji]

I had looked into this previously, but couldn't use that because Pointer() is only available for specific kinds (not available for types based on kinds: struct, int, etc). 

[Russ Cox]

That's not what I suggested. What I wrote gets the Pointer of the reflect.Type implementation, which is always available.

[Ugorji]

Aha. Yes, I get it now. I misunderstood it back when I had read the docs previously. Will try that and see what performance benefits it may provide.

Thanks.

 

[Ugorji]

Filed https://code.google.com/p/go/issues/detail?id=6106 and https://code.google.com/p/go/issues/detail?id=6105 

Russ

[jonathan....@gmail.com]

I was bumping into this problem recently.  The reflect.ValueOf(type).Pointer() solution was actually slower than simply having a map[string]XXX and using reflect.TypeOf(...).String()

I agree that having a faster comparison would be nice--especially for an operation that I'm performing millions of times per second.