🚀 go-pugleaf

Terrance Richard Boyes <tez@pierrot.co.uk> wrote:

> Yep, there's a HASH1 and HASH2 value, though there seem to be
> some problems if both of those overflow (collisions). I couldn't
      ^
      speed

> find my refs to how to understand the numbers behind a hashing
> algorithm. Any good books ?

NB when I refer to 32K, 256K as the HASH values I'm using the
nearest primes above and below that value!

> However with a bit of experimentation I upped both the HASH values
> from ~32K to ~256K, on 32K unique msgids this has dropped the
> collisions from ~5000 to ~700.

Damn, that should have been 128K, at 256K it's 150 collisions,
at 512K it's 50. The default 32K values are good for up to
about 8K articles in the history. 

As far as building the HASH table(s) goes the "size" of the
table (HASH 32K, 512K etc...) makes very little difference in
speed, and using 2 HASHes is only a little slower than one.
However using 2 does result in less collisions.

Speed wise having more than a handful of collisions on a
newshistory of that size is bad news, each one results
in a (table) scan of the history file.

I can see a few ways to help alleviate the collision speed
problem, though they all need more RAM usage (so DOS users
may have problems ?).

I tried extending the idea of using multiple HASH's, to 4,
it was slower than 2 large ones, and no more efficient
at eliminating dupes.

Or using some pseudo-randomising algorithm as Jes suggested ?

Or HASHing the lhs and rhs of the Message-ID: ?

Or storing the overflow in a btree, this could of course 
eat memory rapidly if there are a lot of collisions, OTOH
in a case like that the multiple history scans would be
a speed killer...

Maybe storing a file offset for every collision ?

-- 
<URL:http://www.pierrot.co.uk/>                                  Team AMIGA
What UNIVERSE is this, please??