Re: [boost] [Review] Lockfree review starts today, July 18th

Subject: Re: [boost] [Review] Lockfree review starts today, July 18th
From: Julien Nitard (julien.nitard_at_[hidden])
Date: 2011-07-19 10:40:43

Hi Tim,

Here is a new set of questions: (sorry they may have been more relevant in a
pre-review, I missed it if there was one).

I did not read nor test the code yet, so forgive me if my questions are
stupid.

** On lock-free concepts in general

  - Your definition of obstruction-free is strange, I would have though that
a lock free structure would be quite the opposite :* "if a concurrent
operation is guaranteed to be finished in a finite number of steps, even if*
* another concurrent operation interferes"*. I do not understand the
guarantee that obstruction gives otherwise. I think this section of the
documentation should be expanded and give more details.

  - Is there some kind of inclusion relationship between lock-free,
wait-free, and obstruction free ? (I am thinking something like everything
that is wait-free is also lock-free and everything lock-free is also
obstruction-free)

  - It would be good to define "guard" in the documentation as I would have
considered memory barriers (required for atomic operations) to be guards.

** About performance

  - You don't mention in the "motivations" sections that lock-free data
structures are probably more performant than their locked counter parts.
Though it is obvious too some, it is not to all, and to be honest, I'd
prefer you mention at this stage the typical usage of lock free structures
(for instance, are there situations where locked data structures perform
better ?)

   - You don't give any performance comparisons with a normal, "locked"
stack. It would be interesting to do. It should nearly be a test case ;).

   - Is there a way to force the lock-free data structures to use a locked
implementation ? I'll probably want to compare the two and it could be
useful for the test cases.

** About data structures

   - What's would be a typical use case of a concurrent stack ? Since both
consumers and writers are accessing the same end of the structure, won't it
trigger a lot of cache-sharing and have bad performance ? I had look .Net
has a one, so I guess there is a point, but I can't figure it out on my own.

   - Is it feasible to implement a lock-free pool of objects ? Is
it relevant ? (I am thinking of something vaguely simiral to .net
ConcurrentBag)

** Others

   - Enqueue may block if memory needs to be allocated, but wouldn't it be
possible to avoid this by specifying an optional maximum size as template
parameter or constructor argument ?

   - Documentation : the class synopsis of the data structures should be
accessible from the "Reference" page. (That's where I instinctively looked
for them).

Thanks for your work, it overall looks very promising,

Julien