Previous Table of Contents Next


8.3.6.1. Segmented Architectures

One of the engineering decisions to be made when designing a computer architecture is how to store memory addresses as part of machine instructions. The difficulty stems from the fact that many instructions do not need to be able to address completely arbitrary memory locations. Instead, they use local variables (whose addresses are usually a small offset from a stack register) or variables that are already in registers. This difficulty is compounded by machines whose memory addresses exceed the machine’s natural word size. Such machines often need to store memory addresses in two registers, rather than one, and manipulate those registers as needed to form full addresses.

The most common such machine architecture today is found on so-called 16-bit personal computers. The idea is that the machine’s internal registers are 16 bits long, but the available memory addresses exceed 216. In general, then, it may be necessary to store pointers as two words, one of which contains high-order bits of the address and the other of which contains low-order bits.

The following discussion is somewhat simplified from the actual situation on these machines but is a good description of the general problem. Suppose that every pointer p is represented by two values p0 and p1, where p0 contains some number of low-order bits of p and p1 contains the remaining, high-order bits. Assume the same relationship between q, q0, and q1. Then it is fairly easy to say what it means to claim that p=q: We say that p=q if an only if p0=q0 and p1=q1.

Moreover, the test for p=q is likely to be quite fast as long as we test for p0=q0 first because most of the time p0 and q0 differ and we do not even have to inspect p1 or q1. For instance, in a loop like

   while (p != q) {
         // ...
         ++p;
   }

most of the time, the test p!=q is satisfied after comparing p0 and q0.

Now consider what it means to test whether p<q. It does not help to compare p0 and q0 because the result of that comparison gives no useful information if the high-order bits in p1 and q1 differ.

To see this, consider the analogy of two-digit decimal numbers. You cannot learn that 37<54 by comparing 7 and 4; you must look at the high-order digits first.

The first order of business, then, must be to compare p1 and q1. If p1<q1, then we know that p<q and similarly if p1>q1. But if p1=q1, we must then compare p0 and q0 before we have the final answer. In other words, p<q if and only if p1<q1 or (p1=q1 and p0<q0).

Now consider a loop such as

   while (p < q) {
         // ...
         ++p;
   }

If we are going to count on p and q eventually becoming equal, it is likely that their high-order bits will be equal in many of the comparisons in the loop. That implies that most of the pointer comparisons will have to do two machine-level comparisons (p1<q1 and then p0<q0) instead of the one comparison (p0=q0) that was necessary most of the time when checking for p!=q. It appears, therefore, that loops on machines of this kind are much slower if they use < than if they use !=.

The definition of C circumvented this problem in a clever way. Consider the p<q comparison. If p and q point to elements of different arrays, it is up to the implementation which array comes first in memory. Therefore, goes the reasoning, there is never a legitimate use for comparisons such as p<q unless p and q point to elements of the same array. For that reason, C defines such comparisons only if p and q point to elements of the same array. That way, if a compiler knows that p1=q1 whenever and p and q point to elements of the same array (and it is possible for a compiler to arrange that in many cases), it is not necessary to compare p1 and q1 at all; the compiler can translate p<q directly into p0<q0.

Because C imposes this restriction, it was necessary for C++ to do so as well. To do otherwise would place C++ at a performance disadvantage compared to C when executing programs that use pointers in common ways.

The detailed reasoning here may be hard to follow without reading it several times. The important thing to remember is that, for efficiency reasons, C and C++ define p==q and p!=q for arbitrary pointers, but they define p<q only if p and q point to elements of the same array.


Previous Table of Contents Next