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

[Mark F. Adams]

On Sep 19, 2011, at 7: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

I've lost track of the provenance if this 'expense', I was assuming it was from the rehashing and not a fundamental complexity issue.  My quick and dirty suggestion was meant as a simple option the extend the domain of this code.

This does bring out an issue with PETSc programming model, namely the data structures/algorithms available in the standard template libraries are orders of magnitude better than this ctable stuff (who wrote that s*#t?), and there is lots of cool stuff that does not need to be written (badly) by us.  Data structures/algorithms are a weak spot in the "PETSc language" IMHO.  

This is just a thought, but perhaps -- at some point -- we could require C++ compilers so that we could routinely use STLs without changing APIs ... just a thought.

> 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? How did that turn out?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20110920/83e6a8be/attachment.html>