From: Hugh Sasse Staff Elec Eng <hgs@...>
Date: 2004-11-18T03:39:44+09:00
Subject: x.include? speed observation

I wondered about implementing a fairly small set of  present/absent flags and 
about the resulting performance of various methods.  So I wrote
this:

------8<--------------
#!/usr/local/bin/ruby -w
#
# Attempt to compare the performance when searching in a set, array
# or a hash to find out which is better when serching.
#
#

require 'set'

symbols = [ :stilton, :gloucester, :limeswold, :camembert, :brie]

$times = 2000

(0...symbols.size).each do |c|
     eval "$asym#{c} = symbols.dup[0..#{c}]"
     eval "$ssym#{c} = Set.new(symbols.dup[0..#{c}])"
     eval "$hsym#{c} = Hash.new(); symbols.dup[0..#{c}].each{|x| $hsym#{c}[x] = 1}"
end

def asym
$times.times do
     $asym0.include?(:gloucester)
     $asym1.include?(:gloucester)
     $asym2.include?(:gloucester)
     $asym3.include?(:gloucester)
     $asym4.include?(:gloucester)
end
end

def ssym
($times+633).times do
     $ssym0.include?(:gloucester)
     $ssym1.include?(:gloucester)
     $ssym2.include?(:gloucester)
     $ssym3.include?(:gloucester)
     $ssym4.include?(:gloucester)
end
end

def hsym
$times.times do
     $hsym0.include?(:gloucester)
     $hsym1.include?(:gloucester)
     $hsym2.include?(:gloucester)
     $hsym3.include?(:gloucester)
     $hsym4.include?(:gloucester)
end
end

asym

ssym

hsym


------8<--------------

The 633 was just to check if Hash was being called for set.
The results 
ruby 1.8.2 (2004-11-06) [sparc-solaris2.9]
are, by means of this vim command:
:r! ruby -rprofile ~/progs/ruby/ArrayHashSet.rb
like this:

   %   cumulative   self              self     total
  time   seconds   seconds    calls  ms/call  ms/call  name
  42.84     8.14      8.14        3  2713.33  6293.33  Integer#times
  22.32    12.38      4.24    13165     0.32     0.43  Set#include?
  15.32    15.29      2.91    10000     0.29     0.39  Array#include?
  13.63    17.88      2.59    23165     0.11     0.11  Hash#include?
   5.26    18.88      1.00    10000     0.10     0.10  Kernel.==
   0.16    18.91      0.03        1    30.00    30.00  Profiler__.start_profile
   0.16    18.94      0.03        1    30.00    30.00  Kernel.require
   0.11    18.96      0.02       35     0.57     0.57  Fixnum#to_s
   0.05    18.97      0.01       15     0.67     4.00  Kernel.eval
   0.05    18.98      0.01       15     0.67     0.67  Set#add
   0.05    18.99      0.01        5     2.00     6.00  Set#initialize
   0.05    19.00      0.01       15     0.67     0.67  Array#initialize_copy
   0.05    19.01      0.01       15     0.67     1.33  Kernel.dup
   0.05    19.02      0.01        5     2.00     4.00  Set#merge
   0.00    19.02      0.00       10     0.00     0.00  Hash#initialize
   0.00    19.02      0.00        1     0.00     0.00  Fixnum#+
   0.00    19.02      0.00        1     0.00     0.00  Array#size
   0.00    19.02      0.00        1     0.00     0.00  Module#append_features
   0.00    19.02      0.00        2     0.00     0.00  Class#inherited
   0.00    19.02      0.00       50     0.00     0.00  Module#method_added
   0.00    19.02      0.00        1     0.00     0.00  Module#included
   0.00    19.02      0.00        1     0.00     0.00  Module#protected
   0.00    19.02      0.00        1     0.00  9150.00  Object#ssym
   0.00    19.02      0.00       15     0.00     0.00  Array#[]
   0.00    19.02      0.00       30     0.00     0.00  Hash#[]=
   0.00    19.02      0.00        5     0.00     0.00  Kernel.is_a?
   0.00    19.02      0.00        5     0.00     0.00  Module#==
   0.00    19.02      0.00        1     0.00     0.00  Module#include
   0.00    19.02      0.00        1     0.00  3430.00  Object#hsym
   0.00    19.02      0.00        1     0.00    80.00  Range#each
   0.00    19.02      0.00        3     0.00     0.00  Kernel.singleton_method_added
   0.00    19.02      0.00        1     0.00 19000.00  #toplevel
   0.00    19.02      0.00        5     0.00     0.00  Kernel.nil?
   0.00    19.02      0.00        1     0.00     0.00  String#==
   0.00    19.02      0.00        1     0.00  6300.00  Object#asym
   0.00    19.02      0.00       10     0.00     0.00  Kernel.class
   0.00    19.02      0.00       10     0.00     1.00  Array#each
   0.00    19.02      0.00       15     0.00     2.00  Class#new

----------------

My observations are these, for what they are worth, and explain why
I post this to Ruby-Core:

   * Sets seemed remarkably slow.  They don't need to hold values as
     well as keys, so if I hadn't realised that they were implemented
     by means of Hashes, I'd have expected them to be faster.  Is my
     expectation that sets should be fast too naive, or is there a
     case for re-implementing sets, to reflect this viewpoint?

   * Arrays were slower than Hashes.  I think I expected this, but it
     makes me wonder what could be done to speed up Arrays: would it
     make sense to have an Array subclass native to Ruby that was
     sorted, allowing binary search?

   * Hashes beat the lot.  Obviously the thing to go for at the
     moment.  If I don't need values, would using a singleton like
     nil make them more efficient at all, or is there anything else
     short of coding in C that I can do to optimise this?

I expect these observations are biased, being based on cases with a
few elements only, but I was trying to refactor switch statements,
without having to go to true polymorphism, because in my case a
small number of possible values will be tested many times.

If now isn't the time to consider these matters, hopefully having
this test and its results in the archive will benefit someone in the
furure, so feel free to deal with more pressing matters :-)

         Thank you,
         Hugh