Pleased to announce the initial release of the "google_hash" gem.

Its goal. To boldly be faster than any hash hash before (cue star trek TNG theme).

The goal is basically a better hash, either one that is faster or more space efficient than ruby's default.  To attempt this we wrap the google sparse and dense hashes [1].

Speed results (populating 500000 integers):

1.9.1p376 (mingw):

Hash (Ruby default)
0.359375 (populate)
1.1875   (each)

GoogleHashDenseIntToInt
0.1875   (populate)
0.078125 (each)

GoogleHashSparseIntToInt
0.53125  (populate)
0.078125 (each)

Usage:

a = GoogleHashDenseRubyToRuby.new
b = GoogleHashDenseIntToRuby.new # :int => Ruby
c = GoogleHashSparseIntToInt.new # :int => :int
d = GoogleHashSparseIntToInt.new # :long => :long  (longs are 8 byte ints on 64-bit machines, so can store larger numbers)

a[3] = 4
b[4] = 'abc'
b['abc'] = 'some complex object' 
c[3] = 4 # all you can use are ints

a.each{|k, v| ... }

a.keys => Array
a.values => Array

For a complete list, see types.txt, but it's all the various combinations of Ruby, Int, and Long.

To learn if sparse or dense is right for you, check their documentation: 

http://google-sparsehash.googlecode.com/svn/trunk/doc/index.html
Dense is faster, sparse uses less memory.

Installation:

gem install os # install a dependency
gem install sane # install a dependency
gem install google_hash (if on doze, you'll also first need the devkit installed)

Note that if you use a type other than "Ruby" that you will be saving the values away as native values, so they will be using less space than a typical ruby object (which is 20 bytes), using 4 bytes instead of 20 (or instead of 40, in the case of 64 bit machines).  In addition to taking less memory, they are also stored separate from Ruby's heap, meaning that they should release stress on the GC, if you are spending much time in GC.

If you have a desired use case that's not covered, let me know and I might well be able to code it up for you and add it.

ex: currently it uses longs internally instead of ints--if you want ints or chars or what not, let me know.

if you want it to remember insertion order, I could do that, too, or native "store away" strings/bignums, whatever.


This is meant to be one more tool in the rubyists toolbelt when trying to optimize speed-wise, and plans to expand to more types, but at least with this release it has a #each method.

Enjoy.

-r

[1] http://code.google.com/p/google-sparsehash

If you want to see the code/hack on it, run extconf.rb within the ext directory, to create the code it actually uses (from a template).

Related:

judy http://groups.google.com/group/ruby-talk-google/browse_thread/thread/05ed587925526a7f/314375891d12b672?lnk=raot