[petsc-dev] use of hash table vs array in various places in PETSc

[Jed Brown]

On Mon, Sep 19, 2011 at 23:29, Mark F. Adams <mark.adams at columbia.edu>wrote:

> An alternative to a virtual function is changing the hash table code:
>
> #define HASH_FACT 79943
> #define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned
> long)x)%ta->tablesize))
>
> and make HASH_FACT a variable.  Set HASH_FACT  to 1 if you want an array
> (and thus the index (x) is less than the table size tablesize).  The index x
> is one based so the hash function should modified:
>
> #define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned
> long)(x-1))%ta->tablesize))
>

This is an interesting idea. Storage is still double the array, but I think
the cases where we want a dense array will generally not be so space
limited.

As for very bad behavior shown earlier, I wonder if those problems were
causing clustering of some sort so that the linear probing was having
problems. It would be interesting for diagnostic purposes to record
collision statistics.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20110919/cb523586/attachment.html>