# Overview

The Hash class in Ruby is an implementation of a dictionary in which a payload
is associated with a key and the keys are unique for a given Hash instance.
The Hash class provides all sorts of fanciness like default values, iteration,
conditional deletion, etc. but there are only four essential operations:

    1. insert(key, value)
    1. update(key, value)
    1. lookup(key)
    1. delete(key)

Ideally, the Hash data structure has O(1) complexity for each of these
operations. In practice, there is a constant factor that can have a
significant impact on performance.

There are three key characteristics for implementing this data structure:

    1. how the elements are stored
    1. the definition of the hash function h(x) taking a key to a location in
       the data structure
    1. how collisions (i.e. h(x) == h(y) but x != y) are handled

There are three main academic papers that were referenced while conducting
these experiments:

    1. "Cuckoo Hashing" by Rasmus Pagh and Flemming Friche Rodler
       www.cs.nyu.edu/courses/fall05/G22.3520-001/cuckoo-jour.pdf
    1. "How Caching Affects Hashing" by Gregory L. Heileman and Wenbin Luo
       www.siam.org/meetings/alenex05/papers/13gheileman.pdf
    1. "Fast and Compact Hash Tables for Integer Keys" by Nikolas Askitis
       members.optusnet.com.au/~askitisn/CRPITV91Askitis.pdf


# Problem Statement

In Rubinius, the Hash class is implemented entirely in Ruby, using one primary
VM data structure, the Tuple (a fixed-sized array of references to objects).
The purpose of this investigation is to implement various of the alternate
Hash (Dictionary) algorithms and determine which performed the best.

One important thing to note is the assumptions under which the various Hash
algorithms in the academic papers are tested. Typical code does not create and
iterate Hash instances containing millions of keys. This is discussed below in
"Preparation".

Another note is that in Ruby, the semantics of matching keys is complex. The
cost of matching the keys adds significantly to the overall cost of the Hash
operations. When matching keys, the keys are compared according to their #hash
values and whether they are #eql?. Also note that while #== and #eql? are
often synonyms, they are not always so, for example 1.eql? 1.0 is false. The
following code will print :ponies.

    class Five
      def hash
        5.hash
      end

      def eql?(other)
        5.eql? other
      end
    end

    h = {}
    h[5] = :ponies

    five = Five.new
    p h[five]

The point here is that nothing guarantees that given a != b, a.hash != b.hash.
In fact, it is quite possible that a.hash == b.hash! This requires a separate
call to #eql?. How often are the values returned by #hash for different
objects the same? On the one hand, it doesn't matter unless they are
guaranteed to be different. So there is no short circuiting the (a.hash ==
b.hash and a.eql?(b)) test for key equality.

In the definition of a Hash, given a key x, the location of the key is
returned by the function h(x). In Ruby, the key matching semantics can be
considered to be part of h(x)'s computation.


# Preparation

To know whether an implementation, A, of Hash is better than an implementation
B, there must be some way to compare the performance of A ond B. The key issue
is the assumptions we make about how to compare the performance. There is no
question that we need to write benchmarks, but what should the benchmarks do?
Part of the answer is easy: the benchmarks should gather total execution time
for the core Hash operations detailed above. Two questions seem reasonable:

    1. what object(s) do we use for the keys?
    1. do we test the operations separately, together, in what ratios, etc.?

Rather than speculating, we can gather some info about actual Hash usage is
some programs. We do not say the programs are exactly representative of all
Ruby programs or even a particular class of Ruby programs. This is essential
to keep in mind. We make assumptions based on the programs we examine.
Nevertheless, it is better to examine at least some programs rather than just
making loops of things and assuming the performance there represents any
realistic results in real programs.

To examine the actual Hash instances created, the ClassSpy utility was
written. The code is at:

    benchmark/utils/class_spy.rb
    benchmark/utils/hash_spy.rb

The utility was run on the the Array specs, using rdoc to process the RDoc
source, and to run 'rails -h'. The results are included below:

    1. Running the Array specs

    $ bin/mspec ci -r benchmark/utils/hash_spy core/array
    rubinius 0.11.0-dev (ruby 1.8.6) (9d13d2499 12/31/2009) [i686-apple-darwin9.7.0]
    ............................................................................

    Finished in 10.998081 seconds

    76 files, 1006 examples, 2856 expectations, 0 failures, 0 errors

    ClassSpy results for Hash

    Method name (*)     Max Min  Mean  25%  50%  75%  81.3%  87.5%  93.8%  96.3%  97.5%  98.8%
    ------------------------------------------------------------------------------------------
    size                243   0   8.7    0    2    6      7      7      7     86    144    144
    ==                    0   0   0.0    0    0    0      0      0      0      0      0      0
    []=                 244   0   9.4    1    2    8      8      8     10     87    145    145
    []                23268   0  23.1    0    2   10     10     11     83    145    145    147
    fetch                 0   0   0.0    0    0    0      0      0      0      0      0      0
    key?                 20   0   0.3    0    0    0      0      0      1      3      3      6
    member?               0   0   0.0    0    0    0      0      0      0      0      0      0
    include?              0   0   0.0    0    0    0      0      0      0      0      0      0
    has_key?              0   0   0.0    0    0    0      0      0      0      0      0      0
    keys                  4   0   0.2    0    0    0      1      1      1      1      1      1
    values                0   0   0.0    0    0    0      0      0      0      0      0      0
    each                  5   0   0.3    0    0    0      1      1      2      2      2      2
    each_pair             0   0   0.0    0    0    0      0      0      0      0      0      0
    delete              358   0   0.0    0    0    0      0      0      0      0      0      0

    (*) Units are # of calls except for 'size' which is the object's size.
        The values listed in the percentages columns tells the number of
        data points <= to the listed value. E.g. if 8 is listed under 50%
        in the row for #each, then 50% of Hash instances had <= 8 calls
        to the #each method.

    9833 Hash instances

    Key class                   Number
    ----------------------------------
    Array                          342
    Fixnum                         131
    Float                           11
    MockObject                      14
    String                       19056
    Symbol                       70042

    28 instances with mixed keys


    1. Running RDoc

    $ bin/rbx -r benchmark/utils/hash_spy -S rdoc -o ../test_rdoc rdoc-2.4.3

    Parsing sources with 2 thread(s)...
    100% [62/62]  rdoc-2.4.3/lib/rdoc.rb

    Generating Darkfish...

    Files:   62
    Classes: 120
    Modules: 14
    Methods: 723
    Elapsed: 594.7s

    ClassSpy results for Hash

    Method name (*)     Max Min  Mean  25%  50%  75%  81.3%  87.5%  93.8%  96.3%  97.5%  98.8%
    ------------------------------------------------------------------------------------------
    size                214   0   3.8    4    4    4      4      4      4      4      5      6
    ==                    0   0   0.0    0    0    0      0      0      0      0      0      0
    []=                3345   0   4.4    4    4    5      5      5      5      5      6     10
    []              1820825   0 100.6    5    5    7      7      7      8      9     12     55
    fetch               184   0   0.0    0    0    0      0      0      0      0      0      0
    key?              12105   0   2.7    0    0    0      0      0      0      0      5     20
    member?               0   0   0.0    0    0    0      0      0      0      0      0      0
    include?            414   0   0.0    0    0    0      0      0      0      0      0      0
    has_key?             24   0   0.0    0    0    0      0      0      0      0      0      0
    keys               1023   0   0.0    0    0    0      0      0      0      0      0      0
    values              309   0   0.0    0    0    0      0      0      0      0      0      0
    each               2052   0   0.1    0    0    0      0      0      0      0      0      0
    each_pair             0   0   0.0    0    0    0      0      0      0      0      0      0
    delete              419   0   0.0    0    0    0      0      0      0      0      0      0

    (*) Units are # of calls except for 'size' which is the object's size.
        The values listed in the percentages columns tells the number of
        data points <= to the listed value. E.g. if 8 is listed under 50%
        in the row for #each, then 50% of Hash instances had <= 8 calls
        to the #each method.

    96521 Hash instances

    Key class                   Number
    ----------------------------------
    Array                           13
    Class                       318858
    FalseClass                       1
    Fixnum                         901
    NilClass                         2
    OptionParser::Switch::NoArgument      746
    OptionParser::Switch::RequiredArgument     1094
    RbYAML::MappingNode              1
    RbYAML::ScalarNode               6
    RbYAML::SequenceNode             1
    Regexp                           6
    String                       16432
    Symbol                       30905
    TrueClass                        1

    860 instances with mixed keys


    1. Running rails -h

    $ bin/rbx -r benchmark/utils/hash_spy -S rails -h
    <output omitted>

    ClassSpy results for Hash

    Method name (*)     Max Min  Mean  25%  50%  75%  81.3%  87.5%  93.8%  96.3%  97.5%  98.8%
    ------------------------------------------------------------------------------------------
    size                390   0  10.4    2    2    6      6      7     17     73    103    190
    ==                    0   0   0.0    0    0    0      0      0      0      0      0      0
    []=                 396   0  13.5    3    3    8     10     10     25     85    161    231
    []               269290   0 103.6    0    0    6     10     14     34     77     90    161
    fetch               100   0   0.0    0    0    0      0      0      0      0      0      0
    key?                686   0   2.8    0    0    0      0      2      6     11     22     37
    member?               0   0   0.0    0    0    0      0      0      0      0      0      0
    include?              6   0   0.0    0    0    0      0      0      0      0      0      0
    has_key?             25   0   0.0    0    0    0      0      0      0      0      0      0
    keys                 74   0   0.0    0    0    0      0      0      0      0      0      0
    values               16   0   0.0    0    0    0      0      0      0      0      0      0
    each                 74   0   0.0    0    0    0      0      0      0      0      0      0
    each_pair             0   0   0.0    0    0    0      0      0      0      0      0      0
    delete              411   0   0.0    0    0    0      0      0      0      0      0      0

    (*) Units are # of calls except for 'size' which is the object's size.
        The values listed in the percentages columns tells the number of
        data points <= to the listed value. E.g. if 8 is listed under 50%
        in the row for #each, then 50% of Hash instances had <= 8 calls
        to the #each method.

    16727 Hash instances

    Key class                   Number
    ----------------------------------
    Array                            3
    Class                        76646
    FalseClass                       1
    Fixnum                         272
    NilClass                         2
    OptionParser::Switch::NoArgument      258
    OptionParser::Switch::RequiredArgument       98
    RbYAML::MappingNode              1
    RbYAML::ScalarNode               6
    RbYAML::SequenceNode             1
    Regexp                           3
    String                       20032
    Symbol                       87031
    TrueClass                        1

    159 instances with mixed keys


Based on the data from running these three programs, the Hash benchmarks in
the benchmark/rubinius/hash directory where created. Since Symbol keys were
use the vast majority of the time, the benchmarks use Symbol keys. Benchmarks
that use other keys should definitely be added, but initially the benchmarks
where written to represent aspects of the data above.

Given the data on Hash sizes, the benchmarks create Hash instances with the
following sizes and iterate the following number of times:

    Size      Iterations

    5         20,000
    10        10,000
    50        1500
    100       1000
    1000      100
    10,000    10

This distribution does not represent the data precisely but it does represent
a realistic range of sizes. The iterations where chosen so that the execution
times were approximately equal, representing a roughly equivalent amount of
work done on the Hash instances of different sizes.

The Hash benchmarks look at four types of operations: creating, inserting,
lookup, and mixed operations.

    bm_create.rb
    bm_insert.rb

    bm_get_existing.rb
    bm_get_missing.rb
    bm_get_mixed.rb

    bm_balanced_get_set.rb
    bm_proportional_get_set.rb
    bm_proportional_get_set_delete.rb
    bm_proportional_set_get.rb


# Algorithms

The following four algorithms were compared:

    1. Chained Bucket
    1. Cuckoo
    1. Linear Probing
    1. Array Hash

All of these algorithms essentially have a Tuple of entries, use essentially
the same hash function h(x) to locate a key, x, and use the same method to
compare two keys for equality. The main distinction is how the algorithms
handle collisions (i.e. when two different keys would end up in the same
location).


## Chained Bucket

This algorithm handles collisions by creating a chain of entries
(singly-linked list) where the head of the chain is directly accessible at the
Tuple index given by h(x) for some key, x. Graphically, this looks like:

    +---+---+---+---+----+
    | 0 | 1 | 2 | 3 | ...|  <---- Tuple of entries
    +---+---+---+---+----+
          |
          v
        +-------+-------+-------+-------+
        | key   | hash  | value | next  |
        +-------+-------+-------+-------+
                                    |
                                    v
                                +-------+-------+-------+-------+
                                | key   | hash  | value | next  |
                                +-------+-------+-------+-------+


## Cuckoo

The Cuckoo hash uses two tables and two hash functions, h1(x) and h2(x). To
insert an entry (key, value), first compute the location i = h1(key). If index
i of table1 is empty, insert the entry.

If index i is occupied by entry1 (key1, value1), insert the new entry at index
i in table1, then compute j = h2(key1). If index j of table2 is empty, insert
entry1 there.

Otherwise, insert entry1 at index j of table2. Take entry2 that was at index j
of table2 and compute k = h1(key2) and look at index k of table1... This
process repeats until every entry has a place. If there is no way to insert
all the entries, enlarge the tables and start inserting the entries again.

Four variations of the basic Cuckoo algorithm were examined:

    1. Bucketized cuckoo where each slot in the table contains an array of
       entries rather than a single entry.
    1. Using bucketized cuckoo, move entries later in the array forward when
       an earlier entry is deleted. The idea is to shorten the list of entries
       that must be searched on insert to determine whether an existing key is
       being updated or a new key is being inserted.
    1. Altering the load factor from just less than 0.5 to 0.4.
    1. Combining probing one location forward with the normal cuckoo insert.
       In other words, calculate i = h1(x). If i is occupied, look at i + 1.
       If i + 1 is not occupied, insert there. If it is occupied, insert at i,
       booting the existing entry and try to insert it in table2.


## Linear Probing

Given the Tuple of entries, calculate i = h(x) for some key. If index i is
occupied, look at i + 1. If that index is empty, insert there. Otherwise, look
at index i + 2. Continue in this way up to some constant C <= total number of
slots in the Tuple of entries.

It should be obvious that if we let C be the number of possible entries (in
other words, the capacity of the Hash), then the total number of places we may
have to look at increases as the Hash increases in size. In this case, the
worst case insert behavior is not bounded (it grows with the size of the
Hash). In practice, it is easy to bound worst case insert behavior by simply
choosing C to be some constant.

In the experiments, C was set to 4, 3, and 2. For the case of C = { 3, 4 }, a
loop was used. In the case of C = 2, the loop was manually unrolled (i.e. the
code was duplicated in the method for checking if a key exists in the Hash or
for inserting a key).

Two methods of storing the entries was also implemented: inline in the entries
Tuple or in separate Entry objects. This is represented graphically below:


    1. Store key, value inline

    +-------+-------+--------+-------+-------+--------+------+
    | key1  | hash1 | value1 | key2  | hash2 | value2 | ...  |
    +-------+-------+--------+-------+-------+--------+------+
      ^
      |
      +--- Tuple of entries


    1. Store key, value in Entry objects

    +---+---+---+---+----+
    | 0 | 1 | 2 | 3 | ...|  <---- Tuple of entries
    +---+---+---+---+----+
          |
          v
        +-------+-------+-------+
        | key   | hash  | value |
        +-------+-------+-------+


## Array Hash

The Array Hash algorithm is much like the chained bucket algorithm, but
instead of using a linked list of entries, a resizeable array of entries is
used. Two variations were investigated: storing the keys, values inline and
storing a reference to an Entry object.


# Results

The results of running the benchmarks against the different Hash
implementations were collected in a Google Docs spreadsheet. An .xls file
exported from the spreadsheet is at doc/experiments/hash/hash-benchmarks.xls.
Direct links to the Google Docs spreadsheet and an Html representation are at:

    http://spreadsheets.google.com/ccc?key=rdiNYWh0xTGShVHikWVmnUA
    http://spreadsheets.google.com/pub?key=rdiNYWh0xTGShVHikWVmnUA&gid=3

The spreadsheet has tabs for each general type of Hash algorithm. Within a
tab, the spreadsheet contains two types of columns: columns that report the
timing data and columns that relate two different columns of timing data.

In the timing data columns, all times reported are in seconds. The times are
the median value of five iterations of each benchmark for each of the sizes
and iterations pairs above.  For example, bm_create.rb was run five times in
which a Hash instance of five keys was created 20,000 times. So the benchmark
itself consists of creating a Hash of five keys 20,000 times. The benchmark is
run five times. The middle value of the five runs is recorded in the
spreadsheet.

Each comparison column relates to the first timing data column to its left.
The heading of the comparison colums tells how much faster the data colums is
compared to the column specified. For example, in the "Array Hash" tab, the
comparison column "F" says that column "E" (array hash algorithm using the
ArrayEntry class) is X times faster than column "C", which is the default
chained bucket algorithm in Rubinius core library. The value of X may be
greater than one, which is faster, or less than one, which is slower. The
spreadsheet colors slower values red and faster values green.


# Analysis

At a high level, the results indicate that there is a fairly small difference
between reasonably written implementations of the various algorithms. A
particular algorithm is faster on some benchmarks and slower on others. While
we can investigate and analyze which particular benchmarks are faster or
slower for a given algorithm, it is clear that no algorithm is uniformly
better performing than the default chained bucket algorithm.

What these results appear to indicate is that the total number of operations
is the crucial factor for overall performance. Each algorithm makes
trade-offs. Those trade-offs are based on assumptions about what will take
more time. For example, consider the linear probe algorithm versus the chained
bucket algorithm. The linear probe assumes that looking forward C slots for an
empty slot will take less time than following link in the chain of buckets.
Also, just looking forward at the next C slots will cost less than allocating
the buckets in the linked list.

However, in Ruby, when inserting a key, all possible slots for that key must
be checked using the key-matching semantics to determine whether the value for
an existing key will be updated or a new entry will be added. With C = 4 in
the linear probe algorithm, that means all four slots have to be checked, even
if they are empty. The algorithm could move entries forward on delete, so you
only have to check until you reach an empty slot or you've checked four slots.
But there is a cost to moving entries when deleting. On the other hand, with
the chained bucket algorithm, if there is no entry at the index in the Tuple,
insert a new entry and done. If there is an entry, follow the chain until you
get a match OR the next link is nil. In each case, the minimum amount of work
is needed to update or insert an entry in that no extra locations need to be
looked at.

The preceding discussion assumes that all operations have the same cost. This
is a reasonable assumption under some circumstances. But we need to consider a
deeper level. The following is simplified, but essentially accurate.

There are three things to consider about the performance of a modern CPU:

    1. total number of instructions executed
    1. branch instructions
    1. memory acceses

All other things being equal, executing 50 instructions will take half as long
as executing 100 instructions. So performance can be increased by executing
less instructions.

Branching instructions impact CPU performance when they are mis-predicted. In
that case, the CPU may need to flush execution pipelines and CPU cycles are
spent loading and executing the other code path. The CPU does not operate at
optimal efficiency.

Memory accesses can impact CPU performance if the memory location accessed was
not in the cache. In that case, the CPU may be stalled waiting for the memory
to be loaded into the cache so the CPU can access it.

At the level of the bytecode interpreter, the number of actual CPU
instructions that are being executed would appear to dominate items 2 and 3
above. This may not always be the case as the JIT implementation improves.
However, this factor was also examined. Refer to the JIT tab in the
spreadsheet. This shows the speedup obtained using the JIT as of the commit
referenced. The columns with purple headers show how much faster the JIT made
a particular algorithm compared to how much faster the JIT made the chained
bucket implementation. In other words, it shows which implementation the JIT
(recognizing that the JIT as of the time of these experiments is in no way
near complete) was able to speed up the most

Finally, it is very important to carefully review the result reported here and
at every point consider what assumptions are being made in the design and
execution of the experiments. Generally, we need to develop sufficient
emperical knowledge of performance characteristics to be begin to be able to
predict the effects of particular types of optimizations on the performance of
Ruby code.


# Further exploration

The information and analysis above represents merely the beginning of
developing an emperical understanding of actual Hash preformance. More work
absolutely needs to be done. The following sections detail how to run the
specs against an alternate implementation and how to run the benchmarks. Note
that the benchmarking harness may change some in the future so you may need to
investigate that and update this document.


## Running the specs

The Hash specs in RubySpec have been generalized to not use the Hash constant
directly. Rather, MSpec provides a helper method, #new_hash, that relies on a
method, #hash_class, to construct a Hash instance for the specs. This greatly
simplifies writing and testing alternate Hash implementations without
interfering with the core library Hash class.

Create a file named hash_class.rb in your path. Edit the file to contain the
following code:

    class Object
      def hash_class
        Rubinius::ArrayHash
      end
    end

Substitute the Hash class you are testing for Rubinius::ArrayHash in the code
above.

To run the Hash specs using your alternate class, use the following command:

    bin/mspec -r hash_class -r fancy_hash core/hash

where the fancy_hash.rb file contains the FancyHash class implementation.


## Running the benchmarks

The Hash benchmarks use the benchmarking harness written to integrate the RBS
benchmarks. Rake tasks allow running a single file or a directory of files.
The Hash benchmarks use the HASH_CLASS environment variable to specify the
name of the class to use for creating Hash instances.

To run all the benchmarks in the benchmark/rubinius/hash directory, use the
following command:

    rake -q bench:dir DIR=benchmark/rubinius/hash \
    VM='rbx -r array_hash_entry' HASH_CLASS=Rubinius::ArrayHash

This command will run all the bm_*.rb files in benchmark/rubinius/hash using
the Rubinius::ArrayHash class which is implemented in the array_hash_entry.rb
file. You can use the -I DIR command line switch to add the directory
containing array_hash_entry.rb to the load path.

To run an individual Hash benchmark, use the command:

    rake -q bench:file FILE=benchmark/rubinius/hash/bm_insert.rb \
    VM='rbx -I doc/experiments/hash/code -r array_hash_entry' \
    HASH_CLASS=Rubinius::ArrayHash

This command runs just the bm_insert.rb benchmark and uses the -I command line
option to set the load path.

Each time you invoke the bench:dir or bench:file Rake tasks, a YAML file is
written or appended to. The tasks report the location and name of this file.
After running one or several benchmarks, convert the data in the YAML file to
a CSV file with the following command:

    rake bench:to_csv

This will extract the minimum time recorded for each benchmark and write a
comma-separated value file that is suitable for importing into a spreadsheet.
To select a different value to extract, use the FIELD environment variable.
Possible options are 'min', 'max', 'median', or 'mean'. For example:

    rake bench:to_csv FIELD=median

