From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-03-03T02:01:32+09:00
Subject: Re: Is Ruby slower?

On Mon, Mar 03, 2003 at 01:10:08AM +0900, MikkelFJ wrote:
> 
> "Mauricio Fern�ndez" <batsman.geo@yahoo.com> wrote in message
> news:20030302083833.GA8115@student.ei.uni-stuttgart.de...
> 
> > > it seems to me that the adoption of one-at-a-time hashes does' nt
> 
> What does "one at time" mean? One character at a time as opposed to Jenkins
> 4 characters at a time?

That's the name given to perl's current hash function in Bob Jenkins'
webpage.
 
> >  * Jenkins should be even worse as the additive constant to its
> >    complexity is higher
> >  * however, a perf. increase of 1-3% can be achieved by setting the
> >    number of bins in the hash to be a power of 2, so that we can later
> >    use bitwise AND instead of the modulus operator [I assume our hash is
> >    good enough not to increase the num. of collisions a lot]
> 
> There is some work going on in Jenkins hash, but it happens at the best
> possible location: inside the processor and at least it attempts to exploit
> parellism. Modern processors are much faster than memory. If the hash avoids
> an additional memory access ever so often, it may pay off decently. I would
> estimate the benefits of any good hash will only really show up in large
> hash tables. This is because a cache-miss is expensive (many hundred
> instruction cycles). An extra memory access in a small hash table is likely
> to happen in memory that is already conveniently in cache.

This (as several other things) should perhaps be adjusted at run-time
with a built-in class

Tuning.use_hash = Tuning::HASH_JENKINS
Tuning.gc_growth_const = 1.9

etc
 
We cannot optimize for both small (the most usual) and big (where speed
matters the most) hashes at the same time.

It probably makes more sense for the GC than for the hash, as you can
always use RJudy or whatever instead of the built-in hashes...

> If the bucket size is large you get fewer collissions, but you also increase
> the risc of cache-misses.
> 
> This must, however, be held against the cache-misses of reading and
> comparing the actual keys if not stored inside the bucket itself.
> 
> If the full 32-bit (or whatever) hash is compared first (i.e. store the full
> hash key in the bucket), the bucket count does not affect the number of
> external keys that must be accessed - only the quality of the hash itself.
> This technique also makes it cheaper to perform a rehash operation when
> expanding the buckettable.

This is what happened when I modified st.c to use Judy; then the full
hash value was used and there just were no collisions.  I thought it
would be faster than the current implementation for the reason you give
but it wasn't... I'll give it a try again with Jenkins' hash some time
to see if there's any change.

> (I sent a copy of my hashtable in private mail). It only operates on 32 bit
> keys (e.g. storing pointers to already internalized strings), but it uses
> the above mentioned principle of storing the hash and could be enhanced to
> operate on longer keys without much effort.
> 
> The avoidance of modulus prime is good both for avoiding the calculation,
> and because it makes it much easier to scale the bucket size on demand -
> thus avoiding large initial bucket tables - which in turn makes conflict
> resolution cheaper, although more frequent.
> 
> For small hashtables it may not pay off with a good, but more expensive hash
> function. When frequently accessed, everything, including keys, will be
> in-cache, and the statistical spread over buckets is probably unpredictable.

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

But what can you do with it?
	-- ubiquitous cry from Linux-user partner