[ANN] google_hash 0.1.1 -- it has a #each!

[Roger Pack]

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

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


Or 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/iterating over 500000 integers):

1.9.1p376 (mingw):

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

GoogleHashDense
0.1875 (populate)
0.078125 (each)

GoogleHashSparse
0.53125 (populate)
0.078125 (each)

Usage:

a = GoogleHashSparse.new
b = GoogleHashDense.new # or just GoogleHash.new

a[3] = 4
b[4] = 'abc'
a['abc'.hash] = 'some complex object'
# it only accepts int's currently--only because I'm too lazy to add more
types yet.
a.each{|k, v| }


Installation:

gem install google_hash (if on doze, you'll need the devkit installed)


Both these classes are currently more space efficient than a hash,
because they store keys as "native" ints, so the keys no longer affect
GC time, as well as only use 4 bytes instead of 20 (or 8 instead of 40,
on 64 bit). This should release some stress on the GC. In terms of
total memory usage, GoogleHashDense uses more (more buckets), and is
more speedy, and GoogleHashSparse uses less space, and is much more
memory efficient (2 bits per entry, or so I'm told).

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.

If you have a desired use case let me know and I might well be able to
code it up for you.

Enjoy.
-r

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

 

[Aldric Giacomoni]

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


Both these classes are currently more space efficient than a hash,
because they store keys as "native" ints, so the keys no longer affect
GC time, as well as only use 4 bytes instead of 20 (or 8 instead of 40,
on 64 bit). This should release some stress on the GC. In terms of
total memory usage, GoogleHashDense uses more (more buckets), and is
more speedy, and GoogleHashSparse uses less space, and is much more
memory efficient (2 bits per entry, or so I'm told).


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

Neat. Does it keep the order in which the elements were entered? Is it
sortable?

 

[Roger Pack]

Neat. Does it keep the order in which the elements were entered? Is it
sortable?

Nope. What would be the requirements for something you're looking for?

I have a big need for a fast Set of integers/bignums

You just need fast iteration? Fast insertion?

Yeah it should be doable.

The google hash lib itself has both Hashes and Sets--I just have focused
on the Hash stuff as of yet, but hope to do them all (with more types)
eventually.

With just int (or double) you could reasonably easily store your keys
and/oor values as native.

With Bignum I'm not totally sure how they're stored in memory, but with
some hacking it is probably possible to "store them away" (i.e. store a
copy of them on entry so that Ruby is no longer memory tracking them).

What would the ideal be in terms of requirements? (oh and feel free to
checkout the code/fork/file issues -- http://github.com/rdp/google_hash
)

Enjoy.
-r

 

[Ralf Mueller]

Hi,
I'm not sure, but Judy (http://judy.sourceforge.net/) and it's Ruby
bindings (http://rjudy.sourceforge.net/) seem to be another candidate
for efficient hash implementations. I tried purple
(http://purple.rubyforge.org/), which is built upon Judy, too.

hth
ralf

 

[Aldric Giacomoni]

Nope. What would be the requirements for something you're looking for?

In Ruby 1.9, hashes remember in which order the data was entered (as
opposed to being "somehow sorted". Basically, a data structure with the
capabilities of the Dictionary in the Facets gem.

 

[Roger Pack]

Or 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].

As a note, also released 0.2.1 recently.

Changes:

Added RubyToRuby Hash [drop in replacement for the default hash].
added #keys and #values and #keys_combination_2 methods.

In general the :int => Ruby hashes are much faster than Ruby's hash
lookups.
The RubyToRuby Hash is a bit slower for insertion/lookup and far
faster for #each than the default hash.

new usage:

a = GoogleHashDenseRubyToRuby.new # or GoogleHash.new
b = GoogleHashDenseLongToRuby.new # a hash that is only :int => Ruby
b = GoogleHashSparseLongToRuby.new # a hash that is only :int => Ruby,
and uses less memory [Sparse]

a[3] = 4
b[4] = 'abc'
b['abc'.hash] = 'some complex object'

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

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

speed comparison:

1.9 mingw results

http://pastie.org/752318

1.9.2 linux:

http://pastie.org/752333

Enjoy.
-r

 

[Roger Pack]

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

Speed results (populating/iterating over 500000 integers):

1.9.1p376 (mingw):

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

GoogleHashDense
0.1875 (populate)
0.078125 (each)

Released another update..

v 0.3.0

ChangeLog:

Now has several new types of hashes, ex:

GoogleHashDenseRubyToRuby # just like a normal Hash--you can store Ruby
values and Ruby keys.

GoogleHashDenseIntToInt # :int => :int only -- this one stores all its
keys and values a native, so ruby's GC doesn't ever touch them!

also has some slight speed improvements.

See http://github.com/rdp/google_hash

for more information.

Merry Christmas.
-r

 

[Eric Wong]

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

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


Or 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].

Both these classes are currently more space efficient than a hash,
because they store keys as "native" ints, so the keys no longer affect
GC time, as well as only use 4 bytes instead of 20 (or 8 instead of 40,
on 64 bit). This should release some stress on the GC. In terms of
total memory usage, GoogleHashDense uses more (more buckets), and is
more speedy, and GoogleHashSparse uses less space, and is much more
memory efficient (2 bits per entry, or so I'm told).

Hi Roger,

Any chance of having one of these can become the default MRI Hash
implementation, or even replace most MRI-internal uses of st.c?
Much of the st.c stuff inside MRI uses numeric keys.

 

[Roger Pack]

Hi Roger,

Any chance of having one of these can become the default MRI Hash
implementation, or even replace most MRI-internal uses of st.c?
Much of the st.c stuff inside MRI uses numeric keys.

I'm sure it would be possible--and possibly not even terribly hard--the
only concerns would be licensing, and the fact that it's written in C++
instead of C.

That being said, I could create a wrapper for it that takes a file and
converts its hashes "automagically" into GoogleHash.new's...
if desired.
-r