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

[Aron Ahmadia]

Jed, do you mind posting a quick summary of what's going on here?  I am
guessing there have been some offline discussions/results regarding this
conversation.

Barry, are you proposing an API similar to the VecScatter interface offers a
series of various MPI implementation choices?  I've found this to be really
convenient for experimenting with performance gains, but it might be
engineering overkill if there isn't an obvious data structure choice.   I
agree that the if test can be deferred to run time from a performance
standpoint, but it feels to me that a specific hash table/trie/array/list is
usually always the 'right' data structure, given the context of the role
it's playing.

A

On Mon, Sep 19, 2011 at 8:38 AM, Jed Brown <jedbrown at mcs.anl.gov> wrote:

> On Mon, Sep 19, 2011 at 03:55, Barry Smith <bsmith at mcs.anl.gov> wrote:
>
>> The problem is that this assumes that it can be a compile-time decision
>> whether to use the hash table or not. This is not always true  so I propose
>> the following change: we make the decision hash table or array at run time
>> (in PetscTableCreate()) and store the hash table/array in the same data
>> structure and have PetscTableFind() and PetscTableAdd() be in-line functions
>> sort of like
>>
>
> Did Jungho's subsequent runs confirm that this 50% business is really hash
> table overhead? Is this a "good" hash table implementation in the sense of
> being competitive with others for the sort of use cases we care about? Can
> we check if there are a lot of hash collisions?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20110919/1351aab5/attachment.html>