[lockfree review] rfc: naming and interface
hi all, i am starting a new thread, because i want to start a new discussion on one aspect of boost.lockfree: the naming of the data structure and the interface naming: the current names of the data structures are fifo, stack and ringbuffer. during the pre-review some people suggested to use different names, lifo instead of stack or queue instead of fifo. in general i think it is a good idea to use a consistent naming (probably fifo should be renamed to queue), but how does the ringbuffer come in? it is a queue as well, but with different characteristics (spsc and wait-free). data structure configuration: stack and fifo currently use 3 template arguments: T for the managed type, freelist_t as a tag to select the underlying freelist and Alloc as the allocator which is used for the internal nodes: template<typename T, typename freelist_t = caching_freelist_t, typename Alloc = std::allocator<T> > class fifo/stack; however i have been thinking about replacing it with a boost.parameter interface, something like: template<typename T, ... Options> class fifo/stack; with the options: boost::lockfree::freelist_can_allocate<true/false> to disable memory allocation during enqueue/push boost::lockfree::allocator<> to specify the allocator ringbuffer size: the ringbuffer currently has the signature: template<typename T, size_t max_size> class ringbuffer; if max_size is 0, the size of the ringbuffer can be configured at run-time with a constructor. this is not really the cleanest interface, but i would like to provide an interface, which supports both compile-time and run-time setting of the size. i would apprechiate a discussion about these points during the review. thanks, tim
On Jul 21, 2011, at 2:46 AM, Tim Blechmann wrote:
i am starting a new thread, because i want to start a new discussion on one aspect of boost.lockfree: the naming of the data structure and the interface
naming: the current names of the data structures are fifo, stack and ringbuffer. during the pre-review some people suggested to use different names, lifo instead of stack or queue instead of fifo. in general i think it is a good idea to use a consistent naming (probably fifo should be renamed to queue), but how does the ringbuffer come in? it is a queue as well, but with different characteristics (spsc and wait-free).
I generally prefer plain English over acronyms -- especially since stack and queue are terms and concepts well-understood by computer scientists, but LIFO and FIFO may require mentally deducing which one is which. So my vote is on "stack" and "queue". As for "ringbuffer", I would consider shortening it to just "ring". Josh
On Thu, Jul 21, 2011 at 11:58, Joshua Juran <jjuran@gmail.com> wrote:
As for "ringbuffer", I would consider shortening it to just "ring".
I'm not sure if ringbuffer share exactly the same concepts than boost::circular_buffer but to be consistent with this library naming maybe ringbuffer should be circular_buffer? I prefer "ring" alone personnally but as circular_buffer have been accepted before maybe it's naming is more explicit to a lot of reviewers? Joël Lamotte
on Thu Jul 21 2011, Joshua Juran <jjuran-AT-gmail.com> wrote:
I generally prefer plain English over acronyms -- especially since stack and queue are terms and concepts well-understood by computer scientists, but LIFO and FIFO may require mentally deducing which one is which. So my vote is on "stack" and "queue".
As for "ringbuffer", I would consider shortening it to just "ring".
Not bad. Alternatively, consistency with the C++ standard would argue for something like wait_free_queue. HTH, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sat, Jul 23, 2011 at 11:03 AM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Jul 21 2011, Joshua Juran <jjuran-AT-gmail.com> wrote:
I generally prefer plain English over acronyms -- especially since stack and queue are terms and concepts well-understood by computer scientists, but LIFO and FIFO may require mentally deducing which one is which. So my vote is on "stack" and "queue".
As for "ringbuffer", I would consider shortening it to just "ring".
Not bad. Alternatively, consistency with the C++ standard would argue for something like wait_free_queue.
HTH,
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
We should imagine that more specialized queues will be added. So it would be nice to somehow be able to name them, or ask for them via template param. Here are just *some* of the options that can be combined in various ways: - single vs multiple producer and consumer (typically called spsc,mpmc,spmc,mpsc queues) - node based, array based, hybrid - bounded/unbounded - intrusive / non-intrusive - fail/overwrite/wait on overflow, fail/wait on underflow - growing/shrinking - etc I don't think all options are of the same importance - ie array vs node vs hybrid isn't as important to me as mpmc vs spsc (because the underlying data structure is an implementation detail, but mpmc vs spsc means whether it will work correctly or not in a given situation). But often the choice between vector vs list, etc is the implementation details (which lead to key runtime characteristics) and not a difference in interface. Could (should?) this be done with template attributes? ie queue< spsc, bounded, intrusive > myQueue; Any params not given mean "I don't care, go with default". If you request a queue that is mpmc, hybrid, unbounded, shrinkable, waitable, and we don't have one yet, then it doesn't compile. Note also that they queues would probably have *almost* the same interface, but some functions like 'size()' might not exist depending on which combination you choose. Maybe that makes it a bad idea. Alternatively, even without using templates for selection, we should "leave room" for more queues and other data structures. And if the ringbuffer is a type of queue it should be named as such - it is a spsc_queue I think? Or queue could be a sub-namespace? lockfree::queue::ringbuffer<>; lockfree::queue::mpmc<>; etc? Tony
I generally prefer plain English over acronyms -- especially since stack and queue are terms and concepts well-understood by computer scientists, but LIFO and FIFO may require mentally deducing which one is which. So my vote is on "stack" and "queue".
As for "ringbuffer", I would consider shortening it to just "ring".
Not bad. Alternatively, consistency with the C++ standard would argue for something like wait_free_queue.
but then, wait_free_queue or spsc_queue? spsc_queue may be better as there are probably going to be more bugs of the sort `spsc data structure used for mpmc operations' than `lock-free data structure used, but wait-free is required'
We should imagine that more specialized queues will be added. So it would be nice to somehow be able to name them, or ask for them via template param.
Here are just *some* of the options that can be combined in various ways: - single vs multiple producer and consumer (typically called spsc,mpmc,spmc,mpsc queues) - node based, array based, hybrid - bounded/unbounded - intrusive / non-intrusive
to add some more confusion: intrusive, but not ABA prone (if the program logic prevents this)
- fail/overwrite/wait on overflow, fail/wait on underflow
is `overwrite' reasonable? and there would be quite a number of options, how to wait: spin, spin-and-yield(), wait for semaphore (it there were a boost.semaphore), wait for condition variable and if, we really want to go that way: - fifo-ordered/lifo-ordered. then we won't even need the stack class and the library could be renamed as lockfree_queue ;)
Could (should?) this be done with template attributes? ie
queue< spsc, bounded, intrusive > myQueue;
Any params not given mean "I don't care, go with default". If you request a queue that is mpmc, hybrid, unbounded, shrinkable, waitable, and we don't have one yet, then it doesn't compile.
there are different opinions about this: some people say that different template arguments should not conflict, while others say this is fine to throw a compile- time error.
Note also that they queues would probably have *almost* the same interface, but some functions like 'size()' might not exist depending on which combination you choose. Maybe that makes it a bad idea.
compile-time assertions can be thrown in this case. i am using this for the (to- be-renamed) ringbuffer to ensure that the correct constructor is used when the data structures is compiled as compile-time-sized vs run-time-sized. cheers, tim
On Sun, Jul 24, 2011 at 5:22 AM, Tim Blechmann <tim@klingt.org> wrote:
- fail/overwrite/wait on overflow, fail/wait on underflow
is `overwrite' reasonable? and there would be quite a number of options, how to wait: spin, spin-and-yield(), wait for semaphore (it there were a boost.semaphore), wait for condition variable
Yes overwrite is reasonable. Imagine real-time data like the accelerometer/magnetometer of a cell phone. The most recent data can overwrite the oldest because typically the most recent is most important (ie which way is the phone facing *now*) and then maybe some recent history data (to detect gestures), but the oldest data can be thrown away. Tony
- fail/overwrite/wait on overflow, fail/wait on underflow
is `overwrite' reasonable? and there would be quite a number of options, how to wait: spin, spin-and-yield(), wait for semaphore (it there were a boost.semaphore), wait for condition variable
Yes overwrite is reasonable. Imagine real-time data like the accelerometer/magnetometer of a cell phone. The most recent data can overwrite the oldest because typically the most recent is most important (ie which way is the phone facing *now*) and then maybe some recent history data (to detect gestures), but the oldest data can be thrown away.
ok ... `overwrite' will only reasonably work for the mpmc queue (and there it is more a `node stealing'). the stack implementation has no way to find the oldest element, and the spsc queue (aka ringbuffer) cannot implement it correctly because the produce thread would need to modify the index, which can only be modified from the consumer thread. cheers, tim
Tim Blechmann wrote:
the current names of the data structures are fifo, stack and ringbuffer. during the pre-review some people suggested to use different names, lifo instead of stack or queue instead of fifo. in general i think it is a good idea to use a consistent naming (probably fifo should be renamed to queue), but how does the ringbuffer come in? it is a queue as well, but with different characteristics (spsc and wait-free).
Consistency is good. Internal consistency is better. Either fifo and lifo or queue and stack. Both sets use well understood terms. Given that all three data structures are buffers of sorts, including "buffer" in the name of ringbuffer may be redundant, but it also implies contiguity. "circular_buffer" has been suggested, but if ringbuffer deviates in significant ways -- beyond just being lock-free -- from boost::circular_buffer, then "circular_buffer," while consistent, would be misleading.
data structure configuration: stack and fifo currently use 3 template arguments: T for the managed type, freelist_t as a tag to select the underlying freelist and Alloc as the allocator which is used for the internal nodes:
template<typename T, typename freelist_t = caching_freelist_t, typename Alloc = std::allocator<T> > class fifo/stack;
The template parameters should all start with a capital letter and use CamelCase. Thus, s/freelist_t/FreeList/.
however i have been thinking about replacing it with a boost.parameter interface, something like:
template<typename T, ... Options> class fifo/stack;
with the options:
boost::lockfree::freelist_can_allocate<true/false> to disable memory allocation during enqueue/push
boost::lockfree::allocator<> to specify the allocator
Anyone wanting to specify an allocator will not be put out having to specify the FreeList type, too. Besides, template aliases in C++11 will make capturing specializations easy enough. I don't think Boost.Parameter is warranted for such a trivial case.
ringbuffer size: the ringbuffer currently has the signature:
template<typename T, size_t max_size> class ringbuffer;
if max_size is 0, the size of the ringbuffer can be configured at run-time with a constructor. this is not really the cleanest interface, but i would like to provide an interface, which supports both compile-time and run-time setting of the size.
Perhaps you could provide a tag type which indicates dynamic sizing. Then, move your existing code to a base class, probably in the detail namespace, and provide a derivate that is specialized for non-zero size_t values and your tag type. That is, make a size_t of zero be a compile time error, thereby requiring the tag type for the dynamic allocation case. (The base class would use zero as you now do.) _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On Thu, Jul 21, 2011 at 2:46 AM, Tim Blechmann <tim@klingt.org> wrote:
hi all,
i am starting a new thread, because i want to start a new discussion on one aspect of boost.lockfree: the naming of the data structure and the interface
I hope to look through the documentation and provide some feedback before the end of the review.
naming: the current names of the data structures are fifo, stack and ringbuffer. during the pre-review some people suggested to use different names, lifo instead of stack or queue instead of fifo. in general i think it is a good idea to use a consistent naming (probably fifo should be renamed to queue), but how does the ringbuffer come in? it is a queue as well, but with different characteristics (spsc and wait-free).
Queue, stack, and ring seem fine. data structure configuration:
stack and fifo currently use 3 template arguments: T for the managed type, freelist_t as a tag to select the underlying freelist and Alloc as the allocator which is used for the internal nodes:
template<typename T, typename freelist_t = caching_freelist_t, typename Alloc = std::allocator<T> > class fifo/stack;
however i have been thinking about replacing it with a boost.parameter interface, something like:
template<typename T, ... Options> class fifo/stack;
with the options:
boost::lockfree::freelist_can_allocate<true/false> to disable memory allocation during enqueue/push
boost::lockfree::allocator<> to specify the allocator
Boost.Parameter seems like overkill for just 2 optional parameters. If you have plans for expanding the class of policies one can specify in the future, however... ringbuffer size:
the ringbuffer currently has the signature:
template<typename T, size_t max_size> class ringbuffer;
if max_size is 0, the size of the ringbuffer can be configured at run-time with a constructor. this is not really the cleanest interface, but i would like to provide an interface, which supports both compile-time and run-time setting of the size.
Actually, I think it's reasonably clean, if max_size defaults to 0, so that a dynamic max_size ring is simply ring<T>. - Jeff
hi all, i've modified the interface and uploaded a snapshot of the docs to http://tim.klingt.org/boost_lockfree_wip (_wip for `work in progress', the original documentation is still online)
naming: the current names of the data structures are fifo, stack and ringbuffer. during the pre-review some people suggested to use different names, lifo instead of stack or queue instead of fifo.
i have decided to use the names queue, stack and ringbuffer. i came to the conclusion that `ringbuffer' is probably better than ring or circular_buffer, because there are many implementations of the same algorithm that use this name.
data structure configuration: stack and fifo currently use 3 template arguments: T for the managed type, freelist_t as a tag to select the underlying freelist and Alloc as the allocator which is used for the internal nodes:
both stack and queue now support boost.parameter template arguments: queue<T, ...Options> with the options; template <bool B> freelist_can_allocate<B> template <typename Alloc> allocator<Alloc> maybe there is a better name for `freelist_can_allocate'? something like enqueue_can_allocate_memory_from_os_if_freelist_is_exhausted? maybe a native speaker can suggest a good and expressive name?
ringbuffer size: the ringbuffer currently has the signature:
template<typename T, size_t max_size> class ringbuffer;
if max_size is 0, the size of the ringbuffer can be configured at run-time with a constructor.
i have also used boost.parameter arguments for the ringbuffer: template <size_t element_count> ringbuffer_size<element_count> template <typename Alloc> allocator<Alloc> if ringbuffer_size is given, the size is specified at compile-time and the default constructor must be used. otherwise, the ringbuffer(size_t) constructor must be used. this is ensured via static asserts. the allocator parameter can only be used, if the size is specified at runtime. (again a static assert is used to ensure this). cheers, tim
participants (7)
-
Dave Abrahams -
Gottlob Frege -
Jeffrey Lee Hellrung, Jr. -
Joshua Juran -
Klaim - Joël Lamotte -
Stewart, Robert -
Tim Blechmann