When "Generic Code" Doesn't Quite Cut It





When "Generic Code" Doesn't Quite Cut It

Consider the following example:

template<typename T> 
class Array { 
  private: 
    T* data; 
     
  public: 
    Array(Array<T> const&); 
    Array<T>& operator = (Array<T> const&); 

    void exchange_with (Array<T>* b) { 
        T* tmp = data; 
        data = b->data; 
        b->data = tmp; 
    } 
    T& operator[] (size_t k) { 
        return data[k]; 
    } 
     
}; 

template<typename T> inline 
void exchange (T* a, T* b) 
{ 
     T tmp(*a); 
     *a = *b; 
     *b = tmp; 
} 

For simple types, the generic implementation of exchange() works well. However, for types with expensive copy operations, the generic implementation may be much more expensive—both in terms of machine cycles and in terms of memory usage—than an implementation that is tailored to the particular, given structure. In our example, the generic implementation requires one call to the copy constructor of Array<T> and two calls to its copy-assignment operator. For large data structures these copies can often involve copying relatively large amounts of memory. However, the functionality of exchange() could presumably often be replaced just by swapping the internal data pointers, as is done in the member function exchange_with().

1 Transparent Customization

In our previous example, the member function exchange_with() provides an efficient alternative to the generic exchange() function, but the need to use a different function is inconvenient in several ways:

  1. Users of the Array class have to remember an extra interface and must be careful to use it when possible.

  2. Generic algorithms can generally not discriminate between various possibilities. For example:

    template<typename T> 
    void generic_algorithm(T* x, T* y) 
    { 
        
       exchange(x, y);  // How do we select the right algorithm? 
        
    } 

Because of these considerations, C++ templates provide ways to customize function templates and class templates transparently. For function templates, this is achieved through the overloading mech-anism. For example, we can write an overloaded set of quick_exchange() function templates as follows:

template<typename T> inline 
void quick_exchange(T* a, T* b)                // (1) 
{ 
    T tmp(*a); 
    *a = *b; 
    *b = tmp; 
} 

template<typename T> inline 
void quick_exchange(Array<T>* a, Array<T>* b)  // (2) 
{ 
    a->exchange_with(b); 
} 

void demo(Array<int>* p1, Array<int>* p2) 
{ 
    int x, y; 
    quick_exchange(&x, &y);                    // uses (1) 
    quick_exchange(p1, p2);                    // uses (2) 
} 

The first call to quick_exchange() has two arguments of type int* and therefore deduction succeeds only with the first template (declared at point (1)) when T is substituted by int. There is therefore no doubt regarding which function should be called. In contrast, the second call can be matched with either template: Viable functions for the call quick_exchange(p1, p2) are obtained both when substituting Array<int> for T in the first template and when substituting int in the second template. Furthermore, both substitutions result in functions with parameter types that exactly match the argument types of the second call. Ordinarily, this would lead us to conclude that the call is ambiguous, but (as we will discuss later) the C++ language considers the second template to be "more specialized" than the first. All other things being equal, overload resolution prefers the more specialized template and hence selects the template at point (2).

2 Semantic Transparency

The use of overloading as shown in the previous section is very useful in achieving transparent customization of the instantiation process, but it is important to realize that this "transparency" depends a great deal on the details of the implementation. To illustrate this, consider our quick_exchange() solution. Although both the generic algorithm and the one customized for Array<T> types end up swapping the values that are being pointed to, the side effects of the operations are very different.

This is dramatically illustrated by considering some code that compares the exchange of struct objects with the exchange of Array<T>s:

struct S { 
    int x; 
} s1, s2; 

void distinguish (Array<int> a1, Array<int> a2) 
{ 
    int* p = &a1[0]; 
    int* q = &s1.x; 
    a1[0] = s1.x = 1; 
    a2[0] = s2.x = 2; 
    quick_exchange(&a1, &a2);  // *p == 1 after this (still) 
    quick_exchange(&s1, &s2);  // *q == 2 after this 
} 

This example shows that a pointer p into the first Array becomes a pointer into the second array after quick_exchange() is called. However, the pointer into the non-Array s1 remains pointing into s1 even after the exchange operation: Only the values that were pointed to were exchanged. The difference is significant enough that it may confuse clients of the template implementation. The prefix quick_ is helpful in attracting attention to the fact that a shortcut may be taken to realize the desired operation. However, the original generic exchange() template can still have a useful optimization for Array<T>s:

template<typename T> 
void exchange(Array<T>* a, Array<T>* b) 
{ 
    T* p = &a[0]; 
    T* q = &b[0]; 
    for (size_t k = a->size(); --k != 0; ) { 
        exchange(p++, q++); 
    } 
} 

The advantage of this version over the generic code is that no (potentially) large temporary Array<T> is needed. The exchange() template is called recursively so that good performance is achieved even for types such as Array<Array<char> >. Note also that the more specialized version of the template is not declared inline because it does a considerable amount of work of its own, whereas the original generic implementation is inline because it performs only a few operations (each of which is potentially expensive).


     Python   SQL   Java   php   Perl 
     game development   web development   internet   *nix   graphics   hardware 
     telecommunications   C++ 
     Flash   Active Directory   Windows