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

[Barry Smith]

On Sep 19, 2011, at 4:29 PM, Mark F. Adams 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))

  But if you define the hashtable size to be as large as the entire array, don't you then use twice as much memory as the array since the hashtable needs that other array to store where the hash was successful, that isn't needed without the hashtable.

   Barry

> 
> Mark
> 
> On Sep 19, 2011, at 4:20 PM, Jed Brown wrote:
> 
>> On Mon, Sep 19, 2011 at 22:13, Aron Ahmadia <aron.ahmadia at kaust.edu.sa> wrote:
>> BG/P has in-order superscalar execution, you *will* stall on that cache miss because the compiler will not do you any favors in terms of separating the load of the data from its use.
>> 
>> An indirect call without SMT has a hard stall if the vtable is not in cache too because nothing can be done until that address is loaded. Of course if you call through the same objects a bunch of times, the vtable will be hot, so no issues.
>