From: Robert Klemme <bob.news@...>
Date: 2006-01-02T22:17:58+09:00
Subject: Re: strange speeds

------=_NextPart_000_0006_01C60FA6.CE1C5970
Content-Type: text/plain;
	format=flowed;
	charset="ISO-8859-2";
	reply-type=response
Content-Transfer-Encoding: 7bit

kryglik <kryglik@iol.cz> wrote:
> Robert Klemme wrote:
>> kryglik <kryglik@iol.cz> wrote:
>>> Hello ruby people,
>>>  I've tried to make some speed test in ruby to find out how fast is
>>> searching in hash (using has_key?)
>>>
>>> The results were OK but I discovered curious thing -- when i
>>> generate big hash the speed is different when i unserialize
>>> (marshal.load) the same hash.
>>>
>>> Unserialized Hash is 1.5x faster in has_key? method. Tried it with
>>> GC.disable as well, results were same.
>>>
>>> What am I missing?
>>>
>>> Thanx for any ideas
>>
>> The first reason that comes to mind is different insertion order.
>> But I hardly believe it could make such a big difference.  Care to
>> post your testing code?
>>
>> Kind regards
>>
>>    robert
>>
>
> Well, insertion order will be same, won't be?

Not necessarily.  If Marshal.dump uses the current order in the hash for 
writing then the insertion order during loading is likely to be different 
from the original insertion order.

> h = {}
> h_slovo = []
>
> if not true  #HERE YOU SWITCH IF GENERATE/LOAD
>     for x in 1..40_000
>         if x % 2000  == 0
>             puts x
>         end
>
>         slovo = ""
>
>         for z in 1..32
>             slovo += (rand(25)+65).chr
>         end
>
>         if rand(10) == 3
>             h_slovo << slovo
>         end
>
>         h.update slovo => rand(1_000_000)
>         slovo = nil
>     end
>
>     f = File.new("hash.marshal","w+")
>     f.puts(Marshal.dump(h))
>     f.close
>
>     f = File.new("hash1.marshal","w+")
>     f.puts(Marshal.dump(h_slovo))
>     f.close
> else
>
>     puts "loading hash"
>     h = Marshal.load(File.open("hash.marshal","r"))
>     puts "loading hash1"
>     h_slovo = Marshal.load(File.open("hash1.marshal","r"))
>     puts "done"
> end
>
> t1 = Time.now
>
> for slovo1 in h_slovo
> h.has_key? h_slovo
> end
>
> t2 = Time.now
>
> puts "hash: " + h.size.to_s
> puts "hled: " + h_slovo.size.to_s
> puts t2-t1

Your time measurement is far too unprecise on a modern system.  You'll have 
to repeat lookups to get more accurate results. I get a difference between 5 
and 10 percent with the attached code - regardless of GC enabled or 
disabled. Strange though that the copy is always slower.  This is an 
interesting issue.

Note, if you freeze keys lookups in the original hash are much faster 
because then hash keys are not copied on insertion (an optimisation of 
unfrozen Strings as hash keys), i.e., during lookup if the key is the same 
it's also the same object which will be the first test - and of course this 
test is much faster than sequential comparison of characters.

Another note, a more realistic scenario would be if not 10% of all keys were 
used for lookup but if there also were keys that are not present in the 
hash.

Kind regards

    robert

------=_NextPart_000_0006_01C60FA6.CE1C5970
Content-Type: application/octet-stream;
	name="hash-lookup.rb"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="hash-lookup.rb"

#!/usr/bin/env ruby=0A=
=0A=
require 'benchmark'=0A=
=0A=
REP =3D 100=0A=
=0A=
hash =3D {}=0A=
lookup_keys =3D []=0A=
=0A=
40_000.times do=0A=
  key =3D ""=0A=
  32.times { key << 65 + rand(25) }=0A=
  # key.freeze=0A=
=0A=
  hash[key] =3D true=0A=
  lookup_keys << key if rand(10) =3D=3D 0=0A=
end=0A=
=0A=
copy_of_hash =3D Marshal.load(Marshal.dump(hash))=0A=
=0A=
raise "Hashes different" unless hash =3D=3D copy_of_hash=0A=
=0A=
# GC.disable=0A=
=0A=
Benchmark.bmbm 15 do |bm|=0A=
  bm.report("original") do=0A=
    REP.times do=0A=
      lookup_keys.each {|key| hash.has_key? key}=0A=
    end=0A=
  end=0A=
=0A=
  bm.report("copy") do=0A=
    REP.times do=0A=
      lookup_keys.each {|key| copy_of_hash.has_key? key}=0A=
    end=0A=
  end=0A=
=0A=
  bm.report("copy rehashed") do=0A=
    REP.times do=0A=
      lookup_keys.each {|key| copy_of_hash.has_key? key}=0A=
    end=0A=
  end=0A=
end=0A=

------=_NextPart_000_0006_01C60FA6.CE1C5970--