Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: map access quite slow with interface key compared to integer key (over 10X slower) #6106

Closed
ugorji opened this issue Aug 11, 2013 · 7 comments
Milestone

Comments

@ugorji
Copy link
Contributor

ugorji commented Aug 11, 2013

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

Results:
BenchmarkIntfEqual  100000000            14.5 ns/op
BenchmarkReflectTypeEqual   100000000    14.4 ns/op
BenchmarkPtrEqual   2000000000           1.06 ns/op
BenchmarkIntEqual   2000000000           0.70 ns/op
BenchmarkIntMapAccess   500000000            5.22 ns/op
BenchmarkReflectTypeMapAccess   50000000     57.6 ns/op
BenchmarkIntMapAccessMiss   100000000           16.4 ns/op
BenchmarkReflectTypeMapAccessMiss   50000000    58.3 ns/op

Which compiler are you using (5g, 6g, 8g, gccgo)?
6g

Which operating system are you using?
Linux 3.8.0-27-generic #40-Ubuntu SMP Tue Jul 9 00:17:05 UTC 2013 x86_64 x86_64 x86_64
GNU/Linux

Which version are you using?  (run 'go version')
go version devel +21ae2c5817da Fri Aug 09 23:23:34 2013 +1000 linux/amd64

Please provide any additional information below.

Groups discussion leading to this is at:
https://groups.google.com/d/msg/golang-dev/Oik3353DJ2w/aNxNhwC9J_kJ
@cznic
Copy link
Contributor

cznic commented Aug 11, 2013

Comment 1:

Don't use 'interface{}' typed map keys if you're after performance. In the case of
'interface{}' typed keys, there are probably three things that must be checked _at
runtime_: 
- If both "sides" of the cmp are of same types.
- If that type has '==' defined. ([]slices do not, for example)
- If the values are equal or not, but only using a dynamically dispatched "comparator"
(a function call, I guess).
If you compare this to the single instruction that the compiler can emit for comparing
two integers, the 10 times slowdown seems to me not surprising at all.

@robpike
Copy link
Contributor

robpike commented Aug 12, 2013

Comment 2:

Marking as WontFix because the analysis presented by 0xjnml is right: we expect it to be
slower because no specialization is possible. If you think it's unreasonably slow (I
don't), please reopen the issue and say why.

Status changed to WontFix.

@robpike
Copy link
Contributor

robpike commented Aug 12, 2013

Comment 3:

Issue #6105 has been merged into this issue.

@ugorji
Copy link
Contributor Author

ugorji commented Aug 12, 2013

Comment 4:

This issue was filed as a result of discussion in
https://groups.google.com/d/msg/golang-dev/Oik3353DJ2w/aNxNhwC9J_kJ
The genesis of the thread was to find a fast way to do comparison checks for
reflect.Type or do fast map access with reflect.Type keys. I needed this because I was
building an encoder where users could map reflect.Type to custom encode/decode
functions. Doing a map access every time the recursive function was called caused a
performance hit.
This is fleshed out in that same thread above, or linked directly at
https://groups.google.com/d/msg/golang-dev/Oik3353DJ2w/gPPLMfONvIAJ
In that thread, Russ mentioned that interface comparison should be equivalent to 2
integer comparisons, and we can look to make operations on interfaces faster (instead of
working around them). Direct link:
https://groups.google.com/d/msg/golang-dev/Oik3353DJ2w/d6ei8LbyehEJ
I filed the issues separately because, even though they look like the same issue to me,
they might not be. Keith may look into maps with interface keys, while someone else
looks into interface comparison.
Can Russ weigh in on this before we finalize this as WNF, and merge both of them?. He
has more context per the discussion.

@cznic
Copy link
Contributor

cznic commented Aug 12, 2013

Comment 5:

@4: IMO Russ by "equivalent to 2 integer comparisons" meant comparing two reflect.Type
values for equality (ie. types referred to by them are identical). But that's only the
step #1 (of 3) mentioned in one of the previous posts.

@rsc
Copy link
Contributor

rsc commented Aug 13, 2013

Comment 6:

0xjnml is right and I was wrong. You do need more than 2 comparisons in general.
If you need reflect.Type to be faster in particular, my suggestion is to use the Pointer
trick I suggested.

@ugorji
Copy link
Contributor Author

ugorji commented Aug 13, 2013

Comment 7:

Thanks.
I tried the Pointer trick 2 days ago and it worked well, giving roughly the same
performance benefits as the ID() hack I tried previously (from 4-20% perf improvement).
This took care of my immediate need.
Having said that, I think we should keep the previous issue (6105) open at least. There
may be some things we can do to improve interface comparisons in some specific scenarios:
- for pointer types when the types are equal. For example, comparing reflect.Type falls
into this category, and the comparison is that both are *rtype and both pointers are
equal.
- base types which are numbers or booleans.
We could do a fast path for these common and seemingly trivial interface comparisons, to
improve their performance to something less than the 20X.
Currently, the 20X for equality check vs non-interface equality of same underlying value
seems excessive.
Disclaimer: I looked through the runtime.ifaceeq and runtime.efaceeq but couldn't figure
it out.

@rsc rsc added this to the Go1.2 milestone Apr 14, 2015
@rsc rsc removed the go1.2maybe label Apr 14, 2015
@golang golang locked and limited conversation to collaborators Jun 24, 2016
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants