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

[Gail Zacharias]

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.


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

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?




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