From: "Mauricio Fernández" <batsman.geo@...>
Date: 2002-08-29T08:56:27+09:00
Subject: Re: ANN: RJudy-0.1 - Judy Arrays for Ruby

On Wed, Aug 28, 2002 at 02:52:26AM +0900, Joseph McDonald wrote:
> 
> LJ> I've just uploaded RJudy, an extension module that provides a Ruby
> LJ> interface to the Judy arrays library. This extension exposes four new 
> LJ> classes to Ruby (Judy1, JudyL, JudySL and JudyHash). The first three are 
> 
> 
> Thanks Lyle!
> 
> It works great. I find that insertion time is faster using judy,
> retrieval time is about the same. I also find that memory usage is
> lower with judy. Here is reading 1,000,000 unique words (12MB of
> data):
> 
> JudySL takes 23MB
> JudyHash takes 26MB
> RubyHash takes 40MB

Bad news everyone...
This, and insertion being faster with Judy*, is an illusion :-(
Read below.

> (I subtracted the baseline process size of 54MB that the words array
> and ruby itself used).
> 
> Another datapoint:
> Time to insert 1000000 words into a JudySL array: 6907858.0 usec.
> 
> Doing the same with a straight C program took 3 seconds.  I think the
> extra 3.9 seconds is spent in rubyland doing this:
> 
> words.each do |word|
>     array[word] = word
> end

A regular Hash duplicates the key (word), so the following works
	key = "a key"
	h = {}
	h[key] = "hi"
	key[0] = "0"
	h["a key"] 		==> "hi"
If the key were not cloned, you'd have to access the data with
h["0 key"].
The key isn't cloned if it already present in the hash. Try with 1000000
insertions of only 10000 different words.

JudyHash seems faster than the Hash based on my new st_* functions
(which I'll call Hash') and the standard Hash only because of this.
Note it also accounts for the difference in the memory usage...

If I modify hash.c so that it doesn't duplicate the key, a number of
interesting things happen:
 * Hash' is slightly faster than JudyHash in lookup and
   insertion, but this depends on the duplication/number of keys
 * standard Hash crushes both JudyHash and Hash'
 * things go a little better for JudyHash and Hash' if there's a lot of
   data, but Hash remains faster, *always* :-(
 

> All in all, this is *super-cool*!

It's a pity it isn't quite there yet, but we still have a lot of place
for optimization :-)

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com
  
'Ooohh.. "FreeBSD is faster over loopback, when compared to Linux
over the wire". Film at 11.'
	-- Linus Torvalds