Robert M. Adams is an independent consultant specializing in defense applications. He lives in Dallas, Texas, and can be reached on CompuServe at 71214,1553 or on Internet at [email protected].
Introduction
A problem that frequently occurs in C++ is excessive copying of objects as they are passed around within a program. For example, consider a typical vector class. Whenever a vector object appears on both sides of an equal sign, the program copies the vector from the source object to the destination. When a function returns an object in an assignment statement, there are two copy operations. The second copy operation occurs because C++ creates an intermediate, temporary object as functions and overloaded operators pass complicated objects from source to destination. The C++ program first copies the source object to the temporary object, then copies the temporary object to the destination.
It's unfortunate that operations like the preceding carry such a performance penalty. The vector class exemplifies a group of objects that are potentially quite useful, and seemingly made for overloaded operators and all the other formal goodies that C++ provides. C++ seems especially appropriate for a vector or matrix class since it allows the outward form of vector and matrix expressions to follow the standard notation adopted many years ago in mathematical circles, or at least to approximate it, as FORTRAN does for scalar arithmetic operations.
So, I have looked for ways to provide general vector and matrix capability without invoking the inefficiencies of C++ copy operations. Here is what I would like to find in a vector and matrix class library:
1. Linear algebraic formula conversions
2. Minimization of unnecessary copy operations and other overhead
3. No requirement of programmer awareness of deeper structures in library classes (e.g. multiple access, reference counters, etc.)
In this article, I present a technique for passing complicated objects using efficient copy constructors, through the use of dual classes. Other techniques will accomplish the same results, though they have certain disadvantages. Therefore, I briefly describe these techniques as well. I begin by describing the way C++ normally handles complicated objects in function returns and overloaded operators. I then show some feasible alternatives and, finally, I present my temporary object management technique.
How C++ Returns Complicated Objects
Consider Listing 1, defining the Vector function unit, which receives a reference to a Vector v. After construction of the return parameter, the meat of the function follows. To find a unit vector in the same direction as v, unit divides each element of v by the length of v:
where vi are the components of v. It is very easy to evaluate this function using for loops and the overloaded () operator to access the elements of u and v.
unit then returns the resulting vector u. At this point, things begin to get a little complicated. u is local to the function; therefore, it must be gone when the function ceases to execute. But u contains the result needed by the calling program. To pass u to unit's caller, C++ creates an object, unnamed and invisible, within the scope of the calling program to receive the return parameter of the function. C++ uses the return object class's copy constructor to create this invisible object, with Vector u as the source of the copy. Then the u is destroyed, along with everything else that was local to the function unit, and control makes its way back to the caller. All of these operations are in accordance with the current standard [1].
The calling program may use the function value to perform an assignment or to fill new storage allocated for a vector definition, as in the statement
Vector x = unit(y);In either case, C++ again invokes the copy constructor to copy the invisible Vector object to the destination. The program never uses the invisible Vector object again and this object is ultimately destroyed. The process I have just described accounts for the two copy operations that occur when C++ returns complicated objects from functions.
If these copy operations involved only a few bytes, the issue would be trivial, merely some more exercise for the fast copy routine. But a vector can have any (reasonable) length, so the copy operations can eat up processor power in a hurry if the vectors are big.
Alternative Vector Designs
One way to prevent excessive copying is to avoid Vector function returns entirely by providing the object to be returned in the parameter list, as in:
void unit (const Vector& v, Vector& u);I would call this the retrograde approach, why use C++ to write this kind of statement? The resulting code has lost its formula-like appearance. Moreover, this form doesn't allow the use of overloaded operators.
Another approach to the problem, reference counting, is illustrated by a commercially available linear systems package which I will call Q& (not its real name).
The Q& package defines a variety of vector and matrix classes, having in common that their constructors allocate the Vector Element Space (or VES, the space that holds the vector or matrix data) and their destructors deallocate the VES. Q& does not copy the VES in these classes' copy constructors or in the assignment operators. Instead, Q& writes the pointer to the source VES into the new Vector and maintains a count of references with the VES itself (which therefore has a structure of its own). Thus, several Vectors can exist simultaneously, all pointing to one VES and, by definition, all having the same value. When a Vector is constructed requiring a new VES, Q& allocates the VES and sets the reference count to one. Any time another Vector is constructed that points to an existing VES, the constructor increments the count of references. When a Vector is destroyed, the destructor decrements the count of references, and if the count is zero, Q& releases the VES. Listing 2 illustrates the general idea. (This listing only outlines the technique — it does not represent actual code from the Q& library, which I consider to be very refined and safe.)
Reference counting reduces unnecessary copy operations, but imposes its own difficulties. One difficulty is that when a Vector component changes in one instance, the Vector's value changes for all instances that reference the same VES. Multiple references to a common VES do not often create a problem, but to stay out of trouble the programmer must be aware of the common VES and must have access to a "deep-copy" function that can create a Vector copy with a unique VES when required.
The reference counting mechanism also entails overhead for additional pointer fetches, required for every initial access to the VES.
One writer [2] proposes that the language designers should be: eliminate copy constructor invocation on function return by allocating memory for the function's return parameter within the scope of the calling program. This plan provides the advantage of invisibility (what most people call transparency), but is complicated by the possibility of multiple, different return statements. I wouldn't be surprised if this method introduced other nasty complications, but whatever its implications, it's not available as a C++ feature today.
A New Way
I have developed an object-passing technique that uses efficient copy constructors. While I can't prevent invocation of the copy constructor upon return from a function, I can modify this constructor so that instead of copying the contents of the source object's VES to the temporary invisible object, the constructor passes the temporary object a pointer to the source object's VES. A second crucial step in my technique is to set the source object's VES pointer to null, thereby preventing the source object's destructor from releasing the VES's memory upon function return. I call this two-step process "seizing the VES."
Seizing the VES is similar to reference counting in that no copying of Vector components takes place, but it's different because it maintains no explicit data field indicating when the VES may be destroyed. Eliminating the reference count scheme simplifies the copy constructor and the Vector class, but the class design is not complete because I've yet to solve another nagging problem: a function return is not the only action that will invoke the copy constructor. It would be inappropriate for the copy constructor to seize the VES in the following statement, where t is a previously defined Vector:
Vector x = t;I need some indication of when it is appropriate for the destination object to seize the VES from the source object. I could provide a flag as member data for the Vector class, which would indicate whether or not the VES could be seized. Besides its inelegance, this plan introduces two difficulties, that of setting and testing the flag. A better method for managing the seizure of the VES makes use of knowledge built-in to the structure of the program.
Dual Classes
To communicate the seizability of the VES, I've invented a second class of Vectors called TempVector, having the property that their VES can be seized in the copy construction and the assignment operation. The TempVector object has exactly the same member data and many of the same constructors and other member functions as the Vector object, but has a limited lifetime, appearing only in certain contexts. TempVector's sole purpose is to be the type for the return objects in Vector functions and overloaded operators.
Consider Listing 3. The first class defined is the Vector class with dynamic VES and suitable operators and friend functions. The second class given is TempVector. While it contains many of the same member data and functions, it differs in certain details from the Vector class. In particular, the TempVector copy constructor simply transfers the pointer to the VES from the source TempVector to the destination TempVector, replacing the pointer value in the source TempVector with a null. (This is what is meant by "seizing" the VES.) Now, note that in both class definitions the Vector addition operator + returns a TempVector. In a Vector addition, the compiler first invokes the TempVector copy constructor to seize the VES as it is returned from the addition operator. In an assignment operation involving a function return, the compiler invokes the form of assignment that seizes the VES from the TempVector and gives it to the object on the left side of the equal sign. In effect, those occasions of temporary object use are identified by the assignment of a different type to temporary objects.
An Example
Consider the following example, involving the sum of two existing Vectors with the result to be placed in a third:
t = u + v;The compiler can recognize that the right side is a temporary result, that is, that the right side result is a TempVector. Invoking the correct overloaded assignment operator causes the entire command to be carried out with no unnecessary copy operations. The order of operations are as follows (see Figure 1) :
1. Upon invocation of the + operation, operator+ compares the lengths of the vectors for equality (an error is returned for non-conformal addition).
2. operator+ constructs a TempVector with VES of the appropriate size.
3. operator+ performs Vector addition and stores the result in the TempVector VES.
4. operator+ returns the TempVector.
5. The TempVector copy constructor is invoked to construct an unnamed, invisible TempVector in the calling program scope.
6. The TempVector copy constructor seizes the VES from the operator+ return parameter TempVector, by placing a pointer to the VES in the TempVector being constructed, and setting the VES reference in the return parameter TempVector to NULL so that the VES will not be released.
7. The return TempVector in the operator+ scope is destroyed along with all the other local variables; the destructor finds no VES to release.
8. Control returns to the calling program.
9. The Vector assignment operator is invoked for Vector t with the invisible TempVector as a parameter, also releasing the VES currently owned by t, if any.
10. The assignment operator seizes the VES from the invisible TempVector by placing a pointer to it in the Vector t, and setting the VES reference in the TempVector to null so that the VES will not be released.
11. Control is returned to the calling program; the invisible TempVector is destructed; the invisible TempVector's destructor finds no VES to release.
12. The next instruction is executed.
My scheme imitates the above scenario in all possible Vector expressions. Note that TempVector is the only class that can have its VES seized. The copy constructor for Vector always allocates a new VES and copies the source VES to it. Also, in forming the classes this way, I have accounted for the difference in processing required for
Vector t = u + v;and
Vector t = u;In the former, the Vector t receives the VES from the TempVector produced by the Vector addition operator. In the latter, the Vector t receives a new VES copied from the VES that belongs to and remains with the Vector u.
Dual Class Performance
In an informal comparison of the methods outlined in Listing 2 and Listing 3, I repeatedly summed (100,000 repititions) a set of vectors 12 doubles in length with the result unitized:
c = unit (a + b);I used Borland C++ 3.1 on a 33 MHz 486. The results in seconds were:
Dynamic VES with reference counting 22.14 Dynamic VES with dual classes 17.67The dual class method held a 25% time advantage over the reference counting method. While this informal benchmark is hardly an exhaustive test of the idea, it strongly suggests that I'm on the right track.
Drawbacks and Restrictions
There are certain inherent drawbacks to the system proposed here. For one thing, the number of operator functions proliferates by a factor of approximately four, because I must allow for the possibility in a binary operator that one, the other, both, or neither of the operands may be a TempVector. This proliferation does not pose a problem except in increase of the library debugging effort and in bulkier libraries. Also note that the constructors for TempVector are private, so the user cannot take advantage of the dual class scheme, without making those functions friends (at least) of the Vector and TempVector classes, and thus requiring their obedience to the interior rules of the library.
One interior rule stipulates that when a TempVector is defined in the function to serve as a return parameter, the TempVector must never be used in such a way that it loses its VES. That is, a TempVector must never stand alone on the right-hand side of an operator = (assignment). Also, a TempVector should never be used in a global or static definition. Other than that, the TempVector and Vector structures may be used freely. If the programmer feels comfortable enough with these restrictions, he can make the TempVector constructors public and use them throughout his code as function return parameters.
Conclusion
The dual class of temporary objects have the special property that the VES they may own can be seized by a successor operation, such as copy construction following function return or the assignment operation. This feature is designed to reduce the overhead of unnecessary copy operations. In concert with other measures to reduce the cost of computation, the dual Vector classes can be made the basis for a complete library of vector and matrix functions and operators having very low operating cost. Moreover, the principles exemplified by the TempVector and Vector classes can be extended to the Matrix class, the String class, and any other class containing a large, variable-length data structure of reasonable homogeneity.
1. 1.Ellis, M., Stroustrup, B., The Annotated C++ Reference Manual, Addison-Wesley, Reading Ma, 1990, pp. 300-303.
2. 2.Wilkinson, Nancy M., "C++ Return Value Optimization," C++ Journal, vol. 2, no. 1, 1992, pp. 47-51.
