From: "David G. Andersen" <dga@...>
Date: 2004-11-07T13:58:03+09:00
Subject: Ruby hashes (was: Ruby is a slow performer)

On Sun, Nov 07, 2004 at 11:18:39AM +0900, Christian Szegedy scribed:
> David G. Andersen wrote:
> 
> > Disabling the GC doesn't help most of the hash-bound benchmarks
> > much if they're written properly.  The basic loop iteration is
> > quite fast if you remove the hash access.  You can draw your own
> > conclusions from this.
> >
> 
> Hihi, you are so self-confident. I made some tests, and in fact,
> it turned out, that the hash access is not the problem at all:
> 
> The original code is:

Actually, I was referring more to the performance of the
other hash tests -- you'll note in the comments for the example you
cited below that the test author believes the "hash 1" test to
be dominated by sprintf performance, not hash performance.

Consider instead the code

n = Integer(ARGV.shift || 1)

hash1 = {}
for i in 0 .. 9999
    hash1["foo_" << i.to_s] = i
end

hash2 = Hash.new(0)
n.times do
    for k in hash1.keys
	hash2[k] += hash1[k]
    end
end

printf "%d %d %d %d\n",
    hash1["foo_1"], hash1["foo_9999"], hash2["foo_1"], hash2["foo_9999"]


Which is pretty close to your example of:  

> hash[i.to_s] = 1

but it forces the hashing into a string context so that languages
that don't make a strong distinction between strings and numbers
can't cheat (hi, perl. ;-).  Or consider the "word frequency" test -
it's pretty hash dominated.  For the hash2 test:

503 eep:~> time ./t-hash2.rb 100
1 9999 100 999900
3.518u 0.031s 0:03.70 95.6%     5+4499k 0+0io 0pf+0w

Without the hash access:

505 eep:~> time ./t-hash2.rb 100
1 9999 0 0
0.635u 0.023s 0:00.66 98.4%     14+3998k 0+0io 0pf+0w

(the loop overhead and initial hash creation don't add too much)

With the hash access changed to only be the LHS : hash2[k] += 1

507 eep:~> time ./t-hash2.rb 100
1 9999 100 100
2.793u 0.031s 0:03.35 84.1%     7+4521k 0+0io 0pf+0w

And just accessing the RHS:  hash1[k]

510 eep:~> time ./t-hash2.rb 100
1 9999 0 0
1.590u 0.023s 0:01.68 95.8%     8+4233k 0+0io 0pf+0w

it's pretty clear that assigning to a hash is the most expensive
operation.  The perl equivalent takes
2.367u 0.031s 0:02.48 96.3%     850+3242k 0+0io 0pf+0w

The ruby version could be improved a bit by pre-declaring the
loop variables, but this is all contained within that .66 seconds
that wasn't the hash access;  even if we eliminated it all,
we're still slower than the perl equivalent.  Predeclaring:

520 eep:~> time ./t-hash2.rb 100
1 9999 100 999900
3.349u 0.015s 0:03.49 95.9%     6+4524k 0+0io 0pf+0w

Now, is it the actual hash implementation that's the bottleneck,
or merely the operations required to access it?  That I don't know.
But hash[blah] = blah _does_ seem to be measurably slower than
its equivalent in, say, perl.  It's not drastic, but it's 20%.

  -Dave

-- 
work: dga@lcs.mit.edu                          me:  dga@pobox.com
      MIT Laboratory for Computer Science           http://www.angio.net/