Bug #11396
closedBad performance in ruby >= 2.2 for Hash with many symbol keys
Description
This started out as an issue on stackoverflow, where I found strange performance anomalies when comparing Set.include? and Array.include? in different ruby versions: http://stackoverflow.com/questions/31631284/performance-anomaly-in-ruby-set-include-with-symbols-2-2-2-vs-2-1-6
In the end it came down to problems with lookup of Hash keys. While for smaller Hashes the performance issues went away using ruby_2_2 branch, they staid for bigger Hashes. I'll attach a benchmark script (hash_bench_3.rb) I used that creates a Hash with 200000 keys and does a lookup of 10000 of them.
Here my results:
ruby 2.1.6p336 (2015-04-13 revision 50298) [x86_64-darwin14.0]
string 142.818 (± 2.8%) i/s - 714.000
symbol 505.831 (± 3.0%) i/s - 2.550k
ruby 2.2.2p95 (2015-04-13 revision 50295) [x86_64-darwin14]
string 143.404 (± 3.5%) i/s - 728.000
symbol 76.945 (± 6.5%) i/s - 385.000
ruby 2.2.3p147 (2015-07-04 revision 51143) [x86_64-darwin14] self-compiled
string 138.349 (± 2.2%) i/s - 702.000
symbol 77.495 (± 3.9%) i/s - 392.000
As you can see 2.2 is much slower than 2.1.6 for symbol keys. I was recommended to disable Garbage Collection for Symbols for testing and did so on the ruby_2_2 branch
ruby 2.2.3p147 (2015-07-04 revision 51143) [x86_64-darwin14] self-compiled, USE_SYMBOL_GC=0
string 145.179 (± 3.4%) i/s - 728.000
symbol 602.008 (± 7.6%) i/s - 3.050k
I would have expected that symbol GC may have some performance impact, but this looks like it is too big. I can't say exactly at which point Garbage Collection really hurts, but the bigger the Hash and the bigger the number of include? calls, the slower it gets.
Files
Updated by brunoe (Bruno Escherl) over 9 years ago
- Description updated (diff)
Updated by brunoe (Bruno Escherl) over 9 years ago
- Description updated (diff)
Updated by normalperson (Eric Wong) over 9 years ago
Possible fix is to memoize hashval inside struct RSymbol:
http://80x24.org/spew/m/1437992270-20549-1-git-send-email-e@80x24.org.txt
Much better than before, but still slower than 2.1, I think.
Only lightly-tested, and on hardware which doesn't benefit from
power-of-two sizing anyways. Sorry busy and don't have access to
better HW for benchmarking for a few days.
Updated by brunoe (Bruno Escherl) over 9 years ago
Eric Wong wrote:
Possible fix is to memoize hashval inside struct RSymbol:
http://80x24.org/spew/m/1437992270-20549-1-git-send-email-e@80x24.org.txt
Much better than before, but still slower than 2.1, I think.
Only lightly-tested, and on hardware which doesn't benefit from
power-of-two sizing anyways. Sorry busy and don't have access to
better HW for benchmarking for a few days.
Hi Eric, I compiled the ruby_2_2 branch with your patch and got the following results
ruby 2.1.6p336 (2015-04-13 revision 50298) [x86_64-darwin14.0]
string 144.345 (± 3.5%) i/s - 728.000
symbol 506.609 (± 2.4%) i/s - 2.550k
ruby 2.2.3p147 (2015-07-04 revision 51143) [x86_64-darwin14] without patch
string 138.830 (± 6.5%) i/s - 700.000
symbol 75.236 (± 4.0%) i/s - 378.000
ruby 2.2.3p147 (2015-07-04 revision 51143) [x86_64-darwin14] with patch
string 147.566 (± 4.7%) i/s - 742.000
symbol 495.675 (± 6.9%) i/s - 2.494k
The patch is working and getting quite close to 2.1.6 :-)
For more realistic hashes I also used the script with 2000 keys and 100 lookups:
ruby 2.1.6p336 (2015-04-13 revision 50298) [x86_64-darwin14.0]
string 43.020k (± 1.1%) i/s - 217.406k
symbol 72.882k (± 0.9%) i/s - 367.565k
ruby 2.2.2p95 (2015-04-13 revision 50295) [x86_64-darwin14]
string 43.348k (± 2.8%) i/s - 219.402k
symbol 22.336k (± 3.6%) i/s - 113.049k
ruby 2.2.3p147 (2015-07-04 revision 51143) [x86_64-darwin14] without patch
string 44.412k (± 3.9%) i/s - 224.773k
symbol 41.240k (± 3.3%) i/s - 209.721k
ruby 2.2.3p147 (2015-07-04 revision 51143) [x86_64-darwin14] with patch
string 44.537k (± 2.3%) i/s - 224.561k
symbol 85.511k (± 1.7%) i/s - 427.952k
So performance-wise this looks great! Can't judge of course, if there could be other side effects of this change.
Updated by normalperson (Eric Wong) over 9 years ago
- Backport changed from 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN to 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: REQUIRED
Updated by Anonymous over 9 years ago
- Status changed from Open to Closed
Applied in changeset r51410.
symbol.h: memoize hashval for RSymbol
This speeds up the hash function for dynamic symbols.
[ruby-core:70129] [Bug #11396], nearly up to Ruby 2.1 levels
Power-of-two hash sizing [Feature #9425] speeds up cases where we
have a good hash, but this means we can no longer hide behind weak
hashes. Unfortunately, object IDs do not hash well, but we may
use the extra space in the RSymbol struct to memoize the hash value.
Further optimizations should be possible. For now, the st.c APIs
force us to calculate rb_str_hash redundantly at dsym registration.
- symbol.h (struct RSymbol): add hashval field
- symbol.c (dsymbol_alloc): setup hashval field once
- hash.c (rb_any_hash): return RSymbol->hashval directly
- common.mk: hash.o depends on symbol.h
Thanks to Bruno Escherl bruno@escherl.net for the bug report
[ruby-core:70129] [Bug #11396]
Updated by normalperson (Eric Wong) over 9 years ago
Thanks for testing, committed as r51410 and 2.2 backport requested.
The only downside is slightly increased dynamic symbol registration
time because of the redundant call to rb_str_hash, but I doubt anybody
would notice. There's no extra space overhead since RSymbol wasn't
using all the space available provided by RVALUE (40 bytes on 64-bit)
before. Now it is.
I also considered making the `id' field based on the hash value last
year, but haven't gotten around to trying it (dealing with conflicts
might make it more trouble than it's worth).
Updated by dunric (David Unric) over 9 years ago
I can report patch is functional and seems to be working also on current ruby_2_2 branch [ruby 2.2.3p147 (2015-07-04 revision 51143)] .
What about pushing commit also to this branch ? More testing needed ?
The speed-up is drastic, tempting to have it in next 2.2 release yet before 2.3 comes out.
Updated by normalperson (Eric Wong) over 9 years ago
Thanks for testing. A backporter will backport it to 2.2 since this
is a regression.
I am also working on more improvements, rb_objid_hash seems weak.
Updated by normalperson (Eric Wong) over 9 years ago
Eric Wong normalperson@yhbt.net wrote:
I am also working on more improvements, rb_objid_hash seems weak.
Maybe this:
http://80x24.org/spew/m/88e7b6dcf59adf35c5c292c91c54cb7b986bd4a4.txt
Updated by nagachika (Tomoyuki Chikanaga) about 9 years ago
Thank you for testing the patch on ruby_2_2
branch.
r51410 was backported into ruby_2_2
branch at r51589.
Updated by nagachika (Tomoyuki Chikanaga) about 9 years ago
- Backport changed from 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: REQUIRED to 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: DONE
Updated by usa (Usaku NAKAMURA) about 9 years ago
- Backport changed from 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: DONE to 2.0.0: DONTNEED, 2.1: DONTNEED, 2.2: DONE