[petsc-users] PetscTableCreateHashSize

[Jed Brown]

Satish Balay <balay at mcs.anl.gov> writes:

>> Why is it not sufficient to be coprime?
>
> Well whatever was implemented previsously with PETSC_HASH_FACT [a
> prime number] didn't work well. [there were a couple of reports on it].

That was linear probing, right?

> Checking double hashing [Intro to algorithms, Coremen et all.]:
>
> For a hashtable size 'm' - and using hash functions h1(k), h2(k) - it
> says: h2(k) must be relatively prime to 'm'. [for all possilbe 'k'
> values? its not clear. Also any constraints on h1(k)?]

relatively prime = coprime

> And it suggested the following as one way to imlement:
> choose a prime 'm'
> h1(k) = k mod m
> h2(k) = 1 +  (k mod m')
>
> This was simple enough for me - so I updated ctable to use it. I've
> added entries up to INT_MAX.

Thanks.

> If its still lacking (I could potentially add more entries - perhaps
> for 64bitincides? or) - feel free to change the algorithm for arbirary
> sizes...

I would use khash (hash.h) because it is a portable and well-optimized
hash implementation.  The version in PETSc uses primes and double
hashing, though upstream now uses quadratic probing (better cache
locality).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 800 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20170109/7fe52bbf/attachment.pgp>