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

Subject: Re: [boost] [Review] Lockfree review starts today, July 18th
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-07-19 14:10:06

hi julien,

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

i am basically taking the definitions from herlihy&shavit. but i can try to 
improve this part of the docs.

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

exactly.

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

yes, possibly. i am trying to avoid the term `lock', because using the 
terminology of wait-free/lock-free/obstruction-free, there are data structures, 
which do not use locks, but that are not lock-free.

> ** 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 ?)

there is a section about `performance of non-blocking data structures'. there i 
mention that in some cases blocking data structures can outperform their lock-
free equivalent.

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

i basically want to avoid all discussion about performance and performance 
characteristics in the docs, because it heavily depends on the design of the 
CPU, the instruction set, and probably the connection between the cpu cores. so 
my advice is to test with the specific workload.
synthetic benchmarks with 8 threads hammering a stack (which basically uses one 
memory location) will most likely be slower than a synthetic benchmark using 
locks because of contention (threads interfering with each other).

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

this is not really feasible: if you want to use a blocking implementation, you 
will use a different layout of a data structure (e.g. a std::vector using a 
continuous memory region instead of the node-based lock-free data structures).

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

the fifo requires more atomic operations than the stack.

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

one can implement a lock-free linked list, which serves as set-like data 
structure. i the main reason, why there is none in boost.lockfree is that i 
never needed one myself. but it may be a good addition in a future version.

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

there are two ways:
* there is a constructor, which reserves a number of nodes for the freelist
* one can use the freelist_t tag to configure the stack/fifo to avoid any memory
  allocations. this is mainly required for hard-realtime systems.

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

true ... but i will need some help from a quickbook/doxygen master for that :/

cheers, tim