C++ : Reference and value semantics

PART 15


Q98: What is value and/or reference semantics, and which is best in C++?
A: With reference semantics, assignment is a pointer-copy (ie: a *reference*).
Value (or `copy') semantics mean assignment copies the value, not just the
pointer.  C++ gives you the choice: use the assignment operator to copy the
value (copy/value semantics), or use a ptr-copy to copy a pointer (reference
semantics).  C++ allows you to override the assignment operator to do anything
your heart desires, however the default (and most common) choice is to copy the
*value*.  Smalltalk and Eiffel and CLOS and most other OOPLs force reference
semantics; you must use an alternate syntax to copy the value (clone,
shallowCopy, deepCopy, etc), but even then, these languages ensure that any
name of an object is actually a *pointer* to that object (Eiffel's `expanded'
classes allow a supplier-side work-around).

There are many pros to reference semantics, including flexibility and dynamic
binding (you get dynamic binding in C++ only when you pass by ptr or pass by
ref, not when you pass by value).

There are also many pros to value semantics, including speed.  `Speed' seems
like an odd benefit to for a feature that requires an object (vs a ptr) to be
copied, but the fact of the matter is that one usually accesses an object more
than one copies the object, so the cost of the occasional copies is (usually)
more than offset by the benefit of having an actual object rather than a ptr to
an object.

There are three cases when you have an actual object as opposed to a pointer to
an object: local vars, global/static vars, and fully contained subobjects in a
class.  The most common & most important of these is the last (`containment').

More info about copy-vs-reference semantics is given in the next questions.
Please read them all to get a balanced perspective.  The first few have
intentionally been slanted toward value semantics, so if you only read the
first few of the following questions, you'll get a warped perspective.

Assignment has other issues (ex: shallow vs deep copy) which are not covered
here.



Q99: What is `virtual data', and how-can / why-would I use it in C++?
A: Virtual data isn't strictly a `part' of C++, however it can be simulated.
It's not entirely pretty, but it works.  First we'll cover what it is and how
to simulate it, then conclude with why it isn't `part' of C++.

Consider classes Vec (like an array of int) and SVec (a stretchable Vec; ie:
SVec overrides operator[] to automatically stretch the number of elements
whenever a large index is encountered).  SVec inherits from Vec.  Naturally
Vec's subscript operator is virtual.

Now consider a VStack class (Vec-based-Stack).  Naturally this Stack has a
capacity limited by the fixed number of elements in the underlying Vec data
structure.  Then someone comes along and wants an SVStack class (SVec based
Stack).  For some reason, they don't want to merely modify VStack (say, because
there are many users already using it).

The obvious choice then would be to inherit SVStack from VStack, however
then there'd be *two* Vecs in an SVStack object (one explicitly in VStack,
the other as the base class subobject in the SVec which is explicitly in
the SVStack).  That's a lot of extra baggage.  There are at least 2 solns:
 * break the is-a link between SVStack and VStack, text-copy the code from
   VStack and manually change `Vec' to `SVec'.
 * activate some sort of virtual data, so subclasses can change the
   class of subobjects.

To effect virtual data, we need to change the Vec subobject from a physically
contained subobject into a ptr pointing to a dynamically allocated subobject:

_____original_____		|_____to_support_virtual_data_____
class VStack {			| class VStack {
protected:			| protected:
  Vec v;  //where data stored	|   Vec& v; //where data is stored
  int sp; //stack pointer	|   int sp; //stack pointer
public:				| public:
  VStack(int cap=10)		|   VStack(int cap=10)
    : v(cap), sp(0) { }		|     : v(*new Vec(cap)), sp(0) { } //FREESTORE
  void push(int x) {v[sp++]=x;}	|   void push(int x) {v[sp++]=x;}   //no change
  int  pop()  {return v[--sp];}	|   int  pop()  {return v[--sp];}   //no change
  ~VStack() { }   //unnecessary	|   ~VStack() {delete &v;}          //NECESSARY
};				| };

Now the subclass has a shot at overriding the defn of the object referred to as
`v'.  Ex: basically SVStack merely needs to bind a new SVec to `v', rather than
letting VStack bind the Vec.  However classes can only initialize their *own*
subobjects in an init-list.  Even if I had used a ptr rather than a ref, VStack
must be prevented from allocating its own `Vec'.  The way we do this is to add
another ctor to VStack that takes a Vec& and does *not* allocate a Vec:
	class VStack {
	protected:
	  VStack(Vec& vv) : v(vv), sp(0) { }	//`protected' constructor!
	//...					//(prevents public access)
	};

That's all there is to it!  Now the subclass (SVStack) can be defined as:
	class SVStack : public VStack {
	public:
	  SVStack(int init_cap=10) : VStack(*new SVec(init_cap)) { }
	};

Pros:	* implementation of SVStack is a one-liner
	* SVStack shares code with VStack

Cons:	* extra layer of indirection to access the Vec
	* extra freestore allocations (both new and delete)
	* extra dynamic binding (reason given in next question)

We succeeded at making *our* job easier as implementor of SVStack, but all
clients pay for it.  It wouldn't be so bad if clients of SVStack paid for it,
after all, they chose to use SVStack (you pay for it if you use it).  However
the `optimization' made the users of the plain VStack pay as well!

See the question after the next to find out how much the client's `pay'.  Also:
*PLEASE* read the few questions that follow the next one too (YOU WILL NOT GET
A BALANCED PERSPECTIVE WITHOUT THE OTHERS).



Q100: What's the difference between virtual data and dynamic data?
A: The easiest way to see the distinction is by an analogy with `virtual fns':
A virtual member fn means the declaration (signature) must stay the same in
subclasses, but the defn (body) can be overridden.  The overriddenness of an
inherited member fn is a static property of the subclass; it doesn't change
dynamically throughout the life of any particular object, nor is it possible
for distinct objects of the subclass to have distinct defns of the member fn.

Now go back and re-read the previous paragraph, but make these substitutions:
	`member fn' --> `subobject'
	`signature' --> `type'
	`body'      --> `exact class'
After this, you'll have a working defn of virtual data.

`Per-object member fns' (a member fn `f()' which is potentially different in
any given instance of an object) could be handled by burying a function ptr in
the object, then setting the (const) fn ptr during construction.

`Dynamic member fns' (member fns which change dynamically over time) could also
be handled by function ptrs, but this time the fn ptr would not be const.

In the same way, there are three distinct concepts for data members:
 * virtual data: the defn (`class') of the subobject is overridable in
   subclasses provided its declaration (`type') remains the same, and this
   overriddenness is a static property of the [sub]class.
 * per-object-data: any given object of a class can instantiate a different
   conformal (same type) subobject upon initialization (usually a `wrapper'
   object), and the exact class of the subobject is a static property of the
   object that wraps it.
 * dynamic-data: the subobject's exact class can change dynamically over time.

The reason they all look so much the same is that none of this is `supported'
in C++.  It's all merely `allowed', and in this case, the mechanism for faking
each of these is the same: a ptr to a (probably abstract) base class.  In a
language that made these `first class' abstraction mechanisms, the difference
would be more striking, since they'd each have a different syntactic variant.



Q101: Should class subobjects be ptrs to freestore allocated objs, or contained?
A: Usually your subobjects should actually be `contained' in the aggregate
class (but not always; `wrapper' objects are a good example of where you want a
a ptr/ref; also the N-to-1-uses-a relationship needs something like a ptr/ref).

There are three reasons why fully contained subobjects have better performance
than ptrs to freestore allocated subobjects:
	* extra layer to indirection every time you need to access subobject
	* extra freestore allocations (`new' in ctor, `delete' in dtor)
	* extra dynamic binding (reason given later in this question)



Q102: What are relative costs of the 3 performance hits of allocated subobjects?
A: The three performance hits are enumerated in the previous question:
 * By itself, an extra layer of indirection is small potatoes.
 * Freestore allocations can be a big problem (standard malloc's performance
   degrades with more small freestore allocations; OO s/w can easily become
   `freestore bound' unless you're careful).
 * Extra dynamic binding comes from having a ptr rather than an object.
   Whenever the C++ compiler can know an object's *exact* class, virtual fn
   calls can be *statically* bound, which allows inlining.  Inlining allows
   zillions (would you believe half a dozen :-) optimization opportunities
   such as procedural integration, register lifetime issues, etc.  The C++
   compiler can know an object's exact class in three circumstances: local
   variables, global/static variables, and fully-contained subobjects.

Thus fully-contained subobjects allow significant optimizations that wouldn't
be possible under the `subobjects-by-ptr' approach (this is the main reason
that languages which enforce reference-semantics have `inherent' performance
problems).



Q103: What is an `inline virtual member fn'?  Are they ever actually `inlined'?
A: A inline virtual member fn is a member fn that is inline and virtual :-).
The second question is much harder to answer.  The short answer is `Yes, but'.

A virtual call (msg dispatch) via a ptr or ref is always resolved dynamically
(at run-time).  In these situations, the call is never inlined, since the
actual code may be from a derived class that was created after the caller was
compiled.

The difference between a regular fn call and a virtual fn call is rather small.
In C++, the cost of dispatching is rarely a problem.  But the lack of inlining
in any language can be very Very significant.  Ex: simple experiments will show
the difference to get as bad as an order of magnitude (for zillions of calls to
insignificant member fns, loss of inlining virtual fns can result in 25X speed
degradation! [Doug Lea, `Customization in C++', proc Usenix C++ 1990]).

This is why endless debates over the actual number of clock cycles required to
do a virtual call in language/compiler X on machine Y are largely meaningless.
Ie: many language implementation vendors make a big stink about how good their
msg dispatch strategy is, but if these implementations don't *inline* method
calls, the overall system performance would be poor, since it is inlining
--*not* dispatching-- that has the greatest performance impact.

NOTE: PLEASE READ THE NEXT TWO QUESTIONS TO SEE THE OTHER SIDE OF THIS COIN!



Q104: Sounds like I should never use reference semantics, right?
A: Wrong.

Reference semantics is A Good Thing.  We can't live without pointers.  We just
don't want our s/w to be One Gigantic Pointer.  In C++, you can pick and choose
where you want reference semantics (ptrs/refs) and where you'd like value
semantics (where objects physically contain other objects etc).  In a large
system, there should be a balance.  However if you implement absolutely
*everything* as a pointer, you'll get enormous speed hits.

Objects near the problem skin are larger than higher level objects.  The
*identity* of these `problem space' abstractions is usually more important than
their `value'.  These combine to indicate reference semantics should be used
for problem-space objects (Booch says `Entity Abstractions'; see on `Books').

The question arises: is reference semantics likely to cause a performance
problem in these `entity abstractions'?  The key insight in answering this
question is that the relative interaction frequency is much lower for problem
skin abstractions than for low level server objects.

Thus we have an *ideal* situation in C++: we can choose reference semantics for
objects that need unique identity or that are too large to copy, and we can
choose value semantics for the others.  The result is very likely to be that
the highest frequency objects will end up with value semantics.  Thus we
install flexibility only where it doesn't hurt us, and performance where we
need it most!

These are some of the many issues the come into play with real OO design.
OO/C++ mastery takes time and high quality training.
That's the investment-price you pay for a powerful tool.

	<<<>>>



Q105: Does the poor performance of ref semantics mean I should pass-by-value?
A: No.  In fact, `NO!' :-)

The previous questions were talking about *subobjects*, not parameters.  Pass-
by-value is usually a bad idea when mixed with inheritance (larger subclass
objects get `sliced' when passed by value as a base class object).  Generally,
objects that are part of an inheritance hierarchy should be passed by ref or by
ptr, but not by value, since only then do you get the (desired) dynamic
binding.

Unless compelling reasons are given to the contrary, subobjects should be by
value and parameters should be by reference.  The discussion in the previous
few questions indicates some of the `compelling reasons' for when subobjects
should be by reference.