move semantic in C++

  • Permalink
  • submit to reddit
  • Email
  • Follow


I finally found some time to gather thoughts that were burrowing my
mind for very long time and put them "on paper". It looks somewhat
messy -- definitely I am not a master of quill but I tried. :)
This is not really a proposal (so I decided not to bother comp.std.c++)
-- I have nor time nor specific experience to develop proposal for such
big thing. However, I hope this paper will raise popularity of 'move
semantic' in people's mind which ultimately will lead to introduction
of this feature into C++ -- I strongly believe we could benefit from
it. I definitely will ;).

here is it:
http://home.iprimus.com.au/crusader7/prg/cpp_move.htm

it is about how we need 'move', how compiler could implement it and
what problemms we will get along with benefits.

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply mpryhodko (3) 5/26/2005 9:56:29 AM

See related articles to this posting


In article <1117019154.545527.195600@g47g2000cwa.googlegroups.com>,
Michael Pryhodko <mpryhodko@westpac.com.au> writes
> here is it:
> http://home.iprimus.com.au/crusader7/prg/cpp_move.htm
>
> it is about how we need 'move', how compiler could implement it and
> what problemms we will get along with benefits.

A pity that you did not first read the existing proposals in WG21. IIRC
N1770 and N1771 are the papers concerned with move semantics (though
they talk about rvalue references). Not only is move semantics on the
active work list but Metroworks have extensive internal experience of
implementing and using them.


-- 
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: 
http://www.spellen.org/youcandoit/projects


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Francis 5/26/2005 1:34:18 PM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

> I finally found some time to gather thoughts that were burrowing my
> mind for very long time and put them "on paper". It looks somewhat
> messy -- definitely I am not a master of quill but I tried. :)
> This is not really a proposal (so I decided not to bother comp.std.c++)
> -- I have nor time nor specific experience to develop proposal for such
> big thing. However, I hope this paper will raise popularity of 'move
> semantic' in people's mind which ultimately will lead to introduction
> of this feature into C++ -- I strongly believe we could benefit from
> it. I definitely will ;).
>
> here is it:
> http://home.iprimus.com.au/crusader7/prg/cpp_move.htm
>
> it is about how we need 'move', how compiler could implement it and
> what problemms we will get along with benefits.

That feature is already well on its way into the standard, with
complete proposals, proposed standard wording, and everything:

  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1770.html
  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html

Earlier work, with motivation, narrative, etc.  A bit easier to read:

  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html
  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

n1770 has been forwarded to the core working group for review prior to
voting on whether it will be in C++0x.

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 5/27/2005 8:46:18 AM

> > it is about how we need 'move', how compiler could implement it and
> > what problemms we will get along with benefits.
>
> That feature is already well on its way into the standard, with
> complete proposals, proposed standard wording, and everything:
>
>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1770.html
>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html
>
> Earlier work, with motivation, narrative, etc.  A bit easier to read:
>
>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html
>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm
>
> n1770 has been forwarded to the core working group for review prior to
> voting on whether it will be in C++0x.

Hmm... Everything new is just well forgotten old. I read whose papers,
unfortunately they do not have everything I'd like to see in C++ (with
respect to move semantic). And at this pace I'll die before it will
made its way into C++. :)
Too bad I was born too late to participate in related discussions that
happend it seems very long ago. Also I'd vote for 'destructive move',
since it:
- more logical
- more efficient -- you do not need to pay in run-time for things you
do not need

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 5/29/2005 1:40:59 PM

> A pity that you did not first read the existing proposals in WG21. IIRC
> N1770 and N1771 are the papers concerned with move semantics (though
> they talk about rvalue references). Not only is move semantics on the
> active work list but Metroworks have extensive internal experience of
> implementing and using them.

- do you have any links to papers about it?
- how did they augmented C++? which 'type' of move semantic they
implemented?

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 5/29/2005 1:52:18 PM

In article <1117369488.149197.135220@g43g2000cwa.googlegroups.com>,
 "Michael Pryhodko" <mpryhodko@westpac.com.au> wrote:

> Also I'd vote for 'destructive move',
> since it:
> - more logical
> - more efficient -- you do not need to pay in run-time for things you
> do not need

>From N1377:

> However the current proposal does not prohibit destructive move semantics in 
> the future. It could be done in addition to the non-destructive move 
> semantics outlined in this proposal should someone wish to carry that torch.

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 5/29/2005 2:23:39 PM

>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html

Found a typo: "specializationss"

>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html
>   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

Do you know if extending non-static member function syntax to:

<whatever-tokens>() [const volatile] && [throw-spec] [= 0];

were considered at one point? That way you don't have to overload
global operators to handle lhs rvalues and you can make assignment to
rvalue private (among other things).


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Me 5/30/2005 11:14:47 AM

>>From N1377:
>> However the current proposal does not prohibit destructive move semantics in
>> the future.

But makes it more complicated :))


>> It could be done in addition to the non-destructive move
>> semantics outlined in this proposal should someone wish to carry that torch.

So, basically, everyone understands that 'move' is good, but nobody
wants to "carry that torch" because it is too heavy? :)
It seems that C++ itself becomes too "heavy" -- with all features it
has it is almost impossible for an individual to consider every aspect
of adding new (or forgotten) feature.
Maybe we could design new language from scratch? and provide some kind
of mechanism to use old source code without being backward compatible?
for example: new language should be able to work with special
preprocessed old code (i.e. all templates are instantiated, defines
substitued, maybe some additional processing to fix type-system and so
on). Hmm... I suppose that kind of project needs dedicated individual
that will start it and get some results. After that it could be
"standartised". In this way it will repeat life of C++, but with less
mistakes. Just a dream

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 5/30/2005 11:15:08 AM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

> Hmm... Everything new is just well forgotten old. I read whose papers,
> unfortunately they do not have everything I'd like to see in C++ (with
> respect to move semantic). And at this pace I'll die before it will
> made its way into C++. :)
> Too bad I was born too late to participate in related discussions that
> happend it seems very long ago.

Only a few years ago.  That's long in computer time, I guess.

> Also I'd vote for 'destructive move', since it:

> - more logical

That's highly debatable.

> - more efficient -- you do not need to pay in run-time for things you
> do not need

If you can show us how to write correct code with destructive move, it
might be worth considering.

   template <class T>
   void f(T& x)
   {
       if (some_predicate(x))
       {
           T y = destructive_move(x);
       }
   }

How does code that calls f know whether to generate a destructor for
the argument to f?

That problem is just the tip of the iceberg.  The shape of the whole
mountain is outlined in http://tinyurl.com/9jerj
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm#Alternative%20move%20designs)
http://groups-beta.google.com/group/comp.std.c++/msg/fad24f4e357ac4b1?hl=en
also has some information.

I assure you that the implications of destructive move semantics were
very carefully considered before we decided not to propose it.

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 5/30/2005 11:40:51 AM

In article <1117410841.531946.81690@g49g2000cwa.googlegroups.com>,
  "Me" <anti_spam_email2003@yahoo.com> wrote:

> Do you know if extending non-static member function syntax to:
>
> <whatever-tokens>() [const volatile] && [throw-spec] [= 0];
>
> were considered at one point? That way you don't have to overload
> global operators to handle lhs rvalues and you can make assignment to
> rvalue private (among other things).

I believe what your asking about is in this paper:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1784.htm

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 5/30/2005 7:32:26 PM

In article <1117412422.582048.155030@z14g2000cwz.googlegroups.com>,
  "Michael Pryhodko" <mpryhodko@westpac.com.au> wrote:

> >>From N1377:
> >> However the current proposal does not prohibit destructive move semantics
> >> in
> >> the future.
>
> But makes it more complicated :))

How so?  N1377 even suggests the syntax that could be used for
destructive move semantics.

> >> It could be done in addition to the non-destructive move
> >> semantics outlined in this proposal should someone wish to carry that
> >> torch.
>
> So, basically, everyone understands that 'move' is good, but nobody
> wants to "carry that torch" because it is too heavy? :)

You have an imaginative interpretation of our current status.

I read your paper with interest.  I agree that there is a place in C++
for destructive move semantics, but disagree with your view of that
place, the importance of destructive move semantics (relative to
non-destructive move), and the use cases laid out in your paper.  I
specifically do not like the suggested undef functionality.

I anticipate that a destructive move would occur in real code with about
the same frequency that an explicit call to a destructor does today.  I
don't see such code very often, but one place I do see it is in the
implementation of containers (which is a very important use case).

There are many similarities between your paper and N1377.  Because your
paper references N1385, and N1385 references N1377, I was quite
surprised that your paper does not reference N1377 extensively (which is
even published in the same mailing as N1385), comparing and contrasting
with it, perhaps even building upon it, and/or offering solutions to the
destructive move problems which are outlined in N1377.

There is no need for you to work "outside" of this system.  Your
willingness to write a paper about a subject you care deeply about is a
very good start.  May I suggest that persistence is another quality
necessary to influence an international standard.  If it would aid you,
I'd be happy to offer assistance offline, such as any clarifications you
might request about the current (N1377-based) move proposal, or even
running small demo programs for you since implementations of N1377 are
not yet publicly available.

Note that N1377 is only one base document.  Others that I recommend
familiarity with include:

N1385
N1690
N1770
N1771
N1784

All of these are available at:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 5/31/2005 5:18:58 PM

> > Also I'd vote for 'destructive move', since it:
> > - more logical
> That's highly debatable.

Sure. Every my word is my 'imho', if you agree with it -- it is
coincidence. :)


> > - more efficient -- you do not need to pay in run-time for things you
> > do not need
>
> If you can show us how to write correct code with destructive move, it
> might be worth considering.
>
>    template <class T>
>    void f(T& x)
>    {
>        if (some_predicate(x))
>        {
>            T y = destructive_move(x);
>        }
>    }
>
> How does code that calls f know whether to generate a destructor for
> the argument to f?

No problem, I spoke about that in my paper. Answer is very simple: yes,
in all cases. If you destroy varible though pointer -- it is considered
as if it belongs to dynamic storage. If you like to shoot yourself --
you are free to do it. However if you wish to control caller's stack
frame (let's use MSVC+x86 for now) you need to use 'special functions'
(see my paper) -- but in this case f's declaration would be different
(for example parameters could be 'marked' as belonging to local storage
-- depends on a way you implement this feature).

Lets look at this example from another angle:
what is local variable? what this code means?:
(1)
{
....
     T var(...);
}

you know what is the 'scope' in C++, right? Now let me play with 'local
variable' definition:
- C++ has only one storage -- STORAGE
- when you declare local variable's memory is taken from STORAGE.
Variable name is a 'special' construction, 'pointer' which is used to
access variable (and destroy variable whenever execution reaches the
end of the scope).

now since all variables logically belongs to the same STORAGE your
'hard' example becomes very simple:
- if you pass a pointer to variable -- it means you do not care about
scope unwinding effect, either because this variable has no name (not
bound to scope), or you want to shoot your leg.
- (1) in this light could be rewritten like this:
{
....
     T% var = new T(...);
}

where T% stands for 'special scope-tied pointer type' or simply --
'variable name'. I.e. at the end of scope C++ runtime will call
destructor and free memory used by variable pointed by 'var'.
- now if you need your example to behave correctly you need to take
'scope' rules into account, i.e. you need to pass variable name:

template <class T>
void f(T% x)
{
     if (some_predicate(x))
     {
         T y = destructive_move(x); // this will update scope unwinding
                                    // mechanism of f's caller
     }
}

- it is evident how to make static variables fit into this model.
- please, look at 'my C++' chapter in my paper -- it uses similar logic
for unnamed variables: 'new' returns pointer object (which looks like
T% above, but not tied to scope). I understand that my english is bad,
my writer's skill is low, but lets discuss! I'll gladly clarify
everything you did not understood.
- common, people, just try to think differently!


Any other obstacles?


> That problem is just the tip of the iceberg.  The shape of the whole
> mountain is outlined in http://tinyurl.com/9jerj

I read it, thank you. Imho, main problem is the appearance of a new
'suicide' method (to be more precise 'legalisation' of exisiting
suicide method). But this comes with great rewards, while negative
effects could be reduced with various mechanisms and compiler warnings
(for example allowing move only inside of specific regions).

I wonder if 'my' :) two-phase move implementation was proposed before?


> I assure you that the implications of destructive move semantics were
> very carefully considered before we decided not to propose it.

:) I understand. Let me show my point: I am fascinated with this idea,
I've spent about 3 years thinking how it could be implemented, what
effect it will cause (rewards is obvious) and so on. I really want this
feature -- C++ extention for 'guru  only' would suffice for me. Without
'move' C++ is somewhat crippled, incomplete.

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 5/31/2005 6:58:20 PM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

> template <class T>
> void f(T% x)
> {
>      if (some_predicate(x))
>      {
>          T y = destructive_move(x); // this will update scope unwinding
>                                     // mechanism of f's caller
>      }
> }

What you've described isn't easy to understand, but it seems to me
that you're saying there should be some runtime information associated
with the thing x refers to that tells the "scope unwinding mechanism"
whether that thing should be destroyed when the scope is exited.  If
so, that's an unacceptable runtime cost to pay to make every automatic
variable moveable-from.  If that's not what you're saying, then what?

> Any other obstacles?
>
>
>> That problem is just the tip of the iceberg.  The shape of the whole
>> mountain is outlined in http://tinyurl.com/9jerj
>
> I read it, thank you. Imho, main problem is the appearance of a new
> 'suicide' method (to be more precise 'legalisation' of exisiting
> suicide method). But this comes with great rewards, 

What rewards?  Have you done measurements that show a significant
advantage over non-destructive move?

> while negative effects could be reduced with various mechanisms and
> compiler warnings (for example allowing move only inside of specific
> regions).

Sounds complicated and hard-to-use.

> I wonder if 'my' :) two-phase move implementation was proposed before?

Not to my knowledge.

>> I assure you that the implications of destructive move semantics were
>> very carefully considered before we decided not to propose it.
>
> :) I understand. Let me show my point: I am fascinated with this idea,
> I've spent about 3 years thinking how it could be implemented, what
> effect it will cause (rewards is obvious) and so on. I really want this
> feature -- C++ extention for 'guru  only' would suffice for me. Without
> 'move' C++ is somewhat crippled, incomplete.

Sure.  But you can move destructively, *explicitly*, today: just write
the function to do it for each moveable type.  What you can't get
today is implicit destructive move... and so far I'm pretty sure you
can almost never make good use of that feature.

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 6/1/2005 1:08:58 AM

David Abrahams <dave@boost-consulting.com> writes:

>>> I assure you that the implications of destructive move semantics were
>>> very carefully considered before we decided not to propose it.
>>
>> :) I understand. Let me show my point: I am fascinated with this idea,
>> I've spent about 3 years thinking how it could be implemented, what
>> effect it will cause (rewards is obvious) and so on. I really want this
>> feature -- C++ extention for 'guru  only' would suffice for me. Without
>> 'move' C++ is somewhat crippled, incomplete.
>
> Sure.  But you can move destructively, *explicitly*, today: just write
> the function to do it for each moveable type.  What you can't get
> today is implicit destructive move... and so far I'm pretty sure you
> can almost never make good use of that feature.

I take it back.  It's the explicit destructive move that's dangerous.
At least, that's how it looks to me at 10:30 pm.  Maybe it's time for
bed ;-)

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 6/1/2005 8:58:51 AM

> > template <class T>
> > void f(T% x)
> > {
> >      if (some_predicate(x))
> >      {
> >          T y = destructive_move(x); // this will update scope unwinding
> >                                     // mechanism of f's caller
> >      }
> > }
>
> What you've described isn't easy to understand, but it seems to me
> that you're saying there should be some runtime information associated
> with the thing x refers to that tells the "scope unwinding mechanism"
> whether that thing should be destroyed when the scope is exited.  If
> so, that's an unacceptable runtime cost to pay to make every automatic
> variable moveable-from.

Right. However I do not disagree with "unacceptable runtime cost". Let
me point that:
1. there is no payment in case of f's inlining
2. this is a payment for abstraction of access to caller's context,
i.e. if you need to update unwinding information without knowing
caller's context -- you need to pay abstraction penalty. And it won't
be bigger than equivalent payment for abstraction called 'virtual
functions'. And in this case all you need to pass is a info, necessary
to find x's unwinding information, which is basically equivalent to
passing one extra 'int' parameter.
3. Depending on your compiler you could be already paying 90% of this
payment! For example in MSVC each (lets not consider optimizer's work)
stack frame has a table with flags for every local object with
non-trivial destructor (GCC unfortunately :) uses another approach for
unwinding imlementation).


> > I read it, thank you. Imho, main problem is the appearance of a new
> > 'suicide' method (to be more precise 'legalisation' of exisiting
> > suicide method). But this comes with great rewards,
>
> What rewards?  Have you done measurements that show a significant
> advantage over non-destructive move?

1. Hmm, strange question. How do you measure 'C++ with templates'
against 'C++ without them'? It is a feature -- you can not measure it's
"performance". It is not possible to measure exactly runtime costs.
Because different compilers could implement it in different ways, it
depends on hardware platform (for example virtual function call,
relatively expensive on 8086, costs almost nothing on Itanium due to
hardware features that makes calling function through pointer cheaper).
All you could do is to estimate costs using logic.
2. Difference between non- and destructive move is the same as between
using swap and move -- in first case you will pay twice: for swap and
for destruction of empty object, in second case you'll pay less than
for 'swap'. Also I'd like to note that it is not easy to swap variables
wich has external dependencies (i.e. somebody points to that variable).
In my 'proposition' C++ runtime gives you mechanism to overcome this
(helper_obj).
3. I described rewards in my paper. It is not only speed efficiency of
containers -- you could achieve the same effect by tedious work of
uglyfying your code (changing classes to PODs). It is absence of
expensive implicit 'copy', which is expensive not only in terms of CPU
time, but also influence development time since you need always to
remember about it and take measures. For example I am tired writing
stuff like this:
void func(string const& var);
It is a possiblity to treat every value of type T in the same way...
Well, rewards quite numerous (for me). Most of them descirbed in the
paper.


> > while negative effects could be reduced with various mechanisms and
> > compiler warnings (for example allowing move only inside of specific
> > regions).
>
> Sounds complicated and hard-to-use.

If I'd have exact syntax, with every feature considered and described
-- I'd put this post on comp.std.c++ :). Also let me point that C++ is
ALREADY complicated and hard-to-use -- and 'move' feature could make it
less complicated for use by removing some problems.


> > I wonder if 'my' :) two-phase move implementation was proposed before?
>
> Not to my knowledge.

Good... maybe something still could be invented, not only 'found in the
past'.


> > effect it will cause (rewards is obvious) and so on. I really want this
> > feature -- C++ extention for 'guru  only' would suffice for me. Without
> > 'move' C++ is somewhat crippled, incomplete.
>
> Sure.  But you can move destructively, *explicitly*, today: just write
> the function to do it for each moveable type.  What you can't get
> today is implicit destructive move... and so far I'm pretty sure you
> can almost never make good use of that feature.

No you can't. It is just like saying: "Bah, you could do
constructor/destructor thing in C -- just create methods for every type
and call them !". C++ gives you automatic storage + unwinding, atomic
constructor/destructor coupling when you use inheritance, binds
together allocation and initialization and so on -- basically solves
problems on every intersection of this feature with any other language
features.

And in case of 'move' we need deep language support like we have for
construction/destruction. Otherwise we'll just get crippled monster. :)

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/1/2005 9:06:07 AM

First, I want to clarify some things:
- I do not have syntax and semantic ready to be 'inserted' in C++
standard
- All I have is the 'vision' :) of how 'move' could be implemented
logically and how it will 'intersect' with other C++ features. Also I
have idea how it could be implemented technically, e.g. on x86
assembler level.

The whole purpose of this thread is to share my vision with others and
after (in case of popularity) go from clouds to ground -- to try
creating necessary C++ syntax. I understand that this will be painful,
but I really want to either include it all into C++ or not include at
all, because crippled man is crippled until he has two hands and two
legs. :)


> That problem is just the tip of the iceberg.  The shape of the whole
> mountain is outlined in http://tinyurl.com/9jerj
> http://groups-beta.google.com/group/comp.std.c++/msg/fad24f4e357ac4b1?hl=en
> also has some information.

This link describes moving into vector's middle as a problem for move
semantic. Here I'll describe how it could be implemented with features
described in my paper. This is in vague pseudocode:

suppose that:
- vector has enough reserved memory
- most of features from paper is implemented in language
- vector's buffer is chunk of memory in form of array of T's: T*
m_buffer;

template<class T>
void insert_move(size_t pos, T% var_name)
{
     // phase 1 -- could throw
     // move_1 right part of buffer
     for(size_t i = size(); i > pos; ++i)
     {
         move_1(m_buf[i - 1] ==> m_buf[i]);
     }

     // move_1 var_name into m_buffer[1]
     move_1(var_name ==> m_buf[pos]);

     // phase 2 -- throw()
     // finalize right part movement
     for(i = size(); i > pos; ++i)
     {
         move_2(m_buf[i - 1] ==> m_buf[i]);
     }

     // finalize var_name movement
     move_2(var_name ==> m_buf[pos]);
}

For types with trivial move_X this will result in one memove and one
memcpy (considering reasonable optimizer). For most C++ types this
insert will not throw if it has enough allocated memory.
For types with complex move this will result in atomic-like insert
(i.e. vector and var_name invariantness is saved).

Note that to implement this method we need next features:
- 'special' functions
- controllable move, i.e. program is able to control move phases

Also to pass additional information into movement logic we need syntax
to pass arbitrary number of arbitrary arguments and reference them with
one keyword. something like this:
template<class T, arg_list Rest>
void insert_move(size_t pos, T% var_name, Rest)
{
     ...
     move_1(var_name ==> m_buf[pos])(Rest);
     ...
}

It is hard to implement this feature for usual functions, but could be
implemented for template functions.

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/1/2005 9:09:00 AM

> > >>From N1377:
> > >> However the current proposal does not prohibit destructive
> > >> move semantics in the future.
> > But makes it more complicated :))
> How so?  N1377 even suggests the syntax that could be used for
> destructive move semantics.

For example if C++ will include non-destructive move it would be VERY
hard to put destructive move after -- simply because most of people
will be satisfied.
Another thought: as far as I understand N1377 does not have all
features 'move' needs from my point of view, if it make into standard
it would be hard to add missing features later. Just like in case of
template typedef -- templates were introduced long ago, but
'templatedef' was forgotten and now it cannot get into standard for
quite a long time.


> I read your paper with interest.  I agree that there is a place in C++
> for destructive move semantics, but disagree with your view of that
> place, the importance of destructive move semantics (relative to
> non-destructive move), and the use cases laid out in your paper.  I
> specifically do not like the suggested undef functionality.

Well, from my point of view non- and destructive semantic are mostly
interchangeable. Main difference between them is that in non- case you
will pay extra: default constructor call, swap, destructor; while
destructive move is cheaper. Also my proposal has mechanism for
external references update (I consider this quite important). So
importance of non- and destructive semantic is equal.
About undef: unfortunately I do not have exact syntax of how 'move'
could look like in C++. My speculations mostly describes a 'vision' of
how this could be implemented in C++. It is logical -- first you think
how it will work, then you invent syntax. If you could reach the same
with different looking syntax -- it is ok.


> I anticipate that a destructive move would occur in real code with about
> the same frequency that an explicit call to a destructor does today.  I
> don't see such code very often, but one place I do see it is in the
> implementation of containers (which is a very important use case).

I disagree. As I told before destructive move is almost equivalent to
nondestructive but more efficient. And 'move' itself will be used much
more frequently than explicit destructor call:
- implicit move (e.g. returning/passing temporary/local variable)
- new functions which move local variables from caller's scopes (e.g.
move_into_vector)
- generic code that will move values around (for example I need it
quite often in my code)

Also appearance of 'move' in C++ will change coding style dramatically,
I believe. From that point every associated resource could be
fearlessly encapsulated into the class; PODs will become rare (people
use POD structures mostly because it is more efficient with
containers); horrible stuff like auto_ptr's copy constructor will go
away; people will be more convinced to replace 'operator new' with
something new :) that returns not plain pointer but object that will
free associated variable upon destruction (i.e. memory leaks will go to
museum) and so on and so on.


> There are many similarities between your paper and N1377.  Because your
> paper references N1385, and N1385 references N1377, I was quite
> surprised that your paper does not reference N1377 extensively (which is
> even published in the same mailing as N1385), comparing and contrasting
> with it, perhaps even building upon it, and/or offering solutions to the
> destructive move problems which are outlined in N1377.

:)) I did not used these papers. Everything is simple:
Most of my life I was too busy (or too lazy) to participate in
newsgroups, so my appearances in com.lang.c++.* was very short and
irregular. Some months ago I started reading this newsgroup seriously
and somebody (James Kanze?) gave me link to NXXXX papers. I did some
reading at the beginning, then I just browsed through table of content
and N1385 just caught my eye, I read it, understood general idea and
forgot about it. However I keep list of papers I read, so it was not
forgotten completely and used later when I was preparing my 'paper'.


> There is no need for you to work "outside" of this system.  Your
> willingness to write a paper about a subject you care deeply about is a
> very good start.  May I suggest that persistence is another quality
> necessary to influence an international standard.

:) I just started...


> If it would aid you,
> I'd be happy to offer assistance offline, such as any clarifications you
> might request about the current (N1377-based) move proposal, or even
> running small demo programs for you since implementations of N1377 are
> not yet publicly available.
>
> Note that N1377 is only one base document.  Others that I recommend
> familiarity with include:
>
> N1385
> N1690
> N1770
> N1771
> N1784

Thanks, I'll use your help, if something will be unclear.


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/1/2005 12:51:58 PM

In article <1117609130.100166.234590@o13g2000cwo.googlegroups.com>, 
Michael Pryhodko <mpryhodko@westpac.com.au> writes
>First, I want to clarify some things:
>- I do not have syntax and semantic ready to be 'inserted' in C++
>standard

And therein lies the difference. Those working on move semantics for the 
next version of C++ have been giving consideration to exactly how their 
proposals will interact with the whole of the language (actually a very 
difficult thing which really does require many eyes)

In addition they have not just been writing papers but actively testing 
their ideas on real compilers.

>- All I have is the 'vision' :) of how 'move' could be implemented
>logically and how it will 'intersect' with other C++ features. Also I
>have idea how it could be implemented technically, e.g. on x86
>assembler level.

Yes, but C++ has to work on general cpu's not just a specific family.
>
>The whole purpose of this thread is to share my vision with others and
>after (in case of popularity) go from clouds to ground -- to try
>creating necessary C++ syntax. I understand that this will be painful,
>but I really want to either include it all into C++ or not include at
>all, because crippled man is crippled until he has two hands and two
>legs. :)

Thanks for sharing the vision but I say again, it is a pity that you do 
not appear to have first researched for existing proposals. An open 
minded discussion with those who have already put in a great deal of 
practical work might be a lot more constructive.

Now you want to advocate a destructive move (if memory serves me 
correctly, that was considered way back when the current proposals were 
being shaped up). Please provide a convincing case study showing how 
that such would be really useful in practical code. Above all those 
working on the C++ Standard take note of proposals grounded in practical 
issues. For example one of the most convincing pieces of evidence for 
the current proposals is a clear demonstration using a real commercial 
grade C++ implementation, that move semantics can have a major impact on 
the performance of important STL components that are in wide use.

-- 
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Francis 6/1/2005 1:00:15 PM

In article <1117624354.520630.100060@g43g2000cwa.googlegroups.com>, 
Michael Pryhodko <mpryhodko@westpac.com.au> writes
>For example if C++ will include non-destructive move it would be VERY
>hard to put destructive move after -- simply because most of people
>will be satisfied.

IOWs the current proposal meets most people's needs? So what special 
extra benefits are met by your proposal that makes it worth the extra 
resources that would be need to put it in the Standard?  If we can get 
90% of the benefits for 20% of the cost that is what will happen. It is 
now up to you to demonstrate that what is on the table is either 
considerably less than 90% and/or that the cost of the extra is much, 
much less than my estimate. There is also a time issue. We are not going 
to delay the standard to add a few extra tweaks how ever good they look 
to some.

>Another thought: as far as I understand N1377 does not have all
>features 'move' needs from my point of view, if it make into standard
>it would be hard to add missing features later.

Then list the missing features and provide persuasive arguments that 
they are both missing and valuable. Just asserting that something is 
missing will buy you nothing. If you want something you are going to 
have to put in the work (quite a lot of it)

> Just like in case of
>template typedef -- templates were introduced long ago, but
>'templatedef' was forgotten and now it cannot get into standard for
>quite a long time.

I very much doubt that it was simply forgotten. When we came to study it 
for the coming revised Standard we were only mildly surprised by just 
how complex the issue was. Had we included a template typedef in the 
current version we would have got it wrong and it would then have been 
ten years too late to get it right.

>
>
>> I read your paper with interest.  I agree that there is a place in C++
>> for destructive move semantics, but disagree with your view of that
>> place, the importance of destructive move semantics (relative to
>> non-destructive move), and the use cases laid out in your paper.  I
>> specifically do not like the suggested undef functionality.
>
>Well, from my point of view non- and destructive semantic are mostly
>interchangeable. Main difference between them is that in non- case you
>will pay extra: default constructor call, swap, destructor; while
>destructive move is cheaper.

And those who have actually looked and tried it seem to disagree with 
you. Between theoretical performance and measured performance I am quite 
clear which I will believe.

> Also my proposal has mechanism for
>external references update (I consider this quite important). So
>importance of non- and destructive semantic is equal.
>About undef: unfortunately I do not have exact syntax of how 'move'
>could look like in C++. My speculations mostly describes a 'vision' of
>how this could be implemented in C++. It is logical -- first you think
>how it will work, then you invent syntax. If you could reach the same
>with different looking syntax -- it is ok.

And the devil is in the detail. Yes almost everyone who has spent more 
than a couple of years involved with C++ Standards knows the truth of 
that statement.
>
>
>> I anticipate that a destructive move would occur in real code with about
>> the same frequency that an explicit call to a destructor does today.  I
>> don't see such code very often, but one place I do see it is in the
>> implementation of containers (which is a very important use case).
>
>I disagree. As I told before destructive move is almost equivalent to
>nondestructive but more efficient. And 'move' itself will be used much
>more frequently than explicit destructor call:
>- implicit move (e.g. returning/passing temporary/local variable)
>- new functions which move local variables from caller's scopes (e.g.
>move_into_vector)
>- generic code that will move values around (for example I need it
>quite often in my code)

>
>Also appearance of 'move' in C++ will change coding style dramatically,
>I believe. From that point every associated resource could be
>fearlessly encapsulated into the class; PODs will become rare (people
>use POD structures mostly because it is more efficient with
>containers); horrible stuff like auto_ptr's copy constructor will go
>away; people will be more convinced to replace 'operator new' with
>something new :) that returns not plain pointer but object that will
>free associated variable upon destruction (i.e. memory leaks will go to
>museum) and so on and so on.

I think that the results will  be much, much smaller than you seem to 
think. And changes will take much longer.

>
>
>> There are many similarities between your paper and N1377.  Because your
>> paper references N1385, and N1385 references N1377, I was quite
>> surprised that your paper does not reference N1377 extensively (which is
>> even published in the same mailing as N1385), comparing and contrasting
>> with it, perhaps even building upon it, and/or offering solutions to the
>> destructive move problems which are outlined in N1377.
>
>:)) I did not used these papers. Everything is simple:
>Most of my life I was too busy (or too lazy) to participate in
>newsgroups, so my appearances in com.lang.c++.* was very short and
>irregular. Some months ago I started reading this newsgroup seriously
>and somebody (James Kanze?) gave me link to NXXXX papers. I did some
>reading at the beginning, then I just browsed through table of content
>and N1385 just caught my eye, I read it, understood general idea and
>forgot about it. However I keep list of papers I read, so it was not
>forgotten completely and used later when I was preparing my 'paper'.

Then, it seems you did not do the background research that would have 
given your paper adequate underpinning. I suspect that you do not 
understand the number of hours invested in even the simplest of 
proposals. I think your time would be much better spent working within 
the current proposals and investigating if minor changes would give you 
more of what you want. At this late stage (yes, it is late even for a 
Standard planned to ship in 2009) that is probably the most constructive 
way you could work.

>
>
>> There is no need for you to work "outside" of this system.  Your
>> willingness to write a paper about a subject you care deeply about is a
>> very good start.  May I suggest that persistence is another quality
>> necessary to influence an international standard.
>
>:) I just started...
>
Unfortunately you only have a couple of years to finish. Actually much 
less than that because we (WG21) are already in a position where we will 
have to triage proposals and the basis of how much time it will take to 
refine them and incorporate them into the Working Paper.

-- 
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Francis 6/1/2005 2:39:10 PM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

>> > template <class T>
>> > void f(T% x)
>> > {
>> >      if (some_predicate(x))
>> >      {
>> >          T y = destructive_move(x); // this will update scope unwinding
>> >                                     // mechanism of f's caller
>> >      }
>> > }
>>
>> What you've described isn't easy to understand, but it seems to me
>> that you're saying there should be some runtime information associated
>> with the thing x refers to that tells the "scope unwinding mechanism"
>> whether that thing should be destroyed when the scope is exited.  If
>> so, that's an unacceptable runtime cost to pay to make every automatic
>> variable moveable-from.
>
> Right. However I do not disagree with "unacceptable runtime cost". Let
> me point that:
> 1. there is no payment in case of f's inlining
> 2. this is a payment for abstraction of access to caller's context,

Or access to dynamic memory, since the callee doesn't really know
which context the pointee is allocated in.

> i.e. if you need to update unwinding information without knowing
> caller's context -- you need to pay abstraction penalty. 

This has nothing to do with "unwinding" in the usual sense of the word
-- that refers to what happens when an exception is thrown.  You're
talking about changing what happens in the *normal* (non-exceptional)
control path as well.

> And it won't be bigger than equivalent payment for abstraction
> called 'virtual functions'. 

There's an important reason that virtual functions are an optional
abstraction in C++.

> And in this case all you need to pass is
> a info, necessary to find x's unwinding information, which is
> basically equivalent to passing one extra 'int' parameter.

It's not just how much you pass, but how much work has to be done in
the caller to check whether to destroy x.  Branches are well-known to
be expensive in performance-critical code.  You're proposing to add
tests-and-branches.

> 3. Depending on your compiler you could be already paying 90% of
> this payment! For example in MSVC each (lets not consider
> optimizer's work) stack frame has a table with flags for every local
> object with non-trivial destructor

IIRC, MSVC doesn't check these flags when executing the normal control
flow that leaves a function.  They're only used for exception
unwinding.  The efficiency of the normal path is usually the important
one.

More importantly, Using a compiler whose EH implementation sucks as
your benchmark for whether there's going to be a significant cost is
pretty unconvincing.

> (GCC unfortunately :) uses another approach for unwinding
> imlementation).

That's hardly unfortunate; it's the right thing to do, and results in
a huge performance gain.  Even MSVC does that when compiling 64-bit
code.

>> > I read it, thank you. Imho, main problem is the appearance of a new
>> > 'suicide' method (to be more precise 'legalisation' of exisiting
>> > suicide method). But this comes with great rewards,
>>
>> What rewards?  Have you done measurements that show a significant
>> advantage over non-destructive move?
>
> 1. Hmm, strange question. How do you measure 'C++ with templates'
> against 'C++ without them'? It is a feature -- you can not measure it's
> "performance". 

'scuse me, but it's perfectly possible to make useful and instructive
measurements.  Howard Hinnant has done real performance measurements
of a standard library implemented with non-destructive move semantics
vs. one implemented without move semantics.

> 2. Difference between non- and destructive move is the same as between
> using swap and move -- in first case you will pay twice: for swap and
> for destruction of empty object, in second case you'll pay less than
> for 'swap'. 

Except that you additionally incur runtime costs for passing extra
parameters (according to you), and storing/checking these flags.
Until you measure how those costs trade off against the cost of
destroying empty objects, you can't claim your scheme is better.

> 3. I described rewards in my paper. It is not only speed efficiency of
> containers -- you could achieve the same effect by tedious work of
> uglyfying your code (changing classes to PODs). It is absence of
> expensive implicit 'copy', which is expensive not only in terms of CPU
> time, but also influence development time since you need always to
> remember about it and take measures. For example I am tired writing
> stuff like this:
> void func(string const& var);
> It is a possiblity to treat every value of type T in the same way...
> Well, rewards quite numerous (for me). Most of them descirbed in the
> paper.

Even destructive move won't save you from writing 

   void func(string const& var);

if you want efficiency.  In all the cases where the compiler could
take advantage of an implicit move, it's _already_ allowed to elide
the copy today when passing to:

   void func(string var);

The real advantage of 

   void func(string const& var);

is that it saves copies when the argument is an lvalue and couldn't be
moved from anyway.

>> > while negative effects could be reduced with various mechanisms and
>> > compiler warnings (for example allowing move only inside of specific
>> > regions).
>>
>> Sounds complicated and hard-to-use.
>
> If I'd have exact syntax, with every feature considered and described
> -- I'd put this post on comp.std.c++ :). Also let me point that C++ is
> ALREADY complicated and hard-to-use -- and 'move' feature could make it
> less complicated for use by removing some problems.

Show me how.

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 6/1/2005 9:25:02 PM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

> As I told before destructive move is almost equivalent to
> nondestructive but more efficient.

Only when you're ignoring some of its costs.  You actually have no
basis for comparison.

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 6/1/2005 9:25:52 PM

In article <1117624354.520630.100060@g43g2000cwa.googlegroups.com>,
 "Michael Pryhodko" <mpryhodko@westpac.com.au> wrote:

> > > But makes it more complicated :))
> > How so?  N1377 even suggests the syntax that could be used for
> > destructive move semantics.
> 
> For example if C++ will include non-destructive move it would be VERY
> hard to put destructive move after -- simply because most of people
> will be satisfied.

Hmm... I've also concluded that non-destructive move will satisfy most 
needs.  That's why I've given it such higher priority over destructive 
move semantics.  But I also believe destructive move has some uses, 
which is why I don't object to someone else leading that crusade, and am 
interested in the discussion.

Let me be more concrete.  Consider:

vector<int> v1(m);
vector<vector<int>> v;
v.assign(n, v1);

v.insert(v.begin(), v1);

Assume for the moment that v.capacity() == n before the insert (which is 
typical in today's implementations, and I see no motivation to change 
that).  The insert must create a new buffer internally and copy/move the 
existing inner vectors to it.

With copy semantics the time complexity of the insert is O(n*m).

With non-destructive move semantics the time complexity of the insert is 
O(n).

With destructive move semantics the time complexity of the insert is 
O(n).

That is, move semantics over copy semantics (whether destructive or not) 
is going to get us an O(m) times speed up for this case.  That is huge!  
Going with destructive move semantics (in addition to non-destructive 
move semantics) would probably lower the constant on that O(n) estimate.  
But this is not nearly as big a gain as the O(m) speed up gained just 
from eschewing internal copying.  Still it is something, and if someone 
wants to carry that torch, I'd be interested in reaping that extra 
optimization.  But I have to focus my limited resources on the O(m) gain.

Note that destructive move is not always a win over non-destructive move:

vector<int> v1(m);
vector<vector<int>> v;
v.reserve(n+1);
v.assign(n, v1);

v.insert(v.begin(), v1);

Now the insert does not need to create the new internal buffer.  The 
existing internal buffer has sufficient capacity.  The insert merely 
needs to move existing data within the buffer to make room for the new 
element.  Non-destructive move constructions and non-destructive move 
assignments are better suited to this task than a destructive move, both 
in terms of performance and code size (though both would still have the 
same time complexity - and much improved over the time complexity 
associated with internal copying).

So destructive move is best in the relatively rare case when the buffer 
needs to be reallocated, but not in the more common case where 
sufficient capacity already exists, further increasing my desire to 
prioritize non-destructive move semantics.

> Another thought: as far as I understand N1377 does not have all
> features 'move' needs from my point of view, if it make into standard
> it would be hard to add missing features later. Just like in case of
> template typedef -- templates were introduced long ago, but
> 'templatedef' was forgotten and now it cannot get into standard for
> quite a long time.

"template typedef" (now called template aliasing) is being worked on for 
inclusion into the standard at the next available opportunity (C++0X).

C++0X is what we are discussing.  There is no opportunity to do anything 
faster than that with respect to move semantics.

In article <1117609130.100166.234590@o13g2000cwo.googlegroups.com>,
 "Michael Pryhodko" <mpryhodko@westpac.com.au> wrote:

> > http://groups-beta.google.com/group/comp.std.c++/msg/fad24f4e357ac4b1?hl=en
> > also has some information.
> 
> This link describes moving into vector's middle as a problem for move
> semantic. Here I'll describe how it could be implemented with features
> described in my paper. This is in vague pseudocode:
> 
> suppose that:
> - vector has enough reserved memory
> - most of features from paper is implemented in language
> - vector's buffer is chunk of memory in form of array of T's: T*
> m_buffer;
> 
> template<class T>
> void insert_move(size_t pos, T% var_name)

The link above is actually talking about insert_copy, not insert_move.  
That is, what do you do if the /copy/ construction from var_name throws 
an exception?  I would be interested in seeing your pseudo code for 
that.  Might want to change those ++i to --i.

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 6/1/2005 9:28:06 PM

> Let me be more concrete.  Consider:
>
> vector<int> v1(m);
> vector<vector<int>> v;
> v.assign(n, v1);
>
> v.insert(v.begin(), v1);
>
> Assume for the moment that v.capacity() == n before the insert (which is
> typical in today's implementations, and I see no motivation to change
> that).  The insert must create a new buffer internally and copy/move the
> existing inner vectors to it.
>
> With copy semantics the time complexity of the insert is O(n*m).

:) imho it is O((n+1)*m) + C, but that is not important. Also if 'int'
is not POD this figure will be bigger.


> With non-destructive move semantics the time complexity of the insert is
> O(n).
>
> With destructive move semantics the time complexity of the insert is
> O(n).
>
> That is, move semantics over copy semantics (whether destructive or not)
> is going to get us an O(m) times speed up for this case.  That is huge!
> Going with destructive move semantics (in addition to non-destructive
> move semantics) would probably lower the constant on that O(n) estimate.
> But this is not nearly as big a gain as the O(m) speed up gained just
> from eschewing internal copying.  Still it is something, and if someone
> wants to carry that torch, I'd be interested in reaping that extra
> optimization.  But I have to focus my limited resources on the O(m) gain.

Understandable, but it does not conform to old rule "you do not need to
pay for what you do not need".
I understand your point, but it is very tempting to get more if it is
possible.


> Note that destructive move is not always a win over non-destructive move:
>
> vector<int> v1(m);
> vector<vector<int>> v;
> v.reserve(n+1);
> v.assign(n, v1);
>
> v.insert(v.begin(), v1);
>
> Now the insert does not need to create the new internal buffer.  The
> existing internal buffer has sufficient capacity.  The insert merely
> needs to move existing data within the buffer to make room for the new
> element.  Non-destructive move constructions and non-destructive move
> assignments are better suited to this task than a destructive move, both
> in terms of performance and code size (though both would still have the
> same time complexity - and much improved over the time complexity
> associated with internal copying).

Hmm... it seems I missed something, but in case of nondestructive move
you are supposed to:
- construct default value at n+1'th position
- for every move from [i] to [i+1] you need to fill [i] with meaningful
value -- if this is done with 'swap' you'll also have one extra copy to
temporary variable
This results in O(n) + C extra operations (O(2*n) + C in case of
'swap')
This is still a bit more than in 'destructive move' case. This extra
could be insignificant if you use complex types, but for small and
easy-to-move types it could be relatively big. For example for this
type:

class Int
{
     int m_val;
public:
     Int() throw() {m_val = 0;}
     // everything else is compiler-generated
};

for operation:

vector<Int> v;
v.reserve(n+1);
v.assign(n, Int());
v.insert(v.begin(), Int());

results will be:

O(n+1) for destructive move
O(2*n+1) + C for non-destructive move
O(3*n + 1) + C for 'swap' case

it could make difference...


> "template typedef" (now called template aliasing) is being worked on for
> inclusion into the standard at the next available opportunity (C++0X).
>
> C++0X is what we are discussing.  There is no opportunity to do anything
> faster than that with respect to move semantics.

:(
Joke:
C++0X could mean anything from 2000 to 2009, but because of truncation
it could also mean 2105, 2307 and 3009 ;)


> > template<class T>
> > void insert_move(size_t pos, T% var_name)
>
> The link above is actually talking about insert_copy, not insert_move.
> That is, what do you do if the /copy/ construction from var_name throws
> an exception?  I would be interested in seeing your pseudo code for
> that.

Sure, here it is:

#include "previous_stuff" :)

template<class T, arg_list Rest>
void insert_copy(size_t pos, T val, Rest)
{
     insert_move(pos, val, Rest);
}

or caller could do it himself:

{
     T var(...);
....
     v.insert_move(pos, T(var), move_arg1, ...);
}

case when vector has not enough memory is quite simple too -- just
declare something local that will free allocated memory in case of
exception.


>  Might want to change those ++i to --i.

Certainly, I am sorry.


Now I have some questions:
Objects could have external references that points to them. During
'move' they need to be updated and this 'update' could throw.
1. What 'current' nondestructive semantic has to solve this task?
2. What will happen in insert_move example if one of objects' move
constructor will throw during 'external references update'?


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/2/2005 9:39:32 AM

> >- I do not have syntax and semantic ready to be 'inserted' in C++
> >standard
>
> And therein lies the difference. Those working on move semantics for the
> next version of C++ have been giving consideration to exactly how their
> proposals will interact with the whole of the language (actually a very
> difficult thing which really does require many eyes)

Sorry, Francis, but without posting my thoughts to public newsgroup I
can not get required 'many eyes'. And I told before that indeed it is a
difficult thing to consider every implication of implementing my ideas
into C++. Also I told that I do not have much of time to do it alone --
I simply cannot dedicate all my time to this feature: my friends
already noticed that my mailing domain changed to com.au not long ago
-- so I have a huge amount of problems and tasks before me right now
which is not C++-related.


> In addition they have not just been writing papers but actively testing
> their ideas on real compilers.

Lucky -- I envy them...


> >Also I
> >have idea how it could be implemented technically, e.g. on x86
> >assembler level.
>
> Yes, but C++ has to work on general cpu's not just a specific family.

Certainly, but having ideas how feature could be implemented on one
specific platform is much better than having nothing. Especially
considering that most compilers generate similar code regardless of
platform: i.e. local/temporaries storage implemented as stack-like
structure, structures is a contiguous chunks of memory and so on.


> Thanks for sharing the vision but I say again, it is a pity that you do
> not appear to have first researched for existing proposals.

I did! After I got this link to site with papers some months ago I read
most of papers for 2005 and 2004 year, believe me it is not very easy
reading. for other yars I just quickly glanced over the list of the
paper titles. I am really surprised that paper dated back to 2003 is
still "alive".


> An open
> minded discussion with those who have already put in a great deal of
> practical work might be a lot more constructive.

What do you think I am trying to do? I am sorry, but you sounds like a
man who thinks that somebody wants to steal something from him. It is
not true.


> Now you want to advocate a destructive move (if memory serves me
> correctly, that was considered way back when the current proposals were
> being shaped up). Please provide a convincing case study showing how
> that such would be really useful in practical code. Above all those
> working on the C++ Standard take note of proposals grounded in practical
> issues. For example one of the most convincing pieces of evidence for
> the current proposals is a clear demonstration using a real commercial
> grade C++ implementation, that move semantics can have a major impact on
> the performance of important STL components that are in wide use.

Agreed, but I thought I clearly explained why I do not have it:
- I am alone
- limited time
- there are still significant number of dark corners to discuss
- I do not have stable syntax yet

And if you wish to participate this discussion on 'non-destructive
side', why do not you provide simple 'few words' description of use
case which proves that destructive move proposed by me is wrong? ;)
Instead you attacks me for not having more convincing proofs -- I know
it myself, but I find these ideas beautiful and I love C++, so I am
trying other peoples opinion about them.


> Please provide a convincing case study showing how  that such would be
> really useful in practical code.

What exactly do you want? Be prepared for vague pseudo-code, however...
Also, since 'move' semantic idea is so ancient most of its usefulness
should have already been discussed.


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/2/2005 9:41:29 AM

{I have an increasing feeling that this thread would be much more at 
home in comp.std.c++. clc++m is really intended for matters concerned 
with using the current Standard C++ rather than an in depth discussion 
of a proposal for the next version. -mod}

[skip discussion of idea about how caller's unwinding mechanism]
[could be updated and why MS sucks and GC rulez :)]

Ok, you got me here. Here is another idea:
How we are doing the same thing in current C++? We are creating class
like that:
class T
{
     ... // members
     bool bFlag;
     ~T()
     {
         if (!bFlag)
         {
             ... // do usual destruction work
         }
     }
};

and then pass pointer to such object into f:

{
     T var(...);
     f(&var); // inside f will call T::close() --> 'm_bFlag = true'
     ...
}

all is ok. Now it should be clear how it could be implemented with
destructive move:

class T
{
     ... // no flag here
     ~T()
     {
         ... // usual destruction work
     }
};

void f(T% var_name)
{
     T tmp <== var_name; // destructive move
}

....
{
     T var(...);
     f(var);
}

Description of compiler behavior:
for every scope-tied(local/temporary/static) variable compiler
generates extra flag which follows that variable in memory and used as
a 'destroyed' flag whenever variable should be automatically destroyed
(also it could be used in DEBUG builds for diagnostics). Compiler
supposed to detect every variable that could be destroyed
'unnaturally'. T% in f's declaration could be used as an indication
that:
- you could pass only scope-based variables here
- this variable will be followed in memory by destroyed/init'ed flag
(this fact will be used by f's implementation)

Impacts:
- extra stuff will be applied only for variables that could be
destroyed in called functions
- code becomes a bit cleaner -- you do not need to care for m_bFlag (or
NULL values -- I hate them ;) ), it is automated by compiler
- MSVC and GCC could implement this easily
- size of stack could be slightly bigger, but I doubt it could cause
any problems, especially considering that flag will be created for SOME
instances of type T -- if we do it 'by hands' flag will be in EVERY
instance of T (regardless of storage type).

David, did I proved to you that this mechanism could be implemented
efficiently?

Now as I told before -- main problem of destructive move is the
'legalization of already exisitng possibility of presence of undefined
variables'.


> > 1. Hmm, strange question. How do you measure 'C++ with templates'
> > against 'C++ without them'? It is a feature -- you can not measure it's
> > "performance".
>
> 'scuse me, but it's perfectly possible to make useful and instructive
> measurements.  Howard Hinnant has done real performance measurements
> of a standard library implemented with non-destructive move semantics
> vs. one implemented without move semantics.

I understand, but sometimes it is easy to estimate. In this case I do
not have nor time nor sources nor experience building C++ compiler. So
'estimate using logic' is my only option.


> > 2. Difference between non- and destructive move is the same as between
> > using swap and move -- in first case you will pay twice: for swap and
> > for destruction of empty object, in second case you'll pay less than
> > for 'swap'.
>
> Except that you additionally incur runtime costs for passing extra
> parameters (according to you), and storing/checking these flags.
> Until you measure how those costs trade off against the cost of
> destroying empty objects, you can't claim your scheme is better.

Considering poem above, can I claim it now?


> Even destructive move won't save you from writing
>
>    void func(string const& var);

Agreed my mistake, too much heat. :) Not everywhere, but some places
could be like:
void func(string% var_name);

others:
void func(string var);
and you could call it as:
string s = "my string";
func(move s(...)); // no copy here at all


> if you want efficiency.  In all the cases where the compiler could
> take advantage of an implicit move, it's _already_ allowed to elide
> the copy today when passing to:
>
>    void func(string var);

Oops... How it is allowed? what if you change 'var'?


> The real advantage of
>
>    void func(string const& var);
>
> is that it saves copies when the argument is an lvalue and couldn't be
> moved from anyway.

In current C++ -- yes.


> > If I'd have exact syntax, with every feature considered and described
> > -- I'd put this post on comp.std.c++ :). Also let me point that C++ is
> > ALREADY complicated and hard-to-use -- and 'move' feature could make it
> > less complicated for use by removing some problems.
>
> Show me how.

I am trying...
1. you could now hold complex values in the container without thinking
how it will be moved inside
2. operator new now could return object instead of raw pointer (see 'my
C++' for clues) -- this could solve everlasting memory leak problem (or
at least it will make it hard to do any kind of leak)
3. look here:
http://blogs.msdn.com/oldnewthing/archive/2005/05/18/419130.aspx
What do you see here? I see: "If you wish speed and efficiency do not
use classes -- use PODs". And this guy has quite big audience. That
kind of crap will go to history -- aren't that great?

Please, note that applies to both kind of 'move'... simply destructive
one is more efficient while giving one extra opportunity to shoot
yourself. Also my idea with two phased move and passing move context is
'more generic' -- i.e. you could move objects which can not be moved by
other means, also it could be used to create complex atomic-like
updates.

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/2/2005 9:44:17 AM

> >For example if C++ will include non-destructive move it would be VERY
> >hard to put destructive move after -- simply because most of people
> >will be satisfied.
>
> IOWs the current proposal meets most people's needs? So what special
> extra benefits are met by your proposal that makes it worth the extra
> resources that would be need to put it in the Standard?  If we can get
> 90% of the benefits for 20% of the cost that is what will happen. It is
> now up to you to demonstrate that what is on the table is either
> considerably less than 90% and/or that the cost of the extra is much,
> much less than my estimate. There is also a time issue. We are not going
> to delay the standard to add a few extra tweaks how ever good they look
> to some.

1. I am sure you'd not delay standard in any case, even if I put ready
standard text with move in it before you. :)
2. It is not an official proposal -- I'd use c++.std in that case
3. I did knew that work on move is underway -- I had nothing to compare
with.

Question was: why introduction of non-destructive semantic makes it
hard to introduce destructive semantic
Answer: because it would be not SO needed, also it is a kinda of
'replace each other' things -- once one of them make its way into
standard another one is likely to be doomed.


> IOWs

What does it stands for?
{In Other Words -mod}


> >Another thought: as far as I understand N1377 does not have all
> >features 'move' needs from my point of view, if it make into standard
> >it would be hard to add missing features later.
>
> Then list the missing features and provide persuasive arguments that
> they are both missing and valuable. Just asserting that something is
> missing will buy you nothing. If you want something you are going to
> have to put in the work (quite a lot of it)

I understand it. Now I want:
- to influence your mind with my thought on 'move semantic' topic
- to get some experience from conversation
- if my theories proves to be interesting and 'real' enough -- prepare
proposal, maybe get some help from those interested

List of missing features:
- two-phased move (with ability to control phases)
- move context passing
- other features are related to destructive semantic specific, i.e.
declaration of undefinded variables and so on

Valuability: well.. they are valuable for me, like pieces of mosaic
they make overall picture complete. When you create a class you usually
consider it's copy constructor even if you are not going to use it
anywhere. The same for features: it is always nice to have full set of
possibilities at hand.


> > Just like in case of
> >template typedef -- templates were introduced long ago, but
> >'templatedef' was forgotten and now it cannot get into standard for
> >quite a long time.
>
> I very much doubt that it was simply forgotten. When we came to study it
> for the coming revised Standard we were only mildly surprised by just
> how complex the issue was. Had we included a template typedef in the
> current version we would have got it wrong and it would then have been
> ten years too late to get it right.

Hmm... Could you give me any direction which leads to answer to this
question:
what is wrong with construction like this:

template<class T> class type {};
template<class T, class U> class ptr {};

templatedef<class T, class U> ptr< T, type<U> > TmplAlias;
?

I understand that people who consider template typedef have found
something bad -- I like to know what.


> >Well, from my point of view non- and destructive semantic are mostly
> >interchangeable. Main difference between them is that in non- case you
> >will pay extra: default constructor call, swap, destructor; while
> >destructive move is cheaper.
>
> And those who have actually looked and tried it seem to disagree with
> you. Between theoretical performance and measured performance I am quite
> clear which I will believe.

:)) understandable... where can I read about this performance
comparison? how destructive semantic was implemented?


> >Also appearance of 'move' in C++ will change coding style dramatically,
> >I believe. From that point every associated resource could be
> >fearlessly encapsulated into the class; PODs will become rare (people
> >use POD structures mostly because it is more efficient with
> >containers); horrible stuff like auto_ptr's copy constructor will go
> >away; people will be more convinced to replace 'operator new' with
> >something new :) that returns not plain pointer but object that will
> >free associated variable upon destruction (i.e. memory leaks will go to
> >museum) and so on and so on.
>
> I think that the results will  be much, much smaller than you seem to
> think. And changes will take much longer.

Maybe. Depends how much people will be resisting ;)


> Then, it seems you did not do the background research that would have
> given your paper adequate underpinning. I suspect that you do not
> understand the number of hours invested in even the simplest of
> proposals. I think your time would be much better spent working within
> the current proposals and investigating if minor changes would give you
> more of what you want. At this late stage (yes, it is late even for a
> Standard planned to ship in 2009) that is probably the most constructive
> way you could work.

Yes, I did not researched deep enough. But this does not prevents me
from rambling on public newsgroup.


> Unfortunately you only have a couple of years to finish. Actually much
> less than that because we (WG21) are already in a position where we will
> have to triage proposals and the basis of how much time it will take to
> refine them and incorporate them into the Working Paper.

We'll see. In the worst case I'll get some experience from all of this.

If you are interested -- why do not you ask specific questions, like:
- how compiler supposed to implement feature X?
- which syntax do you propose?
- how implementation of vector.insert will look like?

Imho -- in this way it would be more productive...


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/2/2005 9:49:37 AM

Michael Pryhodko wrote:
> > With copy semantics the time complexity of the insert is O(n*m).
>
> :) imho it is O((n+1)*m) + C, but that is not important. Also if 'int'
> is not POD this figure will be bigger.
>
>
> > With non-destructive move semantics the time complexity of the insert is
> > O(n).
> > With destructive move semantics the time complexity of the insert is
> > O(n).
>
> O(n+1) for destructive move
> O(2*n+1) + C for non-destructive move
> O(3*n + 1) + C for 'swap' case

You appear not to understand the O() notation.  To say that a function
f(n,m,...) is big-O some other function g(n,m,...) is to say that there
exists values j and K, such that for all n>j, f(n,m,...) <=
K*g(n,m,...).

It says NOTHING about how big k has to be, or the size of the constant
K, it only speaks about the relative speed of increase of the two
functions.


Thus while your statements are true, it would ALSO be true to describe
destructive move as being O(500n + 25).  It would be more conventional
to describe all three cases as being O(n) (but with different
constants).

Howard's point is that changing O(nm) to O(n) is a "big" win, whereas
changing the constant K from 3 to 1 is not so significant.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Martin 6/2/2005 12:46:03 PM

In article <1117674472.454209.85160@g43g2000cwa.googlegroups.com>, 
Michael Pryhodko <mpryhodko@westpac.com.au> writes
>And if you wish to participate this discussion on 'non-destructive
>side', why do not you provide simple 'few words' description of use
>case which proves that destructive move proposed by me is wrong? ;)

Because I have not said it is wrong, just that the onus is on you to 
persuade me, among others, that your proposal is valuable enough to 
invest the extra resources needed to achieve it. There are a vast number 
of things that we could add to the Standard, but even if our resources 
were not heavily limited we would not want to add them all even though 
individual proposals might be excellent. We already have a very large 
language which is littered with awkward corner cases. One of our primary 
objectives this time is to reduce those. That means that we will be very 
circumspect about what we add.



-- 
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Francis 6/2/2005 12:46:25 PM

In article <1117674472.454209.85160@g43g2000cwa.googlegroups.com>, 
Michael Pryhodko <mpryhodko@westpac.com.au> writes
>Sorry, Francis, but without posting my thoughts to public newsgroup I
>can not get required 'many eyes'. And I told before that indeed it is a
>difficult thing to consider every implication of implementing my ideas
>into C++. Also I told that I do not have much of time to do it alone --
>I simply cannot dedicate all my time to this feature: my friends
>already noticed that my mailing domain changed to com.au not long ago
>-- so I have a huge amount of problems and tasks before me right now
>which is not C++-related.

Then there are three viable options:

1) Start from a base of the existing proposals, understand them and 
introduce yourself to their authors and offer to work with them

2) Read the exist proposals and then post comments and suggested 
amendments to comp.std.c++ where the majority of the active participants 
are well familiar with the Standard and with problems of changing it

3) Join your National Body committee/panel or whatever and work through 
them. However I note that this may not be an option for you because a 
couple of years ago Australia dropped out of SC22. However, at some 
cost, J16 (US) will accept membership from anywhere.

It is exactly that you do not have time to do it all which is why you 
need to team up with others who share (at least in part) your 
objectives.


-- 
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Francis 6/2/2005 12:46:47 PM

> > > template<class T>
> > > void insert_move(size_t pos, T% var_name)
> >
> > The link above is actually talking about insert_copy, not insert_move.
> > That is, what do you do if the /copy/ construction from var_name throws
> > an exception?  I would be interested in seeing your pseudo code for
> > that.
>
> Sure, here it is:
>
> #include "previous_stuff" :)
>
> template<class T, arg_list Rest>
> void insert_copy(size_t pos, T val, Rest)
> {
>      insert_move(pos, val, Rest);
> }
>
> or caller could do it himself:
>
> {
>      T var(...);
> ...
>      v.insert_move(pos, T(var), move_arg1, ...);
> }
>

Hmm.. In this case var will be 'copy construct'ed and then moved. We
could evade movement by 'copy construct'ing right inside of vector's
buffer, but since copy constructor could fail we need to store m_buf[i]
binary representation somewhere in order to rollback. I.e. smth like
this:

template<class T>
void insert_move(size_t pos, T const& var)
{
     // phase 1 -- could throw
     // move_1 right part of buffer
     for(size_t i = size(); i > pos; --i)
     {
         move_1(m_buf[i - 1] ==> m_buf[i]);
     }

     // remember m_buf[pos]'s binary representation
     // and returns it back in case of exception
     auto_hold_data<T> auto_data(m_buf[pos]);

     // copy construct T at m_buf[pos]
     m_buf[pos].T(var);
     // or in pseudocode:  construct(m_buf[pos], var);

     // phase 2 -- throw()
     // finalize right part movement
     for(i = size(); i > pos; --i)
     {
         move_2(m_buf[i - 1] ==> m_buf[i]);
     }

     // deactivate auto_data
     auto_data.deactivate();
}


Looks really ugly, but as efficient as it could be. Maybe it is
possible to create nice syntax for that? And in this way it is possible
to insert-copy array of values atomically.

Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/2/2005 12:51:28 PM

In article <1117682707.753613.321500@g14g2000cwa.googlegroups.com>, 
Michael Pryhodko <mpryhodko@westpac.com.au> writes
>Hmm... Could you give me any direction which leads to answer to this
>question:
>what is wrong with construction like this:
>
>template<class T> class type {};
>template<class T, class U> class ptr {};
>
>templatedef<class T, class U> ptr< T, type<U> > TmplAlias;
>?
>
>I understand that people who consider template typedef have found
>something bad -- I like to know what.

In very simple terms we early (when considering it for the next version 
of C++) on discovered that there are two conflicting ideas as to what a 
template alias could mean. As that realisation was almost five years ago 
and we have done a great deal of work on the topic since I am not sure 
that I can clearly and simply explain what the two things were here and 
now.

The moral is that what appears absolutely clear and safe to a proposer 
can have quite unexpected problems.

Let me give you a more recent case, the proposal from me and Herb Sutter 
for delegating constructors. At first sight it all looks very clear and 
relatively simple. Yet hidden in that simplicity is a serious quest 
about when an object is fully constructed (and so would use the type's 
destructor should an exception be thrown). Is it fully constructed on 
the completion of the delegated constructor, or only on completion of 
all the constructors, including the whole chain of delegating 
constructors?

Yes, we did resolve that issue but the two authors of the paper were 
arguing for opposite resolutions. That fact was actually helpful to the 
Committee because they could see the issues fully worked out rather than 
suddenly being surprised by them at some later stage.


-- 
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Francis 6/2/2005 12:51:54 PM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

> {I have an increasing feeling that this thread would be much more at
> home in comp.std.c++. clc++m is really intended for matters concerned
> with using the current Standard C++ rather than an in depth discussion
> of a proposal for the next version. -mod}

OK, followups to this message are directed there.

> Ok, you got me here. Here is another idea:
> How we are doing the same thing in current C++? We are creating class
> like that:
>
> class T
> {
>      ... // members
>      bool bFlag;
>      ~T()
>      {
>          if (!bFlag)
>          {
>              ... // do usual destruction work
>          }
>      }
> };
>
> and then pass pointer to such object into f:
>
> {
>      T var(...);
>      f(&var); // inside f will call T::close() --> 'm_bFlag = true'
>      ...
> }
>
> all is ok. Now it should be clear how it could be implemented with
> destructive move:
>
> class T
> {
>      ... // no flag here
>      ~T()
>      {
>          ... // usual destruction work
>      }
> };
>
> void f(T% var_name)
> {
>      T tmp <== var_name; // destructive move
> }
>
> ...
> {
>      T var(...);
>      f(var);
> }
>
> Description of compiler behavior:
> for every scope-tied(local/temporary/static) variable compiler
> generates extra flag which follows that variable in memory and used as
> a 'destroyed' flag whenever variable should be automatically destroyed
> (also it could be used in DEBUG builds for diagnostics). Compiler
> supposed to detect every variable that could be destroyed
> 'unnaturally'. T% in f's declaration could be used as an indication
> that:
> - you could pass only scope-based variables here

That makes destructive move useless for very important things like
moving the elements of a vector.

> - this variable will be followed in memory by destroyed/init'ed flag
> (this fact will be used by f's implementation)
>
> Impacts:
> - extra stuff will be applied only for variables that could be
> destroyed in called functions
> - code becomes a bit cleaner -- you do not need to care for m_bFlag (or
> NULL values -- I hate them ;) ), it is automated by compiler
> - MSVC and GCC could implement this easily
> - size of stack could be slightly bigger, but I doubt it could cause
> any problems, especially considering that flag will be created for SOME
> instances of type T -- if we do it 'by hands' flag will be in EVERY
> instance of T (regardless of storage type).
>
> David, did I proved to you that this mechanism could be implemented
> efficiently?

No, this is just exactly the mechanism I thought you were proposing in
the first place.

>> > 1. Hmm, strange question. How do you measure 'C++ with templates'
>> > against 'C++ without them'? It is a feature -- you can not measure it's
>> > "performance".
>>
>> 'scuse me, but it's perfectly possible to make useful and instructive
>> measurements.  Howard Hinnant has done real performance measurements
>> of a standard library implemented with non-destructive move semantics
>> vs. one implemented without move semantics.
>
> I understand, but sometimes it is easy to estimate. In this case I do
> not have nor time nor sources nor experience building C++ compiler. So
> 'estimate using logic' is my only option.

No, there are still a few options left.  You can write the "equivalent
C++98 code" just like you were doing above as a way of demonstrating
how the compiler would implement move.  Then compare performance.
BTW, implicit move (destructive or otherwise) can be completely
emulated with library techniques so this should not be _too_ painful.
You can build a move-enabled STL library based on STLPort, for
example, to see what the effects are.

>> > 2. Difference between non- and destructive move is the same as between
>> > using swap and move -- in first case you will pay twice: for swap and
>> > for destruction of empty object, in second case you'll pay less than
>> > for 'swap'.
>>
>> Except that you additionally incur runtime costs for passing extra
>> parameters (according to you), and storing/checking these flags.
>> Until you measure how those costs trade off against the cost of
>> destroying empty objects, you can't claim your scheme is better.
>
> Considering poem above, can I claim it now?

'Fraid not.

>> if you want efficiency.  In all the cases where the compiler could
>> take advantage of an implicit move, it's _already_ allowed to elide
>> the copy today when passing to:
>>
>>    void func(string var);
>
> Oops... How it is allowed? what if you change 'var'?

The argument was already an rvalue; there's no code that can detect
your change because func has the only reference.  Otherwise, the
argument was an lvalue and it certainly wouldn't have been legal to
move implicitly for the same reasons you're concerned about.

>> The real advantage of
>>
>>    void func(string const& var);
>>
>> is that it saves copies when the argument is an lvalue and couldn't be
>> moved from anyway.
>
> In current C++ -- yes.

Also in C++ with move semantics (destructive or otherwise).

>> > If I'd have exact syntax, with every feature considered and described
>> > -- I'd put this post on comp.std.c++ :). Also let me point that C++ is
>> > ALREADY complicated and hard-to-use -- and 'move' feature could make it
>> > less complicated for use by removing some problems.
>>
>> Show me how.
>
> I am trying...
> 1. you could now hold complex values in the container without thinking
> how it will be moved inside

Already possible, with non-destructive move or even without a language
extension.

> 2. operator new now could return object instead of raw pointer (see 'my
> C++' for clues) -- this could solve everlasting memory leak problem (or
> at least it will make it hard to do any kind of leak)

I don't see how that helps.

> 3. look here:
> http://blogs.msdn.com/oldnewthing/archive/2005/05/18/419130.aspx
> What do you see here? I see: "If you wish speed and efficiency do not
> use classes -- use PODs". And this guy has quite big audience. That
> kind of crap will go to history -- aren't that great?

a. No it won't.  People are superstitious and will remain so
b. non-destructive move also allows speed and efficiency.

> Please, note that applies to both kind of 'move'... simply destructive
> one is more efficient

I am not convinced of that.

> while giving one extra opportunity to shoot yourself. Also my idea
> with two phased move and passing move context is 'more generic' --
> i.e. you could move objects which can not be moved by other means,

Example?

> also it could be used to create complex atomic-like updates.

What use is an "atomic-like" update?

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 6/2/2005 3:23:01 PM

In article <1117708331.135475.132510@g47g2000cwa.googlegroups.com>,
 "Michael Pryhodko" <mpryhodko@westpac.com.au> wrote:

> > #include "previous_stuff" :)
> >
> > template<class T, arg_list Rest>
> > void insert_copy(size_t pos, T val, Rest)
> > {
> >      insert_move(pos, val, Rest);
> > }
> >
> > or caller could do it himself:
> >
> > {
> >      T var(...);
> > ...
> >      v.insert_move(pos, T(var), move_arg1, ...);
> > }
> >
> 
> Hmm.. In this case var will be 'copy construct'ed and then moved. We
> could evade movement by 'copy construct'ing right inside of vector's
> buffer,

<nod> Exactly.  I always try to put something into its final place on 
the first copy/move for performance reasons.  Granted that isn't always 
possible (esp. when reading from input iterators) but I believe it is in 
this case.  For types where the expense of a move and copy are the same, 
a copy plus a move is just two copies, and twice as expensive as need be.

> but since copy constructor could fail we need to store m_buf[i]
> binary representation somewhere in order to rollback. I.e. smth like
> this:

Note that we do not require strong exception safety for this case, only 
basic.  And again the reason is performance.

> template<class T>
> void insert_move(size_t pos, T const& var)
> {
>      // phase 1 -- could throw
>      // move_1 right part of buffer
>      for(size_t i = size(); i > pos; --i)
>      {
>          move_1(m_buf[i - 1] ==> m_buf[i]);
>      }
> 
>      // remember m_buf[pos]'s binary representation
>      // and returns it back in case of exception
>      auto_hold_data<T> auto_data(m_buf[pos]);
> 
>      // copy construct T at m_buf[pos]
>      m_buf[pos].T(var);
>      // or in pseudocode:  construct(m_buf[pos], var);
> 
>      // phase 2 -- throw()
>      // finalize right part movement
>      for(i = size(); i > pos; --i)
>      {
>          move_2(m_buf[i - 1] ==> m_buf[i]);
>      }
> 
>      // deactivate auto_data
>      auto_data.deactivate();
> }
> 
> 
> Looks really ugly, but as efficient as it could be. Maybe it is
> possible to create nice syntax for that? And in this way it is possible
> to insert-copy array of values atomically.

I'm confused (which is my normal state ;-) ):  If I just concentrate on 
what is happening at m_buf[pos] I see:

move_1(m_buf[pos] ==> m_buf[pos+1]);
auto_hold_data<T> auto_data(m_buf[pos]);
construct(m_buf[pos], var);
move_2(m_buf[pos] ==> m_buf[pos+1]);

Exactly what are move_1 and move_2 doing to this location?

If move_1 modifies m_buf[pos] then the following auto_hold_data will be 
holding the wrong data.  So that first move_1 must be a copy-only 
operation (perhaps a memcpy but not a destruct?).

If the construct throws, who constructs a value back into m_buf[pos]?  
The answer is presumably auto_data, however does not m_buf[pos+1] own 
those resources now?  Or perhaps that is the job of move_2?

But if move_2 does anything at all, then it will be operating on the new 
value at m_buf[pos], not the old value.  Perhaps the functionality of 
move_2(x ==> y) is independent of the value at x?

Clarifications welcome.

> I understand your point, but it is very tempting to get more if it is
> possible.

I think we're in violent agreement on that point. :-)

> > Now the insert does not need to create the new internal buffer.  The
> > existing internal buffer has sufficient capacity.  The insert merely
> > needs to move existing data within the buffer to make room for the new
> > element.  Non-destructive move constructions and non-destructive move
> > assignments are better suited to this task than a destructive move, both
> > in terms of performance and code size (though both would still have the
> > same time complexity - and much improved over the time complexity
> > associated with internal copying).
> 
> Hmm... it seems I missed something, but in case of nondestructive move
> you are supposed to:
> - construct default value at n+1'th position
> - for every move from [i] to [i+1] you need to fill [i] with meaningful
> value -- if this is done with 'swap' you'll also have one extra copy to
> temporary variable

It is necessary to distinguish between a (non-destructive) move 
construction, and a move assignment.  The former has a target that is 
not yet constructed.  The latter has a target that is already 
constructed.

For every element that needs to be moved beyond the existing size, you 
move construct from within the vector to beyond the current size, 
increasing the size by one each time.  Each type gets to decide for 
itself how a move construct is implemented (and will then presumably be 
done in the most efficient way possible).

For scalars, a move construct and a copy construct are exactly the same 
operation (right down to the object code).  This leaves the source (from 
[i]) already filled with a valid value and the cost to do so is 0 
operations.

For user-defined types, a valid technique would be to default construct 
the target and then to swap source and target, as you suggest above.  
Another valid technique would be to memcpy from source to target and 
then to memset the source to 0.  Still another valid technique would be 
to memcpy from source to target and leave the source intact (just as is 
done for scalars).  And there will be types with internal references 
where a move construction is more complicated than any of these options.  
All of these techniques will be optimal for some types and not others.  
Only the class author can know for sure.  So just as the class author 
must write a copy constructor, he too must write a move constructor.

Unlike the copy constructor case, the current proposal does not advocate 
a compiler generated move constructor by default.  However there has 
been some discussion about letting the type author explicitly request a 
compiler generated move constructor (which would move construct each 
sub-object).

> This results in O(n) + C extra operations (O(2*n) + C in case of
> 'swap')
> This is still a bit more than in 'destructive move' case. This extra
> could be insignificant if you use complex types, but for small and
> easy-to-move types it could be relatively big. For example for this
> type:

<nod> Not pessimizing vector<pod> has been a driving force from the 
beginning.  Years ago a common suggestion was to just have vector always 
use swap when scooting around elements internally.  But as you point 
out, this can be disastrous for vector<pod>.  Thus the need for uniform 
syntax that means:

copy construct (source remains unchanged)
copy assign    (source remains unchanged)
move construct (source remains constructed)
move assign    (source remains constructed)
swap           (source and target values swapped)

and possibly:

move construct (source is destructed)

and I've even stumbled across minor use cases for:

move assign    (source is destructed)

-------

Let's look a little deeper at the situation where we need to move/copy a 
vector element from one place within the vector's size to another place 
within the vector's size.  Such an operation is common for both the 
erase and insert functions.

move(m_buf[i] ==> m_buf[j]);

Before the move, both m_buf[i] and m_buf[j] are constructed and possibly 
own resources.

But after the move what of m_buf[i]?  Left in a constructed or 
destructed state?

Before this (insert or whatever) operation is over, something from 
somewhere is either going to be moved into or copied into m_buf[i] so 
that it is once again in a valid constructed state.  If the move left 
m_buf[i] in a destructed state, the total sequence of operations on 
m_buf[i] will look something like:

transfer value from m_buf[i] to m_buf[j]
m_buf[i].~T();
::new (m_buf + i) T(new_value);

If the move left m_buf[i] in a constructed state, the total sequence of 
operations will look something like:

transfer value from m_buf[i] to m_buf[j]
m_buf[i] = new_value;

In general it has been my experience that it is faster to copy or move a 
new value into an already constructed object than to go through a 
destruct-construct sequence.  It isn't an order of magnitude difference.  
But this type of operation is going to be happening a lot, and we don't 
want to prematurely pessimize it.  For example consider the case that 
the value_type of the vector is vector<int> (i.e. the entire object is a 
vector<vector<int>>):

In the former (destruct) case ownership of the internal vector buffer 
has been transferred from m_buf[i] to m_buf[j], and m_buf[j] has deleted 
any buffer it might have previously owned.  Then, in the case that we 
are copying from new_value, a new buffer must be allocated for m_buf[i] 
in order to copy construct from new_value.

In the latter (non-destruct) case ownership of m_buf[i]'s buffer has 
again been transferred to m_buf[j].  But in this case m_buf[i] is left 
in a constructed state.  The logical thing to do is have m_buf[j] 
transfer ownerhip of its buffer to m_buf[i] instead of deallocating it 
(just do a swap(m_buf[i], m_buf[j])).  Now when we (copy) assign 
new_value to m_buf[i], there is a decent chance that m_buf[i] already 
has sufficient capacity (donated from m_buf[j]) to handle the assignment.

Using destructive move semantics for this case guarantees two trips to 
the heap:  a deallocation followed by an allocation.

Using non-destructive move semantics for this case, one might still have 
two trips to the heap.  But one might also get away with zero trips to 
the heap.  In a completely random situation, those odds are 50%, which 
would average out to one trip to the heap - or roughly twice as fast as 
the destructive case.

> Now I have some questions:

Sure!

> Objects could have external references that points to them. During
> 'move' they need to be updated and this 'update' could throw.

<nod>

> 1. What 'current' nondestructive semantic has to solve this task?

Nothing really.  The class author must code the move constructor or move 
assignment manually, and thus will manually fix up such references.  The 
Metrowerks implementation of all of the node-based containers do exactly 
this (they all are self referencing).  Same issue with swap.  For us 
these are all no-throw operations.

The current proposal requires for the containers (quoted from N1771):

> If the contained value_type alters the value of the source (even if the 
> source is an rvalue) when constructing or assigning, then the operation must 
> not throw an exception.

I.e. If you want to put a type into a std::container, then it must have 
a no-throw move constructor and a no-throw move assignment, else it must 
be CopyConstructible and CopyAssignable (which are allowed to throw, but 
are not allowed to modify the source).

The requirements for the std::algorithms are more relaxed.  They will 
maintain basic exception safety even if a move constructor or move 
assignment throws.

> 2. What will happen in insert_move example if one of objects' move
> constructor will throw during 'external references update'?

Exactly.  Disaster.  And the only cure I know of is to say "don't do 
that", just as we currently do for destructors (17.4.3.6p2).  But we 
still must allow copy constructors and copy assignment to throw and 
maintain existing exception safety guarantees.

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 6/2/2005 4:06:12 PM

> > :) imho it is O((n+1)*m) + C, but that is not important. Also if 'int'
> > is not POD this figure will be bigger.
> >
> > O(n+1) for destructive move
> > O(2*n+1) + C for non-destructive move
> > O(3*n + 1) + C for 'swap' case
>
> You appear not to understand the O() notation.  To say that a function
> f(n,m,...) is big-O some other function g(n,m,...) is to say that there
> exists values j and K, such that for all n>j, f(n,m,...) <=
> K*g(n,m,...).
>
> It says NOTHING about how big k has to be, or the size of the constant
> K, it only speaks about the relative speed of increase of the two
> functions.
>
> Thus while your statements are true, it would ALSO be true to describe
> destructive move as being O(500n + 25).  It would be more conventional
> to describe all three cases as being O(n) (but with different
> constants).

Indeed, exactly 10 years passed since I was working with O's and o's
definitions in University. And I do not remember their exact
definition. But I think I still understand their meaning quite
correctly.
Also I think that O(3*n + 1) could be reduced as O(n) + C. But:

- evaluations above were derived from the same source
- no reducing/cancelling was applied

that means that we could evaluate !relative! complexity of these
processes using these formulas. I think Howard understood what I meant
:)


> Howard's point is that changing O(nm) to O(n) is a "big" win, whereas
> changing the constant K from 3 to 1 is not so significant.

if he'd used vector<vector<vector<int>>> for this example the win would
be O(xyz) against O(x). :))
However I think that moveing from O(3*n+1) + C to O(n+1) is still
important even in this light.


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Michael 6/3/2005 7:52:43 AM

[according to moderator's will I am trying to move this thread to
comp.std.c++'s processor :-)]


> Note that we do not require strong exception safety for this case, only
> basic.  And again the reason is performance.

Hmm... anyway -- we could get strong guarantee here with efficient
implementation. If every vector's operation could have it -- it is
easier for developer to use vector, because now he won't need to care
about it -- any operation either fail, leaving vector in the previous
state, or succeeds completely. How do you think -- what percentage of
C++ developers over the world knows what is 'strong exception safety'?
;)


> > template<class T>
> > void insert_move(size_t pos, T const& var)
> > {
> >      // phase 1 -- could throw
> >      // move_1 right part of buffer
> >      for(size_t i = size(); i > pos; --i)
> >      {
> >          move_1(m_buf[i - 1] ==> m_buf[i]);
> >      }
> >
> >      // remember m_buf[pos]'s binary representation
> >      // and returns it back in case of exception
> >      auto_hold_data<T> auto_data(m_buf[pos]);
> >
> >      // copy construct T at m_buf[pos]
> >      m_buf[pos].T(var);
> >      // or in pseudocode:  construct(m_buf[pos], var);
> >
> >      // phase 2 -- throw()
> >      // finalize right part movement
> >      for(i = size(); i > pos; --i)
> >      {
> >          move_2(m_buf[i - 1] ==> m_buf[i]);
> >      }
> >
> >      // deactivate auto_data
> >      auto_data.deactivate();
> > }
> >
> >
> > Looks really ugly, but as efficient as it could be. Maybe it is
> > possible to create nice syntax for that? And in this way it is possible
> > to insert-copy array of values atomically.
>
> I'm confused (which is my normal state ;-) ):  If I just concentrate on
> what is happening at m_buf[pos] I see:
>
> move_1(m_buf[pos] ==> m_buf[pos+1]);
> auto_hold_data<T> auto_data(m_buf[pos]);
> construct(m_buf[pos], var);
> move_2(m_buf[pos] ==> m_buf[pos+1]);
>
> Exactly what are move_1 and move_2 doing to this location?

move_1 does not change source. It is purpose:
if object can be moved by memcpy (has not external references) does
nothing at all
otherwise -- prepares helper_obj (located for example in local storage)
of type defined by move_1's implementation. helper_obj state will be
used in move_2 to 'finalize' move or to 'undo' move preparations in
case of exception.

move_2:
implicitly copies object binary representation into new place and
executes whatever instruction T has in it's move_2. Exceptions are
forbidden.

Please note that this example gives strong guarantee, and for types
with no-throw copy constructor it is possible to get top performance by
detecting that 'auto_data' is unnecessary. Have not got a foggiest idea
how to do it -- maybe smart optimizer? :).


> > Hmm... it seems I missed something, but in case of nondestructive move
> > you are supposed to:
> > - construct default value at n+1'th position
> > - for every move from [i] to [i+1] you need to fill [i] with meaningful
> > value -- if this is done with 'swap' you'll also have one extra copy to
> > temporary variable

[skip]

> For user-defined types, a valid technique would be to default construct
> the target and then to swap source and target, as you suggest above.
> Another valid technique would be to memcpy from source to target and
> then to memset the source to 0.  Still another valid technique would be
> to memcpy from source to target and leave the source intact (just as is
> done for scalars).  And there will be types with internal references
> where a move construction is more complicated than any of these options.
> All of these techniques will be optimal for some types and not others.
> Only the class author can know for sure.  So just as the class author
> must write a copy constructor, he too must write a move constructor.

It is still leaves us with extra-work for user-defined types:
for each i in [size(),pos)
{
    when moving from [i] to [i+1] do extra work:
        make it so that [i] is left in valid destructible state
}


> Unlike the copy constructor case, the current proposal does not advocate
> a compiler generated move constructor by default.  However there has
> been some discussion about letting the type author explicitly request a
> compiler generated move constructor (which would move construct each
> sub-object).

Hmm... in my case move_X are implicitly generated -- just like
constructors. And behaves in ways similar to constructors -- makes it
look more convenient for C++ developer to accept (I hope).


> > This results in O(n) + C extra operations (O(2*n) + C in case of
> > 'swap')
> > This is still a bit more than in 'destructive move' case. This extra
> > could be insignificant if you use complex types, but for small and
> > easy-to-move types it could be relatively big. For example for this
> > type:
>
> <nod> Not pessimizing vector<pod> has been a driving force from the
> beginning.  Years ago a common suggestion was to just have vector always
> use swap when scooting around elements internally.  But as you point
> out, this can be disastrous for vector<pod>.  Thus the need for uniform
> syntax that means:
>
> copy construct (source remains unchanged)
> copy assign    (source remains unchanged)
> move construct (source remains constructed)
> move assign    (source remains constructed)

I can't see where vector needs these two. Well, it could be useful for
fixed-size vector, where insert into full vector causes highest value
to 'fall out'. But as I'll show later it should be part of vector, not
move semantic and could be implemented efficiently without these two.


> swap           (source and target values swapped)

In my case 'swap' is provided by language itself based on T's move
definition.


> and possibly:
>
> move construct (source is destructed)
>
> and I've even stumbled across minor use cases for:
>
> move assign    (source is destructed)
>
> -------
>
> Let's look a little deeper at the situation where we need to move/copy a
> vector element from one place within the vector's size to another place
> within the vector's size.  Such an operation is common for both the
> erase and insert functions.
>
> move(m_buf[i] ==> m_buf[j]);
>
> Before the move, both m_buf[i] and m_buf[j] are constructed and possibly
> own resources.
>
> But after the move what of m_buf[i]?  Left in a constructed or
> destructed state?

1. you can not put two values into one variable. That means if you
whant to put giraffe into fridge you need to take out elephant first.
:))
2. should be implemented like this:
move_1(m_buf[i] ==> m_buf[j]); // could throw
m_buf[j].~T(); // should not throw
move_2(m_buf[i] ==> m_buf[j]); // throw()

on success: m_buf[j] hold previos value of m_buf[i], m_buf[i] is
undefined (i.e. this variable has no value in it)

this gives us atomic move to defined variable.


> Before this (insert or whatever) operation is over, something from
> somewhere is either going to be moved into or copied into m_buf[i] so
> that it is once again in a valid constructed state.

Wait a second! If you a going to insert something into vector you do
not ever need to perform 'move to defined variable' operation. In
pseudocode above every move is 'from defined to undefined'.


>  If the move left
> m_buf[i] in a destructed state, the total sequence of operations on
> m_buf[i] will look something like:
>
> transfer value from m_buf[i] to m_buf[j]
> m_buf[i].~T();
> ::new (m_buf + i) T(new_value);
>
> If the move left m_buf[i] in a constructed state, the total sequence of
> operations will look something like:
>
> transfer value from m_buf[i] to m_buf[j]
> m_buf[i] = new_value;
>
> In general it has been my experience that it is faster to copy or move a
> new value into an already constructed object than to go through a
> destruct-construct sequence.  It isn't an order of magnitude difference.
> But this type of operation is going to be happening a lot, and we don't
> want to prematurely pessimize it.  For example consider the case that
> the value_type of the vector is vector<int> (i.e. the entire object is a
> vector<vector<int>>):
>
> In the former (destruct) case ownership of the internal vector buffer
> has been transferred from m_buf[i] to m_buf[j], and m_buf[j] has deleted
> any buffer it might have previously owned.  Then, in the case that we
> are copying from new_value, a new buffer must be allocated for m_buf[i]
> in order to copy construct from new_value.
>
> In the latter (non-destruct) case ownership of m_buf[i]'s buffer has
> again been transferred to m_buf[j].  But in this case m_buf[i] is left
> in a constructed state.  The logical thing to do is have m_buf[j]
> transfer ownerhip of its buffer to m_buf[i] instead of deallocating it
> (just do a swap(m_buf[i], m_buf[j])).  Now when we (copy) assign
> new_value to m_buf[i], there is a decent chance that m_buf[i] already
> has sufficient capacity (donated from m_buf[j]) to handle the assignment.
>
> Using destructive move semantics for this case guarantees two trips to
> the heap:  a deallocation followed by an allocation.
>
> Using non-destructive move semantics for this case, one might still have
> two trips to the heap.  But one might also get away with zero trips to
> the heap.  In a completely random situation, those odds are 50%, which
> would average out to one trip to the heap - or roughly twice as fast as
> the destructive case.

This advantage comes from the knowledge of std::vector's nature:
- vector's resource is a chunk of memory filled with values ot type T
- if target's buffer is large enough we could 'take a shortcut' by
moving elements instead of destroying target and moving vector's state.

But:
- there is a price: target's reserved space could be too big -- I do
not like the idea of big chunk of memory forever hanging around
- the same effect could be reached with destructive move:

insert_copy(T const& new_val)
{
        swap(m_buf[i], m_buf[j]); // it could be implemented using move, see
'paper'
        m_buf[i] = new_val; // here vector will decide: 2 trips to heap or 0
}

Anyway -- problem you have described is not a problem of 'move'. It is
a problem of 'how to implement insert_copy which will involve moving to
defined variable internally'. And I think that problem should be
adressed by insert_copy implementation based on knowledge of current
move semantic implementation or T's specific. As I showed to you it
implements independently of move semantic type.

More thoughts:
suppose we are working with vector1<vector2<T>>

since advantage comes from vector's ability to use big enough MEMORY
chunk from other vector we could:
1. use 'generic' method described at the beginning
2. vector2's allocator could reuse freed chunks (for example through
static cache)

In this way we will get almost the same situation: 50% chance of going
into the heap. Difference will be that in this case insert_copy will
generate N calls to T's copy constructor, while in swap'based it will
be N T's operator=s. And now it depends on T's implementation what is
faster.

Nah, definitely that sort of optimization should be part of vector's
logic, not move semantic. Insert_copy's implemetor will have two
options: either use generic one or specific one -- and this is good to
have a choice.


> > Objects could have external references that points to them. During
> > 'move' they need to be updated and this 'update' could throw.
>
> <nod>
>
> > 1. What 'current' nondestructive semantic has to solve this task?
>
> Nothing really.  The class author must code the move constructor or move
> assignment manually, and thus will manually fix up such references.  The
> Metrowerks implementation of all of the node-based containers do exactly
> this (they all are self referencing).  Same issue with swap.  For us
> these are all no-throw operations.
>
> The current proposal requires for the containers (quoted from N1771):
>
> > If the contained value_type alters the value of the source (even if the
> > source is an rvalue) when constructing or assigning, then the operation must
> > not throw an exception.
>
> I.e. If you want to put a type into a std::container, then it must have
> a no-throw move constructor and a no-throw move assignment, else it must
> be CopyConstructible and CopyAssignable (which are allowed to throw, but
> are not allowed to modify the source).
>
> The requirements for the std::algorithms are more relaxed.  They will
> maintain basic exception safety even if a move constructor or move
> assignment throws.
>
> > 2. What will happen in insert_move example if one of objects' move
> > constructor will throw during 'external references update'?
>
> Exactly.  Disaster.  And the only cure I know of is to say "don't do
> that", just as we currently do for destructors (17.4.3.6p2).  But we
> still must allow copy constructors and copy assignment to throw and
> maintain existing exception safety guarantees.

I do not like it. :-| No offence. All of this sounds like complication
of existing state of things.


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

[ 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                       ]

0
Reply Michael 6/3/2005 3:21:01 PM

David Abrahams wrote:
> "Michael Pryhodko" <mpryhodko@westpac.com.au> writes:
>
> > {I have an increasing feeling that this thread would be much more at
> > home in comp.std.c++. clc++m is really intended for matters concerned
> > with using the current Standard C++ rather than an in depth discussion
> > of a proposal for the next version. -mod}
>
> OK, followups to this message are directed there.

David did a mistake typing comp.std.c++, so this message will apear on
comp.std.c++ first. :)



> > Ok, you got me here. Here is another idea:
> > How we are doing the same thing in current C++? We are creating class
> > like that:
> >
> > class T
> > {
> >      ... // members
> >      bool bFlag;
> >      ~T()
> >      {
> >          if (!bFlag)
> >          {
> >              ... // do usual destruction work
> >          }
> >      }
> > };
> >
> > and then pass pointer to such object into f:
> >
> > {
> >      T var(...);
> >      f(&var); // inside f will call T::close() --> 'm_bFlag = true'
> >      ...
> > }
> >
> > all is ok. Now it should be clear how it could be implemented with
> > destructive move:
> >
> > class T
> > {
> >      ... // no flag here
> >      ~T()
> >      {
> >          ... // usual destruction work
> >      }
> > };
> >
> > void f(T% var_name)
> > {
> >      T tmp <== var_name; // destructive move
> > }
> >
> > ...
> > {
> >      T var(...);
> >      f(var);
> > }
> >
> > Description of compiler behavior:
> > for every scope-tied(local/temporary/static) variable compiler
> > generates extra flag which follows that variable in memory and used as
> > a 'destroyed' flag whenever variable should be automatically destroyed
> > (also it could be used in DEBUG builds for diagnostics). Compiler
> > supposed to detect every variable that could be destroyed
> > 'unnaturally'. T% in f's declaration could be used as an indication
> > that:
> > - you could pass only scope-based variables here
>
> That makes destructive move useless for very important things like
> moving the elements of a vector.

Wait a second. It does not make whole 'destructive move' useless for
this. Only this function becomes useless. You can't get away from it!
If you are to move something scope-based you need to update something
(so that leaving the scope won't kill you). If you are moving value
from non-scoped variable -- you do not need to update anything.
Unfortunately that means we have a branch here. This problem could be
solved. For example I have some ideas:
- passing hidden flag (scope-based/free)
- checking in runtime variable address (stack-based variables sometimes
detectable in this way)
- having two function declaration that are doing the same -- one for
scope-based, another -- for the rest.

anyway it is solveable.



> > David, did I proved to you that this mechanism could be implemented
> > efficiently?
>
> No, this is just exactly the mechanism I thought you were proposing in
> the first place.

Cool... That means we invented this independendly :). But you should
agree -- this mechanism is efficient! It could even rise slightly
performance, since check for flag will be always 'inlined', while, when
flag is realized by developer, check for flag lies in destructor which
is not always inlined. In this way we avoid function call for already
destroyed variables.


> >> > 1. Hmm, strange question. How do you measure 'C++ with templates'
> >> > against 'C++ without them'? It is a feature -- you can not measure it's
> >> > "performance".
> >>
> >> 'scuse me, but it's perfectly possible to make useful and instructive
> >> measurements.  Howard Hinnant has done real performance measurements
> >> of a standard library implemented with non-destructive move semantics
> >> vs. one implemented without move semantics.
> >
> > I understand, but sometimes it is easy to estimate. In this case I do
> > not have nor time nor sources nor experience building C++ compiler. So
> > 'estimate using logic' is my only option.
>
> No, there are still a few options left.  You can write the "equivalent
> C++98 code" just like you were doing above as a way of demonstrating
> how the compiler would implement move.  Then compare performance.
> BTW, implicit move (destructive or otherwise) can be completely
> emulated with library techniques so this should not be _too_ painful.
> You can build a move-enabled STL library based on STLPort, for
> example, to see what the effects are.

Hmm... I should have thought about that. Shame on me :)


> >> > 2. Difference between non- and destructive move is the same as between
> >> > using swap and move -- in first case you will pay twice: for swap and
> >> > for destruction of empty object, in second case you'll pay less than
> >> > for 'swap'.
> >>
> >> Except that you additionally incur runtime costs for passing extra
> >> parameters (according to you), and storing/checking these flags.
> >> Until you measure how those costs trade off against the cost of
> >> destroying empty objects, you can't claim your scheme is better.
> >
> > Considering poem above, can I claim it now?
>
> 'Fraid not.

You are unbearable!


> >> > If I'd have exact syntax, with every feature considered and described
> >> > -- I'd put this post on comp.std.c++ :). Also let me point that C++ is
> >> > ALREADY complicated and hard-to-use -- and 'move' feature could make it
> >> > less complicated for use by removing some problems.
> >>
> >> Show me how.
> >
> > I am trying...
> > 1. you could now hold complex values in the container without thinking
> > how it will be moved inside
>
> Already possible, with non-destructive move or even without a language
> extension.

... but you always need to consider consequences. I think your
objective is wrong.


> > 2. operator new now could return object instead of raw pointer (see 'my
> > C++' for clues) -- this could solve everlasting memory leak problem (or
> > at least it will make it hard to do any kind of leak)
>
> I don't see how that helps.

It solves major problem of C++: newbies always mess things up. Now it
would be hard to make leak.


> > 3. look here:
> > http://blogs.msdn.com/oldnewthing/archive/2005/05/18/419130.aspx
> > What do you see here? I see: "If you wish speed and efficiency do not
> > use classes -- use PODs". And this guy has quite big audience. That
> > kind of crap will go to history -- aren't that great?
>
> a. No it won't.  People are superstitious and will remain so
> b. non-destructive move also allows speed and efficiency.

I told later that these arguments apply to both types of 'move'. People
tends to change.


> > Please, note that applies to both kind of 'move'... simply destructive
> > one is more efficient
>
> I am not convinced of that.

Could you give an example of case where nondestructive move is more
efficient?


> > while giving one extra opportunity to shoot yourself. Also my idea
> > with two phased move and passing move context is 'more generic' --
> > i.e. you could move objects which can not be moved by other means,
>
> Example?

see parallel conversation with Howard (insert_move and insert_copy).


> > also it could be used to create complex atomic-like updates.
>
> What use is an "atomic-like" update?

For example giving strong exception safety guarantee for
vector.insert.May I remind you that C++ class constructor is the fine
example of atomic-like update -- and it is used quite extensively.


Bye.
Sincerely yours, Michael.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

[ 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                       ]

0
Reply Michael 6/3/2005 3:21:01 PM

In article <1117760565.159819.142460@g47g2000cwa.googlegroups.com>,
 Michael Pryhodko <mpryhodko@westpac.com.au> wrote:

> > move_1(m_buf[pos] ==> m_buf[pos+1]);
> > auto_hold_data<T> auto_data(m_buf[pos]);
> > construct(m_buf[pos], var);
> > move_2(m_buf[pos] ==> m_buf[pos+1]);
> >
> > Exactly what are move_1 and move_2 doing to this location?
> 
> move_1 does not change source. It is purpose:
> if object can be moved by memcpy (has not external references) does
> nothing at all
> otherwise -- prepares helper_obj (located for example in local storage)
> of type defined by move_1's implementation. helper_obj state will be
> used in move_2 to 'finalize' move or to 'undo' move preparations in
> case of exception.
> 
> move_2:
> implicitly copies object binary representation into new place and
> executes whatever instruction T has in it's move_2. Exceptions are
> forbidden.

I'm sorry, but I'm still confused.  If move_1 does nothing at all for a 
pod, and move_2 memcpy's the pod, it looks to me like move_2 is going to 
be copying the wrong value because we've already constructed var at 
m_buf[pos].

> > For user-defined types, a valid technique would be to default construct
> > the target and then to swap source and target, as you suggest above.
> > Another valid technique would be to memcpy from source to target and
> > then to memset the source to 0.  Still another valid technique would be
> > to memcpy from source to target and leave the source intact (just as is
> > done for scalars).  And there will be types with internal references
> > where a move construction is more complicated than any of these options.
> > All of these techniques will be optimal for some types and not others.
> > Only the class author can know for sure.  So just as the class author
> > must write a copy constructor, he too must write a move constructor.
> 
> It is still leaves us with extra-work for user-defined types:
> for each i in [size(),pos)

I don't understand what the range [size(),pos) means.  Did you mean 
[pos, size())?

> {
>     when moving from [i] to [i+1] do extra work:
>         make it so that [i] is left in valid destructible state
> }

> > Unlike the copy constructor case, the current proposal does not advocate
> > a compiler generated move constructor by default.  However there has
> > been some discussion about letting the type author explicitly request a
> > compiler generated move constructor (which would move construct each
> > sub-object).
> 
> Hmm... in my case move_X are implicitly generated -- just like
> constructors. And behaves in ways similar to constructors -- makes it
> look more convenient for C++ developer to accept (I hope).

Implicitly generated copy constructors and assignment operators have 
been and will continue to be the source of a great many bugs.  This was 
a necessary evil for C compatibility.  We don't need to go that route 
for move semantics.

If the language can't guarantee that an implicitly generated move 
constructor (or assignment) is correct 100% of the time, we shouldn't be 
implicitly generating them.

> > move construct (source remains constructed)
> > move assign    (source remains constructed)
> 
> I can't see where vector needs these two. Well, it could be useful for
> fixed-size vector, where insert into full vector causes highest value
> to 'fall out'. But as I'll show later it should be part of vector, not
> move semantic and could be implemented efficiently without these two.

move construct is needed during insert (sufficient capacity case) for 
each existing element that needs to be moved beyond the current size().

move assign is needed during erase for each element moved to a lower 
position in the array, and for which the source of the move is to be 
left constructed after the erase (i.e. most elements if erasing only a 
few elements far from the end).  It is also needed during insert 
(sufficient capacity case) for each existing element that needs to be 
moved from its current location to a higher spot in the array but within 
the current size() (i.e. most elements if inserting only a few elements 
far from the end).

> > swap           (source and target values swapped)
> 
> In my case 'swap' is provided by language itself based on T's move
> definition.

This can be suboptimal for those classes that aren't movable with 
memcpy.  There are more reference fixup operations associated with 3 
moves than with a single swap.

> > Let's look a little deeper at the situation where we need to move/copy a
> > vector element from one place within the vector's size to another place
> > within the vector's size.  Such an operation is common for both the
> > erase and insert functions.
> >
> > move(m_buf[i] ==> m_buf[j]);
> >
> > Before the move, both m_buf[i] and m_buf[j] are constructed and possibly
> > own resources.
> >
> > But after the move what of m_buf[i]?  Left in a constructed or
> > destructed state?
> 
> 1. you can not put two values into one variable. That means if you
> whant to put giraffe into fridge you need to take out elephant first.
> :))

<shrug> Thanks, I'll keep that in mind.

> 2. should be implemented like this:
> move_1(m_buf[i] ==> m_buf[j]); // could throw
> m_buf[j].~T(); // should not throw

Why is m_buf[j] being destructed here?  Or is this a type-o?

> move_2(m_buf[i] ==> m_buf[j]); // throw()
> 
> on success: m_buf[j] hold previos value of m_buf[i], m_buf[i] is
> undefined (i.e. this variable has no value in it)
> 
> this gives us atomic move to defined variable.

Sorry, this is still unclear to me.  I'm afraid I need a bug-free 
description.  I'm making too many guesses at what you mean.

> > Before this (insert or whatever) operation is over, something from
> > somewhere is either going to be moved into or copied into m_buf[i] so
> > that it is once again in a valid constructed state.
> 
> Wait a second! If you a going to insert something into vector you do
> not ever need to perform 'move to defined variable' operation. In
> pseudocode above every move is 'from defined to undefined'.

<sigh>

vector-> _ _ _ _ _
            ^
            |
insert -----+

After the insert the element at v[2] will be moved to the location of 
v[3].  The element at v[2] will have a new value after the insert.

Before the insert both v[2] and v[3] are constructed.

After the insert both v[2] and v[3] are constructed.

What you do during the insert is an implementation detail.  If you want 
to destruct v[2] and re-construct it fine.  But I'm arguing that this is 
not efficient.  It is more efficient to leave v[2] constructed 
throughout the insert operation.  Same assertion applies to elements 
v[3] through v[size()-1].

> insert_copy(T const& new_val)
> {
>         swap(m_buf[i], m_buf[j]); // it could be implemented using move, see
> 'paper'
>         m_buf[i] = new_val; // here vector will decide: 2 trips to heap or 0
> }

The swap is inefficient for pods.  swap is the wrong semantics here.  
The value of m_buf[i] is not important after your swap statement because 
we are about to assign it a new value.  Move assign from m_buf[i] to 
m_buf[j] is what is required.  If a type implements move assign as a 
swap, fine.  But for pods it should be a plain copy.

> Anyway -- problem you have described is not a problem of 'move'. It is
> a problem of 'how to implement insert_copy which will involve moving to
> defined variable internally'. And I think that problem should be
> adressed by insert_copy implementation based on knowledge of current
> move semantic implementation or T's specific. As I showed to you it
> implements independently of move semantic type.

<shrug>

> More thoughts:
> suppose we are working with vector1<vector2<T>>
> 
> since advantage comes from vector's ability to use big enough MEMORY
> chunk from other vector we could:
> 1. use 'generic' method described at the beginning
> 2. vector2's allocator could reuse freed chunks (for example through
> static cache)

allocator caching is not something we want to tread on here.  That is an 
independent topic, at least if we want to continue to support user 
defined allocators.

> Nah, definitely that sort of optimization should be part of vector's
> logic, not move semantic. Insert_copy's implemetor will have two
> options: either use generic one or specific one -- and this is good to
> have a choice.

Move detection?  How?  I know of two solutions:  traits and concepts.  
Traits are intrusive and error prone (requires type author to register 
with trait).  Concepts may or may not happen.  I don't want to hinge the 
success of move semantics on concepts.

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

0
Reply hinnant 6/3/2005 8:56:09 PM

Howard Hinnant wrote:
>
> The current proposal requires for the containers (quoted from N1771):
>
> > If the contained value_type alters the value of the source (even if the
> > source is an rvalue) when constructing or assigning, then the operation must
> > not throw an exception.
>

I have a question about a possible interpretation of this.

Is a move constructor which uses the following two stage process
allowed?

   1) Stage 1 may throw, but does not alter the source
   2) Stage 2 alters the source, but is guaranteed not to throw

I can see real advantages to allowing this behaviour. On the down-side,
it's harder to write algorithms using move operations if you can't
assume they are no-throw. I haven't yet thought of any cases where it
forces inefficiency, though.


The motivating case for this is a type composed in the following way:

  struct S
  {
    CheapToCopyButNotMoveable only_copyable; // copy constructor may
throw

    ExpensiveToCopyButMoveable movable;
  };

(The non-moveable type may be defined in a non-move-aware library, for
example)

Clearly, operations on a container of S could benefit greatly from S
defining the obvious move operators. These operations may throw.


James


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply James 6/4/2005 2:34:56 AM

Michael Pryhodko <mpryhodko@westpac.com.au> writes:

> David Abrahams wrote:
>> "Michael Pryhodko" <mpryhodko@westpac.com.au> writes:
>>
>> > {I have an increasing feeling that this thread would be much more at
>> > home in comp.std.c++. clc++m is really intended for matters concerned
>> > with using the current Standard C++ rather than an in depth discussion
>> > of a proposal for the next version. -mod}
>>
>> OK, followups to this message are directed there.
>
> David did a mistake typing comp.std.c++, so this message will apear on
> comp.std.c++ first. :)

I don't know what you mean about mistakes.  Directing followups to
comp.std.c++ was entirely intentional.

>> > David, did I proved to you that this mechanism could be implemented
>> > efficiently?
>>
>> No, this is just exactly the mechanism I thought you were proposing in
>> the first place.
>
> Cool... That means we invented this independendly :). But you should
> agree -- this mechanism is efficient! 

I don't see why I should agree.  You're inserting tests and branches
that would otherwise be unneeded.

> It could even rise slightly performance, since check for flag will
> be always 'inlined', while, when flag is realized by developer,
> check for flag lies in destructor which is not always inlined. In
> this way we avoid function call for already destroyed variables.

And if there's no flag at all it's even more efficient.

>> >> > 2. Difference between non- and destructive move is the same as between
>> >> > using swap and move -- in first case you will pay twice: for swap and
>> >> > for destruction of empty object, in second case you'll pay less than
>> >> > for 'swap'.
>> >>
>> >> Except that you additionally incur runtime costs for passing extra
>> >> parameters (according to you), and storing/checking these flags.
>> >> Until you measure how those costs trade off against the cost of
>> >> destroying empty objects, you can't claim your scheme is better.
>> >
>> > Considering poem above, can I claim it now?
>>
>> 'Fraid not.
>
> You are unbearable!

Please refrain from name-calling.  You don't have to carry on this
discussion with me if you find me unbearable.

>> >> > If I'd have exact syntax, with every feature considered and described
>> >> > -- I'd put this post on comp.std.c++ :). Also let me point that C++ is
>> >> > ALREADY complicated and hard-to-use -- and 'move' feature could make it
>> >> > less complicated for use by removing some problems.
>> >>
>> >> Show me how.
>> >
>> > I am trying...
>> > 1. you could now hold complex values in the container without thinking
>> > how it will be moved inside
>>
>> Already possible, with non-destructive move or even without a language
>> extension.
>
> .. but you always need to consider consequences. I think your
> objective is wrong.

I have no clue what you're talking about.

>> > 2. operator new now could return object instead of raw pointer (see 'my
>> > C++' for clues) -- this could solve everlasting memory leak problem (or
>> > at least it will make it hard to do any kind of leak)
>>
>> I don't see how that helps.
>
> It solves major problem of C++: newbies always mess things up. Now it
> would be hard to make leak.

I don't see how the change you're proposing makes it harder to leak.
You'd have to show some detailed examples for me to get it.

>> > 3. look here:
>> > http://blogs.msdn.com/oldnewthing/archive/2005/05/18/419130.aspx
>> > What do you see here? I see: "If you wish speed and efficiency do not
>> > use classes -- use PODs". And this guy has quite big audience. That
>> > kind of crap will go to history -- aren't that great?
>>
>> a. No it won't.  People are superstitious and will remain so
>> b. non-destructive move also allows speed and efficiency.
>
> I told later that these arguments apply to both types of 'move'. People
> tends to change.
>
>
>> > Please, note that applies to both kind of 'move'... simply destructive
>> > one is more efficient
>>
>> I am not convinced of that.
>
> Could you give an example of case where nondestructive move is more
> efficient?

I didn't say nondestructive move was more efficient.  I only said that
I'm not convinced your destructive move is more efficient than
nondestructive move.

>> > while giving one extra opportunity to shoot yourself. Also my idea
>> > with two phased move and passing move context is 'more generic' --
>> > i.e. you could move objects which can not be moved by other means,
>>
>> Example?
>
> see parallel conversation with Howard (insert_move and insert_copy).

Sorry, I've been watching, but I don't see such an example in
evidence.  If you don't feel like repeating yourself, post a google
groups link to the article and tell me what text to search for to see
the example.

>> > also it could be used to create complex atomic-like updates.
>>
>> What use is an "atomic-like" update?
>
> For example giving strong exception safety guarantee for
> vector.insert.

The strong guarantee is available for vector.insert today, in the case
where neither the element's copy nor its assign can throw an
exception.

With nondestructive move, we'll have the strong guarantee also in the
case where move construct and move assign can't throw an exception.

What new case of the strong guarantee does destructive move provide
for?

> May I remind you that C++ class constructor is the fine
> example of atomic-like update -- and it is used quite extensively.

No, you can't "remind" me, because I don't know what "atomic-like" is
supposed to mean, and I have never considered C++ ctors to be
"atomic-like."

Either an update is atomic or it's not.  An atomic-like operation is
not atomic, and I don't see how it being somehow "atomic-like" can be
useful to anyone.

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

0
Reply dave 6/4/2005 6:25:22 AM

In article <1117816249.590795.171390@f14g2000cwb.googlegroups.com>,
  "James Hopkin" <tasjaevan@gmail.com> wrote:

> Howard Hinnant wrote:
> >
> > The current proposal requires for the containers (quoted from N1771):
> >
> > > If the contained value_type alters the value of the source (even if the
> > > source is an rvalue) when constructing or assigning, then the operation
> > > must
> > > not throw an exception.
> >
>
> I have a question about a possible interpretation of this.
>
> Is a move constructor which uses the following two stage process
> allowed?
>
>    1) Stage 1 may throw, but does not alter the source
>    2) Stage 2 alters the source, but is guaranteed not to throw
>
> I can see real advantages to allowing this behaviour. On the down-side,
> it's harder to write algorithms using move operations if you can't
> assume they are no-throw. I haven't yet thought of any cases where it
> forces inefficiency, though.
>
>
> The motivating case for this is a type composed in the following way:
>
>   struct S
>   {
>     CheapToCopyButNotMoveable only_copyable; // copy constructor may
> throw
>
>     ExpensiveToCopyButMoveable movable;
>   };
>
> (The non-moveable type may be defined in a non-move-aware library, for
> example)
>
> Clearly, operations on a container of S could benefit greatly from S
> defining the obvious move operators. These operations may throw.

Good question.

I believe the answer is no.  The reason is that the container must deal
with multiple objects, and to gain the necessary exception safety,
nothing must throw across moving /all/ of the necessary values.

Consider vector<T>::reserve(size_type), which must have no effect if an
exception is thrown (strong guarantee). When the new size exceeds the
current capacity(), elements in the old data buffer must be moved to the
new data buffer. Once a single element is moved from the old buffer to
the new, the original vector is modified. If an exception is thrown
while moving the second element of the vector, neither the old buffer
nor the new one can be used to represent the vector's original state,
and an exception might equally well be thrown while trying to restore
the original buffer. Thus, move constructors used with the standard
library must not throw exceptions (if the move constructor alters the
source).

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 6/4/2005 12:24:48 PM

> > David Abrahams wrote:
> >> OK, followups to this message are directed there.
> >
> > David did a mistake typing comp.std.c++, so this message will apear on
> > comp.std.c++ first. :)
>
> I don't know what you mean about mistakes.  Directing followups to
> comp.std.c++ was entirely intentional.

- go to: http://tinyurl.com/8h3yr
- click 'show options'
- I see here something like this:
Newsgroups: comp.lang.c++.moderated, comp.sdtd.c++
Followup-To: comp.std.c++
From: David Abrahams <d...@boost-consulting.com>

as you can see newsgroups list has mistype in the newsgroup name. If
this is not your fault (maybe moderator's?) -- please, accept my
apologies, I thought you did it.


> > But you should agree -- this mechanism is efficient!
>
> I don't see why I should agree.  You're inserting tests and branches
> that would otherwise be unneeded.

I'll explain my point:
- we started with a problem:
template <class T>
void f(T& x)
{
    T y = destructive_move(x);
}
> How does code that calls f know whether to generate a destructor for
> the argument to f?

- I propose to use marking to indicate that f could destroy variable:
void f(T% x)
{
    T y = destructive_move(x);
}
we have two possibility:
1. if f was called with local/temporary/static variable as argument:
- compiler must detect it (it is easy) and append flag to variable's
memory representation (no losses here, since it is done on compile
stage)
- if f destroys x it should change this flag
- whenever execution leaves caller scope this flag must be used to
detect if destructor should be called

2. if f is called with variable with unknown origin it should be
considered that it does not bound to any automatic destruction
mechanism, we could:
- forbid passing such variables into f, because '%' means:
local/temp/static only. That is inconvenient -- user must overload f
with exactly the same body, but different header:
void f(T& x)
{
    T y = destructive_move(x);
}
- or compiler could help us here by:
a) generating new f's body if he detects that f is called with another
type of variable.
b) or generating f's body in a special way, for example:

  -> entry point for local/temp/static calls
  set flag to true // really depends on platform or compiler vendor
  -> entry point for vars with unknown status (flag is false by
default)
  ...
  destructive_move code
  if (flag)
      mark_variable_destroyed

(later-addition:
hmm... if we have N marked arguments, f's code should take care about
2^N possible arguments configuration, luckily we will rarely have many
marked arguments, but for cases of big N compiler could switch to:
z) or by passing additional hidden parameter which holds information
necessary to find if K-th argument was passed as local/temp/static
variable.
end-of-later-addition)

c) or some platforms could use tricks to pass this information: for
example if variable's address is less than X -> it is not from heap ->
it is local/temp/static variable.
(later-addition:
won't work if you pass address of local object's subobject (e.g element
of array)
end-of-later-addition)

well, can't invent anything else at this moment...


Also compiler could help us by detecting and warning against such code:
void f(T& x)
{
    T y = destructive_move(x); // caller is not prepared
}

Now I'll try to compare non- and destructive moves:
A) destructive.
losses:
1. extra bool in stack/static storage for variables that passed as
marked argument
2. f's payment for variable status detection support
3. f's payment for setting 'dead' flag if variable was destroyed
4. check for flag before calling destructor
gains:
5. destructor won't be called for moved variable

B) nondestructive:
losses:
1. payment for leaving source in valid 'minimal' state
2. payment for 'minimal state', e.g. checking for INVALID_HANDLE_VALUE
in destructor
gains:
<nothing that is not already listed in A)losses>


Here are some thoughts:
- A's losses are constant, B's -- increases with T's complexity (e.g.
if T is derived from another type), so in following notes I'll consider
that T is simple type, but we'll keep in mind that T's movement price
is a sum of subobjects' prices (in non-destructive case)
- sometimes T's 'minimal state' can not be expressed as NULL value of
one of it's members -- in this case we need to add bool member flag --
as result every instance of T will have increased size, while in
destructive case -- only those that are passed as marked arguments
- A.4 == to B.2 (if T is simple)


Hmm, from all this analysis it is hard to say which approach is
better... I am close to propose to forbid this 'marking' functionality
-- this will cross out A.1-A.4, making destructive move winner, but
leaving us without possibility to move local variables. Well, comments
are welcome.


> >> > 1. you could now hold complex values in the container without thinking
> >> > how it will be moved inside
> >>
> >> Already possible, with non-destructive move or even without a language
> >> extension.
> >
> > .. but you always need to consider consequences. I think your
> > objective is wrong.
>
> I have no clue what you're talking about.

I was talking about 'move' in general, i.e. with any 'move' destructive
or not.
Also 'two-phased move' (I do not know if it could be implemented with
non-destructive move) makes it even more better:
- complex updates to container's state could have strong safety
guarantee (i.e. either succeeded or failed and container is in previous
state) -- i.e. vector.insert now could have strong guarantee

In the light of these discussions I start thinking that 'two-phased'
feature maybe could be discussed separately from 'non- vs destructive'
subject. If it is possible to separate it from destructive move...

By the way, thanks to this discussion I did very disturbing discovery:
- in one of my projects I used small_map<T> class -- this is basically
a map built on top of vector (it was designed to hold small number of
values)
- vector is always sorted, small_map::insert is implemented with
vector::insert
- that means that if T's operator= throws vector will be left in valid
but undefined state, ruining program state
- glance into vector's code confirms my fears

Hmm... This reveleation comes to me as a shock. T could be a structure
with two std::string for example. This showed me how fundamental
problem exception safety is... And how badly we need strong guarantee
at as much places as we could get.



> > It solves major problem of C++: newbies always mess things up. Now it
> > would be hard to make leak.
>
> I don't see how the change you're proposing makes it harder to leak.
> You'd have to show some detailed examples for me to get it.

Note again that this apply for any kind of move. Also I suggest you to
look upon 'How C++ could look like' chapter in my paper, it could help
to understand my point. Now suppose:
- we have 'move' in C++ (plus implicit move) -- that means it is ok to
return object by value
- 'new' returns object, that will free associated memory in it's
destructor (it's more precise description is in paper)

Now:
- it is hard to make leak (you need to call specific function
explicitly to break link between handler and resource)
- and you do not risk to do an expensive copy accidentally, because
every time your handler will be moved, not copied

Pseudocode:
template<class T> handler<T> new(...);
handler<T> t = new T(...);

Also for convenience I was proposing:
- to merge C++ reference and C++ pointer functionality and use '&'
symbol to denote reference
- to use '*' symbol to denote handler

This idea is extremely 'raw', do not judge it too harshly. Any comments
are welcome.


> > Could you give an example of case where nondestructive move is more
> > efficient?
>
> I didn't say nondestructive move was more efficient.  I only said that
> I'm not convinced your destructive move is more efficient than
> nondestructive move.

If you take away 'two-phased' feature, my destructive move is typical
destructive move. What makes you uncertain about efficiency of
destructive move?


> >> > while giving one extra opportunity to shoot yourself. Also my idea
> >> > with two phased move and passing move context is 'more generic' --
> >> > i.e. you could move objects which can not be moved by other means,
> >>
> >> Example?
> >
> > see parallel conversation with Howard (insert_move and insert_copy).
>
> Sorry, I've been watching, but I don't see such an example in
> evidence.  If you don't feel like repeating yourself, post a google
> groups link to the article and tell me what text to search for to see
> the example.


> >> > also it could be used to create complex atomic-like updates.
> >>
> >> What use is an "atomic-like" update?
> >
> > For example giving strong exception safety guarantee for
> > vector.insert.
>
> The strong guarantee is available for vector.insert today, in the case
> where neither the element's copy nor its assign can throw an
> exception.
>
> With nondestructive move, we'll have the strong guarantee also in the
> case where move construct and move assign can't throw an exception.
>
> What new case of the strong guarantee does destructive move provide
> for?

destructive move itself does not make situation better. I was speaking
about 'my destructive move' which have 'two-phase' feature. It could
give strong guarantee while still being reasonable efficient.


> > May I remind you that C++ class constructor is the fine
> > example of atomic-like update -- and it is used quite extensively.
>
> No, you can't "remind" me, because I don't know what "atomic-like" is
> supposed to mean, and I have never considered C++ ctors to be
> "atomic-like."

For me 'atomic-like' means: ability of given operation to succeed
completely, or fail leaving environment in previous state. For example
if given function:
void f()
{
    m_vector1.push_back(1);
    m_vector2.push_back(1);
}
written so that it will behave 'atomic-like' it is very convenient to
use it. You never need to worry about state of your program when you
use it; just call it, catch exceptions and continue work. Generally if
you have to work only with 'atomic-like' functions developing is much
easier.


> Either an update is atomic or it's not.  An atomic-like operation is
> not atomic, and I don't see how it being somehow "atomic-like" can be
> useful to anyone.

Sorry for messy definition. Should have used something more
appropriate.


Bye.
Sincerely yours, Michael.

---
[ 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                       ]

0
Reply Michael 6/4/2005 2:46:28 PM

"Michael Pryhodko" <mpryhodko@westpac.com.au> writes:

> Hmm, from all this analysis it is hard to say which approach is
> better... 

That was my point.  They are close enough in efficiency from an
analytical point-of-view that only real performance measurements can
tell us anything.

> I am close to propose to forbid this 'marking' functionality
> -- this will cross out A.1-A.4, making destructive move winner, but
> leaving us without possibility to move local variables. Well, comments
> are welcome.

If you find yourself tempted to change your proposal in order to make
it "win" the contest, you probably are more attached to the idea of
having destructive move "win" than you are interested in having the
best alternative in the language.

>> >> > 1. you could now hold complex values in the container without
>> >> > thinking how it will be moved inside
>> >>
>> >> Already possible, with non-destructive move or even without a language
>> >> extension.
>> >
>> > .. but you always need to consider consequences. I think your
>> > objective is wrong.
>>
>> I have no clue what you're talking about.
>
> I was talking about 'move' in general, i.e. with any 'move' destructive
> or not.

"move" is a wrong objective?
Sorry, I'm baffled.

> Also 'two-phased move' (I do not know if it could be implemented with
> non-destructive move) makes it even more better:
> - complex updates to container's state could have strong safety
> guarantee (i.e. either succeeded or failed and container is in previous
> state) -- i.e. vector.insert now could have strong guarantee

I don't see how that could possibly be the case unless you are willing
to pay O(N) additional storage for the partially-moved objects.

> In the light of these discussions I start thinking that 'two-phased'
> feature maybe could be discussed separately from 'non- vs destructive'
> subject. If it is possible to separate it from destructive move...
>
> By the way, thanks to this discussion I did very disturbing discovery:
> - in one of my projects I used small_map<T> class -- this is basically
> a map built on top of vector (it was designed to hold small number of
> values)
> - vector is always sorted, small_map::insert is implemented with
> vector::insert
> - that means that if T's operator= throws vector will be left in valid
> but undefined state, ruining program state
> - glance into vector's code confirms my fears
>
> Hmm... This reveleation comes to me as a shock. T could be a structure
> with two std::string for example. This showed me how fundamental
> problem exception safety is... 

Yes.  Well, sort of; it really has nothing to do with exceptions
per se.  The fundamental problem is how to maintain program invariants
in the face of operations that can fail (by any means).

> And how badly we need strong guarantee at as much places as we could
> get.

No, read http://www.boost.org/more/generic_exception_safety.html
(originally published in M. Jazayeri, R. Loos, D. Musser (eds.):
Generic Programming, Proc. of a Dagstuhl Seminar, Lecture Notes on
Computer Science. Volume. 1766)

We need the strong guarantee exactly where it is "natural" for the
operation to provide it without imposing a big-O efficiency cost.  You
can always add a copy/swap layer on top of whatever is natural if
you're willing to make the operation expensive in order to get the
strong guarantee.

>> > It solves major problem of C++: newbies always mess things up. Now it
>> > would be hard to make leak.
>>
>> I don't see how the change you're proposing makes it harder to leak.
>> You'd have to show some detailed examples for me to get it.
>
> Note again that this apply for any kind of move. Also I suggest you to
> look upon 'How C++ could look like' chapter in my paper, it could help
> to understand my point. 

I find most of your paper very hard to read, so it doesn't help me to
understand very much of what you're saying.  However, what I can
understand seems to have some major holes.  You can't implement shared
ownership without GC or reference counting no matter how much move
semantics you are given.

> This idea is extremely 'raw', do not judge it too harshly. Any
> comments are welcome.

My only comment is that when proposing something as a better
alternative to a very complete and refined proposal, it's probably a
good idea not to argue too strongly while the idea is still 'raw.'

>> > Could you give an example of case where nondestructive move is more
>> > efficient?
>>
>> I didn't say nondestructive move was more efficient.  I only said that
>> I'm not convinced your destructive move is more efficient than
>> nondestructive move.
>
> If you take away 'two-phased' feature, my destructive move is typical
> destructive move. 

Well, two-phase and marking are completely independent issues, so no,
"your move" is not what people typically thought of as destructive
move in the past.  But if you take away marking...

> What makes you uncertain about efficiency of
> destructive move?

...people will need to reinvent marking "manually" somehow.  Plus the
programming model is very difficult.

>> What new case of the strong guarantee does destructive move provide
>> for?
>
> destructive move itself does not make situation better. I was speaking
> about 'my destructive move' which have 'two-phase' feature. It could
> give strong guarantee while still being reasonable efficient.

I doubt it, without extra storage.  I think you're ignoring composite
operations.

>> > May I remind you that C++ class constructor is the fine
>> > example of atomic-like update -- and it is used quite extensively.
>>
>> No, you can't "remind" me, because I don't know what "atomic-like" is
>> supposed to mean, and I have never considered C++ ctors to be
>> "atomic-like."
>
> For me 'atomic-like' means: ability of given operation to succeed
> completely, or fail leaving environment in previous state. 

That's just "atomic."

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

0
Reply dave 6/6/2005 2:10:32 AM

Howard Hinnant <hinnant@metrowerks.com> writes:

> In article <1117816249.590795.171390@f14g2000cwb.googlegroups.com>,
>   "James Hopkin" <tasjaevan@gmail.com> wrote:
>
>> Howard Hinnant wrote:
>> >
>> > The current proposal requires for the containers (quoted from N1771):
>> >
>> > > If the contained value_type alters the value of the source (even if the
>> > > source is an rvalue) when constructing or assigning, then the operation
>> > > must
>> > > not throw an exception.
>> >

I am fine-tuning some of Howard's answers here.

>> I have a question about a possible interpretation of this.
>>
>> Is a move constructor which uses the following two stage process
>> allowed?
>>
>>    1) Stage 1 may throw, but does not alter the source
>>    2) Stage 2 alters the source, but is guaranteed not to throw

Yes, it's allowed.  From the point of view of the rest of the program,
that's just a move ctor that gives the strong guarantee.

>> I can see real advantages to allowing this behaviour. On the down-side,
>> it's harder to write algorithms using move operations if you can't
>> assume they are no-throw. 

Actually, there's no problem with the algorithms.  It's the containers
that have special requirements w.r.t. elements not throwing from move.

>> I haven't yet thought of any cases where it forces inefficiency,
>> though.
>>
>>
>> The motivating case for this is a type composed in the following way:
>>
>>   struct S
>>   {
>>     CheapToCopyButNotMoveable only_copyable; // copy constructor may
>> throw
>>
>>     ExpensiveToCopyButMoveable movable;
>>   };
>>
>> (The non-moveable type may be defined in a non-move-aware library, for
>> example)
>>
>> Clearly, operations on a container of S could benefit greatly from S
>> defining the obvious move operators. 
>> These operations may throw.

Not so clear, really.  It's only possible to benefit if the required
operational semantics can be implemented ;-).  In this case, we don't
think they can be (in general).

> Good question.
>
> I believe the answer is no.  The reason is that the container must deal
> with multiple objects, and to gain the necessary exception safety,
> nothing must throw across moving /all/ of the necessary values.

That's certainly true for some containers...

> Consider vector<T>::reserve(size_type), which must have no effect if
> an exception is thrown (strong guarantee). When the new size exceeds
> the current capacity(), elements in the old data buffer must be
> moved to the new data buffer. Once a single element is moved from
> the old buffer to the new, the original vector is modified. If an
> exception is thrown while moving the second element of the vector,
> neither the old buffer nor the new one can be used to represent the
> vector's original state, and an exception might equally well be
> thrown while trying to restore the original buffer. Thus, move
> constructors used with the standard library must not throw
                    "containers"-------------^
> exceptions (if the move constructor alters the source).

Since he's been working on a move-aware standard library
implementation, Howard's in a better position than I am to say for
sure (it's been a while since I've thought about the details of
this)... but it seems to me that most of the containers other than
vector *could* be used with such a type.  vector<T>::reserve is a
multi-element commit-or-rollback operation, but the other containers
only give the strong guarantee for operations that might have to copy
a single element.

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

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply David 6/6/2005 7:21:37 AM

In article <u7jh89xli.fsf@boost-consulting.com>,
 David Abrahams <dave@boost-consulting.com> wrote:

> > Consider vector<T>::reserve(size_type), which must have no effect if
> > an exception is thrown (strong guarantee). When the new size exceeds
> > the current capacity(), elements in the old data buffer must be
> > moved to the new data buffer. Once a single element is moved from
> > the old buffer to the new, the original vector is modified. If an
> > exception is thrown while moving the second element of the vector,
> > neither the old buffer nor the new one can be used to represent the
> > vector's original state, and an exception might equally well be
> > thrown while trying to restore the original buffer. Thus, move
> > constructors used with the standard library must not throw
>                     "containers"-------------^
> > exceptions (if the move constructor alters the source).
> 
> Since he's been working on a move-aware standard library
> implementation, Howard's in a better position than I am to say for
> sure (it's been a while since I've thought about the details of
> this)... but it seems to me that most of the containers other than
> vector *could* be used with such a type.  vector<T>::reserve is a
> multi-element commit-or-rollback operation, but the other containers
> only give the strong guarantee for operations that might have to copy
> a single element.

I believe you're correct Dave.  Take std::list for example.  The only 
time a move constructor would be used is during an insert, push_front or 
push_back.  And in these cases, the move constructor could throw, and 
the list would still maintain the strong exception safety guarantee.  
And std::list will never use the value_type's move assign.

I will try to relax the wording in N1771 for the detailed proposal on 
chapter 23.

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply Howard 6/6/2005 2:38:47 PM

> > move_2:
> > implicitly copies object binary representation into new place and
> > executes whatever instruction T has in it's move_2. Exceptions are
> > forbidden.
>
> I'm sorry, but I'm still confused.  If move_1 does nothing at all for a
> pod, and move_2 memcpy's the pod, it looks to me like move_2 is going to
> be copying the wrong value because we've already constructed var at
> m_buf[pos].

Sorry for confusion, it is my mistake. memory for implicit memcpy
should be taken from auto_data. This makes it looking even more ugly
than it was before.

Hmm... I guess this happens because copy is one-shot operation, while
move is two-phased. If we could have two-phased copy (built in the same
way as 'move') it will fit nicely here:

move_1(m_buf[pos] ==> m_buf[pos+1]);
copy_1(var ==> m_buf[pos]);
move_2(m_buf[pos] ==> m_buf[pos+1]);
copy_2(var ==> m_buf[pos]);

but this is not gonna ever happen. So we have only options:
- trying to live with this uglification
- forfeit two-phased move (no strong guarantee in inserts, no complex
atomic updates)


> > It is still leaves us with extra-work for user-defined types:
> > for each i in [size(),pos)
>
> I don't understand what the range [size(),pos) means.  Did you mean
> [pos, size())?

Well, actually I tried to say (size(), pos], but it is not my fault --
it is all my keyboard. .) Strange order is to show that we traverse
backwards.


> > > move construct (source remains constructed)
> > > move assign    (source remains constructed)
> >
> > I can't see where vector needs these two. Well, it could be useful for
> > [skip]
>
> move construct is needed during insert (sufficient capacity case) for
> [skip]
> move assign is needed during erase for each element moved to a lower
> [skip]

You are thinking in terms of non-destructive move. But vector
operations could be implemented with destructive move (imho more
efficiently) -- in this case they are not needed.


> > In my case 'swap' is provided by language itself based on T's move
> > definition.
>
> This can be suboptimal for those classes that aren't movable with
> memcpy.  There are more reference fixup operations associated with 3
> moves than with a single swap.

No, there will be exactly two reference fixups. Pseudocode:
swap(x <==> y):
  move_1(x==>y)
  move_1(y==>x)
  swap_memory_bits
  move_2(x==>y)
  move_2(y==>x)

Please, note that:
- while I write second phase as move_2(A==>B), move_2 implementation
has access only to heper_obj and B.
- obviously move_2 should not do implicit memcpy, but since 'swap' is
entirely generated by compiler -- he could do everything here (or we
could select implicit memcpy of move_2 as independent step, thus
actually creating 3-phased move, exactly like I thought it should be
about 1 year ago)


> > 1. you can not put two values into one variable. That means if you
> > whant to put giraffe into fridge you need to take out elephant first.
> > :))
>
> <shrug> Thanks, I'll keep that in mind.

Ok, I'll be serious.


> > 2. should be implemented like this:
> > move_1(m_buf[i] ==> m_buf[j]); // could throw
> > m_buf[j].~T(); // should not throw
>
> Why is m_buf[j] being destructed here?  Or is this a type-o?

it is not a mistype. move_1 prepares value to be moved from buf[i] to
buf[j]. But before move is finalized we need to free buf[j] from value
it holds.


> > move_2(m_buf[i] ==> m_buf[j]); // throw()
> >
> > on success: m_buf[j] hold previos value of m_buf[i], m_buf[i] is
> > undefined (i.e. this variable has no value in it)
> >
> > this gives us atomic move to defined variable.
>
> Sorry, this is still unclear to me.  I'm afraid I need a bug-free
> description.  I'm making too many guesses at what you mean.

I proposed a way to do 'move-to-constructed' without need of
move-assignment:
- prepare move [i] -> [j]
- destroy [j]
- finalize move [i] -> [j]

this will give us strong guarantee regardless of type T.
I've spent some time thinking about nature of operator= and 'move
assign'. They have quite interesting features. At the end of this post
I'll try to list my thoughts, maybe you you'd like to comment.


> > > Before this (insert or whatever) operation is over, something from
> > > somewhere is either going to be moved into or copied into m_buf[i] so
> > > that it is once again in a valid constructed state.
> >
> > Wait a second! If you a going to insert something into vector you do
> > not ever need to perform 'move to defined variable' operation. In
> > pseudocode above every move is 'from defined to undefined'.
>
> <sigh>
>
> vector-> _ _ _ _ _
>             ^
>             |
> insert -----+
>
> After the insert the element at v[2] will be moved to the location of
> v[3].  The element at v[2] will have a new value after the insert.
>
> Before the insert both v[2] and v[3] are constructed.
>
> After the insert both v[2] and v[3] are constructed.
>
> What you do during the insert is an implementation detail.  If you want
> to destruct v[2] and re-construct it fine.  But I'm arguing that this is
> not efficient.  It is more efficient to leave v[2] constructed
> throughout the insert operation.  Same assertion applies to elements
> v[3] through v[size()-1].

we have: vector1<vector2<int>>

First: when you insert something into the vector1 at position [i] you
will never get anything useful here, because:
for each i in (size(), pos] { [i - 1]'s buffer will go to [i] }
that means after we finish all our moves [i] will hold something
default (zeros for example). that means in case of insert_copy there
will be always 1 trip to heap.
Second: I think I understood what you mean -- you think that 'move
assign' operator is needed in the same way why we need operator=. So
that for given type author could use alternative way for 'move'
designed using specific application rules. And you think if 'move
assign' is not destructive we could win in some scenarious. Right?

I'll try to describe such scenario:
- we have vector with a cap, i.e. it has maximum size 10
- vector1<vector2<int>> is full
- we are inserting at [i]

> It is more efficient to leave v[2] constructed
> throughout the insert operation.

1. No, it is not. It COULD be more efficient -- it depends on type T
specific.
2. you propose:
- to use use 'move assign' in order to shift elements in vector
- type T (vector2<int>) will swap internal state in it's 'move assign'
operator
- during [i] = new_val assignment if [i] is large enough we well have
zero trips to heap

But also this trick will give us inefficiency in some scenarios, e.g.
when you erase first element of vector: last element will be swapped
with previous and then destroyed, which is not as efficient as it could
be -- i.e. while you are gaining at one end, you lose at another. For
me it is disappointing because theoretically we could win at both ends.
I think vector1 should decide what to use to move element -- swap-based
non-destructive move or destructive move. And this decision should
based on operation type (insert, erase) and T's specific (int or
vector2<int>). Do not know how to do it, however. For example in this
case(using my move) vector could do:
- perform destructive move "in ring" i.e.: [size()-1]->[i], [i]->[i+1],
.., [size()-2]->[size()-1]
- do copy: [i] = new_val
but for PODs one move ([last] -> [i]) will be not needed (it is still
better than non-destructive). Also trying to implement this trick will
prevent us from having strong guarantee. Maybe it is still a good idea
to implement:

insert_copy(size_t pos, T const& val)
{
    insert_move(pos, T(val));
}

- for PODs it will be efficient
- for others we will get strong guarantee in exchange for some
efficiency
In realworld application I'd choose strong guarantee, because if this
operation fails vector will become destructible but invalid -- and
sometimes it is impossible to recreate it. I'd vote for this:
- vector is implemented with 'my' two-phased destructive move
- if vector's user thinks that assignment is better here he should:
 a) ask vector to do 'ring shift'
 b) assign [i] = new_val
   b1) if T's assignment is no-throw he will get strong guarantee
   b2) otherwise he may live with basic guarantee (for example if he
sure that no exception could happen, for example due to plentiness of
memory)
   b3) or if 'move' is a no-throw and T's assignment has a strong
guarantee, he could shift, assign, do backward shift if failed.
   b4) or use insert_move(pos, T(val))

Anyway decision is left to developer.


> Move detection?  How?  I know of two solutions:  traits and concepts.
> Traits are intrusive and error prone (requires type author to register
> with trait).  Concepts may or may not happen.  I don't want to hinge the
> success of move semantics on concepts.

I don't know. Maybe it is impossible to implement every possible
optimization using only move constructor and move assignment.



/////////////////////////////////////////////////////////////////
// general thoughts about copy constructors, operator= and others

copy constructor:
- used to make a copy at unitialized destination
- gives strong guarantee (as long as you nice in constructors' bodies)
- it is easy to get strong guarantee for multiple copy-construct
operations: just setup local object that will destroy already created
objects. Non-trivial objects are created in this way.

-----------------------
operator=:
now we need to copy to constructed variable. It could be done with code
like this:
target.~T();
target.T(source);
not very useful, however. Could be better:

copy_1(source ==> target); // prepares copy, uses extra memory if
needed
target.~T();
copy_2(source ==> target); // can not throw
this is much more useful:
- it gives strong guarantee for any T
- we could do more complex things like copying multiple variables and
still having a strong guarantee
- but this comes with a price of efficiency: we need to be pessimistic
and prepare very assignment using additional memory.
- also for some types it would be more efficient to reuse target's
state
Maybe that is why C++ used another approach -- separate function
'operator=':
- it is by default implemented as a sequence of member's operator=
- that means by default operator= gives only basic guarantee! it was a
surprise for me once:
struct { string s1; string s2;}
and
pair<int, string>
could break application in very mysterious way if you forget about it,
code
my_vec[5] = make_pair(15, "This is 15");
could fail leaving my_vec in destructible but unusable state. This
makes writing fail-proof code hard. You could try to get around that by
creating strong guarantee operator=:
operator=(T const& src, T& trg)
{
    T tmp(src);
    tmp.swap(trg);
}
this will have the same complexity as copy_1/copy_2 based approach. By
sacrificing optimistic performance we could gain strong guarantee for
one operation. But update to environment could be more that one
assignment and trying to make it having strong guarantee will involve
more losses:
- more operations needs to be 'prepared'
- more memory will be used
- more operations which are necessary only in pessimistic case

as problem escalates it becomes unmanageable. And there is no
copy_1/copy_2 in the language -- that means you will need to invent
your own mechanisms. I remember once I have implemented framework for
such 'transactional' programming. Needless to say performance was bad,
program execution path was very similar to RDMS query execution: every
action was creating an entry in transaction log (heap-based stack
structure) which used to rollback changes made so far if something goes
wrong. I had problems with updates from another threads, problems when
execution leaves my code. Basically at the end application was very
close to small memory-based database. That what happens when you try to
make totally fail-safe application by means of providing strong
guarantee on every operation.
As far as I understand to create reliable and efficient applications
you need to 'live with' basic guarantee, but never forget about
operations which have it. That means dividing application state into
weakly-dependent parts which could change state independently. And if
some basic guarantee operation fails -- drop/recreate whole part. For
example: server, where for each connected client there is a structure
of serving objects in memory -- if during request processing
basic-guarantee operation fails (e.g. due to std::bad_alloc) you could
drop connection and all state associated with it. Client will reconnect
later, but server application will be fail-safe and still efficient --
this scheme is a rollback but whithout expensive 'every action' logging
and rolling them back.

Also one more caveat -- in general compiler generated operator= does
not provide even basic guarantee. Example:
class A
{
    int m_v1;
    string m_data;
    int m_v2;  	// this should be equal to (m_v1 + 10)
};
If during assignment m_data's operator= fails target will be in invalid
(but technically destructible) state making program state corrupted.
During following destruction of such object result is undefined because
object invariant was not hold.

-----------------------
move constructor:
we need to move value from one place to another not initialized place
(lets leave non- vs destructive topic alone for a moment). Obviously,
objects without external references could be moved by memcpy. Lets
consider general case where reference fixups could throw.
- it is easy to get strong guarantee for trivial object
- it is impossible to get it for non-trivial objects without mechanism
similar to 'two-phased' move. To make things worse in general it is
impossible to get even basic guarantee! This is a major difference from
copy constructor -- we can't easily organise even basic guarantee for
multiple movement (i.e. movement of all T's subobjects). Suppose we
have:
class A : class B {};
A a_src(...);
..
A a_trg <== a_src;

if B was moved but A throws a_src will have state when B has 'what is
left after move' (destroyed in case of destructive move and 'empty' in
case of non-destructive) A-part will have constructed state. If this
state is valid (belongs to space of all possible a_src's states) -- we
will get basic guarantee here, otherwise -- not. Obviously it is almost
impossible to get it for destructive move in this case.
We could put two-phased move into the language (thus forever
sacrificing efficiency for optimistic case). Or we could use the same
approach as with operator=:
- if move fails source invariant should not be violated (rule wich must
be followed by developer) -- i.e. if you move any subobject of given
object, this object's state should be valid (with respect to
invariantness)
- this gives us basic guarantee (it is still worse than copy
constructor which gives strong g.) -- I am really worried how it will
be to develop with this 'peculiarity', it looks dangerous.
- if developer needs something more strong he should organise its own
transaction context (like with operator= -- making copies, whatever).
This is similar to this example:
T v1(...);
T v2 <== v1; // this gives us basic guarantee
if we need strong g. we need to do additional work:
T v1(...);
T v2 <== T(v1); // this gives us strong basic guarantee

This makes 'my two-phased' feature unnecessary and conforms to spirit
of C++ (efficiency is a top priority). I think, presence of
'two-phased' feature in language makes it easier to write code wich
gives strong guarantee, but now I am quite far from thought that it
*should* be in the language -- it seems it will never get there, maybe
for good. (thanks for paper, David, it really cleans brains)

------------------------
move assignment:
we need to move value to already constructed variable.
since 'two-phased' feature is inappropriate, everything here is similar
to operator=:
- move assignment should give at least basic guarantee:
  that means leaving BOTH target and source in valid state (hmm... it
could be a challenge in some cases, I think)
- all requirements from move constructor applies here


Consclusions:
-------------
- never let compiler to generate 'operator=' for you
- all pecularities with strong/basic guarantees should be clearly
described (in C++ standard, for example) -- so that newbies could get
necessary information immediately, instead of going through long and
painful self-learning process


Destructive vs Nondestructive:
------------------------------
Now based on previous thoughts I'll try to put some ideas about type of
move:
- it is clear that destructive move creates a problem: destroyed
subobject in C++ never was considered as a part of valid object state.
In discussion with David Abrahams there is a description of how
destructive move could be implemented in respect to move from local
storage -- performance is reasonable, but clearly this approach is
unsuitable for cases when we need to move subobject. And we need to do
it because two-phased move is basically out of field of view. That
leaves us with non-destructive move as the only option for generic move
implementation.
- on other hand there are plenty of cases where destructive move could
be more efficient that non-destructive -- for example inside of vector
some operations clearly more efficient with destructive move.

I have an idea:
- when do we need 'make source empty but valid' part of move?:
 a) if object bound to any auto-destruction mechanism
 b) otherwise only when something goes wrong
- what if we divide non-destructive move into two parts:
 1. destructive move part -- it moves object state to new variable
without concerning about source
 2. 'move init' function -- it is logically equivalent to default
constructor:
   - it should init object to some valid 'empty state'
   - it should never throw (very important)
 we could either create new member type (move_init) or state: in order
to get basic guarantee for move operations this object's default
constructor should not throw
- during move destructive part should be used, if it succeeds move_init
should be applied to source or not applied depending on circumstances.
In case of failure move_init will be called for every destroyed
subobject and execution will continue as usual (unwinding).

This mechanism will give us ability to implement wide range of
optimizations for vector's operations, while still giving top
performance in optimistic case. For example:
T a1(...);
T a2(...);
T a3 <== a2;
a2 <== a1;

in optimistic path of execution could look like:
create a1, a2;
move_construct_destructive a2 to a3;
move_construct_destructive a1 to a2;
move_init a1;

if any operation fails pessimistic execution path will move_init
necessary sub-/objects and use usual unwinding mechanism.

It is still unclear how to do vector<vector<int>>::insert_copy
optimization here... I need to think about it -- this post is already
too large.

(later) Hmm... it could be something like this:
T a1(...);
T a2(...);
T a3(...);
a2 ==> a3;
a1 ==> a2;

to use be able to use this technique 'move assignment' should be able
to indicate that move_init is unnecessary. Hmm... Looks ugly. Maybe you
have any ideas?


Bye.
Sincerely yours, Michael.

---
[ 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                       ]

0
Reply Michael 6/6/2005 10:01:03 PM

> > Hmm, from all this analysis it is hard to say which approach is
> > better...
>
> That was my point.  They are close enough in efficiency from an
> analytical point-of-view that only real performance measurements can
> tell us anything.

You are right. I found some logical problems with this approach. E.g.
it is still a problem to move subobjects and so on. Well, forget it --
it was a bad idea.


> If you find yourself tempted to change your proposal in order to make
> it "win" the contest, you probably are more attached to the idea of
> having destructive move "win" than you are interested in having the
> best alternative in the language.

I am trying to push destructive move because in wide range of cases it
gives better performance and looks more 'logical', for example when you
need to shift values inside of vector. But it seems that you can not
get away from non-destructive semantic completely.


> "move" is a wrong objective?
> Sorry, I'm baffled.

Forget this too, I used wrong word 'objective' instead of 'objection'.


> > Also 'two-phased move' (I do not know if it could be implemented with
> > non-destructive move) makes it even more better:
> > - complex updates to container's state could have strong safety
> > guarantee (i.e. either succeeded or failed and container is in previous
> > state) -- i.e. vector.insert now could have strong guarantee
>
> I don't see how that could possibly be the case unless you are willing
> to pay O(N) additional storage for the partially-moved objects.

Exactly -- in general case you'll need O(N) aditional storage. This
two-phased feature was invented in order to make move constructor
having strong guarantee. Your paper and some thoughts did a very strong
blow to the idea of having it. Now I think it is not a very good idea.


> > And how badly we need strong guarantee at as much places as we could
> > get.
>
> No, read http://www.boost.org/more/generic_exception_safety.html
> (originally published in M. Jazayeri, R. Loos, D. Musser (eds.):
> Generic Programming, Proc. of a Dagstuhl Seminar, Lecture Notes on
> Computer Science. Volume. 1766)

Very good paper. Cleans some crap in my head.


> We need the strong guarantee exactly where it is "natural" for the
> operation to provide it without imposing a big-O efficiency cost.  You
> can always add a copy/swap layer on top of whatever is natural if
> you're willing to make the operation expensive in order to get the
> strong guarantee.

Unfortunately this makes it harder and more costly to get strong
guarantee. For example in case of of vector::insert generally it is
enough to backup only values right to the point of insertion. It is
possible to write such code, but hard... so usually everybody do a full
copy. This makes code that needs strong guarantee to perform slower
than needed.


> I find most of your paper very hard to read, so it doesn't help me to
> understand very much of what you're saying.  However, what I can
> understand seems to have some major holes.  You can't implement shared
> ownership without GC or reference counting no matter how much move
> semantics you are given.

You can... explicitly extract pointer from pointer_to_T object with
'detach()' and use it in usual way (pass it to shared_ptr constructor).
Main idea is to protect resources by making every allocation function
to return object, which encapsulates resource release, implicitly.


> My only comment is that when proposing something as a better
> alternative to a very complete and refined proposal, it's probably a
> good idea not to argue too strongly while the idea is still 'raw.'

Ok, I'll try. What do you think about this idea? Having move semantic
will make it possible to return object efficiently. To stop
auto_release mechanism you need to detach resource explicitly. I
believe this could reduce leaks possibility considerably.


> > If you take away 'two-phased' feature, my destructive move is typical
> > destructive move.
>
> Well, two-phase and marking are completely independent issues, so no,
> "your move" is not what people typically thought of as destructive
> move in the past.  But if you take away marking...
>
> > What makes you uncertain about efficiency of
> > destructive move?
>
> ..people will need to reinvent marking "manually" somehow.  Plus the
> programming model is very difficult.

Yes, but getting strong guarantee becomes a bit easier. Anyway, I
already de-illusioned with this feature.


> >> What new case of the strong guarantee does destructive move provide
> >> for?
> >
> > destructive move itself does not make situation better. I was speaking
> > about 'my destructive move' which have 'two-phase' feature. It could
> > give strong guarantee while still being reasonable efficient.
>
> I doubt it, without extra storage.  I think you're ignoring composite
> operations.

It was designed to use extra storage. And specifically designed to give
strong guarantee for composite operations.


> > For me 'atomic-like' means: ability of given operation to succeed
> > completely, or fail leaving environment in previous state.
>
> That's just "atomic."

I thought it will create confusion with 'atomic' from multithreading.


Bye.
Sincerely yours, Michael.

---
[ 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                       ]

0
Reply Michael 6/7/2005 3:10:02 AM

Michael Pryhodko wrote:
> I finally found some time to gather thoughts that were burrowing my
> mind for very long time and put them "on paper". It looks somewhat
> messy -- definitely I am not a master of quill but I tried. :)
> This is not really a proposal (so I decided not to bother comp.std.c++)
> -- I have nor time nor specific experience to develop proposal for such
> big thing. However, I hope this paper will raise popularity of 'move
> semantic' in people's mind which ultimately will lead to introduction
> of this feature into C++ -- I strongly believe we could benefit from
> it. I definitely will ;).
>
> here is it:
> http://home.iprimus.com.au/crusader7/prg/cpp_move.htm
>
> it is about how we need 'move', how compiler could implement it and
> what problemms we will get along with benefits.

Has it been considered to change the Standard so that these templates:

template <typename S>
static void cons_move(void *dest, const S &src)
   { new(dest) D(src); }

template <typename S>
static void assign_move(D &dest, const S &src)
   { dest = src; }

are implicitly defined for all primitive type D, and have these
default definitions (as member templates) unless overridden for all
classes D?  The Standard could also be changed to say that, at
least conceptually, desttype::cons_move() is used if the last use
of a temporary is to construct something, and desttype::assign_move()
is used if the last use of a temporary is to assign it to something.

(By "unless overridden" I don't mean that having the function
member:

staic void assign_move(D &dest, const int src);

makes the default template assign_move disappear.  The default
definitions disappear only if there is no possible usage of
them that wouldn't be overridden by a explicitly defined member.)

I guess it would be necessary for new(void *, size_t) to be
implicitly defined rather than needing the "new" include file
(for cons_move to work). Or not, since cons_move, as an implicitly
defined template, is unavoidably a magical thing anyway.

cons/assign_move would also be likely used explicitly in container
templates like those in the STL.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply wkaras 6/10/2005 10:23:43 AM

Sorry, I overlooked an obvious issue with my
previous post about the cons_move and assign_move implicit
templates/functions.  It would be necessary to allow syntax
like:

int::cons_move(i, j);

for primitive types so that cons/assign_move would be fully
usable within templates.  Would

long int::const_move(i, j);

be legal?  I guess it does't matter as long as
map<long int, xyz> still expanded properly.

The only alternative I can see would be to make the
implicit definitions non-members like this:

template <typename D, typename S>
inline void cons_move(void *dest, const S &src)
   { new(dest) D(src); }

template <typename D, typename S>
inline void assign_move(D &dest, const S &src)
   { dest = src; }

If I'm remembering right, a class can never have a template
as a friend.   So this approach would prevent doing a
partial specialization of either template and having it
be a friend of the class that is the destination of
the copy.

Generally, the proposed change to the treatment of
temporaries is backwards compatible with existing code.
The exception is classes that can't be assigned
or constructed from const references.  Would
it be better if the compiler just implicitly defined
a cons_move function for each copy constructor, and
a assign_move function for each assignment operator,
with the source types being the same?


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Reply wkaras 6/10/2005 10:29:12 AM
comp.lang.c++.moderated 10633 articles. 8 followers. Post

47 Replies
144 Views

Similar Articles

[PageSpeed] 44


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

C++0x move semantics
Hi, I have a question regarding the move copy constructor behavior. I know that normally you bind temporary objects to that constructor, because otherwise you could end up with an "emptied" object after the move operation - object to which you will have access to. In this case: { RealTimeRequestData data(connection); result.push_back(data); } I created a stack object data of type "RealTimeRequestData" - but this was done by not using the shorter variant where we would create the temporary data object because of convenience. 1. Is is true t...

Legacy APIs which output C-style strings: Opportunity to use move semantics?
Greetings, Assuming that the APIs provide me with a way to query to the length of the output string before the actual copy request is made, I can either: * allocate a buffer * call API to copy data to a basic_string * delete said buffer * return basic_string or: * create a vector with a size argument * copy data * return basic string copying out the data (the Meyer's solution) Is there a way I can eliminate the final copying? I would have liked to see basic_string with a move constructor and a move enabled assign at the very least. Or, is there a fundamental...

C-Move and C-Store
Hi , How to know which C-Move request generated a C-Store coming from the data base? I seen in the specification that there are the fields: (0000,1030) Move OriginatorApplication Entity Title AE 1 (0000,1031) Move Originator US Message ID 1 Is the this only means of knowing. Thank you very much for your answers :) Marcelo. Yes, this is the only way to know. However, it does not guarantee a unique C-MOVE request identifier, since the Message ID is only required to be unique within the scope of simultaneous (asynchronous) C-MOVE requests on one Association. A requesting ...

Move constructor. Move semantics experiment.
Hi: A couple of days ago, I posted a letter "Is swap_void(void*) possible?" which is about the move semantics of objects in a dynamic array. http://groups.google.com.tw/group/comp.lang.c++.moderated/browse_frm/thread/74dfca376425c281/74f636d8724862a7?q=swap_void&rnum=1#74f636d8724862a7 David Abrahams provided a useful link: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html which is a proposal about rvalue reference in C++. Now my practice of the dynamic array is like this: template<typename T> class MyVect { T *_bgn, *_end, *_storage_end; public...

Move semantics and moved/empty objects
Following a discussion I had on the boost-devel mailing list [1] about objects that can never be empty/null, I started thinking about issues that move semantics introduce. [1] http://article.gmane.org/gmane.comp.lib.boost.devel/177969 Indeed, when moving an object, it is required to leave the object in a state which is at least valid enough to call its destructor on. In the following, let's only consider objects which own resources that must be freed in the destructor. The moved object is then left in an empty state, which might contradict the invariants of the type. However, it could ...

Moving from C++03 to C++11
Could someone please suggest a good book (or any kind of resource) for someone who's very familiar with C++03 and who wants to get up to speed with C++11. (I was considering getting the 4th addition of Bjarne's book, but rather than read about the entire language from start to finish, I just want to focus on the new stuff brought in with C++11). Rhino On Monday, 27 January 2014 02:06:20 UTC+2, retro...@gmail.com wrote: > Could someone please suggest a good book (or any kind of resource) for someone who's very familiar with C++03 and who wants to get up to sp...

QR/C-find and C-move
I have a question about Query retrieve and what data is returned in the c-find request and c-move. I want to make sure I understand this correctly. First, there are three roots (patient, study, patient-study) for c- find and c-move. Do these levels translate into what data is returned in a query request? That is, if I an SCU makes a request at the patient root, only patient level information is returned by the SCP. On the other hand, the query level (0008,0052) is the level with which the SCU queries the SCP. So if an SCU selects the image query level with a patient root, the SC...

how c-move and c-store works ?
Hello, i'll tell you what i know firstly. then i'll ask my questions.. All the things that i understand from C-Move service class Client wants to get a file from server. It issues C-Move service to Server. This C-Move service holds informatioon . In its command set, Move Destination field will be AE of the server. Because server will start to perform C-Store Service. Server prepares a C-Move Rsp to Client and start a new association to client. Client become a SCP. To do that, client accept requests from its port 104.. Server start to send store-rq packets using this channe...

"Permission Denied" Status Codes for C-STORE, C-GET and C-MOVE?
I am just implementing role-based access control on Study level to an OSS archive (dcm4chee), utilizing DICOM User Identity Negotiation: only a user with roles with "query"(1), "read"(2), "export"(3) or "append"(4) permission for a particular study should be able (1) to query attributes of the study and of its sub-entities, (2) to get or acting as move destination for instances related to the study, (3) to move instances related to the study to a different move destination, or (4) to store additional instances to an existing study. For query, on...

moving from c++ to visual studio c++ (winpcap)
Hi ! i have a problem related to winpcap, i'm curretly making a sniffer aplication for my studies. I want to accomplish this http://www.winpcap.org/docs/man/html/group__wpcap__tut3.html but in visual studio, the problem is related to the function pcap_loop(adhandle, 0, packet_handler, NULL); it has a pointer to the function packet_handler. It works fine in console, but how do i make it work in windows forms?? a have made an form with an button which pressed should do the stuff that the function main does in te program from the above linlk, but should call the function from inside the c...

Question about C semantics/optimizing C compilers
Hello all, we recently had some discussion about "Duff's Device" and which code a modern, optimizing compiler should produce for it. In case you never heard of "Duff's Device", you can read all about it here: <www.lysator.liu.se/c/duffs-device.html>. In short, the author of this code needed some efficient piece of code to write the contents of an array of "short"s to a video hardware register. Now, given the limitations of his C compiler at that time (1983!), he came up with the following amusing solution, which uses loop-unrolling in a very &qu...

C-FIND/ C-MOVE ROOT & LEVEL.
I find the Root and Level to be confusing in C-FIND and C-MOVE. My PACS has a database structure like Patient, Study, Series, Image. As I am searching PACS by Patient ID and / or Accession number I am not sure what bearing the Level has on the query formation or its results. My understanding is that Root is either: 1) PATIENT 2) STUDY 3) PATIENT/STUDY What you use for Root really depends on the PACS you are querying and its particular structure. However, I really don't get what the Level parameter is doing for me. And with respect to C-MOVE I don't see the relavance ...

Private tag in C-Find & C-Move services
In my Dicom implementation, both SCU & SCP, I need the SCU to send to the SCP in C-Find & C-Move some aditional (private) information. Adding a private tag to the data pdv (the identifier), may cause problem to foreign SCPs, that might take my private tag as a key field that should be matched in the response. I think that the correct way of passing additional data, that should not be used for matching, from the SCU to SCP is in the command pdv. I couldn't find any reference to this issue in the standard. Thanks for any help, Leon ...

Moving from Visual C++ 6 to Visual C++ 7.1
Hi, Recently, I've upgraded Visual C++ 6 to VS.NET 2003 (7.1) and one of the project doesn't seem to like the new compiler. The project is coded in C++/Platform SDK and it has no problem compiling using VC6. VS.NET 2003 did a few conversions and opened it. However, the debug build of the program no longer worked. The debugger told me that an unhandled exception occurred somewhere around "CreateWindowEx" of the main program window. If I ran the program with Ctrl+F5, there would be no error messages but the program didn't run at all. The interesting thing was t...

C-Move
Hi, I'm in a decision point to write C-Move functionality.. I cant imagine why i want a client send an image from server to another client.. Which devices need it ? I think modalities dont need it coz they just store their files to server.. I dont know if we use c-move when an print command is issued.. can you tell me why do i need C-Move ? It will force my clients listen to a port and act like a server. it means consuming more resources of client computers.. I'm planning to use just C-Get.. i need your comments.. Thanks in advance.. Atila Gunes don't use C...

Semantic Checking
Hello! We need help. 1. We are trying to improve the semantic analysis of a particular compiler, and we need to identify the errors that compilers usually can or cannot detect. Please take time to review the following list of errors we've gathered and check if any or all of them belongs to the semantic checking routine during compilation/runtime. If you know a specific semantic error that we missed, we'll appreciate it if you could add the details. 2. The process we are planning to do is to make a static semantic checking of C programs so that these kind of semantic errors would not...

Confused about move semantics
I'm still wondering about this http://www.gamedev.net/topic/624328-confused-about-move-semantics/ On May 3, 7:13=A0am, woodbria...@gmail.com wrote: > I'm still wondering about this > http://www.gamedev.net/topic/624328-confused-about-move-semantics/ You changed for (; headCount[0] > 0; --headCount[0]) { cmw::File rep2(buf); az1.push_back(rep2); } to for (; headCount[0] > 0; --headCount[0]) { cmw::File rep2(buf); az1.push_back(std::move(rep2)); } and observed a 492 byte decrease of the executable's size. But the C++ ...

move semantic implementation
Hi I have a question about move semantic implementation in g++. I extracted the following code right from g++. I tested it and it works fine. Unfortunately I don't understand it. I read that "move" may take both lvalue and rvalue. In the implementation below I can see that move may take rvalue only (_Tp&& as an argument). On the other hand when I tested it I found that below move implementation may take both rvalue and lvalue (as written in a documentation). So please explain me what is incorrect in my understanding. Another thing that I don't understand is the tri...

Moving the pointer in C
Hi All, How do you move the pointer in C? I've discovered OS_Word,21 in the StringHelp (and real) PRMs but am confused about how to use it.[1] What's the difference between the "pointer" and the "mouse"? What is "LSB" and "MSB". What is the structure of the block which you're supposed to pass to the SWI? Thanks a lot, Adam [1] From the StrongHelp manual: OS_Word 21,5 => R0 = 21 R1 = pointer to block containing : 0 = 5 1 = x LSB 2 = MSB 3 = y LSB 4 = MSB This OS_Word sets the pointer (not mouse) position from the ...

C++ and moving the mouse...
Hi, I'm writing on Linux an application which needs to move the mouse pointer and simulate button clicks (better: button press and release events separately, e.g. to do drag&drop). I found several ways to move the pointer: - Using QT QCursor::setPos - Using SDL libraries .... - Using XLib directly Now the problem is... I can move it, but I can't really simulate clicks. On Qt, I don't know to who I should send the mouse motion event ( I tried to send it to the application itself, but it doesn't work), because I don't have any interface (it is a command line app). W...

move semantics and stringstream
Stringstreams are often used to format text. Normally, the string is then extracted (using stringstream::str()) and the stringstream is discarded. As far as I understand str() copies the internal string which is a waste, and can be expensive if the string is long. N1682, "Rvalue Reference Recommendations for Chapter 27", doesn't give any method of moving the string instead of copying it. It seems a good idea to either add a member function move_str() which can internally use move(), or provide a rvalue-this overload to stringstream::str() to do it (relying on the N1821 p...

moving from c++ to python
Hi, I'm a pretty sound programmer in C++, but would like to learn python! Does anyone know of any tutorial s aimed at me?? My biggest confusion so far is the lack of pointers in Python ...... Regards Michael Michael wrote: > Hi, > I'm a pretty sound programmer in C++, but would like to learn python! Does > anyone know of any tutorial s aimed at me?? My biggest confusion so far is > the lack of pointers in Python ...... > Regards > > > Michael > > I suggest that you start with the official Python tutorial at http://docs.python.org/tut/tut.html -...

A Question about C-MOVE.
Is there a way to specify not just the Destination AET in a C-MOVE but also the IP address and Port? Or are these supposed to be known by the C-Move request recipient? No, the C-Move SCP must have the destination AE configured in its settings. On Monday, June 17, 2013 8:58:02 PM UTC-6, Colby Dillion wrote: > No, the C-Move SCP must have the destination AE configured in its settings. Ya... I kinda figured that.. ...

C-MOVE clarification
Hi folks, Just a clarification about C-MOVE and the final "pending" response -- I'm not sure about whether I need to suppress the "pending" response for the final image. It would seem to be redundant. Our C-MOVE SCP has been working just fine but suddenly there's an SCU we're having trouble with. Everything looks fine on our end except that I notice that I am sending out one "pending" response for each c-store'd image -- the net effect being that the "pending" response for the final image says "pending" but then also...