From: Robert Klemme <shortcutter@...>
Date: 2008-09-03T18:24:20+09:00
Subject: Re: Hash optimization question

2008/9/3 Roger Pack <rogerpack2005@gmail.com>:
> Are there any libraries that overcome this problem:
>
> (slow example)
>
>>> Benchmark.measure { a = {:abc => :def}; 100_000.times { a.each{}}}
> => #<... @real=0.113940954208374, @utime=0.0999999999999999,
> @cstime=0.0>
>
> (fast example)
>
>>> Benchmark.measure { a = {:abc => :def}.to_a; 100_000.times { a.each{}}}
> => #<...@real=0.0591599941253662, @utime=0.0600000000000001,
> @cstime=0.0>
>
>
> I.e. they optimize hashes such that their .each_xxx functions work as
> fast as arrays?
> My gut instinct is that this is a problem that could be overcome with
> some hacking in the core, but thought I'd ask.

No idea, you would have to look at the sources.

A few thoughts nevertheless: if you have to do the array conversion
prior to iterating then numbers suffer dramatically:

irb(main):003:0> Benchmark.measure { a = {:abc => :def}.to_a;
1_000_000.times { a.each{}}}
=> #<Benchmark::Tms:0x7fed1744 @label="", @real=0.641000032424927,
@cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.641, @total=0.641>

irb(main):004:0> Benchmark.measure { a = {:abc => :def};
1_000_000.times { a.each{}}}
=> #<Benchmark::Tms:0x10013be0 @label="", @real=2.58999991416931,
@cstime=0.0, @cutime=0.0, @stime=0.0, @utime=2.578, @total=2.578>

irb(main):005:0> Benchmark.measure { a = {:abc => :def};
1_000_000.times { a.to_a.each{}}}
=> #<Benchmark::Tms:0x7fee2184 @label="", @real=4.41000008583069,
@cstime=0.0, @cutime=0.0, @stime=0.0, @utime=4.422, @total=4.422>

In other words: if speeding up relies on building an Array like
structure iterating will be dramatically slower - unless you want to
waste the added space of an Array representation and add the logic to
keep track of changes.

I haven't looked into Ruby's Hash iterating in detail but it might be
slower because of a general properties of hash tables: they are
usually bigger (i.e. have more buckets) than the number of elements in
the hash to allow for efficient hashing. Now if there are no links
between hash entries (whose maintenance I believe would increase
insertion overhead) iteration needs to access each hash bucket even
those with no data in.  That might account for the slower runtimes.

I guess it will be difficult to get both: fast hash lookup and
insertion on one hand and fast iteration on the other hand.  Is it
worth the effort?  I don't know.  This depends on your application.
Where is this a problem for you?  Maybe there is a more efficient data
structure for your particular problem.

Kind regards

robert

-- 
use.inject do |as, often| as.you_can - without end