Data structures for real time applications

OneSecVoice/Image objects will contain a total number of packets, packets buffer for that particular Image/OneSecVoice .

As its a real time one thread will continuously scan for queue and take out latest complete Image/OneSecVoice by popping the Image/OneSecVoice from queue.

So which to chose Implementing a queue using a linked list or Implementing a queue using static array.

Me and my friend are having fight over this so we decided to post here.

asked Oct 11, 2009 at 18:14 30.3k 34 34 gold badges 122 122 silver badges 166 166 bronze badges

4 Answers 4

I would use boost::circular_buffer. You will get the cache benefits having a fixed memory area and no unexpected memory allocations.

Use of fixed memory and no implicit or unexpected memory allocation.
Fast constant-time insertion and removal of elements from the front and back.
Fast constant-time random access of elements.
Suitability for real-time and performance critical applications.

Storage of the most recently received samples, overwriting the oldest as new samples arrive.
As an underlying container for a bounded buffer (see the Bounded Buffer Example).
A kind of cache storing a specified number of last inserted elements.
Efficient fixed capacity FIFO (First In, First Out) or LIFO (Last In, First Out) queue which removes the oldest (inserted as first) elements when full.

answered Oct 11, 2009 at 18:46 Fernando N. Fernando N. 6,449 4 4 gold badges 28 28 silver badges 30 30 bronze badges

The cache benefits are going to be negligible, assuming his data structure is at least as big as a cache line. Since each element is going to be popped off and processed once, and then overwritten, the cache isn't going to help much.

Commented Oct 12, 2009 at 4:23 @xinus, you should be very careful with unnecessary copies. Commented Oct 12, 2009 at 10:03

Don't implement either. Use pre-existing implementations in the standard library:

std::queue > std::queue > // uses deque by default, by the way

You can typedef these to make swapping the two very easy:

template struct queue_list < typedef typename std::queue> value_type; > template struct queue_array < typedef typename std::queue> value_type; > typedef queue_list::value_type container_type; // use one typedef queue_array::value_type container_type;

Now profile and find which is better. Likely the array will have better performance, for cache.

You can use boost's pool allocator to try to get the benefit of a list's quick insertion and removal, along with an array's cache performance:

typedef typename std::queue > > value_type;

template struct queue_buffer < typedef typename std::queue> value_type; >

1 1 1 silver badge answered Oct 11, 2009 at 18:30 502k 53 53 gold badges 502 502 silver badges 549 549 bronze badges

If the only operation on the receiving side is to pop off of the queue, I don't really see the point of using a static array, which would generally be useful if you needed to operate on chunks of continuous data or for random access.

I don't think you're going to get any space savings from using a static array. Sure, you're saving a pointer per entry, but at the cost of allocating a large fixed block of memory. And if your queue is going to get that large sometimes, then maybe you need the flexibility afforded by a linked list, since it can grow to an arbitrary size.

If you want to limit the size it can grow to, you can do that in either scheme.