hi matthew,

...

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? :)

boost.atomic should be treated on its own. personally i would encourate a fast- track review because it is an implementation of a c++0x feature, so there is no real need to evaluate the interface for example ;)

- 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.

afaict, empty() cannot correctly be implemented for the fifo (unless using an atomic counter). size() would require an atomic integer (read: one more atomic operation, which will probably be rather expensive) and cannot be implemented accurately (one can just give an lower or upper bound).

- 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.

here again i hesitate: stack and fifo use an internal freelist, which can be configured with a policy to be constant-sized (which is required for real-time systems where you cannot allocate memory). range constructors would therefore also require an additional argument to specify the number of nodes of the free-list.

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.

this is an interesting idea! however it cannot be used to dequeue to a scoped_ptr. although i must admit that dequeueing to a scoped_ptr is debatable ...

...

- What is your evaluation of the documentation?

i won't comment on all of your suggestions: most of them i'll simply agree with (i am not a native speaker and the docs haven't been proofread, as i rewrote it after the boostcon pre-review)

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

yes and no: lock-free is not the same as non-blocking (according to the terminology of herlihy, which i am trying to follow). `obstruction-free' data structures would not be lock-free, but would not use locks, either.

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?

atomic operations are not necessarily lock-free. boost.lockfree requires double- word compare-and-swap, which is not available on all architectures. e.g. ppc does not provide them. c++0x atomics define atomic<>::is_lock_free as non-static member functions (which is reasonable, because on some architectures, a specific alignment is required, so atomic<> instances would be lock-free or not depending on their memory address). targetting c++0x, it cannot be static. even worse: to give a fully correct answer, we would have to check every internal node, which is not possible, if the internal nodes are allocate dynamically. and it is true, that the caching_freelist_t may lock during memory allocations. so maybe instead of a boolean, i shall return an enum with the states `lockfree', `blocking_on_allocation' and `blocking_on_atomic_operation' ...

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).

well, this is what quickbook/doxygen generates by default. i'd prefer to list all headers on reference.html, but i'd need some advice, how to achieve this.

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.

as stated above: is_lock_free is a per-instance member function of atomic<>. i am not sure, if i really should describe the reasons in detail, because it would go quite into the details of the implementation.

Why is dequeue_unsafe unsafe if the platform supports atomics?

the _unsafe operations are unsafe, because they do not use atomics. the reason for this is performance: atomics are slow

What is the ringbuffer specialization for? Why have both the template-fixed-size and constructor-fixed-size versions?

i want to provide the same data structure for specifying the size at compile- time and at run-time. the main reason for compile-time is that using a power of two, the indices math can use bitmasks for performance reasons.

The array methods for ringbuffer need examples. I actually have no idea how to use them by looking at the methods signatures.

ok, will try to add

How is the range enqueue method non-blocking?

it does not enqueue all objects, but only tries to enqueue the first N objects. will improve the docs in this part. thanks for your review, i will try to adapt the docs according to your suggestions. cheers, tim

It might also be a good idea to post the documentation somewhere on the internet so we can browse through it without having to hack our way through the build system first.

The documentation is online at http://tim.klingt.org/boost_lockfree/. There used to be a link on the Boost Review Schedule page [1], but since the review started it's gone (why is there a "Link" column in the "Schedule" table but not in the "Past Review Results and Milestones" table?) Regards, Nate. [1] http://www.boost.org/community/review_schedule.html

On 7/19/11 12:47 AM, Tim Blechmann wrote:

the rendered html docs are also part of the tarball ...

Oh, and so they are! I don't know how I missed them; maybe I clicked in "atomic" by mistake... Thanks for pointing that out! :-) Cheers, Greg

- Enqueue may block if memory needs to be allocated, but wouldn't it be possible to avoid this by specifying an optional maximum size as template parameter or constructor argument ?

Sorry, I wrote that too fast, there is such a constructor. Forget it. Julien

----- Original Message ----

From: Tim Blechmann <tim@klingt.org> To: boost@lists.boost.org Sent: Tue, July 19, 2011 9:10:06 PM Subject: Re: [boost] [Review] Lockfree review starts today, July 18th

hi julien,

...

** On lock-free concepts in general

- Your definition of obstruction-free is strange, I would have though that a lock free structure would be quite the opposite :* "if a concurrent operation is guaranteed to be finished in a finite number of steps, even if* * another concurrent operation interferes"*. I do not understand the guarantee that obstruction gives otherwise. I think this section of the documentation should be expanded and give more details.

i am basically taking the definitions from herlihy&shavit. but i can try to improve this part of the docs.

Actually reading this notes I opened Herlihy & Shavit book "The art of multiprocessor programming" To check if this is correct definition and then I had seen you refer to the book. Which actually gives +1 to the library even more.

...

** About performance

- You don't mention in the "motivations" sections that lock-free data structures are probably more performant than their locked counter parts. Though it is obvious too some, it is not to all, and to be honest, I'd prefer you mention at this stage the typical usage of lock free structures (for instance, are there situations where locked data structures perform better ?)

there is a section about `performance of non-blocking data structures'. there i

mention that in some cases blocking data structures can outperform their

lock-

free equivalent.

I must strongly support this point. Lock free is not always the fastest algorithm but in some cases it is may be very important to ensure conditions like "at-least-one-succeeds-eventually" Artyom

hello holger,

The documentation talks a bit about false sharing and to some extent about cacheline alignment to achieve that, but I don't see that to extent I would expect in code. Specifically, how do you ensure that a given object (I only looked at ringbuffer) _starts_ on a cacheline boundary.

i am trying to ensure that those parts, which are modified by different threads are in different cache lines. however i don't necessarily care, if they are at the beginning of the cache line.

I only see this weird padding "idiom" that everyone seems to use, but nothing to prevent a ringbuffer to be put in the middle of other objects that reside on cacheline that are happily write-allocated by other threads. For instance, what happens for:

ringbuffer<foo> x; ringbuffer<foo> y;

Consider a standard toolchain without fancy optimizations. Wouldn't this normally result in the x.read_pos and y.write_pos to be allocated on the same cacheline.

in this case one could argue, that you should ensure the padding manually :) nevertheless, there is one point that i should probably address: i should enforce that neither read index, write index and the actual ringbuffer array use different cache lines.

There also doesn't seem to be a way to override the allocation of memory. For the kind of low-latency we (as in Morgan Stanley) interested in, we may sometimes care about delays from lazy PTE mechanisms that many operating system have. If you just simply allocate via new[] you may get a few lazily allocated pages from the OS. A 1ms delay for page fault is something we do care about.

Is there any good way to override the allocation?

if the size of the ringbuffer is specified at runtime, there is no way for it, i should probably add allocator support. however this will only help, if your allocators force the memory regions into physical ram by using mlock() or the like and by touching them to avoid minor page faults.

Are there any performance targets/tests? E.g. for a ringbuffer, I found a test with a variable number of producer and consumers useful, where producers feed well-known data and consumers do almost nothing (e.g. just add the dequeued numbers or something) and see what kind of feed rates can be sustained without the consumer(s) falling behind.

the ringbuffer is a single-producer, single-consumer data structure. if you use multiple producers, it will be corrupted! in general i hesitate to add any performance numbers, because the performance heavily depends on the CPU that is used.

Lastly, what's going on with all the atomic code in there? Can I assume that's just implementation details that overrides things in the current Boost.Atomic lib and hence ignore it for the review?

boost.lockfree depends on boost.atomic. for this review, boost.atomic should be ignored and we probably have to decide later, if we postpone the inclusion until boost.atomic is reviewed, or if i provide a modified version of boost.atomic as implementation detail. nevertheless, i have a small wrapper, which could be used to switch between boost::atomic and std::atomic. unfortunately none of my compilers implements the necessary parts of the atomic<> template ... cheers, tim

...

...

ringbuffer<foo> x; ringbuffer<foo> y;

Consider a standard toolchain without fancy optimizations. Wouldn't this normally result in the x.read_pos and y.write_pos to be

allocated

...

on the same cacheline.

in this case one could argue, that you should ensure the padding manually :)

That seems counter-intuitive to me. If you expect users to do so that should probably be spelled out clearly.

well, i think this is not really a common case. if one wants to be sure, that there is absolutely no false sharing, one would have to pad the whole class to ensure that nothing before and nothing after the data structure will be placed in the same cache line. but i think going that far is overkill ...

...

nevertheless, there is one point that i should probably address: i should enforce that neither read index, write index and the actual ringbuffer array use different cache lines.

I'm having trouble understanding this. Do you mean they should go on different cachelines?

yes

...

the ringbuffer is a single-producer, single-consumer data structure. if you use multiple producers, it will be corrupted!

My bad -- sorry haven't read the docs or code carefully.

i've now mentioned it explicitly in the reference section of each function. cheers, tim