Re: About std::vector::resize().

[Dhruv Matani <dhruvbird at gmx dot net>]

On Sat, 2004-05-29 at 04:52, Carlo Wood wrote:
> On Sat, May 29, 2004 at 12:00:34AM +0530, Dhruv Matani wrote:
> > > Ah, you want to specialize it.  
> > > But why not do this very every vector?
> > 
> > What do you mean by the above sentence? I can not understand it?
> 
> s/very/for/
> 
> Thus, not only vector<vector<Foo> >, but every vector: vector<FooBar>.
> 
> [...]
> > However, letting the user not specialize std::swap has 2 advantages:
> > 
> > 1. He/she does not have to if they do not. Meaning that their swap
> > specializations may do something different if they wish, and not perform
> > a fast swap.
> > 
> > 2. Automatic checking for the library implementors. This way, if there
> > is a bogus swap function(not specialized), then the compiler will
> > complain of the missing member swap function. In the scenario, when we
> > ask the user to overload swap, then if he/she does not, then the vector
> > will still compile, but with a worse performance than the normal case.
> 
> I don't understand this.
> "not letting the user specialize std::swap" means, from previous context,
> that you implement __uninitialized_copy_swap by calling a member swap
> function - which imho you can only do when __uninitialized_copy_swap is
> specialized for an element type that we control, and thus only vector,
> list, map etc.

Yes.

>   And then, well - the user is out of the picture again.

Not exactly.

> Otherwise (if you don't specialize) you get errors like: Foo has no
> member function called swap.

Yes. exactly. This is done to prevent happenings wherein the user *does
not* specialize std::swap, and the generic assignment version is used,
where the performance will obviously be dampened further.

>   Obviously you cannot demand that a user
> type 'Foo' has a swap member function when the user wants to use
> vector<Foo>.

No, but if the user wants to take advantage of the internal swapping
algorithm, he/she must provide a member swap function for his/her
class/struct. So, as an added advantage, PODs will *never* make use of
the specialized swapping algorithm.

> > > If you go for specializing __uninitialized_copy_swap for only our
> > > own vector, then note that there is no need to call a constructor
> > > at all (or swap).  You can just move the three members of the
> > > vector over and dealloc the old space, in fact - the fastest
> > > would be to just memcpy the old vector to its new allocation.
> > 
> > That's morally incorrect according to the standard gurus ;-) My
> > imaginary conscious pinches when I do that!
> > 
> > > No need for default constructors and swap members :/
> > 
> > Actually there is a need:
> > 
> > 1. What about list, map, multimap, etc... We would have to use the swap
> > members for them.
> > BTW, do you know why list's swap is sooo... complicated. A few months
> > ago, it was just a swap of the internal pointer.
> 
> But you spoke about specialization.  Then, when specializing for vector<vector<..> >
> it is correct.  So much for me being able to trust (standard) libraries
> being optimal implemented :/.  The memcpy would work and be a LOT faster,
> not just 20% - but a significant factor.

Yes, but this patch is supposed to work not only for vector<vector<> >
but also for vector<any_STL_container>. Now, for list, map, etc... we
can not use good ol. memcpy!

However, more specialization would just obfuscate the code further, and
the performance gains would not be enough to justify that complexity.
But, then again, I haven't actually coded both and profiled it, so all
this is just speculation. But, from past experience(whatever little that
I've had), it seems unnecessary to use memcpy just for vector<vector<>>.

> 
> > 2. We are implementing this optimization not only for the case when the
> > vector needs to re-allocate, but also for the normal insertion case.
> > Consider: 
> > vector<vector<int> > vv(120);
> > vv.reserve(150);
> > 
> > vv.insert(begin(), 23);
> > 
> > Here, not re-allocation is needed, because reserve has done it's trick,
> > but still, the data movement happens just to insert 1 element! This can
> > be avoided by constructing 1 vector at end(), and performing a
> > swap_backward algorithm (akin to copy_backward).
> 
> Ok.  You partly lost me (I am just a C++ hacker, not a libstdc++ developer)
> but I think I can agree with doing this with specialization for vector,

I have submitted a testing-patch to the list, which will probably convey
my ideas in a better way than 100 lines of english that I write. So, you
could have a look at that to get a jist of what I'm trying to convey.

> list, map etc element types only.  In that I am afraid I lost interest :p

:-(

> (I never used vector<vector<> > etc so far, and won't do so anytime soon).

Yes, I realized that this patch has come about heavily because of the
fact that I heavily use vector<vector<char> >, and that's way too
inefficient when I have to emulate a push_front, or insertion in the
middle, so I thought about using vector<vector<char>*>, but then I said
to myself that this can be done without me having to change my code.
Instead, change the library code!, and probably many more like me could
benefit from it!

-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html