Move semantics und operator overloading

[Helmut Zeisel]

Wie schauen die effizienten Versionen fuer operator+() und Move Semantic aus?
In Stack Overflow

http://stackoverflow.com/questions/16136461/move-semantics-and-operator-overloading

habe ich dazu zwei Varianten gefunden:

Eine mit 2 Overloads:

T operator+(T left, T const& right);
T operator+(const T& left, T&& right);

und eine mit 4 Overloads:

T operator+(const T& left, T const& right);
T operator+(T&& left, const T& right);
T operator+(const T& left, T&& right);
T operator+(T&& left, T&& right);

Bei meinen Experimenten (gcc 6.1, --std=c++14 -Ofast)

ist aber die Variante mit 2 Overloads weniger effizient:

(a+b) + c benoetigt eine Copy und zwei Moves

(die Variante mit 4 Overloads hingegen eine Copy und nur ein Move)

(a+b) + (c+d) benoetigt zwei Copies und drei Moves

(die Variante mit 4 Overloads hingegen zwei Copies und nur ein Move).

Frage:

Habe ich einen Fehler in der Implementierung,
oder optimiert der Compiler nicht vollstaendig,
oder ist die Variante mit 2 Overloads tatsaechlich weniger effizient?


Helmut

============== Kompletter Code ===================

#include <iostream>
#include <string>
#include <typeinfo>


template<typename T> struct A
{
A(const char* s): name(s) {}
A(const A& a): name(a.name)
{
std::cout << "Copying " << name << std::endl;
}
A(A&& a): name(std::move(a.name))
{
std::cout << "Moving " << name << std::endl;
}
A& operator+=(const A& a)
{
name += a.name;
}
std::string name;
};


struct One{};
struct Two{};
struct Four{};

// One
A<One> operator+(const A<One>& a1, const A<One>& a2)
{
std::cout << "const " << a1.name << "& + " << a2.name << "&: " ;
A<One> a(a1);
a+=a2;
return a;
}


// Two operators
A<Two> operator+(A<Two> a, const A<Two>& a2)
{
std::cout << a.name << " + const " << a2.name << "&: " ;
a+=a2;
return a;
}
A<Two> operator+(const A<Two>& a1, A<Two>&& a2)
{
std::cout << "const " << a1.name << "& + " << a2.name << "&&: " ;
a2+=a1;
return std::move(a2); // return a2 is worse; See Scott Meyers, Effective Modern C++, Item 25;
}

// Four operators
A<Four> operator+(const A<Four>& a1, const A<Four>& a2)
{
std::cout << "const " << a1.name << "& + const " << a2.name << "&: " ;
A<Four> a(a1);
a+=a2;
return a;
}
A<Four> operator+(A<Four>&& a1, const A<Four>& a2)
{
std::cout << a1.name << "&& + const " << a2.name << "&: " ;
a1+=a2;
return std::move(a1);
}
A<Four> operator+(const A<Four>& a1, A<Four>&& a2)
{
std::cout << "const " << a1.name << "& + " << a2.name << "&&: " ;
a2+=a1;
return std::move(a2);
}
A<Four> operator+(A<Four>&& a1, A<Four>&& a2)
{
std::cout << a1.name << "&&+" << a2.name << "&&: " ;
a1+=a2;
return std::move(a1);
}


template<typename T> void test2()
{
T a("a"), b("b");
std::cout << "a+b" << std::endl;
auto r = a+b;
}


template<typename T> void test3a()
{
T a("a"), b("b"), c("c");
std::cout << "(a+b)+c" << std::endl;
auto r = (a+b)+c;
}


template<typename T> void test3b()
{
T a("a"), b("b"), c("c");
std::cout << "a+(b+c)" << std::endl;
auto r = a+(b+c);
}


template<typename T> void test4()
{
T a("a"), b("b"), c("c"), d("d");
std::cout << "(a+b)+(c+d)" << std::endl;
auto r = (a+b)+(c+d);
}

template<typename T> void testAll()
{

std::cout << "\nTesting " << typeid(T).name() << std::endl;
test2<T>();
test3a<T>();
test3b<T>();
test4<T>();
}

template<typename T0, typename T1, typename ... Ts> void testAll()
{
testAll<T0>();
testAll<T1, Ts...>();
}


int main()
{
testAll<A<One>, A<Two>, A<Four>>();
};


===================== Output ====================


Testing 1AI3OneE
a+b
const a& + b&: Copying a
(a+b)+c
const a& + b&: Copying a
const ab& + c&: Copying ab
a+(b+c)
const b& + c&: Copying b
const a& + bc&: Copying a
(a+b)+(c+d)
const c& + d&: Copying c
const a& + b&: Copying a
const ab& + cd&: Copying ab

Testing 1AI3TwoE
a+b
Copying a
a + const b&: Moving ab
(a+b)+c
Copying a
a + const b&: Moving ab
ab + const c&: Moving abc
a+(b+c)
Copying b
b + const c&: Moving bc
const a& + bc&&: Moving bca
(a+b)+(c+d)
Copying c
c + const d&: Moving cd
Copying a
a + const b&: Moving ab
const ab& + cd&&: Moving cdab

Testing 1AI4FourE
a+b
const a& + const b&: Copying a
(a+b)+c
const a& + const b&: Copying a
ab&& + const c&: Moving abc
a+(b+c)
const b& + const c&: Copying b
const a& + bc&&: Moving bca
(a+b)+(c+d)
const c& + const d&: Copying c
const a& + const b&: Copying a
ab&&+cd&&: Moving abcd

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Wie schauen die effizienten Versionen fuer operator+() und Move Semantic aus?

Wenn Du mit »effizient« "schnell" (wenig Laufzeit) meinst:
Um die Laufzeit zu ermitteln, kann man Microbenchmark-
Techniken einsetzen. Aufgrund von Ausgaben eines C++-
Programms, das »Move« oder »Copy« schreibt, auf
Laufzeitunterschied zu schließen, könnte zu falschen
Ergebnissen führen (s. u.).

>Bei meinen Experimenten (gcc 6.1, --std=c++14 -Ofast)
>ist aber die Variante mit 2 Overloads weniger effizient:
>(a+b) + c benoetigt eine Copy und zwei Moves

In Programmen, in denen Laufzeiteffizienz besonders wichtig
ist, setzt man oft Typen mit Objekten, deren Repräsentation
gar keinen ausgelagerten Speicher mit dynamischer
Lebensdauer umfaßt, ein.

Bei solchen Typen hat ein Verschieben keinen Vorteil
gegenüber dem Kopieren, es kann aber trotzdem
Laufzeitunterschiede zwischen verschiedenen Versionen
eines Programmes geben.

Um dies beurteilen zu können braucht man eben
Microbenchmarks. Dann erhält man aber keine allgemeine
Antwort, sondern eine von der Ausführungsumgebung abhängige.

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>ist die Variante mit 2 Overloads tatsaechlich weniger effizient?

Bei

{ A<Two> a( "a" ), b( "b" ); a + b ; }

wird

A<Two> operator+(A<Two> a, const A<Two>& a2)

selektiert.

Dies bedeutet: Kopieren des ersten Operanden und dann
Verschieben des Ergebnisses. 1 COPY + 1 MOVE.

Bei

{ A<Four> a( "a" ), b( "b" ); a + b ; }

wird

A<Four> operator+(const A<Four>& a1, const A<Four>& a2)

selektiert.

Diese bedeutet: Nur Kopieren des Ergebnisses. 1 COPY.

[Helmut Zeisel]

Ja. Andersrum gefragt: Wieso wird im zweiten Fall (Four) die Return Value Optimization angewendet, im ersten Fall (Two) aber nicht?

Helmut

[Stefan Ram]

Helmut Zeisel <helmut...@gmail.com> writes:
>Ja. Andersrum gefragt: Wieso wird im zweiten Fall (Four) die
>Return Value Optimization angewendet, im ersten Fall (Two)
>aber nicht?

Im Fall

A<Two> operator+(A<Two> a, const A<Two>& a2)

ist »a« ein Kopierparameter, deswegen kann er am Ende der
Funktion entleert werden. Er wird unmittelbar danach ohnehin
zerstört werden.

Im Fall

A<Four> operator+(const A<Four>& a1, const A<Four>& a2)

ist »a« ein Referenzparameter. Er referenziert ein Objekt
des Aufrufers. Wir wissen nicht, ob der Aufrufer damit
einverstanden wäre, wenn wir sein Objekt entleeren würden.
Deswegen ist es besser, wenn es bei der Rückgabe kopiert wird.

[Helmut Zeisel]

Am Sonntag, 8. Januar 2017 15:10:03 UTC+1 schrieb Stefan Ram:

Ich weiß jetzt nicht genau, was Du mit "Deswegen ist es besser, wenn es bei der Rückgabe kopiert wird." meinst. Bei der Rückgabe wird jedenfalls nichts kopiert, sondern statt einer Kopie die RVO angewendet.

Das Stichwort "Parameter" war aber jedenfalls hilfreich.
Google "rvo function parameter" liefert:

http://stackoverflow.com/questions/9444485/why-is-rvo-disallowed-when-returning-a-parameter

Why is RVO disallowed when returning a parameter?

It's stated in [C++11: 12.8/31] :

This elision of copy/move operations, called copy elision, is permitted [...] :

— in a return statement in a function with a class return type, when the expression is the name of a non-volatile automatic object (other than a function or catch-clause parameter) with the same cv-unqualified type as the function return type, the copy/move operation can be omitted by constructing the automatic object directly into the function’s return value

Die zusätzlichen Moves im Fall "Two" kommen also anscheinen daher, dass die RVO für Funktionsparameter nicht angewendet werden darf. Die Variante mit zwei Overloads benötigt demnach im RV-optimierten Fall tatsächlich mehr Moves als die Variante mit 4 Overloads.

Helmut

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Ich weiß jetzt nicht genau, was Du mit "Deswegen ist es
>besser, wenn es bei der Rückgabe kopiert wird." meinst. Bei
>der Rückgabe wird jedenfalls nichts kopiert, sondern statt
>einer Kopie die RVO angewendet.

Ich habe hier mal ein Programm geschrieben, das zeigt, daß
ein konstanter Referenzparameter in solchen Fällen bei der
Rückgabe in das Ziel kopiert wird.

Er kann ja schon deshalb nicht verschoben werden, weil es
ein /konstanter/ Referenzparameter ist.

Quelltext

#include <initializer_list>
#include <iostream>
#include <string>

static void escape( void * p )
{ asm volatile( "" : : "g"(p) : "memory" ); }

static int i = 0;

struct object
{ object() = default;
object( const object & )
{ ::std::cout <<
( i++ ? "Copying r into o2" :
"Copying o into c" )<< '\n'; }
object( object && ) noexcept
{ ::std::cout << "Moving c into o1" << '\n'; }};

static object f( object c )
{ ::std::cout << "in f\n"; return c; }

static object g( object const & r )
{ ::std::cout << "in g\n"; return r; }

int main()
{ object o;
::std::cout << '\n' << "before f" << '\n';
object o1 = f( o ); escape( &o1 );
::std::cout << '\n' << "before g" << '\n';
object o2 = g( o ); escape( &o2 );
::std::cout << '\n'; }

Ausgabe

before f
Copying o into c
in f
Moving c into o1

before g
in g
Copying r into o2

Neben der RVO kann übrigens auch noch die As-If-Regel
einer Implementation zusätzliche Möglichkeiten eröffnen.

Im folgenden Program zeige ich, was passiert wenn wir
das Kopieren mutwillig mit einem »::std::move« unterbinden.

#include <initializer_list>
#include <iostream>
#include <string>

static void escape( void * p )
{ asm volatile( "" : : "g"(p) : "memory" ); }

struct object
{ char const * state = "good state";
object() = default;
object( object const & )= default;
object( object && other ) noexcept
{ this->state = other.state;
other.state = "valid state with an unspecified value"; }};

static object f( object & r )
{ return ::std::move( r ); }

int main()
{ object o;
::std::cout << "o has a " << o.state << ".\n";
object o1 = f( o ); escape( &o1 );
::std::cout << "o has a " << o.state << ".\n"; }

Ausgabe

o has a good state.
o has a valid state with an unspecified value.

In diesem Fall wurde nun das Objekt »o« durch
den Aufruf »f( o )« in einen unspezifizierten
Zustand versetzt. Wenn man »o« lediglich als
Summand einer Summe verwenden will, sollte
dies aber nicht passieren.

[Helmut Zeisel]

On Sunday, January 8, 2017 at 11:30:03 PM UTC+1, Stefan Ram wrote:

> Helmut Zeisel writes:
> >Ich weiß jetzt nicht genau, was Du mit "Deswegen ist es
> >besser, wenn es bei der Rückgabe kopiert wird." meinst. Bei
> >der Rückgabe wird jedenfalls nichts kopiert, sondern statt
> >einer Kopie die RVO angewendet.
>
> Ich habe hier mal ein Programm geschrieben, das zeigt, daß
> ein konstanter Referenzparameter in solchen Fällen bei der
> Rückgabe in das Ziel kopiert wird.

Der Fall tritt hier aber nicht auf; zur Erinnerung:

Version "Four" (und "One"):

A<Four> operator+(const A<Four>& a1, const A<Four>& a2)

{
std::cout << "const " << a1.name << "& + const " << a2.name << "&: " ;
A<Four> a(a1);
a+=a2;
return a;
}

a1 wird (nach dem std::cout) in die lokale Variable a kopiert, bei

der Rückgabe wird jedenfalls nichts kopiert, sondern statt
einer Kopie die RVO angewendet.

Output:

a+b
const a& + const b&: Copying a

Insgesamt eine Kopie, null Move.

Version "Two":

A<Two> operator+(A<Two> a, const A<Two>& a2)

{
std::cout << a.name << " + const " << a2.name << "&: " ;
a+=a2;
return a;
}

Das Argument wird (vor dem std::cout) nach a kopiert, keine RVO fuer den Parameter (sondern move).


Output:

a+b
Copying a
a + const b&: Moving ab

Insgesamt eine Kopie, ein Move.

>
> Er kann ja schon deshalb nicht verschoben werden, weil es
> ein /konstanter/ Referenzparameter ist.

...

>
> Im folgenden Program zeige ich, was passiert wenn wir
> das Kopieren mutwillig mit einem »::std::move« unterbinden.

...

>
> In diesem Fall wurde nun das Objekt »o« durch
> den Aufruf »f( o )« in einen unspezifizierten
> Zustand versetzt.

Passiert das irgendwo bei meinen Operator Overloads Beispielen?

Helmut

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>a1 wird (nach dem std::cout) in die lokale Variable a kopiert, bei
>der Rückgabe wird jedenfalls nichts kopiert, sondern statt
>einer Kopie die RVO angewendet.

Deine ursprüngliche Frage war wohl, warum »Four«
weniger move/copy-Operationen macht als »Two«.

Hier eine etwas erweiterte und manuell
bearbeitete Ausgabe für den Fall »(a+b)+c«:

*************************** Testing 1AI4FourE
### Constructing a 0x60
### Constructing b 0x40
### Constructing c 0x20
(a+b)+c
const a& + const b&: Aufruf 0
### Copying a 0x80
... 0
### Concatenating a + b 0x80
... 1
ab&& + const c&: Aufruf 1
### Concatenating ab + c 0x80
...
### Moving abc 0x00

*************************** Testing 1AI3TwoE
### Constructing a 0x40
### Constructing b 0x20
### Constructing c 0x00
(a+b)+c
### Copying a 0x80
a + const b&: Aufruf 0
### Concatenating a + b 0x80
### Moving ab 0x60
ab + const c&: Aufruf 1
### Concatenating ab + c 0x60
### Moving abc 0xe0

Die Adresse ist der this-Zeiger des Objektes,
das die Ausgabe erzeugt.

In »(a+b)+c« ist »(a+b)« ein Temporär mit der
Adresse 80. (Die Adressen wurden nicht manuell
hinzugefügt, sondern stammen vom Programm.)

Bei »Four« wird für die lokale Variable »a« aus
Aufruf 0 gleich dieser Temporär genommen (RVO)
und Aufruf 1 referenziert diesen Temporär und
schreibt noch ein »c« dahinter. Hier war kein
copy/move notwendig.

Bei »Two« wird für den Parameter »a« ebenfalls
gleich der Temporär genommen. Doch kommt für
die Addition des »c« bei »Two« nur die Überladung
mit dem Kopierparameter »a« in Frage. Dieser hat
die Adresse 0x60 und da es ein Kopierparameter ist
muß der Temporär 0x80 jetzt in die Adresse 0x60
gebracht werden - und dieser Schritt war bei
»Four« nicht nötig, weil dort eine Überladung
verwendet werden konnte, deren erster Parameter
kein Kopierparameter ist.

[Helmut Zeisel]

On Monday, January 9, 2017 at 9:30:04 PM UTC+1, Stefan Ram wrote:

> Deine ursprüngliche Frage war wohl, warum »Four«
> weniger move/copy-Operationen macht als »Two«.

Genau genommen war die urspruengliche Frage:

Habe ich einen Fehler in der Implementierung,
oder optimiert der Compiler nicht vollstaendig,

oder ist die Variante mit 2 Overloads tatsaechlich weniger effizient?

Wir sind uns anscheinend enig, dass die Variante mit 2 Overlaods tatsaechöich weniger effizient ist (weil laut C++11: 12.8/31 RVO fuer Funktionsparameter nicht moeglich ist.

Fuer kommutative Opratoren ist damit klar, dass die 4-Overload-Version gewaehlt werden sollte.

Das fuehrt dann aber auf die naechste Frage: was ist mit nichtkommutativen Operatoren? Es ist ja nicht einzusehen, warum

"(a-b)-c" weniger copies/moves brauchen soll als "a-(b+c)"

Eine generische Loesung ist da wohl aber nicht so einfach.

Helmut

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Fuer kommutative Opratoren ist damit klar, dass die
>4-Overload-Version gewaehlt werden sollte.

Ich orientiere mich in solchen Fälle manchmal an den
Lösungen Herb Sutters, der 2013

complex operator+( complex lhs, const complex& rhs ) {
lhs += rhs;
return lhs;
}

schrieb (also genau /eine/ Überladung). Wenn es gut
genug für Herb Sutter ist, ist es gut genug für mich.

In 20.17.5.5, duration arithmetic findet man auch nur

constexpr operator+
( const duration< Rep1, Period1 >& lhs,
const duration< Rep2, Period2 >& rhs );

Allerdings in 21.3 (vereinfacht)

operator +( const string & lhs, const string & rhs );
operator +( string && lhs, const string & rhs );
operator +( const string & lhs, string && rhs );
operator +( string && lhs, string && rhs );

>Das fuehrt dann aber auf die naechste Frage: was ist mit
>nichtkommutativen Operatoren? Es ist ja nicht einzusehen,
>warum
>"(a-b)-c" weniger copies/moves brauchen soll als "a-(b+c)"

Ich verstehe jetzt nicht, warum die Kommutativität hier
eine Rolle spielt. Aber, falls es für Dich eine Hilfe
ist: der oben gezeigte »::std::string::operator +« ist
ja nicht-kommutativ.

Guidelines:

F.15: Prefer simple and conventional ways of passing
information

Using "unusual and clever" techniques causes surprises,
slows understanding by other programmers, and encourages
bugs. If you really feel the need for an optimization
beyond the common techniques, measure to ensure that it
really is an improvement

F.16: For "in" parameters, pass cheaply-copied types by
value and others by reference to const

Avoid "esoteric techniques" such as:

Passing arguments as T&& "for efficiency". Most rumors
about performance advantages from passing by && are
false or brittle

[Helmut Zeisel]

Am Dienstag, 10. Januar 2017 18:40:05 UTC+1 schrieb Stefan Ram:

> Ich orientiere mich in solchen Fälle manchmal an den
> Lösungen Herb Sutters, der 2013
>
> complex operator+( complex lhs, const complex& rhs ) {
> lhs += rhs;
> return lhs;
> }
>
> schrieb (also genau /eine/ Überladung).

Wo genau schrieb das Herb Sutter?

> Wenn es gut
> genug für Herb Sutter ist, ist es gut genug für mich.

Kommt drauf an. Wenn copy nicht wesentlich teurer als move ist, reicht es.
Bei complex<double> ist das der Fall.

> operator +( const string & lhs, const string & rhs );
> operator +( string && lhs, const string & rhs );
> operator +( const string & lhs, string && rhs );
> operator +( string && lhs, string && rhs );

> Ich verstehe jetzt nicht, warum die Kommutativität hier
> eine Rolle spielt. Aber, falls es für Dich eine Hilfe
> ist: der oben gezeigte »::std::string::operator +« ist
> ja nicht-kommutativ.

Wie implementierst Du

operator +( const string & lhs, string && rhs );

so, dass

auto result=string1 + (string2 + string3)

mit einem einzigen Copy und einem einzigen Move auskommt?
Ich schaffe es nur mit zwei Moves.

Helmut

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Wie implementierst Du
>operator +( const string & lhs, string && rhs );
>so, dass
>auto result=string1 + (string2 + string3)
>mit einem einzigen Copy und einem einzigen Move auskommt?
>Ich schaffe es nur mit zwei Moves.

Ich habe die Objektklasse, welchen den Operator »+=«
enthält, dafür zunächst um einen Operator »-=« erweitert.

Der Name »-=« ist aber irreführend, tatsächlich ist es auch
ein +=, aber mit vertauschter Reihenfolge der Summanden,
unten »swap-append« genannt.

object & operator +=( object const & other )
{ name += other.name;
return *this; }

object & operator -=( object const & other )
{ name = other.name + name;
return *this; }

Nun kann ich definieren:

static object operator +( const object & a1, const object & a2 )
{ object a = a1; a += a2; return a; }

static object operator +( const object & a1, object && a2 )
{ object a = ::std::move( a2 ); a -= a1; return a; }

und komme so auf
(oben sind die debug-Ausgabe-Anweisungen entfernt worden):

value-constructing to 0xc60 with value a
value-constructing to 0xc80 with value b
value-constructing to 0xcc0 with value c

r = a +( b + c )

b& + const c&:
copy-constructing to 0xd00 with value b
appending b 0xd00 + c 0xcc0 to 0xd00

a& + const bc&&:
move-constructing to 0xdc0 with value bc
swap-appending bc 0xdc0 + a 0xc60 to 0xdc0

address of r is 0xdc0
r.name = abc

(Das Effizienzproblem ist damit vielleicht nun in den
Operator »-=» verschoben worden, der statt »+=« »+« verwendet,
was wiederum einen Temporär erzeugen könnte, aber immerhin
nicht von dem ganzen Objekt, sondern nur von einem Felde.)

[Helmut Zeisel]

On Wednesday, January 11, 2017 at 1:30:03 AM UTC+1, Stefan Ram wrote:

> Helmut Zeisel writes:
> >Wie implementierst Du
> >operator +( const string & lhs, string && rhs );
> >so, dass
> >auto result=string1 + (string2 + string3)
> >mit einem einzigen Copy und einem einzigen Move auskommt?
>

> Ich habe die Objektklasse, welchen den Operator »+=«
> enthält, dafür zunächst um einen Operator »-=« erweitert.
>
> Der Name »-=« ist aber irreführend, tatsächlich ist es auch
> ein +=, aber mit vertauschter Reihenfolge der Summanden,
> unten »swap-append« genannt.

Am Dienstag, 10. Januar 2017 18:40:05 UTC+1 schrieb Stefan Ram:

> Ich verstehe jetzt nicht, warum die Kommutativität hier
> eine Rolle spielt.

Ich nehme an, jetzt versteht Du es.
Bei einem kommutativen operator "+" können wir uns problemlos einigen, dass folgende Implementierung effektiv und effizient ist:

T operator +( const T & lhs, T && rhs )
{
rhs+=lhs;
return std::move(rhs);
}

Bei einem nicht-kommutativen Operator fangen die Fragen jetzt erst an:

Soll es wirklich der Operator -= sein? Waere nicht einem Member-Funktion besser?
Wie soll die heißen? swap_append? prepend? add_from_left?

> (Das Effizienzproblem ist damit vielleicht nun in den
> Operator »-=» verschoben worden, der statt »+=« »+« verwendet,
> was wiederum einen Temporär erzeugen könnte, aber immerhin
> nicht von dem ganzen Objekt, sondern nur von einem Felde.)

Genau. Es ist unklar, ob das "swap-append" wirklich effizienter implementiert werden kann. Das ist ein Beispiel, wo die "performance advantages from passing by &&" wirklich "false or brittle" sein koennen.
Für einen nicht-kommutativen Operator +
reichen daher in vielen Faellen die beiden Overloads

T operator +( const T & lhs, const string & T );
T operator +( const T && lhs, const string & T );

Helmut

[Helmut Zeisel]

On Tuesday, January 10, 2017 at 9:50:02 PM UTC+1, Helmut Zeisel wrote:

> Wie implementierst Du
>
> operator +( const string & lhs, string && rhs );
>
> so, dass
>
> auto result=string1 + (string2 + string3)
>
> mit einem einzigen Copy und einem einzigen Move auskommt?
> Ich schaffe es nur mit zwei Moves.

Korrektur:

mit der "normalen" Implementierung

string operator +( const string & lhs, string && rhs )
{
string result(lhs);
result += rhs;
return result;
}

benötigt

auto result = string1 + (string2 + string3)

zwei Copies (und kein Move)

> Am Dienstag, 10. Januar 2017 18:40:05 UTC+1 schrieb Stefan Ram:

> > Ich orientiere mich in solchen Fälle manchmal an den
> > Lösungen Herb Sutters, der 2013
> >
> > complex operator+( complex lhs, const complex& rhs ) {
> > lhs += rhs;
> > return lhs;
> > }
> >
> > schrieb (also genau /eine/ Überladung).

Bei dieser Variante benoetigt

auto result = lhs + rhs

ein Copy und ein (unnoetiges) Move (weil die RVO fuer lhs nicht angewendet wird).

Daher wuerde mich wirklich interessieren, in welchem Zusammenhang Herb Sutter das empfohlen hat.

Helmut

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Für einen nicht-kommutativen Operator +
>reichen daher in vielen Faellen die beiden Overloads

Wenn Effizienz eine hohe Rolle spielt, dann könnte
es angemessen sein, 0 Überladungen bereitzustellen.

Der Endbenutzer der Bücherei müßte dann mit »+=«
arbeiten. Er weiß eventuell, daß er die späteren
Werte von »a« und »b« nicht mehr benötigt, und kann
dann schreiben:

b += c;
a += b;

.

[Helmut Zeisel]

On Wednesday, January 11, 2017 at 11:10:03 AM UTC+1, Stefan Ram wrote:

> Helmut Zeisel writes:
> >Für einen nicht-kommutativen Operator +
> >reichen daher in vielen Faellen die beiden Overloads
>
> Wenn Effizienz eine hohe Rolle spielt, dann könnte
> es angemessen sein, 0 Überladungen bereitzustellen.

Was zu der Frage führt, wieso C++ überhaupt Operator Overlaoding anbietet.
Andere Programmiersprachen verzichten ja darauf.

> Der Endbenutzer der Bücherei müßte dann mit »+=«
> arbeiten.

Oder er definert dann die Overloads von operator+(const T&, const T&) etc selber.

> Er weiß eventuell, daß er die späteren
> Werte von »a« und »b« nicht mehr benötigt, und kann
> dann schreiben:
>
> b += c;
> a += b;

Das kann er so und so. Das Problem der nicht-kommutativen Operatoren ist damit aber auch nicht gelöst. Was ist, wenn ich nicht

a += b

sondern

a = b + a

will?

Helmut

[Bonita Montero]

> Was zu der Frage führt, wieso C++ überhaupt Operator Overlaoding anbietet.
> Andere Programmiersprachen verzichten ja darauf.

C# kennt auch Operator Overloading.

--
http://facebook.com/bonita.montero/

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>On Wednesday, January 11, 2017 at 11:10:03 AM UTC+1, Stefan Ram wrote:
>>>Für einen nicht-kommutativen Operator +
>>>reichen daher in vielen Faellen die beiden Overloads

>Was zu der Frage führt, wieso C++ überhaupt Operator Overlaoding anbietet.
>Andere Programmiersprachen verzichten ja darauf.

Ich hatte an die Möglichkeit gedacht, »+« nicht zu überladen,
aber »+=« zu überladen. Das ist ja auch eine Überladung.
Natürlich sind alle Überladungen nur syntaktischer Zucker.

>>Er weiß eventuell, daß er die späteren
>>Werte von »a« und »b« nicht mehr benötigt, und kann
>>dann schreiben:
>>b += c;
>>a += b;
>Das kann er so und so.

Ja, aber wenn »+« fehlt, wird deutlicher daran erinnert.
Wer denkt denn sonst bei ::std::string::operator+ schon daran,
dies in eine Sequenz von ::std::string::operator+= aufzulösen?

>Was ist, wenn ich nicht
>a += b
>sondern
>a = b + a
>will?

Falls der vorige Wert von »b« danach nicht mehr benötigt
wird, kann man

b += a

schreiben. Falls er danach benötigt wird, muß man vorher
eine Kopie des bisherigen Wertes anlegen. Das ist bei »a += b«
entsprechend genau so für »a«.

(Die Variablen erinnern hier mich etwas an Register in
Maschinensprache, siehe »register allocation«/
»register pressure«. Compiler haben da auch Strategien,
diese zu belegen und wiederzuverwenden, wenn ihr
bisheriger Wert nicht mehr benötigt wird.)

Es gibt wahrscheinlich maschinelle Optimierungsstrategien
für die Registerbelegung in Compilern, und wahrscheinlich
könnte man einen Ausdruck mit Variablen und »+« auch
automatisch in eine Sequenz von »+=« übersetzen, die
copy/moves minimiert, wenn man ihr sagt, die Werte welcher
Variablen hinterher noch benötigt werden.

Wenn es kein »+« gibt, wird dem Benutzer der Bibiothek
verdeutlicht, wann er zusätzlich kopieren muß, weil er dies
dann manuell machen muß, so daß er eventuell Wege zur
Vermeidung sucht und findet, über die er bei »+« mit
"unsichtbaren" Temporären gar nicht nachdenken würde.

Als es in den 90er Jahren closures in Java gab,
wollten die damalige Kunden von Sun dies angeblich nicht,
weil sie keine stillschweigenden Allokationen wollten,
aus Angst, daß diese dann zu leicht in Kauf genommen werden.
Sie wollten gezwungen werden, »new« zu schreiben,
um die Last der Heap-Allokation spüren zu können.

»Guy Steele wrote:

Actually, the prototype implementation *did* allow non-final
variables to be referenced from within inner classes. There was
an outcry from *users*, complaining that they did not want this!«

[Helmut Zeisel]

Am Mittwoch, 11. Januar 2017 23:30:03 UTC+1 schrieb Stefan Ram:

> Ich hatte an die Möglichkeit gedacht, »+« nicht zu überladen,
> aber »+=« zu überladen. Das ist ja auch eine Überladung.
> Natürlich sind alle Überladungen nur syntaktischer Zucker.

Ursprünglich war es vielleicht nur syntaktischer Zucker.
Seit es Templates gibt, kommt aber auch dazu, dass Operator Overloading die generische Programmierung erleichtert. Ansonsten wüßtest Du nicht,
was im generischen Code statt

a += b

schreiben müsstest. Heißt das jetzt

a.append(b), a.increase(b) oder add(a,b)?

> Ja, aber wenn »+« fehlt, wird deutlicher daran erinnert.
> Wer denkt denn sonst bei ::std::string::operator+ schon daran,
> dies in eine Sequenz von ::std::string::operator+= aufzulösen?

Ich verwende nach Möglichkeit immer die += Version.
Das ist weniger Schreibaufwand, ist leichter wartbar und,
sobald man sich daran gewoehnt hat, auch leichter lesbar.
Der Performance-Gewinn ist dann eher nur mehr der Zucker ...

> >Was ist, wenn ich nicht
> >a += b
> >sondern
> >a = b + a
> >will?
>
> Falls der vorige Wert von »b« danach nicht mehr benötigt
> wird, kann man
>
> b += a
>
> schreiben.

Den brauche ich aber, weil ich z.B. viele Strings a[i] mit einem fixen Prefix b versehen muss.

> Falls er danach benötigt wird, muß man vorher
> eine Kopie des bisherigen Wertes anlegen. Das ist bei »a += b«
> entsprechend genau so für »a«.

Ja. Wenn das ofter vorkommt, schreibe ich z.B. eine Funktion

string addPrefix(const string& prefix, string && a)
{
auto result(prefix);
result += a;
return result;
}

Dann komme ich drauf, dass ich die Funktion besser "operator+" nennen sollte.
Das erleichtert die Doku, weil klar ist, was gemeint ist.

Der Punkt ist allerdings, dass die Klassenautoren moeglicherweise Optimierungsmoeglichkeiten haben, die ich nicht habe

z.B. koennte bei

a = b + a

die capacity von a bereits groß genug sein, sodass keine dynamische Allokation noetig ist, nur die characters um b.length() verschoben werden muessen und b vorne eingefuegt wird.

So eine Funktion koennte dann (wie von Dir vorgeschlagen) den Namen "swap_append" tragen und effizienter sein.

Womit wir aber wieder beim Ausgangspunkt sind:

Fuer die Operationen

a = b - a
a = b * a

a = b + a

a = b / a
...

gibt es keinen eigenen Operator, wodurch eine generische Programmierung nicht so einfach moeglich ist (eine moegliche Loesung waeren die C++0x concept maps, die aber in den concepts light nicht mehr drinnen sind).

Helmut

[Helmut Zeisel]

On Wednesday, January 11, 2017 at 11:30:03 PM UTC+1, Stefan Ram wrote:

> Es gibt wahrscheinlich maschinelle Optimierungsstrategien
> für die Registerbelegung in Compilern, und wahrscheinlich
> könnte man einen Ausdruck mit Variablen und »+« auch
> automatisch in eine Sequenz von »+=« übersetzen, die
> copy/moves minimiert, wenn man ihr sagt, die Werte welcher
> Variablen hinterher noch benötigt werden.

Ist nicht genau der Zweck der 4 Overloads

T operator+(const T&, const T&)
T operator+(T&&, const T&)
T operator+(const T&, T&&)
T operator+(TT&, T&&)

"automatisch in eine Sequenz von »+=« [zu] übersetzen, die

copy/moves minimiert, wenn man ihr sagt, die Werte welcher

Variablen hinterher noch benötigt werden."?

> Wenn es kein »+« gibt, wird dem Benutzer der Bibiothek
> verdeutlicht, wann er zusätzlich kopieren muß, weil er dies
> dann manuell machen muß, so daß er eventuell Wege zur
> Vermeidung sucht und findet, über die er bei »+« mit
> "unsichtbaren" Temporären gar nicht nachdenken würde.

An sich ist aber die Philosophie von C++, dem Benutzer solche Arbeit so weit wie moeglich abzunehmen (deswegen gibt es ja RVO und Move Semantik).

Helmut

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Ursprünglich war es vielleicht nur syntaktischer Zucker.
>Seit es Templates gibt, kommt aber auch dazu, dass Operator
>Overloading die generische Programmierung erleichtert.
>Ansonsten wüßtest Du nicht, was im generischen Code statt
>a += b
>schreiben müsstest. Heißt das jetzt
>a.append(b), a.increase(b) oder add(a,b)?

Wenn es die Möglichkeit der Überladung von Operatoren nicht
gäbe, hätte sich vielleicht eine Kultur von Standardnamen
für Funktionen herausgebildet, und man hätte sich darauf
geeinigt, immer »increase« zu schreiben. Und zwar
»increase( a, b )«, damit es auch für fundamentale Typen
verwendbar ist.

template< typename T >
T & increase( T & a, T const & b )
{ a += b; return a; }

Im Grunde haben wir so etwas heute ja mit Namen wie
»begin« und »end«.

sort( begin( str ), end( str ))

[Stefan Ram]

Helmut Zeisel <zei...@liwest.at> writes:
>Ist nicht genau der Zweck der 4 Overloads
>T operator+(const T&, const T&)
>T operator+(T&&, const T&)
>T operator+(const T&, T&&)
>T operator+(TT&, T&&)

>"automatisch in eine Sequenz von »+=« [zu] übersetzen, die

>copy/moves minimiert, wenn man ihr sagt, die Werte welcher
>Variablen hinterher noch benötigt werden."?

Die RVO kann nur einen Schritt weit sehen. In

r = a +( b + c )

weiß das linke »+«, daß es »r« verwenden kann,
aber das rechte nicht, obwohl es dort schon für den
Temporär verwendet werden könnte.

Die Optimierung eines Compilers kann aber noch darüber
hinausgehen. Deswegen verwenden Optimierungsexperten
auch Profiling und Microbenchmarks zusätzlich zu oder
an Stelle von Debug-Ausgaben.

Um mal ein Beispiel zu zeigen:

#include <cstdlib>

static void escape( void * p )
{ asm volatile( "" : : "g"(p) : "memory" ); }

struct object

{ constexpr explicit object( int const n ): value{ n } {}
object & operator +=( object const other )
{ this->value += other.value; return *this; }
int value; };

static object operator +( object n, const object m )
{ n += m; return n; }

int main()
{ constexpr object a{ 0x1001 }, b{ 0x1002 }, c{ 0x1003 };
auto r = a + b + c;
escape( &(r.value) ); }

Das ganze Programm wird hier praktisch in etwas wie

movl $3006, 32(%rsp)

übersetzt. In dem Moment, wo ich jetzt
debug-Ausgabeanweisungen in die Klasse einbaue, könnte die
Übersetzung schon wieder anders ausfallen.

[Helmut Zeisel]

Am Donnerstag, 12. Januar 2017 19:20:04 UTC+1 schrieb Stefan Ram:


> Wenn es die Möglichkeit der Überladung von Operatoren nicht
> gäbe, hätte sich vielleicht eine Kultur von Standardnamen
> für Funktionen herausgebildet, und man hätte sich darauf
> geeinigt, immer »increase« zu schreiben. Und zwar
> »increase( a, b )«, damit es auch für fundamentale Typen
> verwendbar ist.
>
> template< typename T >
> T & increase( T & a, T const & b )
> { a += b; return a; }

Welchen Namen schlaegst Du fuer


template< typename T >
T & increase_from_left(const T & a, T & b )
{ b = a + b; return b; }

vor?

Helmut

[Helmut Zeisel]

On Thursday, January 12, 2017 at 9:30:04 PM UTC+1, Stefan Ram wrote:

> Die RVO kann nur einen Schritt weit sehen. In
>
> r = a +( b + c )
>
> weiß das linke »+«, daß es »r« verwenden kann,
> aber das rechte nicht, obwohl es dort schon für den
> Temporär verwendet werden könnte.

Interessanter Punkt. Schauen wir zuerst

r=a+b+c

an. Der Compiler erzeugt anscheinend

tmp = a // copy
tmp += b
r = tmp // copy or move
r += c

Wieso darf der Compiler nicht

r = a
r += b
r += c

erzeugen (wenn opertor+ inline ist und alle Optimierungsoptione aktiv sind)?

Helmut

[Helmut Zeisel]

On Thursday, January 12, 2017 at 7:20:04 PM UTC+1, Stefan Ram wrote:

> Wenn es die Möglichkeit der Überladung von Operatoren nicht
> gäbe, hätte sich vielleicht eine Kultur von Standardnamen
> für Funktionen herausgebildet, und man hätte sich darauf
> geeinigt, immer »increase« zu schreiben. Und zwar
> »increase( a, b )«, damit es auch für fundamentale Typen
> verwendbar ist.
>
> template< typename T >
> T & increase( T & a, T const & b )
> { a += b; return a; }
>
> Im Grunde haben wir so etwas heute ja mit Namen wie
> »begin« und »end«.
>
> sort( begin( str ), end( str ))

Dass sich "begin" und "end" eingebuergert haben, ist wohl in erster Linie Alexander Stepanov und seinen Mitarbeiterinnen zu verdanken, die mit der STL eine Fuelle generischer Algorithmen (wie eben "sort") mitgeliefert haben, die genau diese Konvention voraussetzen. Daher haben allen, die STL kompatibel sein wollen, diese Konvention gerne uebernommen.

Allerdings gaebe es durchaus auch Bedarf fuer Dein "increase".

Bei

std::vector<std::string> v = ...

scheitert

std::accumulate

schon bei der Verkettung von strings zu einem "super-string" mit einer Laenge von ein paar 10.000 Zeichen.

Da ware Bedarf nach einer Variante mit "+=", also z.B.

namespace hz
{
template<class InputIt, class T>
T accumulate_t(InputIt first, InputIt last, T init)
{
for (; first != last; ++first)
{
init += *first;
}
return init;
}

template<class InputIt, class T, class Trafo>
T accumulate_t(InputIt first, InputIt last, T init, Trafo t)
{
for (; first != last; ++first)
{
t(init,*first);
}
return init;
}
};

"Trafo" ist dann z.B. eine struct "increase:

template<class T, class U=T> struct increase
{
void operator()(T& obj, const U& arg)
{
obj += arg;
}
};


hz::accumulate_t schafft dann durchaus auch die

schon bei der Verkettung von strings zu einem "super-string" mit einer Laenge von ein paar 100 Millionen Zeichen.

Das fuehrt dann aber wieder zurueck zu Move Semantik und Operator-Overloading.
Eine Move-Variante von std::accumulate schafft das naemlich ebenfalls:

namespace hz
{
template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init)
{
for (; first != last; ++first)
{
init = std::move(init) + *first;
}
return init;
}

template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op)
{
for (; first != last; ++first)
{
init = op(std::move(init),*first);
}
return init;
}
};

Als "BinaryOperation" muss dann eine Variante mit rvalue references genommen werden:

template<class T, class U=T> struct plus_rv: std::binary_function<T,U,T>
{
T operator()(T&& lhs, const U& rhs)
{
lhs += rhs;
return std::move(lhs);
}
};

Genauer Code mit Laufzeit-Ergebnissen im Anhang.

Helmut

======================= Code ==========================

#include <iostream>
#include <string>
#include <numeric>
#include <vector>
#include <chrono>
#include <ctime>
#include <cassert>

typedef std::vector<std::string> tVec;

struct timer
{
timer(const std::string& n): name(n), start{std::chrono::system_clock::now()}
{
}
~timer()
{
auto end = std::chrono::system_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
std::cout << "Elapsed time for " << name << ": " << duration << "ms" << std::endl;
}
std::string name;
std::chrono::time_point<std::chrono::system_clock> start;
};

namespace hz
{
template<class InputIt, class T>
T accumulate_t(InputIt first, InputIt last, T init)
{
for (; first != last; ++first)
{
init += *first;
}
return init;
}

template<class InputIt, class T, class Trafo>
T accumulate_t(InputIt first, InputIt last, T init, Trafo t)
{
for (; first != last; ++first)
{
t(init,*first);
}
return init;
}

template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init)
{
for (; first != last; ++first)
{
init = std::move(init) + *first;
}
return init;
}

template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op)
{
for (; first != last; ++first)
{
init = op(std::move(init),*first);
}
return init;
}



template<class T, class U=T> struct increase
{
void operator()(T& obj, const U& arg)
{
obj += arg;
}
};

template<class T, class U=T> struct plus_rv: std::binary_function<T,U,T>
{
T operator()(T&& lhs, const U& rhs)
{
lhs += rhs;
return std::move(lhs);
}
};

};


std::string std_acc(const tVec& in)
{
std::string init="";
timer t(__func__);
auto result = std::accumulate(in.begin(),in.end(), init);
std::cout << "result.size()=" << result.size() << std::endl;
return result;
}

namespace hz
{
std::string acc_t(const tVec& in)
{
std::string init="";
timer t(__func__);
auto result = hz::accumulate_t(in.begin(),in.end(), init);
std::cout << "result.size()=" << result.size() << std::endl;
return result;
}

std::string acc_t_t(const tVec& in)
{
std::string init="";
timer t(__func__);
auto result = hz::accumulate_t(in.begin(),in.end(), init, hz::increase<std::string>());
std::cout << "result.size()=" << result.size() << std::endl;
return result;
}

std::string acc(const tVec& in)
{
std::string init="";
timer t(__func__);
auto result = hz::accumulate(in.begin(),in.end(), init);
std::cout << "result.size()=" << result.size() << std::endl;
return result;
}

std::string acc_op(const tVec& in)
{
std::string init="";
timer t(__func__);
auto result = hz::accumulate(in.begin(),in.end(), init, hz::plus_rv<std::string>());
std::cout << "result.size()=" << result.size() << std::endl;
return result;
}
};

void test(const tVec& v)
{
static const int max_sz = 20*1000;
auto r = hz::acc_t(v);
assert(hz::acc_t_t(v)==r);
assert(hz::acc(v)==r);
assert(hz::acc_op(v)==r);
if(v.size() <= max_sz)
{
assert(std_acc(v)==r);
}
}
int main()
{
tVec v1, v2;
for(int i=0; i<20*1000; ++i)
{
v1.push_back("1234567890");
}
for(int i=0; i<100*1000*1000; ++i)
{
v2.push_back("1234567890");
}

test(v1);
test(v2);
};


================ Ergebnis =================
result.size()=200000
Elapsed time for acc_t: 0ms
result.size()=200000
Elapsed time for acc_t_t: 0ms
result.size()=200000
Elapsed time for acc: 0ms
result.size()=200000
Elapsed time for acc_op: 0ms
result.size()=200000
Elapsed time for std_acc: 2215ms
result.size()=1000000000
Elapsed time for acc_t: 2979ms
result.size()=1000000000
Elapsed time for acc_t_t: 2995ms
result.size()=1000000000
Elapsed time for acc: 3166ms
result.size()=1000000000
Elapsed time for acc_op: 3151ms