[rfc] lockfree API/naming suggestions
hi all, i am preparing boost.lockfree so that it can be merged to trunk. however i'd request some suggestions, concerning interface and names: ringbuffer naming: there is a fixed-sized single-producer/single-consumer wait-free queue, which is implemented as ringbuffer. the linux kernel uses the name `kfifo', the jack-audio-connection-kit refers to it as `ringbuffer', herlihy/shavit discuss it under the name `BoundedQueue'. the boost.lockfree implementation is currently named `ringbuffer', but i could rename it before merging it into trunk. suggestions: ringbuffer waitfree_queue spsc_queue bounded_queue personally i'd be in favor of `ringbuffer' (because i have been using this name for years) or `spsc_queue' (because it makes clear that it doesn't support multiple produces/consumers). but i'd be curious, what other people suggest. fifo/queue bounded push: fifo and queue can be configured to use a dynamically growing freelist for memory management. in this case, the `push' operations may block if the freelist is exhausted and a new node has to be allocated from the OS. currently this can be avoided by a per-class policy. however it would be reasonable to move this policy from a per-class to a per- call policy. so instead of: queue<T, boost::lockfree::bounded<true> > q; T t; q.push(t); one could write: queue<T> q; T t; q.push_nonblocking(t); however this would imply 3 flavors of `push' * push, which may block during memory allocation * push_unsafe, which is not thread-safe (but faster) * push_nonblocking, which is guaranteed not to hit the memory allocator. so i am not sure, whether this introduces too much complexity into the API. any thoughts/comments? thanks, tim
on Tue Nov 15 2011, Tim Blechmann <tim-AT-klingt.org> wrote:
hi all,
i am preparing boost.lockfree so that it can be merged to trunk. however i'd request some suggestions, concerning interface and names:
ringbuffer naming:
there is a fixed-sized single-producer/single-consumer wait-free queue, which is implemented as ringbuffer. the linux kernel uses the name `kfifo', the jack-audio-connection-kit refers to it as `ringbuffer', herlihy/shavit discuss it under the name `BoundedQueue'. the boost.lockfree implementation is currently named `ringbuffer', but i could rename it before merging it into trunk. suggestions:
ringbuffer waitfree_queue spsc_queue bounded_queue
personally i'd be in favor of `ringbuffer' (because i have been using this name for years) or `spsc_queue' (because it makes clear that it doesn't support multiple produces/consumers). but i'd be curious, what other people suggest.
Well, "pipe" kind of captures the idea that it has limited capacity and goes from here to there. But it's probably better to go with bounded_queue if that's accepted terminology.
fifo/queue bounded push:
fifo and queue can be configured to use a dynamically growing freelist for memory management. in this case, the `push' operations may block if the freelist is exhausted and a new node has to be allocated from the OS. currently this can be avoided by a per-class policy. however it would be reasonable to move this policy from a per-class to a per- call policy.
so instead of: queue<T, boost::lockfree::bounded<true> > q; T t; q.push(t);
one could write: queue<T> q; T t; q.push_nonblocking(t);
however this would imply 3 flavors of `push' * push, which may block during memory allocation * push_unsafe, which is not thread-safe (but faster) * push_nonblocking, which is guaranteed not to hit the memory allocator.
so i am not sure, whether this introduces too much complexity into the API.
Under those names, I would say, "yech." is this a single-producer or multiple-producer queue we're talking about? If single, it seems meaningless to say a push operation is not thread-safe. If multiple, "not thread-safe" would indicate to me that it's being used in a single-producer mode. And what are the thread-safety characteristics of push_nonblocking? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
hello dave,
there is a fixed-sized single-producer/single-consumer wait-free queue, which is implemented as ringbuffer. the linux kernel uses the name `kfifo', the jack-audio-connection-kit refers to it as `ringbuffer', herlihy/shavit discuss it under the name `BoundedQueue'. the boost.lockfree implementation is currently named `ringbuffer', but i could rename it before merging it into trunk. suggestions:
ringbuffer waitfree_queue spsc_queue bounded_queue
personally i'd be in favor of `ringbuffer' (because i have been using this name for years) or `spsc_queue' (because it makes clear that it doesn't support multiple produces/consumers). but i'd be curious, what other people suggest.
Well, "pipe" kind of captures the idea that it has limited capacity and goes from here to there. But it's probably better to go with bounded_queue if that's accepted terminology.
well, the mpmc queue of boost.lockfree can also be configured as bounded. so this name is also a bit misleading
however this would imply 3 flavors of `push' * push, which may block during memory allocation * push_unsafe, which is not thread-safe (but faster) * push_nonblocking, which is guaranteed not to hit the memory allocator.
so i am not sure, whether this introduces too much complexity into the API.
Under those names, I would say, "yech." is this a single-producer or multiple-producer queue we're talking about?
spsc would have push and push_unsafe, mpmc an additional push_nonblocking.
If single, it seems meaningless to say a push operation is not thread-safe. If multiple, "not thread-safe" would indicate to me that it's being used in a single-producer mode.
not quite: push_unsafe does not have to use any atomic operations. so it can be more efficient to use this method, when the program logic guarantees that no other thread currently accesses the data structure.
And what are the thread-safety characteristics of push_nonblocking?
push_nonblocking has the same safety guarantees as push. however it also gives stronger guarantees concerning the real-time safety: push may block, if an internal node needs to be allocated, while push_nonblocking would simply fail. it is reasonable to have two different methods for that, because the same data structure may be accessed by threads with different real-time constraints. cheers, tim
on Tue Nov 29 2011, Tim Blechmann <tim-AT-klingt.org> wrote:
hello dave,
however this would imply 3 flavors of `push' * push, which may block during memory allocation * push_unsafe, which is not thread-safe (but faster) * push_nonblocking, which is guaranteed not to hit the memory allocator.
so i am not sure, whether this introduces too much complexity into the API.
Under those names, I would say, "yech." is this a single-producer or multiple-producer queue we're talking about?
spsc would have push and push_unsafe, mpmc an additional push_nonblocking.
If single, it seems meaningless to say a push operation is not thread-safe. If multiple, "not thread-safe" would indicate to me that it's being used in a single-producer mode.
not quite: push_unsafe does not have to use any atomic operations. so it can be more efficient to use this method, when the program logic guarantees that no other thread currently accesses the data structure.
And what are the thread-safety characteristics of push_nonblocking?
push_nonblocking has the same safety guarantees as push. however it also gives stronger guarantees concerning the real-time safety: push may block, if an internal node needs to be allocated, while push_nonblocking would simply fail.
it is reasonable to have two different methods for that, because the same data structure may be accessed by threads with different real-time constraints.
If it were me, I wouldn't label anything "unsafe," since presumably even the push you're calling unsafe is as threadsafe as int, and it seems like the right prefix for the nonblocking one is "try_". I might use ("push", "atomic_push," "try_push") or if the use of the single-threaded version is rare enough, ("single_thread_push"/"serial_push", "push", "try_push"). Just some thoughts; hope they help. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Tim Blechmann-2 wrote
hi all,
i am preparing boost.lockfree so that it can be merged to trunk. however i'd request some suggestions, concerning interface and names:
ringbuffer naming:
there is a fixed-sized single-producer/single-consumer wait-free queue, which is implemented as ringbuffer. the linux kernel uses the name `kfifo', the jack-audio-connection-kit refers to it as `ringbuffer', herlihy/shavit discuss it under the name `BoundedQueue'. the boost.lockfree implementation is currently named `ringbuffer', but i could rename it before merging it into trunk. suggestions:
ringbuffer waitfree_queue spsc_queue bounded_queue
personally i'd be in favor of `ringbuffer' (because i have been using this name for years) or `spsc_queue' (because it makes clear that it doesn't support multiple produces/consumers). but i'd be curious, what other people suggest.
I think that the type must contains whether it is safe to produce/consume from multiple threads. I will use the prefixes: spsc_, spmc_, mpsc_ and mpmc_. bounded and ring mean different things for me. A bounded queue will block when there is no more free space. A ring will override the first element of the queue when there is no more space. I don't know which is the semantics of the operations you are providing, but I gues that your implementing a bounded queue, so xxxx_bounded_queue should be ok. fifo/queue bounded push: fifo and queue can be configured to use a dynamically growing freelist for memory management. in this case, the `push' operations may block if the freelist is exhausted and a new node has to be allocated from the OS. currently this can be avoided by a per-class policy. however it would be reasonable to move this policy from a per-class to a per- call policy. so instead of: queue<T, boost::lockfree::bounded<true> > q; T t; q.push(t); one could write: queue<T> q; T t; q.push_nonblocking(t); I agree that the policy could be on the operation. however this would imply 3 flavors of `push' * push, which may block during memory allocation * push_unsafe, which is not thread-safe (but faster) * push_nonblocking, which is guaranteed not to hit the memory allocator. so i am not sure, whether this introduces too much complexity into the API. IMO, the push should corresponds to the expected behavior. As these queues are in a lockfree library, I would expect that the push is thread safe. I agree with Dave that try_ is a better name for a non blocking operation. I don't know in which cases the application can be sure that there is no thread safe issues, but in any case, the interface should be enough ugly to make it more difficult to use, as it is unsafe. thread_unsafe_push seems quite ugly, isn't it? ;-) Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/rfc-lockfree-API-naming-suggestions-tp404... Sent from the Boost - Dev mailing list archive at Nabble.com.
hi vincente & dave,
personally i'd be in favor of `ringbuffer' (because i have been using this name for years) or `spsc_queue' (because it makes clear that it doesn't support multiple produces/consumers). but i'd be curious, what other people suggest.
I think that the type must contains whether it is safe to produce/consume from multiple threads. I will use the prefixes: spsc_, spmc_, mpsc_ and mpmc_.
bounded and ring mean different things for me. A bounded queue will block when there is no more free space. A ring will override the first element of the queue when there is no more space.
i'll try to avoid the term `bounded' and `ring' then, as they seem to have different conotations. spsc_queue and queue should be the best names then. vincente:
however this would imply 3 flavors of `push' * push, which may block during memory allocation * push_unsafe, which is not thread-safe (but faster) * push_nonblocking, which is guaranteed not to hit the memory allocator.
so i am not sure, whether this introduces too much complexity into the API.
IMO, the push should corresponds to the expected behavior. As these queues are in a lockfree library, I would expect that the push is thread safe. I agree with Dave that try_ is a better name for a non blocking operation.
I don't know in which cases the application can be sure that there is no thread safe issues, but in any case, the interface should be enough ugly to make it more difficult to use, as it is unsafe. thread_unsafe_push seems quite ugly, isn't it? ;-)
dave:
If it were me, I wouldn't label anything "unsafe," since presumably even the push you're calling unsafe is as threadsafe as int, and it seems like the right prefix for the nonblocking one is "try_". I might use ("push", "atomic_push," "try_push") or if the use of the single-threaded version is rare enough, ("single_thread_push"/"serial_push", "push", "try_push").
"atomic" does have some a different meaning then what is implemented (afaict, `linearizable' would be the correct term). i'd like to avoid the name "try_", because all push operations may actually fail. "push" and "push_unsafe" can fail if ringbuffer (aka spsc_queue) space is exhausted or memory allocation fails (queue/stack). "push_nonblocking" may fail, if the internal memory pool is exhausted. "single_thread_push" might cause some misunderstanding, as people may think that it is about a `single producer', not about a `single-threaded use'. so it is really a "thread_unsafe_push", as incorrect use may corrupt the internal data structure. so maybe "thread_unsafe_push", "nonblocking_push" and "push"? thanks, tim
On Tue, Nov 29, 2011 at 5:39 PM, Tim Blechmann <tim@klingt.org> wrote:
dave:
If it were me, I wouldn't label anything "unsafe," since presumably even the push you're calling unsafe is as threadsafe as int, and it seems like the right prefix for the nonblocking one is "try_". I might use ("push", "atomic_push," "try_push") or if the use of the single-threaded version is rare enough, ("single_thread_push"/"serial_push", "push", "try_push").
"atomic" does have some a different meaning then what is implemented (afaict, `linearizable' would be the correct term).
i'd like to avoid the name "try_", because all push operations may actually fail. "push" and "push_unsafe" can fail if ringbuffer (aka spsc_queue) space is exhausted or memory allocation fails (queue/stack). "push_nonblocking" may fail, if the internal memory pool is exhausted.
"single_thread_push" might cause some misunderstanding, as people may think that it is about a `single producer', not about a `single-threaded use'. so it is really a "thread_unsafe_push", as incorrect use may corrupt the internal data structure.
so maybe "thread_unsafe_push", "nonblocking_push" and "push"?
if there is resistance for unsafe_push, I propose push_unsynchronized (or unsynchronized_push). -- gpd
"single_thread_push" might cause some misunderstanding, as people may think that it is about a `single producer', not about a `single-threaded use'. so it is really a "thread_unsafe_push", as incorrect use may corrupt the internal data structure.
so maybe "thread_unsafe_push", "nonblocking_push" and "push"?
if there is resistance for unsafe_push, I propose push_unsynchronized (or unsynchronized_push).
very good idea! unsynchronized is much more expressive than unsafe. thanks, tim
Tim Blechmann wrote:
"single_thread_push" might cause some misunderstanding, as people may think that it is about a `single producer', not about a `single-threaded use'. so it is really a "thread_unsafe_push", as incorrect use may corrupt the internal data structure.
so maybe "thread_unsafe_push", "nonblocking_push" and "push"?
if there is resistance for unsafe_push, I propose push_unsynchronized (or unsynchronized_push).
very good idea! unsynchronized is much more expressive than unsafe.
I use "noncompeting" (such ops need neither atomicity nor synchronization; multiple noncompeting immutable ops may run concurrently; it basically expresses "thread-safe as an int"). regards, alexander.
participants (5)
-
Alexander Terekhov -
Dave Abrahams -
Giovanni Piero Deretta -
Tim Blechmann -
Vicente Botet