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

[Jon S. Anthony]

On Mon, 2010-01-11 at 09:47 -0500, Gail Zacharias wrote:
> At 1/9/2010 04:23 PM, Jon S. Anthony wrote:
> >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?
> 
> It depends on which operation you care about.  When there is no
> contention, the cost of gethash is pretty comparable. Puthash
> is quite a bit more expensive, and there are other costs if
> you're using address-based keys.

OK.  We can set aside the address based key issue as that isn't in the
cards.  Does puthash still need to use some locking under some
conditions?  I guess I should look over the state machine concept here
more closely and try to understand the details...


> >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.
> 
> 
> Locks are pretty expensive.  For gethash, yes, HT should do much better.

That fits with what I was thinking.


> However, why would you need to grab a lock for array access?  Hash 
> tables have a thread issue because they have two words (key and 
> value) that need to be coordinated.  But arrays don't.  What's the lock for?

That arises out of a granularity consideration.  The array would have
the O's in it and they may change (including creation).  You could put a
lock on every O, but that would miss the case where an O is in process
of being created and array not yet updated indicating existence.

Let's set that aside for a moment.  I would have thought that just
accessing the array elements, even if they are the entire "object" of
interest - say just fixnums, could be a locking issue if more than one
thread has access to the array.  Are you saying array element update,
(setf (aref A i) x), is an atomic operation in CCL?  That would lend
itself (in my case) to an even better solution!

Thanks!

/Jon

> 
> 
> 
> >Many thanks for any insights!
> >
> >/Jon
> >
> >_______________________________________________
> >Openmcl-devel mailing list
> >Openmcl-devel at clozure.com
> >http://clozure.com/mailman/listinfo/openmcl-devel
>