# Indexing hash with longer strings faster? **URL:** \ **Category:** Ruby\ **Created:** [July 28, 2009, 6:50pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833 "2009-07-28T18:50:35Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 28, 2009, 6:50pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/1 "2009-07-28T18:50:35Z")
Hi, I have some wierd results measuring Ruby’s hash operations, particulary indexing hash using two member string array. Have a look: > > require ‘benchmark’ > > =\> false > > > puts(Benchmark.measure do > > ?\> h = {} > > > 1000000.times do |i| > > ?\> i1 = rand(100) > > > ``` > > i2 = rand(100) > > a = [i1.to_s, i2.to_s] > > h[a] ||= 0 > > h[a] += 1 > > > > ``` > > > > end > > puts h.size > > end) > > 10000 > > 12.900000 0.050000 12.950000 ( 13.088721) > > =\> nil > > > puts(Benchmark.measure do > > ?\> h = {} > > > 1000000.times do |i| > > ?\> i1 = rand(100) > > > ``` > > i2 = rand(100) > > a = [i1.to_s + '00000', i2.to_s + '00000'] > > h[a] ||= 0 > > h[a] += 1 > > > > ``` > > > > end > > puts h.size > > end) > > 10000 > > 7.700000 0.040000 7.740000 ( 7.858381) > > =\> nil In other words, I just made array members slightly longer and working with hash was considerably faster. Why’s that happening? BTW, jablan-mbp:~ $ ruby -v ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0] ---
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 28, 2009, 7:52pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/2 "2009-07-28T19:52:39Z")
On Tue, Jul 28, 2009 at 6:50 PM, jablan[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: Benchmarking is tricky business. I am not sure my benchmarks are worth much, but they do not confirm your results. BTW using: ruby 1.9.1p243 (2009-07-16 revision 24175) [i686-linux] First you really should not bm inside irb. Second you should use bmbm for rehearsals, but even with that you could get bitten by tons of things happening on your machine. Nevertheless for whats worth it - and because I adore benchmarking 😉 - here is my code and results: require ‘benchmark’ N = 100\_000 5.times do Benchmark.bmbm do | bm | h = Hash::new( 0 ) bm.report( “2 chars” ) do N.times do h[[rand(100).to\_s, rand(100).to\_s] ] += 1 end end h = Hash::new( 0 ) bm.report( “7 chars” ) do N.times do h[[rand(100).to\_s + “00000”, rand(100).to\_s + “00000”] ] += 1 end end end end robert@siena:~/log/ruby/ML 19:50:13 519/25 \> ruby bm1.rb Rehearsal ------------------------------------------- 2 chars 0.700000 0.010000 0.710000 ( 0.953483) 7 chars 0.960000 0.010000 0.970000 ( 1.367117) ---------------------------------- total: 1.680000sec ``` user system total real ``` 2 chars 0.740000 0.020000 0.760000 ( 1.031102) 7 chars 1.010000 0.020000 1.030000 ( 1.323072) Rehearsal ------------------------------------------- 2 chars 0.720000 0.000000 0.720000 ( 0.955180) 7 chars 0.980000 0.010000 0.990000 ( 1.320693) ---------------------------------- total: 1.710000sec ``` user system total real ``` 2 chars 0.710000 0.000000 0.710000 ( 0.923019) 7 chars 0.900000 0.010000 0.910000 ( 1.262338) Rehearsal ------------------------------------------- 2 chars 0.700000 0.000000 0.700000 ( 0.926117) 7 chars 0.990000 0.020000 1.010000 ( 1.356475) ---------------------------------- total: 1.710000sec ``` user system total real ``` 2 chars 0.710000 0.000000 0.710000 ( 0.940901) 7 chars 0.880000 0.020000 0.900000 ( 1.269465) Rehearsal ------------------------------------------- 2 chars 0.700000 0.010000 0.710000 ( 1.016537) 7 chars 0.990000 0.010000 1.000000 ( 1.360516) ---------------------------------- total: 1.710000sec ``` user system total real ``` 2 chars 0.720000 0.010000 0.730000 ( 0.920533) 7 chars 0.920000 0.000000 0.920000 ( 1.198681) Rehearsal ------------------------------------------- 2 chars 0.720000 0.010000 0.730000 ( 0.946056) 7 chars 1.020000 0.010000 1.030000 ( 1.343575) ---------------------------------- total: 1.760000sec ``` user system total real ``` 2 chars 0.720000 0.010000 0.730000 ( 1.023185) 7 chars 0.930000 0.000000 0.930000 ( 1.211184) – Toutes les grandes personnes ont d’abord été des enfants, mais peu d’entre elles s’en souviennent. All adults have been children first, but not many remember. [Antoine de Saint-Exupéry] ---
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 28, 2009, 8:16pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/3 "2009-07-28T20:16:05Z")
First, thanks a lot for your benchmarking tips, I’m new in the business; and thanks for your BM-friendly rewrite of my code. However, I still keep getting unexpected results: jablan-mbp:dev $ ruby bm1.rb Rehearsal ------------------------------------------- 2 chars 0.840000 0.000000 0.840000 ( 0.863001) 7 chars 0.590000 0.010000 0.600000 ( 0.597103) ---------------------------------- total: 1.440000sec ``` user system total real ``` 2 chars 0.900000 0.000000 0.900000 ( 0.909053) 7 chars 0.620000 0.000000 0.620000 ( 0.644989) Rehearsal ------------------------------------------- 2 chars 0.910000 0.000000 0.910000 ( 0.924786) 7 chars 0.620000 0.010000 0.630000 ( 0.631793) ---------------------------------- total: 1.540000sec ``` user system total real ``` 2 chars 0.900000 0.000000 0.900000 ( 0.909935) 7 chars 0.570000 0.000000 0.570000 ( 0.578445) Rehearsal ------------------------------------------- 2 chars 0.880000 0.010000 0.890000 ( 0.892464) 7 chars 0.650000 0.000000 0.650000 ( 0.672226) ---------------------------------- total: 1.540000sec ``` user system total real ``` 2 chars 0.910000 0.010000 0.920000 ( 0.947815) 7 chars 0.580000 0.000000 0.580000 ( 0.593960) Rehearsal ------------------------------------------- 2 chars 0.890000 0.010000 0.900000 ( 0.896618) 7 chars 0.650000 0.000000 0.650000 ( 0.660125) ---------------------------------- total: 1.550000sec ``` user system total real ``` 2 chars 0.900000 0.000000 0.900000 ( 0.919042) 7 chars 0.590000 0.010000 0.600000 ( 0.595202) Rehearsal ------------------------------------------- 2 chars 0.900000 0.000000 0.900000 ( 0.913919) 7 chars 0.660000 0.010000 0.670000 ( 0.682484) ---------------------------------- total: 1.570000sec ``` user system total real ``` 2 chars 0.920000 0.000000 0.920000 ( 0.950286) 7 chars 0.590000 0.010000 0.600000 ( 0.601025) I will try to run the code on other platforms and/or ruby versions and I will post the findings… The bad thing is that I’m not doing this just for kicks, I need to optimise a nasty script… ☹ ---
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 28, 2009, 9:20pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/4 "2009-07-28T21:20:28Z")
On Tue, Jul 28, 2009 at 9:16 PM, Robert D.[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > can you try this in 1.8 >  …map{ |x| x.hash }.uniq.size Sorry forgot two things you did not produce 00, 01, thus [\*0…99].map( &:to\_s ).map( a:hash ) and secondly, a negative result does not say anything about collisions, only a positive (result \< 100) would. In that case we would need to look into the source, ( I do not think profiling might show internal hash behavior ). Cheers Robert > [Antoine de Saint-Exupéry] – Toutes les grandes personnes ont d’abord été des enfants, mais peu d’entre elles s’en souviennent. All adults have been children first, but not many remember. [Antoine de Saint-Exupéry] ---
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 29, 2009, 5:16pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/5 "2009-07-29T17:16:16Z")
You pointed to the right direction here! Although your example gives me 100 as result (all the hashes are unique), here’s what suggests that hash collision indeed is the reason of the slowness: > > [\*0…99].map{|i| [\*0…99].map{|j| [i.to\_s,j.to\_s].hash}}.flatten.uniq.size > > =\> 1756 > > > [\*0…99].map{|i| [\*0…99].map{|j| [i.to\_s + ‘00000’,j.to\_s + ‘00000’].hash}}.flatten.uniq.size > > =\> 10000 Can you please just post the ruby 1.9 results here? Thanks! ---
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 28, 2009, 9:18pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/6 "2009-07-28T21:18:07Z")
2009/7/28 Mladen Jablanović [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): Is this 1.8? Given your results it is not completely unthinkable that the hash values for “00”…“99” have more collisions and if collision handling is with linked lists that might slow down. A priori I would not believe in that but why not check? I get in 1.9 the expected [\*“00”…“99”].map( &:hash ).uniq.size =\> 100 can you try this in 1.8 …map{ |x| x.hash }.uniq.size ? ## HTH Robert Toutes les grandes personnes ont d’abord été des enfants, mais peu d’entre elles s’en souviennent. All adults have been children first, but not many remember. [Antoine de Saint-Exupéry] ---
**Author:** ![jablan](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/c6cbf5/32.png) [@jablan](https://www.ruby-forum.com/u/jablan)\ **Post date:** [July 29, 2009, 6:23pm UTC](https://www.ruby-forum.com/t/indexing-hash-with-longer-strings-faster/172833/7 "2009-07-29T18:23:34Z")
2009/7/29 Mladen Jablanović [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > You pointed to the right direction here! > > Although your example gives me 100 as result (all the hashes are > unique), here’s what suggests that hash collision indeed is the reason > of the slowness: > > > > [\*0…99].map{|i| [\*0…99].map{|j| [i.to\_s,j.to\_s].hash}}.flatten.uniq.size > > > =\> 1756 > > > [\*0…99].map{|i| [\*0…99].map{|j| [i.to\_s + ‘00000’,j.to\_s + ‘00000’].hash}}.flatten.uniq.size > > > =\> 10000 OMG my code was sloppy, but you got it right, here is the 1.9 code 506/18 \> cat hashes.rb && ruby -v hashes.rb #!/usr/local/bin/ruby -w # encoding: utf-8 # file: /home/robert/log/ruby/ML/hashes.rb p [\*0…99].map{|i| [\*0…99].map{|j| [i.to\_s,j.to\_s].hash}}.flatten.uniq.size p [\*0…99].map{|i| [\*0…99].map{|j| [i.to\_s + ‘00000’,j.to\_s + ‘00000’].hash}}.flatten.uniq.size # vim: sts=2 sw=2 ft=ruby expandtab nu : ruby 1.9.1p243 (2009-07-16 revision 24175) [i686-linux] 10000 10000 as expected :). Cheers Robert > Can you please just post the ruby 1.9 results here? > > Thanks! – Toutes les grandes personnes ont d’abord été des enfants, mais peu d’entre elles s’en souviennent. All adults have been children first, but not many remember. [Antoine de Saint-Exupéry]