[boost] [lockfree] review

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