std::deque implementation seems non-optimal for use with std::queue

[Joachim Achtzehnter]

After looking at the implementation some more, it does seem to use a 
circular buffer of sorts, so I was wrong about this point, but there are 
still ongoing heap allocations. These seem to happen because it is 
freeing a node as soon as elements migrate to the next node in the 
circular buffer.

This means I need to slightly adjust my question. If I understand 
correctly, the problem is that the implementation is too eager to free 
its nodes. C++11 has added shrink_to_fit, which was probably intended as 
a way to allow implementations to avoid deallocation, while still 
providing a way to reclaim space, although only by explicit request. The 
standard still doesn't seem to specify enough to guarantee that there 
won't be ongoing allocations even when the contents of a queue remains 
bounded.

Are there any plans to change the current behaviour?

Thanks,

Joachim


On 2014/01/21 17:29, Joachim Achtzehnter wrote:
> With std::deque being the default implementation of std::queue it would
> be useful if the implementation was optimized for repeated push at one
> end and pop at the opposite end.
>
> For example, if such a queue was kept at approximately constant size one
> would hope to avoid further heap allocations once a certain amount of
> allocations have occurred. If the array of pointers to blocks was
> managed as a circular buffer it would not be necessary to perform any
> further heap allocations once all blocks are allocated.
>
> The libstdc++ implementation of std::deque does not seem to work this
> way (at least in v4.7.3). A program that repeatedly pushes and pops, for
> example with always either 1 or 2 elements contained in the queue, seems
> to encounter repeated allocations and deallocations from the underlying
> std::deque.
>
> I've seen another implementation of std::deque, which does use a
> circular buffer. With this implementation a std::queue whose size
> remains limited does run without further heap allocations once the
> elements have cycled around the circular buffer once.
>
> Are there significant drawbacks to the circular buffer approach that
> argue against its use for std::deque? Or would this be a worthwhile
> improvement to consider?
>
> Thanks,
>
> Joachim
>

-- 
joachima@netacquire.com http://www.netacquire.com