wansor42@gmx.de ("Heinz Ozwirk") wrote in message news:<buoatu$m82$01$1@news.t-online.com>...
> "T. Lovset" schrieb im Newsbeitrag news:d2415545.0401210613.13eb196e@posting.google.com...
> :
> : To me, it doesn't make sense to copy construct the elements over to
> : the new area, then destroy the old ones. Why are not the elements
> : simply moved to the new allocated area, and only allocate/deallocate
> : the memory blocks? The (copy) construction of an element in the vector
> : should not depend on where it is allocated/(moved), so it seems like a
> : waste.  Better like this: (?)
> :

Obviously for objects with completely trivial copy ctors (i.e. no
user-defined copy ctor, or any members/bases with user-defined copy
ctor), and likewise for destructors, there is no difference between
doing a big memmove() and invidually copy constructing and deleting
each element.  It would seem a reasonable (even expected) optimization
for an implementation to at least recognize this, and generate the
appropriate object code (something like rep movs on an x86 chip).  The
one compiler I tested didn't even do this much, which I'm sure says
something relevant.*
An interesting question is then whether such an optimization should be
legal if the copy ctor or destructor isn't completely trivial, and in
which exact cases.  If for instance I update a static counter in the
copy-constructor, but otherwise simply bitwise copy all members,
should an optimization that would bypass this updating be legal?

Of course the type of object it really matters for is things like
std::string, which have obvious move semantics, but it would be
perhaps unrealistic for a compiler to be able to judge this purely
from interpreting the code.  Certainly if there were a way to mark
types "moveable", and have this optimization be valid for objects of
these types, it would be nice, but I think there are actually more
pressing needs for move semantics (e.g. begin able to return
non-copyable objects from functions).

Dylan

* Just

 std::vector<A> a(50);
 a.resize(100);

Generated a surprising amount of code under VC 6.0 with full
optimizations.  Still, the amount of time taken to allocate the new
block of memory far outweighs any possible time saved by translating
the above to a memmove-like instruction.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Dylan Nicholson wrote in message

> Certainly if there were a way to mark
> types "moveable", and have this optimization be valid for objects of
> these types, it would be nice, but I think there are actually more
> pressing needs for move semantics (e.g. begin able to return
> non-copyable objects from functions).
>
Have traits class as moveable<>. Specialize the traits for your
classes and then algorithms may (or may) not test fro the traits and
go in optimized way.

The real problem is to have (semi)standard trait class which is
recognized and used by everyone.

/Pavel

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

T. Lovset wrote:
> Andrey Tarasevich wrote:
>> What makes you to conclude that "(copy) construction of an element in
>> the vector should not depend on where it is allocated"? That's, of
>> course, is wrong. Objects stored if the vector can be
>> location-dependent, which immediately means that your 'memmove'-based
>> approach is not feasible.
>
> I am not suggesting that you can memmove objects about in general. But
> references to vector elements (iterators), and thus references within
> such elements becomes invalid after push_back(), reserve(), etc. That
> puts heavy restrictions on how location-dependent vector elements can
> be.

Well, it puts _some_ restrictions of how location-dependent vector
elements can be. One of the primary reasons to re-construct the elements
being relocated is to allow them to keep their internal integrity. Of
course, the element should be able to establish that integrity using
only the information available to copy constructor. If some particular
type contains some internal invariants that can't be kept up-to-date by
copy constructor alone, that immediately means that elements of this
type can't be stored in a 'vector'.

> In fact, I've tried to come up with an example where the given
> reserve() method fail, and where the current work, but I could only
> come up with a really dodgy one with a static vector involved.

I don't understand why it was so difficult. Just use and object with a
pointer to its own data member, for example

  struct S
  {
    int i;
    int* pi;

    S() : i(0), pi(&i) {}
    S(const S& rhs) : i(rhs.i), pi(&i) {}
    S& operator =(const S& rhs) { i = rhs.i; return *this; }
  };

This object's integrity will be destroyed by your implementation of
'reserve', 'resize' etc., while the standard implementation will work
perfectly.

BTW, the general structure of this example is not as artificial as it
might seem at the first sight.

--
Best regards,
Andrey Tarasevich

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

The way I have implemented this in my std::vector counterpart
is by applying memmove only for types which have bitwise_movable
trait set. By default all non-class types have this trait set, but you can
also set the trait explicitly for class types with the trait template class
specialization. Of course it would be nice if you were able to detect
if type has both trivial copy-constructor & destructor to automatize
this atleast for some class types as well (maybe a C++ standard
proposal?), but you would still need to be able to set the trait explicitly,
because it depends on the implementation of copy-constructor &
destructor if it's really possible (for all types with trivial
copy-constructor
& destructor it is). This has been working fine for me by now,
though I haven't been setting the trait explicitly for types really, because
in incurs some maintenance work (something to do as late stage
optimization).

Jarkko

"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:101b38qjvl1tp30@news.supernews.com...
> T. Lovset wrote:
> > Andrey Tarasevich wrote:
> >> What makes you to conclude that "(copy) construction of an element in
> >> the vector should not depend on where it is allocated"? That's, of
> >> course, is wrong. Objects stored if the vector can be
> >> location-dependent, which immediately means that your 'memmove'-based
> >> approach is not feasible.
> >
> > I am not suggesting that you can memmove objects about in general. But
> > references to vector elements (iterators), and thus references within
> > such elements becomes invalid after push_back(), reserve(), etc. That
> > puts heavy restrictions on how location-dependent vector elements can
> > be.
>
> Well, it puts _some_ restrictions of how location-dependent vector
> elements can be. One of the primary reasons to re-construct the elements
> being relocated is to allow them to keep their internal integrity. Of
> course, the element should be able to establish that integrity using
> only the information available to copy constructor. If some particular
> type contains some internal invariants that can't be kept up-to-date by
> copy constructor alone, that immediately means that elements of this
> type can't be stored in a 'vector'.
>
> > In fact, I've tried to come up with an example where the given
> > reserve() method fail, and where the current work, but I could only
> > come up with a really dodgy one with a static vector involved.
>
> I don't understand why it was so difficult. Just use and object with a
> pointer to its own data member, for example
>
>   struct S
>   {
>     int i;
>     int* pi;
>
>     S() : i(0), pi(&i) {}
>     S(const S& rhs) : i(rhs.i), pi(&i) {}
>     S& operator =(const S& rhs) { i = rhs.i; return *this; }
>   };
>
> This object's integrity will be destroyed by your implementation of
> 'reserve', 'resize' etc., while the standard implementation will work
> perfectly.
>
> BTW, the general structure of this example is not as artificial as it
> might seem at the first sight.
>
> --
> Best regards,
> Andrey Tarasevich
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]
>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"T. Lovset" schrieb im Newsbeitrag news:d2415545.0401210613.13eb196e@posting.google.com...
: vector::reserve() is implemented like this:
:
: void reserve(size_type __n) {
:     if (capacity() < __n) {
:       const size_type __old_size = size();
:       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
:       destroy(_M_start, _M_finish);
:       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
:       _M_start = __tmp;
:       _M_finish = __tmp + __old_size;
:       _M_end_of_storage = _M_start + __n;
:     }
: }
:
: To me, it doesn't make sense to copy construct the elements over to
: the new area, then destroy the old ones. Why are not the elements
: simply moved to the new allocated area, and only allocate/deallocate
: the memory blocks? The (copy) construction of an element in the vector
: should not depend on where it is allocated/(moved), so it seems like a
: waste.  Better like this: (?)
:
: void reserve(size_type __n) {
:     if (capacity() < __n) {
:       const size_type __old_size = size();
:       iterator __tmp = _M_allocate(__n);
:       __copy_trivial(_M_start, _M_finish, __tmp); // memmove
:       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
:       _M_start = __tmp;
:       _M_finish = __tmp + __old_size;
:       _M_end_of_storage = _M_start + __n;
:     }
: }
:
: Similar thing for resize().


What about objects then have data members pointing to other data members? Like

    class C
    {
    private:
        char buffer[42];
        char* next;
        ...
    public:
        C(): next(&buffer[0]) {}
        C(C const& that)
        {
            memcpy(buffer, that.buffer, 42);
            next = &buffer[0] + (that.next - &that.buffer[0]);
        }
        ...
    };

    std::vector<C> v;

Regards
    Heinz

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Ken Alverson" <USENET.Ken@Alverson.net> wrote in message news:buovao$nnq$1@eeyore.INS.cwru.edu...

> It shouldn't?  What if it stores a member pointer to a portion of itself?
>
Pointers to member wouldn't be affected.    However, a regular object
pointer to some piece of the object would be hosed.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

tylo@start.no (T. Lovset) wrote in message news:<d2415545.0401220800.3710ffc8@posting.google.com>...
> > So you're suggesting the default  construction + copy is faster than
> > copy construction?
> >
> > Bob
>
> No, I mean that you don't need to call any object constructors or
> destructors when the purpose is just to move an object to a different
> memory location.

If the object being moved contain, a pointer or reference either to or
into itself, that pointer will no longer point at the right location.
If the object being moved contains a pointer or reference to or into
an exclusively owned object, the move will break the exclusivity.

> In std::vector, it is consistently done by allocating
> a new block, then copy constructing the objects onto the new block,
> destructing the old objects, and deallocating the old block.  Instead,
> it is much faster to just bitmove the already constructed objects.

"bitmoving", as you call it, is only guaranteed to work on POD types.
It's faster partly because it doesn't bother with the fix-ups that the
copy constructor performs to make sure that such things as pointers
and references are converted correctly.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Dave Abrahams wrote:
> No, he's suggesting that in general objects can be moved about it
> memory with the equivalent of memcpy.  Of course, it isn't true.

Andrey Tarasevich wrote:
> What makes you to conclude that "(copy) construction of an element in
> the vector should not depend on where it is allocated"? That's, of
> course, is wrong. Objects stored if the vector can be
> location-dependent, which immediately means that your 'memmove'-based
> approach is not feasible.

I am not suggesting that you can memmove objects about in general. But
references to vector elements (iterators), and thus references within
such elements becomes invalid after push_back(), reserve(), etc. That
puts heavy restrictions on how location-dependent vector elements can
be.

In fact, I've tried to come up with an example where the given
reserve() method fail, and where the current work, but I could only
come up with a really dodgy one with a static vector involved.

I challenge you to come up with a (fairly) common situation where the
memmove reserve() will fail. I'd hate to think that this artificial
example is the reason for not utilizing such a nice optimalization:

class E {
public:
 E() : x(0), iter_offset(vec.begin() + 5) {}
 E(const E& e) { iter_offset = vec.begin() + 5; x = e.x; }
 E& operator=(const E& e) { iter_offset = vec.begin() + 5; x = e.x; }

 static std::vector<E> vec;
 std::vector<E>::iterator iter_offset;
 int x;
};
std::vector<E> E::vec(10);

int main() {
        E::vec[0].iter_offset->x = 10;
        E::vec.reserve(30);
        // wouldn't work with memmove reserve().
        std::cout << E::vec[0].iter_offset->x << std::endl;
}

// Thank you for your attention.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> I am not suggesting that you can memmove objects about in general. But
> references to vector elements (iterators), and thus references within
> such elements becomes invalid after push_back(), reserve(), etc. That
> puts heavy restrictions on how location-dependent vector elements can
> be.
>
> In fact, I've tried to come up with an example where the given
> reserve() method fail, and where the current work, but I could only
> come up with a really dodgy one with a static vector involved.
>
> I challenge you to come up with a (fairly) common situation where the
> memmove reserve() will fail. I'd hate to think that this artificial
> example is the reason for not utilizing such a nice optimalization:
<snip>

How about this:


class Handle;

class Body {
friend class Handle;
     Body(Body const &);
     Body &operator=(Body const &);

     Body(Handle *owner) : owner(owner) {}
public:
     Handle &getHandle() {return *owner;}
private:
     Handle *owner;
};

class Handle {
public:
     Handle() : body(new Body(this)) {}
     Handle(Handle const &) : body(new Body(this) {}
     Handle &operator=(Handle const &) { return *this; }
     Body &getBody() { return *body; }
private:
     Body *body;
};

std::vector<Handle> handles;


When a Handle is bit-blitted (when handles gets push_back()ed or
reserve()ed or whatever), its "body" member will still refer to the
proper Body, but the Body's "owner" pointer will dangle.

This example doesn't do anything useful by itself, but I think it
illustrates a pattern that is rather common.  Mutually referenced
objects are not at all uncommon.  I use them in my neural network code
(although that's too big to post here as a real world example).  It is
this very mutual referencing that forces me to do some fancy stuff in my
copy constructors, assignment operators, and swap functions to get the
value semantics to work properly.  These objects _would_ break if any
container assumed it could blit them about in memory whenever they
needed to be moved.

I would venture to say that just about any class participating in a
reference cycle would be susceptible to this type of failure.

Adam Peterson

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

USENET.Ken@Alverson.net (Ken Alverson) wrote in message news:<buovao$nnq$1@eeyore.INS.cwru.edu>...
> "T. Lovset" <tylo@start.no> wrote in message
> news:d2415545.0401210613.13eb196e@posting.google.com...
> >
> > To me, it doesn't make sense to copy construct the elements over to
> > the new area, then destroy the old ones. Why are not the elements
> > simply moved to the new allocated area, and only allocate/deallocate
> > the memory blocks?
>
> How do you suggest "moving" non-POD elements?

A non-POD element can also be bit-copied to another location. That is
my point. It's just a matter of controling that the destructor for the
source element is not ever called, which is the case in my example.

>
> > The (copy) construction of an element in the vector
> > should not depend on where it is allocated/(moved)
>
> It shouldn't?  What if it stores a member pointer to a portion of itself?
>
> Ken
Well, as you know, you may not store a pointer/iterator to another
(arbitrary) element in a vector, because that would be invalidated
after e.g. a push_back. A copy constructor cannot reconstruct that
unless it can be computed by some offset from e.g. begin(). So, in
that very special case, where you store offset pointer in the
elements, you may have code like this in both your default and copy
constructor:

   m_offset_iter = begin() + m_offset;

The current resize() would call the copy constructor and restore
m_offset_iter correctly - my suggestion wouldn't!  I presume that the
above example is the the reason that my suggested optimalization is
not applied. Can anyone confirm that?

I must add that in practice this example shouldn't pose a problem.
Most people would rather just store m_offset, which is invariable, and
use a method like:

  iterator offset_iter() { return begin() + m_offset; }

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Ron Natalie wrote:
> "Ken Alverson" <USENET.Ken@Alverson.net> wrote in message news:buovao$nnq$1@eeyore.INS.cwru.edu...
>
>
>>It shouldn't?  What if it stores a member pointer to a portion of itself?
>>
>
> Pointers to member wouldn't be affected.    However, a regular object
> pointer to some piece of the object would be hosed.
>

The terminology was possibly ambiguous, but I think what the parent
poster intended was sotmething like:

struct C {
 C() : pi(&i) {}
 C(C const &c) : pi(&i) {}
 C &operator=(C const &c) { return *this; }
 int i;
 int *pi;
 // pi is a member that will point to its C's i.
 // Thus C stores a member that is a pointer
 // pointing to a portion of itself.
};

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > How do you suggest "moving" non-POD elements?
> >
>
>    There's a proposal suggesting a way to do just that.  Note that this
> would require a change to the C++ language, not just a new library.  See the
> attached link:
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
>
> Joe Gottman

Thanks a lot for that link. Excellent - forget all my other posts. I
really hope this suggestion will be accepted. Quoting:

"One common example is when you have a full dynamic array of objects
and you want to add to it. You must allocate a larger array and move
the objects from the old buffer to the new. The objects in the array
are obviously not rvalues. And yet there is no reason to *copy* them
to the new array if *moving* can be accomplished much faster."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <d2415545.0401231755.42ae5303@posting.google.com>,
 tylo@start.no (T. Lovset) wrote:

> > > How do you suggest "moving" non-POD elements?
> > >
> >
> >    There's a proposal suggesting a way to do just that.  Note that this
> > would require a change to the C++ language, not just a new library.  See the
> > attached link:
> > http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
> >
> > Joe Gottman
>
> Thanks a lot for that link. Excellent - forget all my other posts. I
> really hope this suggestion will be accepted. Quoting:
>
> "One common example is when you have a full dynamic array of objects
> and you want to add to it. You must allocate a larger array and move
> the objects from the old buffer to the new. The objects in the array
> are obviously not rvalues. And yet there is no reason to *copy* them
> to the new array if *moving* can be accomplished much faster."

I'll be counting on your vote in the upcoming election. ;-)

Seriously, move semantics is not at all assured in C++0X.  If the C++
public wants it, the C++ public needs to maintain vocal support of move
semantics.  Your post helps, thanks.  Your job is not done.  ;-)
Further study and criticism is appreciated.  Or simply further:  Yes, do
it! is also appreciated.

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

T. Lovset wrote:
> USENET.Ken@Alverson.net (Ken Alverson) wrote in message news:<buovao$nnq$1@eeyore.INS.cwru.edu>...
>
>>"T. Lovset" <tylo@start.no> wrote in message
>>news:d2415545.0401210613.13eb196e@posting.google.com...
>>
>>>To me, it doesn't make sense to copy construct the elements over to
>>>the new area, then destroy the old ones. Why are not the elements
>>>simply moved to the new allocated area, and only allocate/deallocate
>>>the memory blocks?
>>
>>How do you suggest "moving" non-POD elements?
>
>
> A non-POD element can also be bit-copied to another location. That is
> my point.

But in the general case it's not true.

> It's just a matter of controling that the destructor for the
> source element is not ever called, which is the case in my example.

No, it's not just a matter of that.  Sometimes the identity
of an object has importance that is respected by its copy
operations but not by a bitwise copy (for example, it may
be registered with some other component, and need to update
that component to know about the new copy).

>>>The (copy) construction of an element in the vector
>>>should not depend on where it is allocated/(moved)
>>
>>It shouldn't?  What if it stores a member pointer to a portion of itself?
>>
>>Ken
>
> Well, as you know, you may not store a pointer/iterator to another
> (arbitrary) element in a vector, because that would be invalidated
> after e.g. a push_back.

Luckily push_back, if it needs to copy elements, will use
the appropriate copy operation and destructor, which then
get a chance to act appropriately.

-- James.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 23 Jan 2004 23:22:01 +0000, T. Lovset wrote:

> I challenge you to come up with a (fairly) common situation where the
> memmove reserve() will fail. I'd hate to think that this artificial
> example is the reason for not utilizing such a nice optimalization:

How about a std::string implementation that stores short strings inside a
small array inside the string object itself. These implementations do
exist. Most probably the string object has a pointer that can either point
to that array or some dynamically allocated memory.

I used similar idioms for objects stored in an OODB. As most objects would
never outgrow the internal array, they had very good locality of reference
and hence where very fast. Only when the number of items stored was more
than the size of the internal array, extra memory was allocated.

HTH,
M4

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Howard Hinnant" <hinnant@metrowerks.com> wrote in message
news:hinnant-EA3C86.22564423012004@syrcnyrdrs-01-ge0.nyroc.rr.com...
> In article <d2415545.0401231755.42ae5303@posting.google.com>,
>  tylo@start.no (T. Lovset) wrote:
>
> > > > How do you suggest "moving" non-POD elements?
> > > >
> > >
> > >    There's a proposal suggesting a way to do just that.  Note that
this
> > > would require a change to the C++ language, not just a new library.
See the
> > > attached link:
> > > http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
> > >
> > > Joe Gottman
> >
> > Thanks a lot for that link. Excellent - forget all my other posts. I
> > really hope this suggestion will be accepted. Quoting:
> >
> > "One common example is when you have a full dynamic array of objects
> > and you want to add to it. You must allocate a larger array and move
> > the objects from the old buffer to the new. The objects in the array
> > are obviously not rvalues. And yet there is no reason to *copy* them
> > to the new array if *moving* can be accomplished much faster."
>
> I'll be counting on your vote in the upcoming election. ;-)
>
> Seriously, move semantics is not at all assured in C++0X.  If the C++
> public wants it, the C++ public needs to maintain vocal support of move
> semantics.  Your post helps, thanks.  Your job is not done.  ;-)
> Further study and criticism is appreciated.  Or simply further:  Yes, do
> it! is also appreciated.

   Who do we contact to register our support for this change?

Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

tylo@start.no (T. Lovset) wrote in message news:<d2415545.0401222347.79e06089@posting.google.com>...
> USENET.Ken@Alverson.net (Ken Alverson) wrote in message news:<buovao$nnq$1@eeyore.INS.cwru.edu>...
..
> > How do you suggest "moving" non-POD elements?
>
> A non-POD element can also be bit-copied to another location.

Citation please? The only relevant part of the standard that I can
find is 3.9p3, and it is explicitly restricted to POD types.

..
> > > The (copy) construction of an element in the vector
> > > should not depend on where it is allocated/(moved)
> >
> > It shouldn't?  What if it stores a member pointer to a portion of itself?
> >
> > Ken
> Well, as you know, you may not store a pointer/iterator to another
> (arbitrary) element in a vector, because that would be invalidated

He said "itself", not "another".

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

tylo@start.no (T. Lovset) wrote in message news:<d2415545.0401230833.225301a@posting.google.com>...
..
> I am not suggesting that you can memmove objects about in general. But
> references to vector elements (iterators), and thus references within
> such elements becomes invalid after push_back(), reserve(), etc. That
> puts heavy restrictions on how location-dependent vector elements can
> be.

No, it doesn't. Those restrictions have no effect on the member
elements themselves; the member elements don't even necessarily know
that they are in a vector<>. They can contain pointers and references
to themselves and each other, not obtained from vector<>. As long as
the copy constructor and copy assignment operators correctly rearrange
those pointers to maintain the class invariants, there's no problem,
which is precisely why it's a problem if vector<> moves then without
invoking either the copy constructor or the copy assignment operator.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Joe Gottman"" <jgottman@carolina.rr.com> wrote in message:

> > Seriously, move semantics is not at all assured in C++0X.  If the
C++
> > public wants it, the C++ public needs to maintain vocal support of
move
> > semantics.  Your post helps, thanks.  Your job is not done.  ;-)
> > Further study and criticism is appreciated.  Or simply further:
Yes, do
> > it! is also appreciated.
>
>    Who do we contact to register our support for this change?
>

My thought exactly. I've heard Howard and David Abrahams say C++ users
need to make known our support for the move proposal. How? Should we
organize a candlelight vigil? :-)

Maybe I should just say this:

    I'm begging, please!

Jonathan



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <8b42afac.0401240954.63cf1f28@posting.google.com>, James
Kuyper <kuyper@wizard.net> writes
>No, it doesn't. Those restrictions have no effect on the member
>elements themselves; the member elements don't even necessarily know
>that they are in a vector<>. They can contain pointers and references
>to themselves and each other, not obtained from vector<>. As long as
>the copy constructor and copy assignment operators correctly rearrange
>those pointers to maintain the class invariants, there's no problem,
>which is precisely why it's a problem if vector<> moves then without
>invoking either the copy constructor or the copy assignment operator.

And note that even a C-style struct is not always copyable with memcpy
or memmove because those sometimes include internal pointers, and are
sometimes referenced by external pointers (consider a typical list
implementation for the type of problem the latter can have)


--
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

vector::reserve() is implemented like this:

void reserve(size_type __n) {
    if (capacity() < __n) {
      const size_type __old_size = size();
      iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
      destroy(_M_start, _M_finish);
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __tmp;
      _M_finish = __tmp + __old_size;
      _M_end_of_storage = _M_start + __n;
    }
}

To me, it doesn't make sense to copy construct the elements over to
the new area, then destroy the old ones. Why are not the elements
simply moved to the new allocated area, and only allocate/deallocate
the memory blocks? The (copy) construction of an element in the vector
should not depend on where it is allocated/(moved), so it seems like a
waste.  Better like this: (?)

void reserve(size_type __n) {
    if (capacity() < __n) {
      const size_type __old_size = size();
      iterator __tmp = _M_allocate(__n);
      __copy_trivial(_M_start, _M_finish, __tmp); // memmove
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __tmp;
      _M_finish = __tmp + __old_size;
      _M_end_of_storage = _M_start + __n;
    }
}

Similar thing for resize().

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

tylo@start.no (T. Lovset) wrote in message news:<d2415545.0401210613.13eb196e@posting.google.com>...
> vector::reserve() is implemented like this:
>
> void reserve(size_type __n) {
>     if (capacity() < __n) {
>       const size_type __old_size = size();
>       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
>       destroy(_M_start, _M_finish);
>       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
>       _M_start = __tmp;
>       _M_finish = __tmp + __old_size;
>       _M_end_of_storage = _M_start + __n;
>     }
> }
>
> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks? The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved), so it seems like a
> waste.  Better like this: (?)
>
> void reserve(size_type __n) {
>     if (capacity() < __n) {
>       const size_type __old_size = size();
>       iterator __tmp = _M_allocate(__n);
>       __copy_trivial(_M_start, _M_finish, __tmp); // memmove
>       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
>       _M_start = __tmp;
>       _M_finish = __tmp + __old_size;
>       _M_end_of_storage = _M_start + __n;
>     }
> }
>
> Similar thing for resize().

So you're suggesting the default  construction + copy is faster than
copy construction?

Bob

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"T. Lovset" <tylo@start.no> wrote in message
news:d2415545.0401210613.13eb196e@posting.google.com...
>
> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks?

How do you suggest "moving" non-POD elements?

> The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved)

It shouldn't?  What if it stores a member pointer to a portion of itself?

Ken


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Ken Alverson" <USENET.Ken@Alverson.net> wrote in message
news:buovao$nnq$1@eeyore.INS.cwru.edu...
> "T. Lovset" <tylo@start.no> wrote in message
> news:d2415545.0401210613.13eb196e@posting.google.com...
> >
> > To me, it doesn't make sense to copy construct the elements over to
> > the new area, then destroy the old ones. Why are not the elements
> > simply moved to the new allocated area, and only allocate/deallocate
> > the memory blocks?
>
> How do you suggest "moving" non-POD elements?
>

   There's a proposal suggesting a way to do just that.  Note that this
would require a change to the C++ language, not just a new library.  See the
attached link:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

belvis@pacbell.net (Bob Bell) writes:

> So you're suggesting the default  construction + copy is faster than
> copy construction?

No, he's suggesting that in general objects can be moved about it
memory with the equivalent of memcpy.  Of course, it isn't true.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> So you're suggesting the default  construction + copy is faster than
> copy construction?
>
> Bob

No, I mean that you don't need to call any object constructors or
destructors when the purpose is just to move an object to a different
memory location. In std::vector, it is consistently done by allocating
a new block, then copy constructing the objects onto the new block,
destructing the old objects, and deallocating the old block.  Instead,
it is much faster to just bitmove the already constructed objects.
Also, e.g. for vector<string>, back().c_str() would survive a
reserve(), although this can not be guaranteed by the std.

It is hard to believe that this obvious efficency saving has been
overlooked, so please tell me what is wrong with it? This time I spell
it out, using the built in allocator:

void reserve(size_type __n) {
   if (capacity() < __n) {
      const size_type __old_size = size();
      // allocate memory only - no construction
      value_type* __tmp = (value_type*)
         operator new (__n * sizeof(value_type));
      memcpy(__tmp, _M_start, __old_size * sizeof(value_type));
      // deallocate - no destruction
      operator delete((void *) _M_start);
      _M_start = __tmp;
      _M_finish = __tmp + __old_size;
      _M_end_of_storage = _M_start + __n;
   }
}
size_type size() const { return _M_finish - _M_begin; }
size_type capacity() const { return _M_end_of_storage - _M_begin; }

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

T. Lovset wrote:
> ...
> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks? The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved), so it seems like a
> waste.

What makes you to conclude that "(copy) construction of an element in
the vector should not depend on where it is allocated"? That's, of
course, is wrong. Objects stored if the vector can be
location-dependent, which immediately means that your 'memmove'-based
approach is not feasible.

> void reserve(size_type __n) {
>     if (capacity() < __n) {
>       const size_type __old_size = size();
>       iterator __tmp = _M_allocate(__n);
>       __copy_trivial(_M_start, _M_finish, __tmp); // memmove
>       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
>       _M_start = __tmp;
>       _M_finish = __tmp + __old_size;
>       _M_end_of_storage = _M_start + __n;
>     }
> }

--
Best regards,
Andrey Tarasevich

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

tylo@start.no (T. Lovset) wrote in message news:<d2415545.0401210613.13eb196e@posting.google.com>...
> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks? The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved), so it seems like a
> waste.

std::vector does not care where in memory the elements are but the
elements perhaps care where in memory they are.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

T. Lovset wrote:
> vector::reserve() is implemented like this:
>
> void reserve(size_type __n) {
>     if (capacity() < __n) {
>       const size_type __old_size = size();
>       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
>       destroy(_M_start, _M_finish);
>       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
>       _M_start = __tmp;
>       _M_finish = __tmp + __old_size;
>       _M_end_of_storage = _M_start + __n;
>     }
> }
>
> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks? The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved), so it seems like a
> waste.  Better like this: (?)
>
> void reserve(size_type __n) {
>     if (capacity() < __n) {
>       const size_type __old_size = size();
>       iterator __tmp = _M_allocate(__n);
>       __copy_trivial(_M_start, _M_finish, __tmp); // memmove
>       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
>       _M_start = __tmp;
>       _M_finish = __tmp + __old_size;
>       _M_end_of_storage = _M_start + __n;
>     }
> }
>
> Similar thing for resize().
>

Changing the value of "this" in the middle of an object's life doesn't
seem very nice.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Thu, 22 Jan 2004 02:21:24 +0000, T. Lovset wrote:

> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks?

Because the type of elements can't communicate whether copying the
representation would work, or how a move should be done in general.
Yes, it is a waste, but currently unavoidable.

> The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved),

It's unlikely that it depends on it, but it can. The objects may point
to some bobjects which point back to the objects.

--
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Thu, 22 Jan 2004 02:21:24 +0000, T. Lovset wrote:

> To me, it doesn't make sense to copy construct the elements over to
> the new area, then destroy the old ones. Why are not the elements
> simply moved to the new allocated area, and only allocate/deallocate
> the memory blocks? The (copy) construction of an element in the vector
> should not depend on where it is allocated/(moved), so it seems like a
> waste.  Better like this: (?)

Because you cannot assume you can move objects, even if it is safe 99% of
the time. Consider:

class X {
  int array[4];
  int *current;
  size_t size;
public:
  X() : current(array): size(0) {}
  ... lots omited ...
};

If this class is moved by memcpy, p points to the wrong place. And this
idiom /is/ used sometimes.

HTH,
M4

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]