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

[Jed Brown]

On Mon, Sep 19, 2011 at 14:43, Barry Smith <bsmith at mcs.anl.gov> wrote:

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

Can we declare the expected sizes and make an automatic choice, perhaps with
manual override?


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

It is not necessarily the case that an if statement is less overhead than a
virtual function. It depends whether the compiler decides to inline the
whole thing and which branch of the if statement is taken. (The if statement
implicitly makes a choice about which branch will be preferred by which
jumps it inserts in the assembly. The virtual function is more symmetric.
Now _PETSc_ virtual functions with string lookup are way expensive, and
PetscFunctionBegin is significant when running in debug mode.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20110919/a87cdb2f/attachment.html>