
hi artyom, thanks for your review!
------------------------------------------------------ - What is your evaluation of the design?
Basically it looks quite simple and straight forward. As the data structures are based (according to the author) on the current papers and studies; it uses quite standard features and seems fine.
a side note: lock-free data structures are a patent minefield. these data structures are the most simple ones and the ones which are (ianal) not patented.
------------------------------------------------------ - What is your evaluation of the documentation?
I think it is too brief and misses important parts.
For example: html/boost/lockfree/ringbuffer.html
Should include in the reference general requirements like it should be single writer single reader and not mentioned in some other places.
In the first glance I assumed that it was multiple-readers-writers ring buffer.
yes. this has already been discussed earlier and i have significantly changed the docs to ensure this!
------------------------------------------------------ - What is your evaluation of the potential usefulness of the library?
ok...
This is probably the biggest problem with this library. [snip]
I'd like to see more:
1. Queues with OS support like waiting - non-waiting with lock-free access when the queue not-empty and not-full
i have avoided this intentionally because i consider this as out of the scope of the library: afaict, in order to wait for empty/full queues, one needs to use either condition variables or semaphores. condition variables will block, if the condition is modified. semaphores are very os-dependent, and i have no idea, if any semaphore operations are actually lockfree. so from my understanding it is not possible without violating the lock-free property
2. Queues with different optimization for different cases.
i'd be curious: what are you thinking about?
3. There are several ways to optimize stacks to reduce contention.
what are you referring to? backoff and elimination?
4. Some transactional memory blocks that allow to implement optimistic strategies
again, do you have any suggestions, ideas, or papers that you suggest i should look at?
5. Combination of locking and lock-free parts.
this again is out of the scope of the library for me.
6. Hash tables
this has already been suggested before. maybe in a future version of the library...
So I vote "Yes" but I strongly recommend and expect from the author:
- Make some building blocks available in detains to library interface allowing users to implement other data-structures easier.
the important building blocks will probably be the tagged_ptr and the freelist. however i'd prefer to keep it an implementation detail, because once they are exposed, their semantics cannot be changed.
- Improve documentation about what and how it should be done
i am already working on this ;)
- Provide more data structures in future and provide data structures with different policies
which policies do you suggest? cheers, tim