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

[Gail Zacharias]

At 1/11/2010 10:28 AM, Jon S. Anthony wrote:
>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...

Puthash doesn't ordinarily use locks, though it uses a couple of
conditional stores, which sync memory.  That's if you're just setting
the values of existing keys.  If you use puthash to add keys, then it
might need to grow the table, in which case it will grab a lock.




> > >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!


For simple vectors it is atomic (there might be some issues for
adjustable arrays).



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