Some Subtleties of Aliasing
Last month, I mentioned an example that slipped by without the scrutiny that it deserved:
void scale(vector<double>& v, const double& x) { for (auto p = v.begin(); p != v.end(); ++p) *p /= x; }
I described this example by saying that it "divides every element of a vector by a given scalar. The program's author defines the scalar parameter x
as a reference in order to avoid copying it."
As an example of a problem with this code, I suggested that it might be called by writing
scale(v, v[n]);
with the aim of dividing every element of v
by v[n]
, but that this call would actually do something else entirely. From the comments on the article, I think that some readers were unclear about what that something else might be. To understand this call's behavior in detail, we have to look at the code more closely.
Let's begin by assuming that v
is a vector<double>
, and look at this code (not as part of a function):
for (auto p = v.begin(); p != v.end(); ++p) *p /= v[0];
What does this code do?
We'll begin by noting that the code does nothing at all unless v
has at least one element. In that case, the first trip through the loop has the effect of executing
v[0] /= v[0];
which, in turn, has the same effect as executing
v[0] = 1;
(unless v[0]
was already zero, in which case the effect is undefined).
Once we have set v[0]
to 1
, each subsequent trip through the loop divides a different element of v
by 1, effectively leaving that element's value unchanged. In other words, this entire loop is equivalent to writing
v[0] = 1;
in all cases in which the original loop is well defined in the first place.
Now let's look back at the original scale
function, and imagine that we call
scale(v, v[0]);
This call has the same effect as executing
v[0] = 1;
for exactly the same reason as before. The second parameter to scale
, x
, is a reference to a const double
. In this case, that reference refers to v[0]
. As soon as the value of v[0]
is set to 1, every additional trip through the loop divides an element of v
by 1 in exactly the same way as the previous example.
You may argue that this behavior is probably not what the programmer intended. In particular, the statement
*p /= v[0];
was almost surely intended to use the same value for v[0]
each time through the loop, rather than having that value change merely because *p
and v[0]
happen to refer to the same location in memory.
But that's the problem: Regardless of what the programmer might have intended, what the programmer wrote is crystal clear. A programmer who intended to use the same value for v[0]
each time through the loop would have defined x
as double
rather than as const double&
. The moment one defines a reference, one admits the possibility that that reference might refer to an object that might have different values at different times.
This example shows how aliasing can cause paradoxical behavior. Often, one writes a function parameter as const double&
rather than as double
because of a desire to avoid copying the parameter when it might not be necessary to do so. However, this strategy of avoiding copying is useful only when it is possible to be sure that the parameter's value does not change at any point in the function that uses the parameter. In this particular example, when the compiler sees that x
is a const double&
, it has to take into account the possibility that any statement that might change the value of any double
object in the entire program might coincidentally be changing the value of the object to which x
refers. As a result, the compiler pretty much has to generate code that copies x
's object every time that object is used, rather than copying the object once at entry to the function and being done with it.
More generally, aliasing is a hazard associated with references and pointers. In the absence of other information, any reference or pointer has the potential of referring or pointing to any object of the given type in the entire program. As a result, using a reference or a pointer typically has to refetch the object from memory, just in case that object might have been changed since last time. As a result, using a reference or a pointer to avoid copying an object has a good chance of backfiring.
As ever, the choice of whether to define a function to be called by reference or by value is better made on the basis of clarity than it is on the basis of whether it is possible to avoid copying an argument.