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

[Mark F. Adams]

The hash table does have to rehash everything when it is full, so if you had huge matrix with 80% nnz (in at least one row), then I could see it taking some time.

A simple fix conceptually is to make the initial size of has table the full size of the range space and use the identity as the has function, if you just want an array.  We could use 'o_nnz' to size that hash table, perhaps, and then flip to an identity hash function when the best table size is >= N.

On Sep 19, 2011, at 8:43 AM, Barry Smith wrote:

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