Re: [boost] [rfc] lockfree API/naming suggestions

Subject: Re: [boost] [rfc] lockfree API/naming suggestions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-11-29 05:04:30

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