[boost] Interest in Devector implementation?

Subject: [boost] Interest in Devector implementation?
From: christopher hopman (cjhopman_at_[hidden])
Date: 2009-11-28 03:53:59

So, I have been working on a devector implementation for the last week or so
(see https://svn.boost.org/trac/boost/wiki/soc2009#Boost.Devector). There is
some stuff that still needs to be done, and some testing that is still
needed, but I thought I would check if there was interest in such a thing.

The implementation is basically a standard deque implementation with one
addition. That is, there can be allocated "chunks" both before and after
those in use. This leads to a couple of advantages for users.

First, in many use cases, devector is faster than deque because it will have
less allocations. For example, when used strictly as a queue, the regular
deque has a number of chunk allocations linear in the total number of
elements inserted in the queue, devector has allocation linear in the
maximum elements in the deque at one time. When used as a stack, a
particularly bad case can occur with a normal deque implementation, the case
where the top of the stack switches back and forth between two chunks.

Second, this allows users of devector to reserve space on either side of the
structure. This does not give the same efficiency boost as vector::reserve,
but, possibly more important, it allows for stronger exception guarantees
and for better guarantees about when iterators are invalidated.

Another benefit of devector is that chunk size is not a compile time
constant. In fact, chunk size is not even required to be constant over the
lifetime of a given devector. Also, devector iterators allow lower level
access than std::deque as described by Matt Austern (
http://lafstern.org/matt/segmented.pdf).

Support for in-place construction (described at
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2212.html) will
become available with c++0x's emplace_back().

Though I expected that std::deque would have a slight performance advantage
due to its compile-time constant chunk_size, early tests have actually shown
devector to have a slight advantage even in cases where it has no advantage
from not deallocating unused blocks. My guess is that this is due to
std::deque needing to do more work to maintain its invariants in the face of
exceptions. Again though, that is just some simple early testing that I did.

The current implementation does not actually allow changing chunk_size
(though this is actually a matter of like 5 LOC), nor does it give the
segmented iterator access (again a simple addition). Code is available at
http://pages.cs.wisc.edu/~hopman/devector/ (along with code that tests most
of the std::deque interface).

-Chris Hopman