|
From: Nicholas N. <nj...@cs...> - 2007-07-22 22:36:15
|
On Sun, 22 Jul 2007, Christoph Bartoschek wrote:
> The current code implements a hash map with a UInt key. On the other hand the
> execution context code uses a hash set. There are good reasons to separate
> both ways to use a hash table. Both Java and C++ use two classes to implement
> a hash set and a hash map. They do not try to use one class that covers both
> functionalities.
The OSet allows both -- if you specify a comparison function, you can
implement a hash map, if you don't it defaults to integer keys, effectively
giving a hash set (if I've understood the distinction).
> On the other hand linear probing seems to be no choice now. The current hash
> table interface exposes the chaining implementation such that clients can
> optimize for speed.
How? If you're worried about changing the interface, don't be too worried,
we've changed things like that before.
> A hash map or a hash set can not replace an AVL implementation because it is
> not possible to have sorted access or to use range searches.
Ah, true.
> If I find time, I am going to change my implementation of the execution
> context to a hash list with linear probing because it allows me to get rid of
> the next pointer in each context. (Valgrind still uses 6GB for all execution
> contexts in my application).
Fair enough.
> However I see no direct way to embed execution contexts into the
> hashtable:
>
> struct ExeContext {
> struct ExeContext * parent; //calling frame
> Addr ip;
> };
>
> To support such a thing one would need a way to distinguish an empty entry
> from a used one and during resize an empty that is already moved from an
> unmoved one. Are there ip values that are not possible? Or values for parent?
>
> I guess I can use the fact that all pointers are 4/8 byte aligned but maybe
> there is a better way.
0 and 1 are unlikely pointer values, for both 'parent' and 'ip'. It's not
great to special-case them like that, but it might be good enough, so long
as it's an internal detail and not exposed to the users of the hash table.
Nick
|