Subj : Re: Question for mr lockfree :)
To   : comp.programming.threads
From : Chris Thomasson
Date : Wed May 18 2005 12:48 am

>> However, you have to do a lot of bookkeeping IMHO, per-thread lists, bin
>> sorting them, iterating them and comparing against per-thread
>> hazard-pointers, tracking of the participating threads, and ( i 
>> think )the
>> amount of hazards per-thread is static...
> For the time being, it is. I have yet to find a "proper" way to reliably
> grow the number of per-thread hazard pointers without stopping the world..

You can get away with using per-thread hash-tables ( an unpublished 
algorithm of mine ) to get an unlimited amount of hazards per-thread. 
However it would add extra memory barrier overhead, and introduce some key 
differences wrt the original SMR algorithm. One key difference is the 
reduced granularity. One per-thread hash bucket ( I call them hazard 
proxy's ) could protect multiple objects, so a thread failure could hold up 
a variable number of objects from being collected.




>>> That is basically also the reason why I don't need a DCAS in libcontain
>>> (for the moment) but the problem is that I have a race condition in my
>>> vector implementation - which I was hoping you wouldn't have in yours..
>>> I.e., you don't have the same problem because you use a realloc to
>>> resize your array, which you apparently assume to be atomic.
>> Yes, the Array API is NOT thread-safe in anyway, shape or form.
> Right - that explains why I couldn't find that "atomic realloc
> implementation" anywhere :)
>
>>> but I'd be interested to know why using realloc on the array is not a
>>> problem, in your opinion/implementation.
>> I just never got around to putting the proxy gc code in there..
> :)
>
>>> I haven't had the time to look at your code in detail yet - mostly
>>> because it doesn't compile /chez moi/ so I can't run the tests on it,
>> You need platform sdk and vc++ 6.0. What errors/warnings do you get?
> I have VC .NET. I don't remember the errors I got, but I'll have a look
> when I have the time.

I have a brand new portable demo library posted, you should check it out; 
it's really tuned up nicely for SMP and/or HyperThreaded systems:


http://appcore.home.comcast.net/
(portable lock-free data-structures)


I believe you are referencing my old stuff for windows that I had up a year 
or two ago...




>>> I've been pondering making a readers/writers lock and only counting
>>> resize() as a writer, but that would kinda defeat the idea of being
>>> lock-free..
>> You can do a fast rw-lock with double-wide cas.
> Would you care to elaborate that a bit?
> Would that be a spinlock or would you use a couple of mutexes, split
> binary semaphores, condvars or some other such lock somewhere?

No, its not a spinlock. I got it to use ( unpublished algorithm ) CAS for 
fast-paths and two condvars for the slow-paths. It was also cancellation 
safe and allowed for timeouts.




> (If you know of a lock-free implementation other than Joe Seigh's
> rw-spinlock, I'd be interested :)

http://appcore.home.comcast.net/appcore/src/ac_rwspinlock_algo1_c.html
http://appcore.home.comcast.net/appcore/include/ac_rwspinlock_algo1_h.html

I think I am not the only person to come up this algorithm. Notice this has 
no specific ordering, unlike Joes elegant algorithm...




>> I will try to post the assembler very soon.
> Thanks - I'll have a closer look at it when I have time (which I don't
> really have the moment...

The assembler code for my old proxy collector was posted here:

http://groups-beta.google.com/group/comp.programming.threads/msg/a4a796e25a157ca1?hl=en

It got a bit garbled by Outlook though.

;(

.