Which STL container should I use for a FIFO?

Question

Which STL container would fit my needs best? I basically have a 10 elements wide container in which I continually push_back new elements while pop_front ing the oldest element (about a million time).

I am currently using a std::deque for the task but was wondering if a std::list would be more efficient since I wouldn't need to reallocate itself (or maybe I'm mistaking a std::deque for a std::vector?). Or is there an even more efficient container for my need?

P.S. I don't need random access

Dislike

Why not try it with both and time it to see which one is faster for your need ? – Arrogant

I was about to do this, but I was looking for a theoretical answer as well. – Dislike

the std::deque won't reallocate. It's a hybrid of a std::list and a std::vector where it allocates larger chunks than a std::list but won't reallocate like a std::vector. – Interlining

Thanks Matt, that was one of my biggest concern with a deque! – Dislike

std::deque is a double-ended queue implemented using a mutable array. It does reallocate. – Irremeable

No, here is the relevant guarantee from the standard: "Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to the copy constructor of T." – Interlining

@John: No, it allocates again. Maybe we're just mixing up terms. I think reallocate means to take the old allocation, copy it into a new allocation, and discard the old one. – Invaluable

std::deque won't reallocate, but it does allocate new blocks periodically on push_back, as the previously allocated block gets used up. This makes it more efficient than vector, since nothing ever moves from an old block to a new one. Also more efficient than a list, which does an allocation on each push_back. – Summersummerhouse

Reading the comments here is like watching a train wreck. – Claudeclaudel

Well I accepted his answer mostly for the ring buffer part. I have to agree though that the std::list doesn't seem like the best idea and thus doesn't make the answer very good. But still. – Dislike

Answer 1

Since there are a myriad of answers, you might be confused, but to summarize:

Use a std::queue. The reason for this is simple: it is a FIFO structure. You want FIFO, you use a std::queue.

It makes your intent clear to anybody else, and even yourself. A std::list or std::deque does not. A list can insert and remove anywhere, which is not what a FIFO structure is suppose to do, and a deque can add and remove from either end, which is also something a FIFO structure cannot do.

This is why you should use a queue.

Now, you asked about performance. Firstly, always remember this important rule of thumb: Good code first, performance last.

The reason for this is simple: people who strive for performance before cleanliness and elegance almost always finish last. Their code becomes a slop of mush, because they've abandoned all that is good in order to really get nothing out of it.

By writing good, readable code first, most of you performance problems will solve themselves. And if later you find your performance is lacking, it's now easy to add a profiler to your nice, clean code, and find out where the problem is.

That all said, std::queue is only an adapter. It provides the safe interface, but uses a different container on the inside. You can choose this underlying container, and this allows a good deal of flexibility.

So, which underlying container should you use? We know that std::list and std::deque both provide the necessary functions (push_back(), pop_front(), and front()), so how do we decide?

First, understand that allocating (and deallocating) memory is not a quick thing to do, generally, because it involves going out to the OS and asking it to do something. A list has to allocate memory every single time something is added, and deallocate it when it goes away.

A deque, on the other hand, allocates in chunks. It will allocate less often than a list. Think of it as a list, but each memory chunk can hold multiple nodes. (Of course, I'd suggest that you really learn how it works.)

So, with that alone a deque should perform better, because it doesn't deal with memory as often. Mixed with the fact you're handling data of constant size, it probably won't have to allocate after the first pass through the data, whereas a list will be constantly allocating and deallocating.

A second thing to understand is cache performance. Going out to RAM is slow, so when the CPU really needs to, it makes the best out of this time by taking a chunk of memory back with it, into cache. Because a deque allocates in memory chunks, it's likely that accessing an element in this container will cause the CPU to bring back the rest of the container as well. Now any further accesses to the deque will be speedy, because the data is in cache.

This is unlike a list, where the data is allocated one at a time. This means that data could be spread out all over the place in memory, and cache performance will be bad.

So, considering that, a deque should be a better choice. This is why it is the default container when using a queue. That all said, this is still only a (very) educated guess: you'll have to profile this code, using a deque in one test and list in the other to really know for certain.

But remember: get the code working with a clean interface, then worry about performance.

John raises the concern that wrapping a list or deque will cause a performance decrease. Once again, he nor I can say for certain without profiling it ourselves, but chances are that the compiler will inline the calls that the queue makes. That is, when you say queue.push(), it will really just say queue.container.push_back(), skipping the function call completely.

Once again, this is only an educated guess, but using a queue will not degrade performance, when compared to using the underlying container raw. Like I've said before, use the queue, because it's clean, easy to use, and safe, and if it really becomes a problem profile and test.

Invaluable

+1 - and if it turns out that boost::circular_buffer<> has the best performance, then just use that as the underlying container (it also provides the required push_back(), pop_front(), front(), and back()). – Begot

Accepted for explaining it in details (which is what I needed, thanks for taking the time). As for the good code first performance last, I have to admit that's one of my biggest default, I always try to do thing perfectly on first run... I did write the code using a deque first tough, but since the thing wasn't performing as well as I thought (it is supposed to be almost real-time), I guessed I should improve it a bit. As Neil also said, I really should have used a profiler though... Although I'm happy to have made these mistakes now while it doesn't really matter. Thanks a lot all of you. – Dislike

-1 for not solving the problem and bloated useless answer. Right answer here is short and it is boost::circular_buffer<>. – Archetype

"Good code first, performance last", that's an awesome quote. If only everyone understood this :) – Brill

I appreciate the stress on profiling. Providing a rule of thumb is one thing and then proving it with profiling is a better thing – Onset

Answer 2

Check out std::queue. It wraps an underlying container type, and the default container is std::deque.

Summersummerhouse

I doubt wrapping a deque with a queue will have better performance characteristics than just using a deque. – Irremeable

Do you think it'll have worse, then? The point is that a queue is the FIFO structure to use in C++. It provides the correct interface, and let's you choose which container it adapts to, so if list ends up being better, it's as simple as saying "use a list", and no other code changes. [cplusplus.com/reference/stl/queue/] – Invaluable

The point I meant to make with my first question was: you don't know. You can guess, but it's unlikely you'll see any performance difference. Inlining will remove the "shell", so it's like using a list, deque or whatever, performance-wise, but there is in fact that "shell" making sure you use the structure correctly. – Invaluable

std::queue is merely a thin wrapper around an underlying data type, which hides some unneeded operations. It's useful in some circumstances, but if performance is a priority then every extra layer should be eliminated. – Irremeable

Every extra layer will be eliminated by the compiler. By your logic, we should all just program in assembly, since the language is just a shell that gets in the way. The point is to use the correct type for the job. And queue is that type. Good code first, performance later. Hell, most performance comes out of using good code in the first place. – Invaluable

And to add on to that, a deque will probably have better cache performance, because those 10 items will probably fit into one allocation. – Invaluable

Sorry to be vague - my point was that a queue is exactly what the question was asking for, and the C++ designers thought deque was a good underlying container for this use case. – Summersummerhouse

"Good code first, performance later" -- obviously, the OP has already written a solution using deque, and found its performance lacking (hence, this question). Using a ring buffer is an appropriate solution. – Irremeable

There's nothing in this question to indicate that he found performance lacking. Many beginners are constantly asking about the most effiicent solution to any given problem, regardless of whether their current solution performs acceptably or not. – Storax

@John, if he found the performance lacking, stripping away the shell of safety queue provides wouldn't increase performance, like I've been saying. You suggested a list, which will probably perform worse. – Invaluable

@Storax If he had not encountered a performance issue, he would not have asked the question. @GMan I suggested a ring buffer. – Irremeable

That's true, but it's not what we're arguing. You said "std::list would be the best STL container -- doubly-linked lists are a textbook solution to your problem." Which is false. – Invaluable

How is it false? A list is the most obvious solution, and therefore, the best. If performance is an issue, he should use a circular queue. – Irremeable

Did you read my answer? A deque is a better choice in every way. And what does "obvious" mean and what good do you think is going to come out of using such a subjective word in an argument? I think a list and deque are equally "obvious" choices, so then I say, "well, deque has better allocation and cache performance". I think that makes deque the "obvious" choice. "Obvious is best' in itself is not sound. Newton's law of gravity was "obvious", now look at it. – Invaluable

The thing about std::queue<> is that if deque<> isn't what you want (for perfomance or whatever reason), it's a one-liner to change it to use a std::list as the backing store - as GMan said way back. And if you really want to use a ring buffer instead of a list, boost::circular_buffer<> will drop right in... std::queue<> is almost definitely the 'interface' that should be used. The backing store for it can be changed pretty much at will. – Begot

@Invaluable Seems like some comments must have gotten removed, so I'm not sure who said "doubly-linked lists are a textbook solution to your problem". In any case, isn't a singly linked list the textbook answer to this problem? This seems to suggest that both std::deque and std::list are unnecessarily bloated for use as an std::queue implementation, which I don't find very confidence-inspiring. – Selfannihilation

@DonHatch it wasn't a comment that was deleted, it was a whole answer - deleted by the author. Yes, a singly linked list would work well, but the standard library doesn't provide one - std::list is doubly linked. You could write your own of course, but if you're going to that much trouble there are probably better data structures to use. I wouldn't say that std::deque or std::list are unnecessarily bloated, just that they have capabilities that are going to go unused for this application. – Summersummerhouse

@MarkRansom "I wouldn't say that std::deque or std::list are unnecessarily bloated, just that they have capabilities that are going to go unused for this application. " Don't they have to store twice as many pointers as is needed for the FIFO functionality? So that seems to imply memory bloat. – Selfannihilation

@DonHatch OK, std::list is overly bloated for this application. But I think if you dig into the implementation of std::deque you won't find a similar problem. – Summersummerhouse

Answer 3

Where performance really matters, check out the Boost circular buffer library.

Interclavicle

Answer 4

I continually push_back new elements while pop_front ing the oldest element (about a million time).

A million is really not a big number in computing. As others have suggested, use a std::queue as your first solution. In the unlikely event of it being too slow, identify the bottleneck using a profiler (do not guess!) and re-implement using a different container with the same interface.

Prologize

Well the thing is, it is a big number as what I want to do is supposed to be real time. Although you are right that I should have used a profiler to identify the cause... – Dislike

The thing is, I'm not really used to using a profiler (we've used gprof a bit in one of our classes but we really didn't go in depth...). If you could point me to some ressources, I would greatly appreciate! PS. I use VS2008 – Dislike

@Gab: Which VS2008 do you have (Express, Pro...)? Some come with a profiler. – Helpless

@Gab Sorry, I don't use VS any more so can't really advise – Prologize

@Sbi, from what I'm seeing, it's only in the team system edition (which I have access to). I'll look into this. – Dislike

Answer 5

Why not std::queue? All it has is push_back and pop_front.

Methodize

Answer 6

A queue is probably a simpler interface than a deque but for such a small list, the difference in performance is probably negligible.

Same goes for list. It's just down to a choice of what API you want.

Cult

But I was wondering if the constant push_back were making the queue or deque reallocate themselves – Dislike

std::queue is a wrapper around another container, so a queue wrapping a deque would be less efficient than a raw deque. – Irremeable

For 10 items, performance is most likely going to be such a tiny issue, that "efficiency" might better be measured in programmer-time than code-time. And the calls from queue to deque by any decent compiler optimizations would be down to nothing. – Cult

@John: I'd like you to show me a set of benchmarks demonstrating such a performance difference. It is no less efficient than a raw deque. C++ compilers inline very aggressively. – Storax

I've tried it. :D A quick & dirty 10 elements container with 100,000,000 pop_front() & push_back() rand() int numbers on Release build for speed on VC9 gives : list(27), queue(6), deque(6), array(8). – Arrogant

Answer 7

Use a std::queue, but be cognizant of the performance tradeoffs of the two standard Container classes.

By default, std::queue is an adapter on top of std::deque. Typically, that'll give good performance where you have a small number of queues containing a large number of entries, which is arguably the common case.

However, don't be blind to the implementation of std::deque. Specifically:

"...deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++)."

To net that out, presuming that a queue entry is something that you'd want to queue, i.e., reasonably small in size, then if you have 4 queues, each containing 30,000 entries, the std::deque implementation will be the option of choice. Conversely, if you have 30,000 queues, each containing 4 entries, then more than likely the std::list implementation will be optimal, as you'll never amortize the std::deque overhead in that scenario.

You'll read a lot of opinions about how cache is king, how Stroustrup hates linked lists, etc., and all of that is true, under certain conditions. Just don't accept it on blind faith, because in our second scenario there, it's quite unlikely that the default std::deque implementation will perform. Evaluate your usage and measure.

Thriller

Answer 8

This case is simple enough that you can just write your own. Here is something that works well for micro-conroller situations where STL use takes too much space. It is nice way to pass data and signal from interrupt handler to your main loop.

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};

Kayo

But how/when would that ever happen? – Kayo

Oh, I thought it could for some reason. Never mind! – Monkery