
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: http://cppcms.sf.net/ CppDB - C++ SQL Connectivity: http://cppcms.sf.net/sql/cppdb/

Den 27-07-2011 15:19, Artyom Beilis skrev:
------------------------------------------------------ - 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)
vector seems like another: http://www.research.att.com/~bs/oopsla09-nonblocking.pdf -Thorsten

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
participants (3)
-
Artyom Beilis
-
Thorsten Ottosen
-
Tim Blechmann