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