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

[Barry Smith]

On Sep 19, 2011, at 4:47 PM, Jed Brown wrote:

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

  It may very well be limiting with MatGetSubMatrix() for VI solvers. In fact we may need yet a different approach to make the MatGetSubMatrix() itself memory scalable for very large problems; that is rather than doing an ISAllGather on the columns it has to be smart about knowing what processes need to know about what columns based on the sparsity of the matrix.

    Barry

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