Boost logo

Boost :

Subject: [boost] [lockfree] review
From: Artyom Beilis (artyomtnk_at_[hidden])
Date: 2011-07-27 09:19:41

Hello, Please consider it as a 1/2 or 1/3 review as I hadn't much time to review this library: I'd start answering the questions in little bit different order: ------------------------------------------------------ - 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. ------------------------------------------------------ - What is your evaluation of the implementation? It seems to be clear, however I miss following: As it is virtually impossible to test concurrent data structures I expect that every critical part in the code that describes concurrent operation would have a reference to specific article or book and include full description and even a small proof that it is right taken from the resources. I think it is very critical for maintenance of the library and in ensuring the fact that it can be maintainable. Finally it looks like a solid code written with good knowledge of what is going on. ------------------------------------------------------ - 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. ------------------------------------------------------ - Did you try to use the library?  With what compiler?  Did you have any problems? I've tested it with gcc-4.3 on cygwin using CMake scripts,no particular problems. ------------------------------------------------------ - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I've spend 2-3 hours reading the code, comparing my own "ringbuffer" with a provided ring buffer and fifo. ------------------------------------------------------ - What is your evaluation of the potential usefulness of the library? ok... This is probably the biggest problem with this library. I understand that Linked List, Stack, Ring are actually the implementable data structures (most of others are much harder to do if possible at all, even thou there are few that can be implemented: hash tables and some others) I understand that this is "lock-free" library not generic-concurrent-data-structures library but this is why I think that it may not be as useful as it seems. 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 2. Queues with different optimization for different cases. 3. There are several ways to optimize stacks to reduce    contention. 4. Some transactional memory blocks that allow to implement    optimistic strategies 5. Combination of locking and lock-free parts. 6. Hash tables And more. ------------------------------------------------------ - Are you knowledgeable about the problem domain? Yes:   - I had implemented several concurrent data structures     for professional needs.   - I had took Prof. Nir Shavit's course in concurrent programming     (The author of the The Art of Multiprocessor Programming) ------------------------------------------------------ Should the library be accepted into Boost? I have doubts, mostly because my considerations about the usability of the library in the real applications. I'd expect the author to provide more data structures more available policies, for example there are several ways to optimize stack object see "The Art of Multiprocessor Programming" chapter 11 section 4. Also I'd like to see some more helpful objects in the interface: Tagged ptr is something that would be seen for many data structures I don't think should it be in details? I really hesitate between "Conditional YES" and "YES" - Finally it seems to be doing what it does - It is not concurrent data structures library but lock-free one. 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. - Improve documentation about what and how it should be done - Provide more data structures in future and provide data structures   with different policies   Artyom Beilis -------------- CppCMS - C++ Web Framework: CppDB - C++ SQL Connectivity:

Boost list run by bdawes at, gregod at, cpdaniel at, john at