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

[Barry Smith]

On Sep 19, 2011, at 6:11 PM, Jed Brown wrote:

> On Tue, Sep 20, 2011 at 01:05, Barry Smith <bsmith at mcs.anl.gov> wrote:
> 
> 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.
> 
> 
> Oh, you're working with the global column space? That explains why it's so expensive. This gather is a problem in PCFieldSplit too unless you use MatNest (which should be easy now). VI doesn't have that luxury, so MatGetSubMatrix() needs to get a scalable implementation. Didn't we talk about this several months ago and Dmitry started writing code for it?

    I am not aware of Dmitry writing code for this nor use talking about it :-)

> How did that turn out?