Re: [boost] [Review] Lockfree review starts today, July 18th

Subject: Re: [boost] [Review] Lockfree review starts today, July 18th
From: Matthew Chambers (matt.chambers42_at_[hidden])
Date: 2011-07-18 17:07:45

On 7/18/2011 8:32 AM, Hartmut Kaiser wrote:
> Boost.Lockfree depends on C++0x atomics. They are not well supported with current compilers yet.
> For this reason Boost.Lockfree depends on the *unreviewed* Boost.Atomic library, that emulates
> C++0x atomics for C++98. This review is about Boost.Lockfree and not about Boost.Atomic,
> although it is included in the tarball and the git repository.
>
> If Boost.Lockfree will be accepted, it won't be merged into trunk before Boost.Atomic is
> accepted.
That's good to hear. So, um, when is Boost.Atomic going to be accepted? :)

I vote yes to the library with the trivial condition that the interface design issues I bring up 
below are considered. This is my first review and vote: w00t.

I've been using this library in its unofficial state since February. Our applications are
command-line multithreaded analysis tools. We routinely run with 8 threads and have run on
more (but not since the lockfree modification).

I have a mix of questions and comments.

> Additionally please consider giving feedback on the following general topics:
>
> - What is your evaluation of the design?
I'm happy with the design for the most part. It's reasonably consistent with the queue and stack
adaptors from the standard library. It can go a little farther though:
- size()/empty(): These should be available and not just "for debugging." I'm aware that using these
doesn't make a lot of sense in multithreaded programming (i.e. just because the queue is empty
doesn't mean the producer is done), but the std adaptors have them so I think the lockfree versions
should as well.  A size() can quite useful for displaying an (estimated) asynchronous counter,
especially for the case of a filled-up-front fifo with multiple consumers. The front()/back()
functions are understandably omitted though.
- range constructors: it's often convenient to construct a container from another container; since 
lockfree fifo is a real container and not just an adaptor, its ctors should have standard container 
ctors.

The only other things that bother me are the class template specializations. The documentation had
me thinking for several minutes that the fifo.hpp reference was duplicated. It wasn't until I read
the description that I understood the specialization. Which got me to thinking about a way to
eliminate that redundancy: instead of a class template specialization, can dequeue's parameter be a
template that must be constructible from T? That way you could have:
fifo<Foo*> q;
q.enqueue(new Foo); q.enqueue(new Foo);
Foo* rawPtr; q.dequeue(rawPtr);
shared_ptr<Foo> sharedPtr; q.dequeue(sharedPtr);
This would also support different pointer types, e.g. tr1::shared_ptr or std::unique_ptr or even
some UDT.

> - What is your evaluation of the implementation?
I'm not really knowledgeable enough to evaluate it. It works well in my multithreaded application.

> - What is your evaluation of the documentation?
There's a lot of nitpicking to be done here. I'll say up front that the examples are clean, easy to
understand, and pleasantly short.

What is the difference between guard and lock? Since this is lockfree and not guardfree, the docs
could just have "lock" :)

Why is the is_lock_free() function needed? If it is needed, why can't it be static? What is a 
real-world use case for it? And doesn't the caching_freelist_t type count as lockfree even though it 
may lock for memory allocations?

Some fun to be had with Search and Replace. Some of these occur more than once:
- "According Maurice Herlihy distinguishes" -> What is the wording supposed to be here? Accordingly?
- "to ensure the correctness" -> "to ensure thread-safety"
- "with no interaction without any direct interaction" -> "without direct interaction"
- "atomic operations, specific CPU instructions, which are executed atomically." ->
   "atomic operations (specific CPU instructions executed without interruption)."
- "Not every hardware supports" -> "Not all hardware supports"
- loosing -> losing
- lock-free' and wait-free' -> are these supposed to be quoted? Please don't use `
- "A mentioned earlier" -> "As mentioned earlier"
- "an interface, which is not compatible to the stl containers." ->
   "an interface which is not compatible with standard containers."
- "produced and consumed by 2 threads each" -> "produced and consumed by 4 threads each"
- "by 2 separate threads" -> "by separate threads"
- "Enqueueing may fail, if the ringbuffer is full." ->
   "Enqueueing will fail if the ringbuffer is full."
- "[begin, end[" -> "[begin, end)"
- poping -> popping
- os -> OS
- "struct caching_freelist_t" -> "caching_freelist_t" (with quotes, bold, and/or monospace font);
   same for all uses of "struct x" or "x_t" in proportional font.

Screwed up quotes and formatting (again with the `):
> The implementations are text-book' implementations of well-known data structures. the queue is
> based on a paper of Michael Scott and Maged Michael, stack and ringbuffer are considered as
> folklore' and are implemented in several open-source projects.
No hyphen in textbook.

In Design & Implementation, the final list of bullet points should have a preface like "The
implementation of lockfree containers comes with some caveats:"

RISC is capitalized. Perhaps list some examples of unsupported RISC processors?

Make hyphenation of lock-free consistent. It's fine to have lockfree in code, but prose should 
always use lock-free (or never).

In reference.html, why are all three headers linked but only fifo.hpp is displayed? The hyperlinks 
are screwed up. When I click on fifo.hpp I want to go to the full page, not the class declaration. 
For that matter, what is the purpose of having a page just for the class declaration and its 
specialization? If you want to show class declarations, show them all on one page (with links to the 
full pages).

What does it mean for a fifo node to be "lockfree"?

Why is it impossible for C++0x atomics to provide "a completely accurate implementation"? I think 
this was already asked and answered but it should be in the docs. And it's especially strange given 
your leading sentence "Boost.Lockfree depends on C++0x atomics". I'm probably missing something.

Why is dequeue_unsafe unsafe if the platform supports atomics?

Ringbuffer methods 4 & 5 don't have "Returns:" documentation.
For method 5, is the array size supposed to be passed in as the template parameter? Rationale?
In method 8 of the ringbuffer specialization, 't' should be 'ret'.
What is the ringbuffer specialization for? Why have both the template-fixed-size and 
constructor-fixed-size versions? The array methods for ringbuffer need examples. I actually have no 
idea how to use them by looking at the methods signatures.

How is the range enqueue method non-blocking?

"While this function is thread-safe, it only guarantees that at some point during the execution of 
the function the stack has been empty."
This definition is kind of confusing. Perhaps "May return true if the queue/stack/ringbuffer was 
empty at some point during the call to empty(). It is rarely practical to use this value in program 
logic."

> - What is your evaluation of the potential usefulness of the library?
The useful producer-consumer paradigm is easier and simpler using the lockfree queue. So yes, it's
useful.

> - Did you try to use the library?  With what compiler?  Did you have any problems?
We build and run our applications primarily with x86_64/GCC 4.1.2 and x86/MSVC 9.

> - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
I spent a couple hours proof-reading the documentation and another to write the review. Which is 
probably more time than it actually took me to switch from my lock-based multi-consumer queue to the 
lockfree fifo. :)

> - Are you knowledgeable about the problem domain?
Not enough to critique the implementation, but I can ask plenty of questions. :)

Thanks for the very useful library Tim (and Helge)!
-Matt