RE: [boost] compact_vector (was optvect)

From: Bill Wade (bill.wade_at_[hidden])
Date: 2000-07-24 08:20:24

> From: tholenst_at_[hidden] [mailto:tholenst_at_[hidden]]
> Greg Colvin writes:

>  > Looking at your performance numbers I had to wonder why your
>  > operator[] was so much faster than the deque you tested, and
>  > why your push_back was so much slower.  Is it fundamental to
>  > the data structures used, or an accident of implementation?
>
> With the operator[], I guess this is a bug in the libstdc++-v3
> implementation.  I don't see a reason why this should be slower in a
> deque.

A fundemental part of a typical deque's [] is division (to find the right
page) and remainder (to find the offset in the page).  For optvec, the
division is replaced by log2().  If the implementation failed to replace the
division with a shift, this might account for the difference (given a fast
log2 implementation).

> The push_back seems logical to me.  A push_back operation in a deque
> is much more easy than in a compact_vector, because compact_vector
> needs to update more information than a deque.

It looks like the expensive operation is updateIndexBlocks().  As written,
your code calls it in every push_back() (via growOne()).  It looks to me as
if you could call updateIndexBlocks() only inside the if() statement in
growOne() (which is rarely entered, especially for large containers).  I'd
expect a significant speedup in this case.  Am I missing something?

Notice that vector::push_back was also slow.  At least one implementation
writes vector::push_back in terms of insert(end()), while the
deque::push_back is optimized to recognize that no existing elements need to
be shifted.