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

[Barry Smith]

On Sep 19, 2011, at 2:42 AM, Jed Brown wrote:

> On Mon, Sep 19, 2011 at 09:31, Matthew Knepley <knepley at gmail.com> wrote:
> 
> I tend to think that Jed is right that a hash table tailored to these lookups should not have
> a big overhad over lookup.
> 
> It will still typically lose the memory locality that you get with an array. Not sure how much difference that makes here.

   In our case of MatGetSubMatrices() there are two main use cases.

   1) something like 80+ percent of the indices are non-null, maybe even 99 percent. Clearly an array makes sense here and there is no reason to use a hash table

    2) something like at most for large problems a couple percent of the indices are non-null. An array is not scalable for large problems.

    3) have two different (but almost identical routines), one that is hardwired with the array lookup one hardwired with hash table look up (yuck)

   In order for the (1) case to be efficient (that is many lookups are done and are successful) I don't want to have "two" implementations handled by the usual virtual function business (too much overhead is introduced) hence I proposed one implementation that handled both cases via a flag. It is still polymorphic but "low-overhead" compared to the full virtual function business (having the lookup be inline screws up an chance of real virtual based polymorphism anyways.)

   Barry