GitHub SG14 library

[Guy Davidson]

As promised...

https://github.com/WG21-SG14/SG14

I have created a GitHub account, WG21-SG14, and a single repository SG14, containing one class, sg14::rolling_queue.  This is a FIFO queue in a fixed-size, non-growing buffer.  Myself and Jonathan Wakely (of RedHat) have reviewed this and I'll work it up into a proposal if there is sufficient support.

Suggest amendements, request contributions, add other classes, everyone go wild.  I haven't added a coding standards document: we have bigger arguments to have, I suspect.

Best wishes,

Guy

[Nicolas Guillemot]

Hi Guy,

Kudos to you and Jonathan for getting the ball rolling!

I have a comment on rolling_queue: What do you think of making the inner Container (currently std::array) a template parameter, in the style of std::priority_queue?

Nicolas

--
You received this message because you are subscribed to the Google Groups "unofficial-real-time-cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-ti...@googlegroups.com.
To post to this group, send email to unofficial-r...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/unofficial-real-time-cxx/91e49274-664c-408d-960e-168055c43961%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Guy Davidson]

Thanks Nicolas.

It's a start.  It's also bedtime over here in the UK.  I'll have a think in the morning, but I intend to add a growing version to the queue as well which caps at a maximum size; this will affect the push function, and I may parameterise that behaviour also; I don't see any reason not to parameterise the container in the style of the queue though.  I'll knock something up by the end of the week.

Cheers,

G

On Wednesday, 10 June 2015 22:09:06 UTC+1, Nicolas Guillemot wrote:

Hi Guy,

Kudos to you and Jonathan for getting the ball rolling!

I have a comment on rolling_queue: What do you think of making the inner Container (currently std::array) a template parameter, in the style of std::priority_queue?

Nicolas

On Wed, Jun 10, 2015 at 1:53 PM, Guy Davidson <elgu...@gmail.com> wrote:

As promised...

https://github.com/WG21-SG14/SG14

I have created a GitHub account, WG21-SG14, and a single repository SG14, containing one class, sg14::rolling_queue.  This is a FIFO queue in a fixed-size, non-growing buffer.  Myself and Jonathan Wakely (of RedHat) have reviewed this and I'll work it up into a proposal if there is sufficient support.

Suggest amendements, request contributions, add other classes, everyone go wild.  I haven't added a coding standards document: we have bigger arguments to have, I suspect.

Best wishes,

Guy

--
You received this message because you are subscribed to the Google Groups "unofficial-real-time-cxx" group.

To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-time-cxx+unsub...@googlegroups.com.

[John McFarlane]

I second having the ability to specify capacity at construction time.

It seems a little odd that you have emplace, yet you are not using placement new. I know it clashes with your choice of container_type but I'd expect that when I create an object of type rolling_queue<T, 10> that there were 0 - and not 10 - instances of T alive. Generally, it feels like this container has std::array-like storage and a std::vector-like interface.

Also, I'm curious what the intended uses of this class would be. I'm afraid I'm not very familiar with ring buffer applications in the industry but I'm guessing inter-thread message buffers - like those used to pass data to render threads - are an intended use case. Is that correct?

If so, would this container be storing pointers to actual data being passed? Or, is the intent to serialize data right onto the buffer - more like stringstream? If the former, then the client needs to manage additional storage outside the container. If the latter, presumably the value type would be something like char and an interface that allows more than element-wise access would be desirable.

I ask because I'm trying to figure out how I'd use this container to underlie the ring buffer container I use for inter-thread communication. I write variable-sized amounts of data to each element to avoid requiring additional storage. So rolling_queue nearly-but-not-quite satisfies my needs.

Cheers,
John

[Guy Davidson]

Hi John, good to hear from you!

On reflection, I think there are two kinds of rolling queue (I am wondering if I prefer the name ring buffer now) required, one over an array and one over a vector.

The advantage of the array version is that there is more opportunity to minimise the requirement for exception handling, since the allocation is known at the point of declaration.  New elements overwrite old elements.  If you know the size in advance and are prepared to keep it at that size then there are optimisations available.

The advantage of a vector version is that it can grow in size (and potentially be capped) in the event of unforeseen circumstances.  Additionally, establishing the size can be deferred to runtime.  However, new elements have to be created in-place first time round and then assigned the second time round.  Also, the noexcept qualifier would be inadmissible on the push function.

I would use a fixed size version when decoding a VP8 video stream: you can fill up address space quite rapidly with frames parking themselves in your queue, as I discovered recently.

There is room for both in the proposal: they are specialisations of the rolling queue concept.  The std::array and std::vector containment stand in contrast to the std::queue which uses a deque or a list, so I think this is a complementary object

Cheers,

G.

[Guy Davidson]

Sorry, I didn't properly answer your questions.  Late night coding, what's become of me...

You are quite right about emplace: there's no need for that in an array implementation.

Yes, inter-thread communications are the application I had in mind; this implementation sprung from a VP8 decoder I wrote for the last Total War game.

I chose to manage fixed size objects, pointers or data.  Writing variable-sized data is beyond the scope of what I was considering and I don't think it suits this approach.  If you have any ideas though I would welcome input to the proposal, however I think you are right in suggesting that storing bytes like stringstream would be the solution, and the rolling_queue would merely form part of your solution.

Cheers,

G

On Thursday, 11 June 2015 20:00:38 UTC+1, John McFarlane wrote:

[John McFarlane]

Thanks Guy.

That all sounds good. I also like ring_buffer. Any of the alternatives on the wikipedia page sound good. It might be worth guaranteeing that actual capacity is at least capacity-1 (and not capacity) in case implementer wishes to forego the count variable. That choice might save memory in case of T=char.

Another advantage of the vector-like implementation is efficient move semantics. Generally I think many would choose the dynamic version as their go-to - even without the advantage of on-demand reallocation. However, I've certainly found situations - averaging FPS values over 30 frames or sampling N ray casts for dynamic obstacle avoidance - where buffer size is small enough to consider keeping it bundled up.

I'm sure what you mean by

new elements have to be created in-place first time round and then assigned the second time round

As with std::vector, raw memory would be allocated and a c'tor called (using placement new) once as emplace or push were called. Then placement delete called inside pop.

I don't have much else to add other than to point to the variable-sized ring_buffer implementation I mentioned. This is a mashup of generic and OO approaches and is not a candidate for standardization. (Not least there's the question of placing a large element in a small space at the end of the buffer.) However, anything that could provide the underlying storage for it would likely be very versatile.

Cheers,
John

[Scott Wardle]

Hey Guy,

 

I like ring or circular buffer as a name myself.   I think I would try and use it like a queue or like an array that could have more or less items.  I'll have to understand deque better to see how difference the performance would be. I can think of a lot of hardware optimization situations where a simpler structure then deque would win like this idea .  GPU communication blocking your data to fit in cache etc...  I just found out that deque does not have a reserve who knew.  It seems like it would be nice to set the page size in deque. How does deque know what type of allocator I will put under it. Also we should look at and understand http://www.boost.org/doc/libs/1_53_0/libs/circular_buffer/doc/circular_buffer.html

 

When I think of the fast as possible version of buffering system between 2 threads here is what I think of.

 

Basically you use a slab allocator to get you new pages. You keep an array of pages between the reader and the writer.  The writer just grabs an empty page from a slab allocator and starts to write objects to it.  The reader pulls pages out once there is at least a full page.  Maybe you could add some flushing system to reduce latency so you could handle partial pages. Humm what would that look like in C++11. A bunch of deque I guess.

 

http://en.wikipedia.org/wiki/Slab_allocation

 

 

Some small points to a generally good idea.

·         I would put the small functions that are often use to the top.  IE increase_back etc... The inliner is likely to do a better job then.

·         If we made a vector version we should work to remove container_type c; I think you only need 2 out of 3 pointers.

·         I think you can get rid of the count with some thought.

·         stl naming of push and pop. Maybe use push_back, pop_front, front in your example.  (I might be wrong here queue has pop and push.  Vector does not... )

 

Anyways I am off to bed.

 

Scott

--

You received this message because you are subscribed to the Google Groups "unofficial-real-time-cxx" group.

To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-ti...@googlegroups.com.

To post to this group, send email to unofficial-r...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/unofficial-real-time-cxx/79b728bf-92b0-4c5b-8a6b-2bfae6cc142c%40googlegroups.com.

[Guy Davidson]

OK, wide awake now.

I think ring_buffer (using std::vector) and fixed_ring_buffer (using std::array) are the names I have landed on.  For the particular application you're describing, that of writing variable length data to the memory, the object sounds like ring_stream would describe it better than ring_buffer.  Perhaps another proposal is needed: interested in collaborating?

The paragraph about creating in-place first time round was a hangover from an earlier design consideration, that push might not fail and you would simply overwrite what was there.  I discarded that idea though.  However, emplace allows you to make the object in-place, rather than making and copying or moving it.  That function should remain.  Nor should it be named emplace_back: there is only one place to add objects.  Therefore push adds existing objects, even rvalues, and emplace creates new objects.

Cheers,

G

[Guy Davidson]

Thanks Scott, that's good stuff.

Skimming through the boost circular buffer, it seems to be rather more heavyweight: it's possibly closer to what John is looking for, and it fulfills many applications, possibly at the cost of being too general.  I will read the documentation more carefully and compare and contrast in my proposal.

I'm now obsessing over the semantic difference between ring and circular.  Perhaps ring is bi-directional and circular is uni-directional...

Cheers,

G

To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-time-cxx+unsub...@googlegroups.com.

[Michael Wong]

+1 Thank you

[Nicolas Guillemot]

Hi Guy,

I have a concern regarding the current rolling_queue implementation: It doesn't seem good for pushing lots of small data.

The uses I have for circular buffers are generally for inter-device communication, and this often comes in the form of small packets.
eg: audio samples, SDL_Event-like structs, networking packets, blocks of files being streamed.

I wouldn't create a rolling_queue to individually push() audio samples, I would rather memcpy a bunch of audio samples into the queue at once (possibly split into two writes to loop around the queue's end.) Therefore, maybe there should be a way to push blocks of data rather than individual units? This could be done by making a push() function that takes two random access iterators. The alternative workaround is to make a rolling_queue<AudioChunk, N> where AudioChunk is struct { size_t numSamples; ushort samples[SOME_DECENT_SIZE]; };

I currently regularly use std::vector in a similar way: I resize the memory to my needs, grab the .data(), then write into it. This saves me the overhead of repeated push_back() calls, which matters a lot in builds with debug iterators where calling push_back on a vector of chars hundreds of thousands of times can take multiple seconds to complete.
One major annoyance of this method is that std::vector pointlessly clears the memory to zero in the initial resize(), even if zero has no meaning for a given use case... but that's a topic for another rant.

Thoughts?

Nicolas

[Guy Davidson]

Thanks Nicolas,

I have been rather ill recently so haven't devoted the time I would like to this, but I will be returning to it shortly. I think your points have merit: I have been considering an additional implementation without a size parameter based on a vector and it seems like pushing multiple objects from another location or container, exploiting SCARYness, would be a trivial-to-implement and useful addition.

Also, why do you use memcpy rather than std::copy?  This falls back to std::memmove for trivially copyable objects, which itself falls back to std::memcpy for non-overlapping ranges.  Or is there a distinct performance advantage, in your particular case, in simply knowing the ranges' relative locations at compile time and avoiding the runtime checks?

I hear what you're saying about ITERATOR_DEBUG_LEVEL: we set it to 0 on the command line and live with it, dealing with third party libraries as appropriate.

Cheers,

G

[Nicolas Guillemot]

>I have been considering an additional implementation without a size parameter based on a vector and it seems like pushing multiple objects from another location or container, exploiting SCARYness, would be a trivial-to-implement and useful addition.

Sweet. I think this capability could be added the fixed length one as well.

It might also be interesting if it was possible to ask for a pair of iterators of distance N that would automatically handle the loop around.

eg: writing 512 samples in `buf` to a circular buffer

auto range = queue.get_range(512);

copy(range.first, range.second, buf); // loops around the end of the circular buffer if necessary

Other suggestions: How about... being able to detect the loop point in a range? or being able to handle out of memory by either overwriting the start of the queue or by dropping the samples?

Kinda just brainstorming at this point. :P

>Also, why do you use memcpy rather than std::copy?

It's a bad habit of mine to refer to any operation that does a copy of a block of memory as 'memcpy' :) sometimes the byte-centric design of memcpy works more naturally than std::copy, but I digress.

--

You received this message because you are subscribed to the Google Groups "unofficial-real-time-cxx" group.

To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-ti...@googlegroups.com.

To post to this group, send email to unofficial-r...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/unofficial-real-time-cxx/0d02dd75-42cd-41ed-8488-b507354b5591%40googlegroups.com.

[Chris Gascoyne]

Hi Guy,

A typical use case that people have mentioned is inter-thread communication. Having a provider thread and a consumer thread.

We have several options when a queue runs out of space...

1) block the push until space becomes available.

2) throw an exception telling the client to create a bigger queue.

3) resize the queue

option 3 looks most flexible but has many pitfalls, especially in the context of inter-thread communication, as the queue access returns items by reference.

If the queue resizes then the item being consumed may be invalidated while in use. It is possible to mitigate this problem by making push and pop mutually exclusive.

Have you considered using "policies" to add thread safety to the queue?

eg 

struct exclusive : std::recursive_mutex 

{

};

struct inclusive 

{ 

   void lock() noexcept() {}

   void unlock() noexcept() {}

};

template <typename T, typename access = inclusive>

class rolling_queue : public access

{

...

};

Pop must "move" the item out of the queue before relinquishing access. Hopefully the return value optimisation would be used here...

value_type pop_front()

{

    std::lock_guard<access>(*this);

    value_type item(std::move(*last_element));

    increase_front();

    return item;

}

Resizing the queue is not necessarily the best choice as it will incur memory allocation and moving memory, and block the pop operation! 

Option 1 of blocking the push operation will hurt performance (depending on how long its blocked) but it is safe. Also increasing the fixed size of the queue will reduce the likelihood of this case occurring. 

This behaviour should be easy to spot when analysing performance. If I was implementing a queue for inter-thread messaging I would probably choose Option 1 for this reason, but it would require the counter to be atomic. 

Adding this thread safe behaviour is also entirely possible using a policy object...

eg

template <std::size_t capacity>

class non_blocking_counter 

{

public:

   non_blocking_counter() : m_count(0) {}

   bool increment() // returns false if at capacity

   void decrement() 

private:

   std::uint32_t m_count;

};

template <std::size_t capacity>

class blocking_counter 

{

public:

   blocking_counter() : m_count(0) {}

   bool increment() // sleeps if at capacity : always returns true!

   void decrement() 

private:

   std::atomic<std::uint32_t> m_count;

};

template <typename T, typename counter = non_blocking_counter>

class rolling_queue : public counter

{

...

};

Lastly, I would probably mimic the interface of std::queue but also adding a max_size accessor function.

Of course this is just how I would approach the problem based on my requirements.

Thanks,

Chris.

[Guy Davidson]

Thanks Chris, good to hear from you.

I do like the idea of using policies to vary the behaviour of the queue: deriving or composing from the policies would offer considerable variety of implementation for clients.  I will revisit this shortly.

Cheers,

G

[John McFarlane]

Hi Assemblers!

I'd be more keen on this idea if inter-thread communication was the sole purpose of this container type. Instead it seems like two concerns are being combined in a way that other STL types avoid doing.

Perhaps we could pursue Nicolas' idea of making one type be a parameter to the other but have a message_queue which can use rolling_queue as it's underlying type the same way std::queue uses std::deque. Then message_queue could expose the parts of rolling_queue's interface necessary to pass messages and have a policy for controlling access. Then maybe rolling_queue could be the fixed-sized solution and deque could be dropped in for the dynamic re-allocation solution.

Alternatively, is there anything in the works to implement a more general-purpose container with the aim of controlling access to a stored object in a thread-safe way - perhaps producing something similar to smart_ptr but with readers-writer lock in place of a reference count?

Cheers,

John

--
You received this message because you are subscribed to a topic in the Google Groups "unofficial-real-time-cxx" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/unofficial-real-time-cxx/sg7wKrxL-AY/unsubscribe.
To unsubscribe from this group and all its topics, send an email to unofficial-real-ti...@googlegroups.com.

To post to this group, send email to unofficial-r...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/unofficial-real-time-cxx/92f1ea31-511e-4719-b5c7-f62380633fcc%40googlegroups.com.

[Matt Newport]

In my opinion it's best to keep a separation between a generic single threaded container type and containers intended to be used in a multithreaded scenario. There are so many different possible ways of building just a multithreaded queue: Single Producer, Single Consumer; Single Producer, Multiple Consumer; MPMC; MPSC; not to mention lock based vs. lock free (with many variations on lock free implementation approaches, wait free queues and more) and they all have pros and cons and are suited to different scenarios. In addition, certain concurrent queue implementations place strict restrictions on the interface that can be provided on the queue beyond what may be desirable for a general purpose single threaded queue.

While you could try and cover the single threaded use cases and all these multithreaded scenarios with a single policy based implementation I think it would rapidly become unwieldy: hard to write, read, maintain, test and debug. 

A standard collection of commonly useful concurrent queue types would be a useful thing to have but I think it should be its own library and would likely need a more restrictive interface than the standard STL containers present.

Matt.

--

You received this message because you are subscribed to the Google Groups "unofficial-real-time-cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-ti...@googlegroups.com.
To post to this group, send email to unofficial-r...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/unofficial-real-time-cxx/ed1ece96-e65c-4dc7-8477-a361abf443a6%40googlegroups.com.