[Openmcl-devel] Non Blocking Nearly Wait Free Hash Table questions...

[Jon S. Anthony]

Hi,

Gail, if you see this I would guess you would be the one most likely to
know.  My understanding is that you were the one to implement these
things in CCL a year and half ago or so.  Anyway,

Let's suppose for a particular scenario, you have a perfect hash, H, for
a set of potential objects that covers an exact range from 0 to n.  So,
there are n+1 objects and (H Oi) is in {0, ..., n-1}, and is unique for
any given Oi.

We have a hashtable HT of size n which uses H.

For the sake of what follows, let's say H takes "about the same" many
cycles as say INCF.

Since, H is perfect for our hashing, comparison function just checks
that the object is an Oi and that this is an O(1) operation with cycles
again in the incf range

We have a simple array A of size n.

1. What would be the expected relative performance (more or less) of HT
compared to a simple index into A?

2. How about for a locking version of A: grab a lock on A and then
index?


I'm thinking that 1. will be something like "nearly the same for most
cases" (nearly wait free part).  And that for 2, HT will be much better
than locking version of A.


Many thanks for any insights!

/Jon