2008-03 Copying

Selected Topics in Computer Programming #1

Selected Topics in Computer Programming #1

To Copy or Not To Copy: A Deeper Look at Values in C++

!

A little about me &

$ '(

&

/

&

'. ( ((

.

#

2

( 3

,

.

&

& <

+ 4( /

%

@

/

(( .

// /

(

. ( . (( %

$

(

1 #

(

1

)

. .

(

1

?

/

.

/

>*

/%

%

%

88 '= 88 B>*

.

/

/.

-

(

%

%

/ (

%

.

((

# (

.

. (

/

: # ;

#

/.

/% $

.

# %

((

.

46-

7

.

?

.

& A

+

((

/

(

<

%

. 55"+ 88 .

((

%

88 '= 88

.

88

9

$

(

0

.

&

. *

(

-. +

/ (

.

/

4(

& $ 2 ( # . 7

#

Today’ Today’s topics

) *+ , -

1

"

# 3

Our most important resource: memory & $

& $

/.

. ( '#

@

7 '.

) ( (

( (

.

. .

9 .

C

D* / .

$ . 9 ( ( . )

Memory address characteristics

(

.

& $

D* .

%

( . .

# .

%

. )

@

.

A

# (

C /

.

D

(( % (#

//

#

. #

.

E.

.

/

E.

. % ( ( ((

' (( (

5

/ (

. .

%

3

#

#

//

.

& 2 ( .

(

( #

#

C ./ .

4

(

(( /

* . ( () (

/ .

6

Memory contents characteristics & $ . . % . ) . $

.

$

.

# F% .

(

.

$ @

& $/ . . . . . 6 #

*

D

(( .

- .

Cooperating cells form important abstractions '/

%

& 2 ( . #

%

/

/ (

(

1

/ %

?

. ) .

#

) ?

((

. #

?

. ( ) # . # . *

% .

.

% %

.?

.

%

7 /

& $ .

.

. /

. . . 6 #

% ? ?

? / '. ( * & $/ . . % / % / . ' 4/ * .

. % ( ( ?

?

'

A

7 %

% #E . ? #E .

/ '. ( * & $ #E . . % / % / . ' 4/ * (

.

%

G

)

/ /

#E . ) #E .

. ?

( 7

A historical perspective

8

Instruction architecture &

=$#

.

/

. (

1

# /

# (

%

.

(

3

>

3

. D 7

'

'G

&

:

*(

*

.

. . (

.

50"

.

D

.

.

.

/ ) ( (

. (

/

.

.

.

%

$ . %

%

.

// . 4

. .

$

%

.

// .

.

9

In the context of a highhigh-level expression & - (

(

! '

& I

%

'

& $

/

%

*

'

!

%

& 9

%

*

94I /

( (

' /

/ .

9/

%

*

#

D

*

. 6 #

%

. ..

1.

% ( (

/.

@ ) 11

* /

%

& $/

%

. )

' '(

I

(

% // . (

!

(

9/

/

& - (

% 9/

(

H 8H –H

(

Recognizing lvalues and rvalues in C++

*

/

10

/ / . . / / .

( ( .

. +

.

. (

.

% 12

Examples of lvalues and rvalues

The lvaluelvalue-toto-rvalue conversion

& 6

& $ "" ""

J #.J

& $/

#$ #$

. "" "" "" ""

#

.

K0L%

/'

/' * /' *

"" ""

#

#

( . .

( (

$

88 %

& - . . %

%

%

@

(

&

*+

. ) % / . . %

%

#

. ) %

. ((

. 1 '

%

%

.

. %

.

(

%

(

1 (

M

'

*+

"" ""

# #

@

% %

H #+ 44

.

/

%

. %

%

. %

# /

%

)

13

Mutable vs. immutable values &

. % . /

'

@

/ #

(

.

@

%

.

@ .

(

%

/ /

.

% / #

*

#

4.

) (

# .

& $

(

/ #

/

% '*

% %

& $

%

updates the newlycreated mod. rvalue

+

.

P .

#

( @ ?

N

# . '* %

/

%

.

14

Analyzing some traditional operators

% (

*

(( %

%

/ /

. ' * ' *

$$

%

.

.

& $/

.

. !

+

' * 8 H

& $/

%

( @ ?

(

P

%

/ #

& 9. ( (

/ #

/ 1/ ( ' * N O . ' * N 88 + O

%

. (

@ ?

.'*

%

c'tor produces a modifiable rvalue

%

88

/ 1/ (

%

88

# %

O+ 15

Using pointer types & G

/

Analyzing some pointerpointer-related operators

%

- (

& G

% %

/

3

/

@

(

% /

.

/

.

(

.

.

%

. %

.

9

D

' # . 7

'

&

%

/

.

17

%

%

*

*

*( ( / . '

( *

%

%

# D

.)

'

%

'

@ ? P

/

( (

P %

M*

' $ %

'#

/ .

%

& 9

#

% %

' %

P

%

%

%

- (

/ @ ?

# ) (

*

& $

/

%

- (

& $ % . %

16

*

* /

% 18

Arrays’ Arrays’ relationship to pointers & G

/

)

Functions’ Functions’ relationship to pointers

(

(

/ #

%

%

'

. & $

%

@

%

. %

)

' P

%

'

4 #.

Q . 3

/

.

@

$

%

(

/ #

% % (

%

%

. % /R S . (

%

%

' / ? .

.

/

/

.

* .

)

. (

&

'* 6 /

' 8#* %

(

.

% / / . ( / #

*D

' KL*

K# L

)

(

& $ & G

(

)

1

.

.

KL* %

@

/ /

*

/

%

& $

& 9

& G %

' (

#

.

Q .

8*D

(

' )

.

.

/ %

.

)

# .

*

%

*

% ./

'/

C

.

P

*

' (

?

%

%

19

Simple decay can be just what’ what’s needed & 2

.

1 (

& $

/ %

2'

20

Using traditional reference types

1 (

*+

&

%$/

/

% /' *+ 2 T / H M /+ 'T/ *' *+

$ + $T H M + 'T *K L+

/

"" "" ""

'

O

$

.

M

.

%

' * N ""

./

(

.

$

H

0 U5 "2+

+ '

& G

$

/ ' *+

/ .

$K L+

/

(

%

#

/

- (

K L+

"" (

/

.

(

& V% % . # # 9/ (

/

. '% 7* W

'

/ #

9/

(

( / #

%

%

#

/

/ #

/

.

*

%

%

%

21

Examples of lvalue reference bindings &

#

(

/

/ # .

. '(

% .

.

22

Binding during call/return ( *

/ #

%

& 9

(+ M H (+

&

#

%

/

. .

(

4

%

(

H (+ H + M H +

""

$

M M

""

/ #

& 9

H ' *+ H +

"" ""

/

'/

. (

) % ' (

. +

( 7 (( #

%

D

.

D . %

# *

.

. (

$

. #

(

(

Q
. (

.

( $

( %

/ (

7 /

M

%

(

@

%

.

.

.

. (+ . . .

7 /

/ ( # * #E . *

. #

. ( #

(

.

( .

( C

.

/

$ 23

24

0

Copying in today’ today’s C++ & $

% %

& A

%

But copying isn’ isn’t always what it seems to be

%

'

.

A (

.

& - . .

.

.)

.

.

%

"" "" #

M

$

$

#

.

.

/ .

.

.

%

1 ( /' K L*+ K L+ /' *+ ""

'

'

X

& 2

RS%)

. *+

.

. *+

'

1 (

% H'@M

.

. %

%

. *+ '

/

& $

$

@'@M @M

% . / .

.

)

M

. .

.

(

%

. *+ H'@.

/ $

. D

*

$

@'@. @M

/

(

. '

""

& A

% ( (#

.

?

/

*

'

'

' ' *+

* *+

*+ ""

'

$

25

26

Why should we programmers care about copying?

Example: unnecessary temporaries [Sutter, 2000]

&

& =$

88 %

.

. L

1 >K =#

.. / C 1 .

%

/

=

(( .

.

/ 2

% . %

.

%

/

1. (

&

.

7

# '%

>

.

%

!

.

% .

$

' X . + ;H / ' T HH

R ( ' X

S X

.

.

+ ( #

X H ' * + 88 * N ( * YS +

* N '*

O

* 1

@

/ / #E . KDL>

(

%

J J+ O

. ) R@S

'

*

(

. 27

28

Strategies to mitigate costly or repeated copying

Introducing a new technique

&

%$& 9

(

. .

! !

& &

/ /

. (

88 H

..

.

8

9

%

/

/

7

. .

. . .

.

(

. . G

( (

&

88 8H

#E . ' #E . # . 7

% (

. .

& 9

*# % / . +

( .

88 B

. / (

/

% 1

( %

( ?

.

( ?

.

.

C %

#

.

(

. ( % #

.

D

%

.

.

(

.

D

( %

% % ' /

(

( .

. (

#

.

* . 29

30

U

Today’ Today’s topics <

Selected Topics in Computer Programming #1

@

To Copy or Not To Copy: A Deeper Look at Values in C++

. (

7

(

<

.

$

?

% 1

88 ?

/.

1 %

. 4.

/

4(

88

.

/

/.

-

88

)

1 /

.

/%

%

/% $

%

.

& A

/ . 1 /

( .

(

%

%

/ (

%

.

# (

. (

%

(

/ (

. 32

Overview of move semantics & , %

.

/

@

. ) %

@

.

%

#

#

#

&

&

Copy semantics visvis-à-vis move semantics

. . / 1

)

.

%

/

( % ' /

% @ ' %

.

.

(

. (

# .

& - . . .

/

%

#

#

( %

(

( .

& , %

D

. 1.

H

? *

& 2 %

. ..

.

.)

( % ( %

. $$

?

(

.

*+ #

( . .

.

$. (

#

(

4( % .)

(

.

*

"" *# *+ ""

' # HH M M M # ;H M ( % ' # *+ "" $$ ' HH *+

@

D

.

'

(

/

) 4. ) .

%

(

' # HH *+ H #+ "" $$ ' HH # M M # HH

/ (

/

.

& D

.

*/

.

& @

.

.

?

)

.

( 7 ( %

)

/

? .

( % #

33

Advantages of a movemove-aware &

% .

R@S .

% .

( ?

.

, part 1

34

Advantages of a movemove-aware

/ @) ( % #

&

# //

% .

R@S . '

old buffer

( ? *

( /

( W - . .

( % #

'

.

# // ( )

* #

. # ( % # // . ( W - . % ( % %

new buffer

, part 2

/ @) ( % # # //

old buffer

new buffer

% .

. = .

'

. =

* >

> C .? #

# // # ( % % 35

36

"

Advantage of a moveable &

Applicability of move semantics

% .

1 (

& , % % . R @ S /' % . R@S ""

* N + '

@

+ ,

+ ""

(

% .

RS)

O

H

W , % /

& , %

( . ((

% .

( , %

.#

/ . # //

/

/

)

1

%

# //

/ # //

% .

$

.

& $

1 .

%

/

()

(

#

# .

/(

(

/ .

(

(

. %

( %

( % /

88

/ #

D

;

( # ( % # # / # % *. 1 , % # %

((

1

D

%

.

1

. .

. (

# // ;

#

? ..

(

# % ( . # D (

.

@ ? 6 %

/

#

( % '#*+

. /( (

& , %

# .

. .

!

.

.

' .

( %

# /

.

37

38

What is an rvalue reference? [H. Hinnant, 20022002-2006]

New function overloading options

& $. (

&

2 (

&

#

( .

?

MM

/

.

/ (

.

1 ( @ MM @ + @ MM

& @

H @' *+ "" H +

) @M @.

$

""

H @' *+ "" M

$

& $/

H @' *+ ""

.

$

/ . .

.

%

M * N MM* N

O O

.

"" ""

.

* *

?

% / .

%

$

4%

(

"" /0 "" /1

.? /' *+ /' 8 *+

. )

/' /'

& I%

$

$

(

% % %

@ MM

/

. %

.

/0 /1

.

/

(

%

#

? %

$

39

Bindings to references

40

Type deduction from an rvalue reference & @

)

.

( % N

. ' @ ' @

.

@

/

/R

% ? * S' *

2

O

& $

41

) . %

R. @S / ' @ M M * ""

#

# % / % .

#

( % .

'. .

.

( ( .

/

* % /' *

% ? % /' * ( / * M . /R M S' *

42

Z

The new library component

ReferenceReference-toto-reference types &

88 /

#

/ (

/

/

.

.

!

@

/@

. M

&

M

@M

(

/

.

/

%

. .

@

C %

..

(

.

Q

&

.

M

@M

M

M

@ MM

M

MM

@M

M

MM

@ MM

MM

/ # '%

@

4%

(

@

/

( % '*

&

/

*

%

.

'

%

( #

.

R. @S ( % X / . R@S ( % ' @ MM * N + O

D

D #E . *

(

&

(# ( % '* % /

MM

. ( %

'

* .

.

( % #

?

@

43

44

Evolution of a movemove-aware standard algorithm

How to make a class movable

&

& $

&

(

R. @S % '@M @M @ ( ' *+ @ H #+ # H ( + # O

.

#

9/ @

. .

#

( % # % / (

9/ @ '

( % # % # .?

'*. .

/

( Transfers the resource from the source to the target

N

.

.

. .

T

% .

Then leaves behind a resource-free source

+

# . '* ' * N O ' MM .* ' . * N M H ' MM .* ' . *+ T + O [ '* N + O

;

' *) # % . ( # *

( %

%

E

%

#

1 ( .

% .

+

# ( %

9/ @ (

& -?

( X

1 /

.

( . ( % .)

.

. )

& 6 )

#* N ( ' ( % ' * *+ H ( % ' # *+ H ( % ' ( *+

.

H + O

N

Exchanges the resources of the source and the target

O+ 45

Movability is orthogonal to copyability & $.

.

# .

9)

#

( % #

.

A . %

& $.

.

! #

@ C

Phasing in move semantics 1

#

/

# ( % #

) # . (

( ( % # / /

?# . ( % #

((

% 1

(

1 .

/

.

. 88

# #

# ; $ D

/

#

% E

#

E

RS

-

(

% A 47

/ %

.

( ( % ((

# # . (

( %

/( % # . ( D . . ( % '*

# ( ( %

% . (

# (

?

. % .

#

1

( . @ I/

( S %+ ( 'J( / J* *+ ( % .

.

1. / ( % / ( . D F # . ( 4 ? ! % % . RS ( . / % ;

(

( % # # / + /( % / .

% . R X# .?'

%

4(

46

. / ( . ( # (

( % # # . % ( ( % #

.

?

48

MoveMove-aware

utility components

( % '*

&

( % X

&

( ? X( % X

&

1 (

'

'*

(

/

.

.

& $.

*

(

R

$

S %' #

"" 3346)

?

%

&

'* ' * *+

(

R

# /

$

. ( % # '

#

, ? , ?

S +

"" 3345)

% .

.

, ,

RS

R % .

When to make a class movable? & 6 ,

&

.

' # '

.

D ;*

(

. /

D ( (#

.

(

#

4( ( #

@W

$ %. ( ? ( ( % # # . @ / # / ( . @ , ? D @ ) / ( . @ , ? ' ( ( % . E . # / *

%

S % ' ( ? X( % X ( ? X( % X

.

/ / ( ( % . #

.

( . (

,\

'** ' * * *+

49

The forwarding problem &

. 9 /

Consider just the generic twotwo-argument case

/'

*

/ ?

'. * ' (

*

/

.

#

%

& $

(

&

(

&

(

&

(

/ .

D

%

&

D

%

% / .

. <

50

'.

9%

* / (

# %

/ (

/(

# (

- %

. (

88

%

#

(

& A

//

%

#

'

# .

)

*

88

# /

/ .

//

.

& $ / .

In sum &

/ .

.

$ S

$ MM X

1 (

R@S '

@'

*

*+

/ /

R$ S' R$ S'

%

.

#

(

( .)

/

.

.

(

) %

M

.

@-

-

*+

$ S

$ M

*+

.

$ S M

*+

'

/

.

#

% // . %

%

# *

.% %

52

% // .

% .

( (

/ %

(

.

88

88 %

. (

$ .

%

%

& 2

* *

'

$ S

) . %

)

. RS' * D

@ /

$

$ S *+ "" $

((

*

O

/

R. @ . X R@S '$ . M

(

N

& @

.

#

&

$

$

%

Solving the forwarding problem in the next C++ R. @ . X R@S ' $ MM

R. @ . X R@S '$ . M

%

51

(

.

R. @ . $ X R@S '$ M $ .

/ .

/ .

R. @ . $ X R@S '$ M $ M

# 4%

?

.

.

@ ( . ((

% / ( . . . ( .

@

.

.

#

C

( ( D

( %

. #

/ # @D 4% 53

54

5

29A Selected Topics in Computer Programming #1

To Copy or Not To Copy: A Deeper Look at Values in C++

!

"

#

$

%