Alexander Stepanov, one of the founding fathers of generic programming, wrote in his book “From Mathematics to Generic Programming”:
Generic programming is an approach to programming that focuses on designing algorithms and data structures so that they work in the most general setting without the loss of efficiency.
Key are:
the most general setting: it’s not only about being able to
choose the type we work with (e.g., int or double), but also the
data structure (e.g., std::vector or std::list),
no loss of efficiency: we don’t want our program to run slower or take more memory because it was generically written; we want our code to run as fast as when it’s meticulously manually crafted.
Generic programming in C++ is supported by templates and overloading. With templates we can use and implement without the loss of efficiency:
generic data structures, most notably the containers of the standard
library, e.g., std::vector,
generic algorithms, most notably the algorithms of the standard
library, e.g., std::sort.
The example below shows how we can use containers and algorithms of the standard library. This example needs a C++17 compiler.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int
main()
{
vector v{3, 1, 2};
sort(v.begin(), v.end());
for(const auto &e: v)
cout << e << endl;
}In the above example we can change the type of the sorted numbers from
int to double: it’s enough to change type vector to
vector<double> (i.e., to give argument double to template type
vector). We can change type vector to array (with
#include <array> added) or deque (with #include <deque> added).
At compile-time, the sort function template is instantiated
(compile-tailored) for the type of the structure, and the type of the
structure elements used.
Generic programming can operate on data that are not objects,
e.g., C-style arrays, and so it is more general than object-oriented
programming (that works with objects only). We can change the above
example, so that it works not only with containers (which are
objects), but with C-style arrays too: we replace the calls to member
functions begin and end with non-member function templates
std::begin and std::end:
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
int
main()
{
int a[] = {3, 1, 2};
sort(begin(a), end(a));
for(const auto &e: a)
cout << e << endl;
}But that example doesn’t work for type list. The compiler produces
a lengthy error message that’s hard to decipher. The problem is the
list iterator is not random access, i.e., we cannot increase the
iterator by an arbitrary number: list{3, 2, 1}.end() + 2 does not
compile. Iterator is random access if the structure has the random
access operator operator[], and list doesn’t have it.
The real problem is the poor diagnostics. We should have received an
error message that function sort expects random access iterators.
C++20 introduced concepts that would allow for proper error messages,
but that functionality has yet to be implemented in the standard
library implementations (e.g., GCC).
For the C++ Standard Committee, the time and memory efficiency is the priority, and the ease of language use comes second. Therefore the program that uses the abstraction mechanisms (e.g., templates) must work as fast as possible (i.e., as fast as the hand-crafted code), albeit the code might be harder to write.
In the simple examples below we check whether the abstraction mechanisms introduce any performance overhead. Each of these programs writes to the standard output numbers 1 and 2. We are interested in the assembly code.
This is the baseline code, i.e., to this code we compare the others
(test_baseline.cc):
#include <iostream>
int
main()
{
std::cout << 1 << 2;
}This example uses templates (test_template.cc):
#include <iostream>
template <typename T>
void
foo(T a, T b)
{
std::cout << a << b;
}
int
main()
{
foo(1, 2);
}We compile both examples to the assembly code (we can use the Compiler
Explorer too) and we look for differences (c++filt can come useful
too):
g++ -O2 -std=c++17 -S test_baseline.cc test_template.cc
meld test_baseline.s test_template.s
There are no differences. Using a function template does not deteriorate performance: the second example is as fast as the baseline example.
In that example, as the assembly language shows, the parameters of a template function are not initialized (copied, specifically) based on the call arguments, even though they are passed by value. In the C language, a function that accepts arguments by value (neither by pointer, nor by reference as it doesn’t exist in C) always has its parameters initialized based on call arguments, and that brings performance down.
A regular (non-template) function can be inlined too:
#include <iostream>
void
foo(int a, int b)
{
std::cout << a << b;
}
int
main()
{
foo(1, 2);
}A tuple (std::tuple) also doesn’t introduce overhead. Type tuple
is a templated structure, so it has a constructor and a destructor but
they are empty. Here’s an example:
#include <iostream>
#include <tuple>
using namespace std;
int
main()
{
tuple t{1, 2};
cout << get<0>(t) << get<1>(t);
}Even iterating over the elements of std::array doesn’t introduce any
overhead:
#include <array>
#include <iostream>
int
main()
{
std::array a{1, 2};
for(auto e: a)
std::cout << e;
}Instantiation allows for better optimization:
#include <iostream>
template <unsigned I>
int
divide(int t)
{
return t / I;
}
int
divide(int t, int I)
{
return t / I;
}
int
main()
{
volatile int x = 2;
// Super-fast division by bit shifting.
std::cout << divide<2>(x) << std::endl;
// Regular division, depending on optimizer.
std::cout << divide(x, 2) << std::endl;
}C++ is multiparadigm: object-oriented, structural, procedural, functional and generic. Generic and object-oriented programming are complementary, not mutually exclusive.
We implement a complex type as a structure, and its specific operations as member functions – that’s a typical example of object-oriented programming. Operations (algorithms) are best implemented as non-member functions (aka free-standing, global or namespace functions), so that they can be overloaded for any type, not only class types – and that’s a typical example of generic programming.
We often need to implement different functionality for different types. Generic programming and object-oriented programming use polymorphism to this end, but of different kind:
In generic programming we use non-member functions and their abstraction mechanisms: templates and overloading. At compile-time, for the given call expression, the compiler chooses a function template or an overload depending on the type and category of call arguments. This way of choosing an implementation is called static polymorphism (aka compile-time polymorphism). Static polymorphism does not introduce overhead at run-time.
In object-oriented programming we use the interface of a base class and virtual functions. At run-time, when calling a virtual function for a given object, an implementation of a virtual function is chosen depending on the type of the object. This way of choosing an implementation is called dynamic polymorphism (aka run-time polymorphism). Dynamic polymorphism introduces performance overhead because calling a virtual function requires an indirect call using a virtual function table.
Bottom line, generic programming is super fast and works with any
type, while object-oriented programming is slower and works with class
types only, e.g., 1.foo() would not compile.
In the example below we use static polymorphism implemented with
function overloading. These overloads have some identical code
(std::cout << "Function foo:"; and std::cout << std::endl), and
some extra code depending on the parameter type (e.g., std::cout <<
i; for integers).
#include <iostream>
struct A
{
};
// B doesn't have to derive from a base class.
struct B
{
};
void foo(const int &i)
{
std::cout << "Function foo: ";
std::cout << i;
std::cout << std::endl;
}
void foo(const A &)
{
std::cout << "Function foo: ";
std::cout << "A";
std::cout << std::endl;
}
void foo(const B &)
{
std::cout << "Function foo: ";
std::cout << "B";
std::cout << std::endl;
}
int
main()
{
foo(1);
foo(A());
foo(B());
}Below we use a function template, where the identical code from the
example above appears once. The function template uses operator <<
that is overloaded for various types. We still rely on overloading,
as in the example above, but for the operator << only, which we
could use in other parts of code. We could say that function foo
now is generic.
#include <iostream>
struct A
{
};
std::ostream &
operator << (std::ostream &os, const A &)
{
os << "A";
return os;
}
// B doesn't have to derive from a base class.
struct B
{
};
std::ostream &
operator << (std::ostream &os, const B &)
{
os << "B";
return os;
}
template <typename T>
void foo(const T &t)
{
std::cout << "Function foo: ";
std::cout << t;
std::cout << std::endl;
}
int
main()
{
foo(1);
foo(A());
foo(B());
}The same functionality we could implement using dynamic programming. However, the assembly code is much more complicated, because of the call to a virtual function.
#include <iostream>
struct A
{
virtual void foo() const
{
std::cout << "A\n";
}
};
// Type B must derive from the base class.
struct B: A
{
void foo() const override
{
std::cout << "B\n";
}
};
void
foo(const A &a)
{
std::cout << "Function foo: ";
a.foo();
std::cout << std::endl;
}
int
main()
{
// foo(1);
foo(A());
foo(B());
}Generic programming:
shortens and better organizes the source code,
offers static polymorphism,
rules in the standard library.
Does the generic programming in C++ suffers from performance loss?
What’s the difference between the static and dynamic polymorphism?
What data types can we use in generic programming?