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