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

Subject: Re: [boost] [Review] Lockfree review starts today, July 18th
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-07-18 18:39:20

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