Re: Is Ruby slower?

il Sun, 2 Mar 2003 17:12:28 +0100, "MikkelFJ"
<[e-mail]> ha scritto::

>
>"Mauricio Fern疣dez" <[e-mail]> wrote in message
>news:[e-mail]...
>
>> > 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?

Yes, I suppose.


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

I don't grok what you mean talking about the cache :(
It seems to me that 1-at-a-time didn't depend on accessing memory more
than jenkins.
Using a big hash would stress the caching system, but we won't be 
measuring the hash performance .


Probably I misunderstood something, would you please explain me what
problem this algorithm could have with the cache stuff?

I agree that maybe jenkins could exploit modern CPU superscalar arch,
but we miss the ability to inline the code reducing the number of
operations from  9n to 5n.
And, 
(I didn't passed passed my CPU-related exam so good, so maybe I'm
wrong) having the work on 1 char per time won't damage the
parallelism, the cpu could work on more than one char at a time
anyway. 

It seems that 1-at-a-time scales well, and that it is actually better
than what we have in current ruby,  at least it got less collision.

And well, the perl guys won't put it in 5.8 if it was'nt someway
better than the old :)





>
>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.
>(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.
>
>Mikkel
>
>