RE: [boost] compact_vector (was optvect)

From: Thomas Holenstein (tholenst_at_[hidden])
Date: 2000-07-24 14:18:25

Bill Wade writes:
 > >  > Looking at your performance numbers I had to wonder why your
 > >  > operator[] was so much faster than the deque you.

 > 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).

I think you could be right.  Someday I might take a look at it.

 > > 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?

Not much.  updateIndexBlocks certainly belongs into the if statement.
Thank you very much.  Howevery, it probably won't help in this case,
because updateIndexBlocks is a nop if constant_time is false.

I changed it now, thank you.

 > Your documentation should probably indicate that compact_vector::swap
 > (unlike vector::swap) invalidates iterators.  Alternatively you could add a
 > layer of indirection (small constant time and space penalties) and have
 > swap() preserve iterators.
 >
 > I don't believe I've ever written code that counted on vector::swap
 > preserving iterators.  I suspect that such code is uncommon.

Uuuh, thats evil.  Actually, this one got me (when I implemented swap,
because the endIter was invalidated).  I didn't notice it anyhow :-( 
I will document this flaw.  I don't think anyone uses this feature.  If
someone thinks he really needs it I might implement it.

Thank you very much!

Thomas