...

The following data structures are provided:

- boost::lockfree::fifo, a lock-free fifo queue - boost::lockfree::stack, a lock-free stack - boost::lockfree::atomic_int, an atomic integer class

The docs of the provided file seem to be out of sync with this? The docs mention fifo, ringbuffer, and stack.

this description is out of sync with the docs :/

On 7/18/2011 9:51 AM, Klaim - Joël Lamotte wrote:

Hi,

On Mon, Jul 18, 2011 at 15:32, Hartmut Kaiser <hartmut.kaiser@gmail.com <mailto:hartmut.kaiser@gmail.com>> wrote:

- What is your evaluation of the documentation?

Just a minor request so far :

If I remember correctly (and I might be very wrong as my memory is really not clear on this point), the presentation at boostcon started by explaining why lockfree data structures should be used only in last resort or something like that.

Maybe a documentation page with such explainations would help the user know if it there are better solutions for their cases? I read that the main purpose is comunication between threads.

Joël Lamotte

One case where I use a lock-free data structure is with high performance network communications in which the client app receives tremendous amounts of data. The app has a thread dedicated to receiving data and another thread dedicated to processing the data. It uses a fixed size lock-free circular buffer to hold the data. In terms of boost::lockfree, this would be akin to the fifo queue. Using a circular queue prevents memory allocations, but does limit the amount of stored data making it critical that the processing thread reasonably keep up. Having a lock-free data structure definitely helps with performance. I haven't looked at boost::lockfree yet, but I'm very curious to know how the fifo queue compares. Perhaps adding a circular queue version to lockfree would be beneficial. The implementation is fairly trivial. I don't even use atomic operations for it (at least on Windows). Although perhaps they may be needed for other platforms. -- Bill

2011/7/18 Klaim - Joël Lamotte <mjklaim@gmail.com>

If I remember correctly (and I might be very wrong as my memory is really not clear on this point), the presentation at boostcon started by explaining why lockfree data structures should be used only in last resort or something like that.

It I recall correctly, using lock free data structures is fine; implementing them is fraught with peril. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

hi john,

- You provide a mp-mc queue, a sp-sc queue, and a mp-mc stack. Are there any other combinations you know of for which an implementation could usefully be provided; e.g. could a sp-mc stack be made faster than the one you've provided?

good questions ... possibly, but i am not aware of such an algorithm ...

- Some of your function declarations have explicitly-void argument lists (e.g. fifo's default constructor). This is correct, but unconventional. An empty argument list would be less confusing, IMO.

this is my personal coding style, if people suggest to remove it, i can do that.

- You describe it as a 'limitation' that "The class T is required to have a trivial assignment operator.". I think this is better described as a 'requirement'. Are there any other requirements? I'm guessing it must be CopyConstructible, or at least MoveConstructible? Are you sure you don't need a trivial destructor and/or copy constructor in addition to the trivial assignment?

hm, you are right. it both needs to have a trivial destructor and a copy constructor. i don't want to provide any move semantic, enqueue/push may fail if no nodes can be allocated.

- fifo::empty is described as non-thread-safe. To what extent? Might it crash the program or corrupt the container, or is it simply that other threads can change the content of the container at a whim, and so the result of calling empty might not persist until the next operation?

it won't crash, but the answer will may be incorrect.

- Does the specialization fifo<T *, freelist_t, Alloc> also require that T is trivially assignable, or even that it is assignable at all? It's not clear. If it is actually storing pointers is there a risk of memory leaks if the container is destroyed while non-empty? If it's not actually storing pointers, then what am I to do if I genuinely want a fifo of pointers? Generally I find this specialization a bit worrying since its semantics differ so markedly from the unspecialized equivalent.

i actually like matthew's proposal of templating the dequeue/pop argument. that would make the specialization obsolete. currently, destroying a non-empty fifo<T*> would leak memory.

- You have documented no requirements on ringbuffer's T type. So I guess it needn't be trivially assignable; but again I guess it must be CopyConstructible?

correct, i should document this

- The ringbuffer docs mention several times the type 'T const (&)', which doesn't make sense; I'm guessing a '[size]' has been cut out at some point in the documentation generation process.

hrrr ... you are right ... will need to add this to my list of questions for the quickbook/doxygen masters ...

- stack's empty is documented differently from the others; is it different somehow; more safe? more suitable for non-debugging purposes?

yes it is: stack::empty() does just need to check if there is a top node available().

- The fifo and stack insertion functions both return false if "if the freelist is not able to allocate a new fifo node.". Is this only when using a fixed-sized freelist which has used all it's size, or might this also happen with a caching freelist when allocation fails (e.g. due to running out of memory). To put it another way: how are you handling exceptions thrown by the allocator?

no, but i guess for consistency reasons i should do that!

- BOOST_STATIC_ASSERT is classed as a "private member function"; I guess this is a side-effect of auto-generated docs or something, but it's rather odd.

thanks, will hide it for the doxygen pass.

- Why does ringbuffer have range enqueue functionality, but not the other two classes?

the ringbuffer will be able to enqueue the range in one step, stack and fifo cannot do this. but maybe it would make sense to add a range interface, but document the behavior.

- Why have you provided a pointer specialization for fifo but not stack?

:) historical reasons ... i should either provide a specializaton for both or for none ...

- Since these classes have various methods in common, would it be worth pulling those out and documenting them once centrally (in the way the standard does).

well, there may be subtle differences because of the implementation. e.g. fifo::empty() vs stack::empty() ... thanks for your comments, i will address the issues in the next days ... cheers, tim

...

...

- fifo::empty is described as non-thread-safe. To what extent? Might it crash the program or corrupt the container, or is it simply that other threads can change the content of the container at a whim, and so the result of calling empty might not persist until the next operation?

it won't crash, but the answer will may be incorrect.

The docs should clarify exactly what can go wrong.

i've already tried to improve the docs (in a separate branch of my git repository)

...

...

- Does the specialization fifo<T *, freelist_t, Alloc> also require that T is trivially assignable, or even that it is assignable at all? It's not clear. If it is actually storing pointers is there a risk of memory leaks if the container is destroyed while non-empty? If it's not actually storing pointers, then what am I to do if I genuinely want a fifo of pointers? Generally I find this specialization a bit worrying since its semantics differ so markedly from the unspecialized equivalent.

i actually like matthew's proposal of templating the dequeue/pop argument. that would make the specialization obsolete. currently, destroying a non-empty fifo<T*> would leak memory.

I don't like this. Fundamentally, you must decide whether a container of pointers is responsible for the memory management of the pointers in it. Compare, for example, std::vector<T*> and boost::ptr_vector<T>. Your interface is much more akin to the std:: containers, and I think it's wiser to stick to that model. If your users store pointers in it they should concern themselves with the corresponding memory management elsewhere. In particular, the enqueue function should take a T*, not a T as it presently does. Adding half-hearted support to help them will only lead to confusion, obscure memory leaks and problems in the long run.

well, if i remove the pointer specialization and modify pop/dequeue to use a templated argument, there would be a simple requirement that the value type T must be convertible to the dequeue type U (): template <typename T> fifo { template <typename U> bool dequeue (U &); }; for me the main reason for adding a specialization for pointers was to be able to dequeue to smart pointers, which could be achieved with this approach.

...

...

- The fifo and stack insertion functions both return false if "if the freelist is not able to allocate a new fifo node.". Is this only when using a fixed-sized freelist which has used all it's size, or might this also happen with a caching freelist when allocation fails (e.g. due to running out of memory). To put it another way: how are you handling exceptions thrown by the allocator?

no, but i guess for consistency reasons i should do that!

It's not clear that you want to catch the exceptions. Personally I would expect you not to, but the docs should certainly clarify either way. And you should check what guarantees your methods offer in the face of such exceptions, and document them (I imagine the strong guarantee should be no trouble here).

yes, after thinking about it for some time, i actually decided the same way and modified my code accordingly! cheers, tim

...

...

- Why does ringbuffer have range enqueue functionality, but not the other two classes?

the ringbuffer will be able to enqueue the range in one step, stack and fifo cannot do this. but maybe it would make sense to add a range interface, but document the behavior.

For a node-based stack, can't you build the linked list of nodes "on the side" with the last node pointing to head, then CAS the head to point the first node in your on-the-side list, to enqueue the whole range atomically? And then also have the strong exception guarantee?

Or am I missing something (about the allocation scheme maybe?)

hm, i was actually thinking about both enqueuing and dequeuing of multiple objects. but if it is just about enqueuing it, it might be reasonable ... will check ... tim

...

If Boost.Lockfree will be accepted, it won't be merged into trunk before Boost.Atomic is accepted.

That seems unnecessary. Can't Boost.Lockfree simply include (a version of) Boost.Atomic as an implementation detail for now?

this would somehow mean to fork boost.atomic, move everying to a `namespace detail'. might introduce some maintenance overhead to keep it in sync with the original library. but it might be a possibility, if boost.atomic won't be reviewed in the near future. but if this won't be the case, maybe some people can join their effort to adopt boost.atomic, if the original author won't have time to do the review. imo this would be reasonable, because the library will hopefully have a short lifespan. it will be obsolete, when most compilers provide c++0x atomics. tim

...

...

...

If Boost.Lockfree will be accepted, it won't be merged into trunk before Boost.Atomic is accepted.

That seems unnecessary. Can't Boost.Lockfree simply include (a version of) Boost.Atomic as an implementation detail for now?

this would somehow mean to fork boost.atomic, move everying to a `namespace detail'. might introduce some maintenance overhead to keep it in sync with the original library.

Excuse me if it's common knowledge around here, but I've seen several libraries relying on boost.atomic that have been reviewed, so may I ask : why haven't Boost.Atomic been reviewed yet? It looks like it's already finished and reliable...

mainly because the original author did not submit it. nor has he been very active during the last few months: the boost.lockfree repository contains some fixes to boost.atomic, which haven't been applied to the upstream repository, although i have sent them the author. cheers, tim