C++ Newsletter/Tutorial Issue 10
Issue #010
May, 1996
Contents
- Introduction to Templates Part 2 - Class Templates
- Introduction to Stream I/O Part 5 - Streambuf
- Using C++ as a Better C Part 10 - General Initializers
- Performance - Per-class New/Delete
INTRODUCTION TO TEMPLATES PART 2 - CLASS TEMPLATES
To continue our introduction of C++ templates, we'll be saying a few things about class templates in this issue. Templates are a part of the language still undergoing major changes, and it's tricky to figure out just what to say. But we'll cover some basics that are well accepted and in current usage.
A skeleton for a class template, and definitions of a member function and a static data item, looks like this:
template <class T> class A {
void f();
static T x;
};
template <class T> void A<T>::f()
{
// stuff
}
template <class T> T A<T>::x = 0;
T is a placeholder for a template type argument, and is bound to that argument when the template is instantiated. For example, if I say:
A<double> a;
then the type value of T is "double". The binding of template arguments and the generation of an actual class from a template is a process known as "instantiation". You can view a template as a skeleton or macro or framework. When specific types, such as double, are added to this skeleton, the result is an actual C++ class.
Template arguments may also be constant expressions:
template <int N> struct A {
// stuff
};
A<-37> a;
This feature is useful in the case where you want to pass a size into the template. For example, a Vector template might accept a type argument that tells what type of elements will be operated on, and a size argument giving the vector length:
template <class T, int N> class Vector {
// stuff
};
Vector<float, 100> v;
A template argument may have a default specified (this feature is not widely available as yet):
template <class T = int, int N = 100> class Vector {
// stuff
};
Vector<float, 50> v1; // Vector<float, 50>
Vector<char> v2; // Vector<char, 100>
Vector<> v3; // Vector<int, 100>
To see how some of these basic ideas fit together, let's actually build a simple Vector template, with set() and get() functions:
template <class T, int N = 100> class Vector {
T vec[N];
public:
void set(int pos, T val);
T get(int pos);
};
template <class T, int N> void Vector<T, N>::set(int pos, T val)
{
if (pos < 0 || pos >= N)
; // give error of some kind
vec[pos] = val;
}
template <class T, int N> T Vector<T, N>::get(int pos)
{
if (pos < 0 || pos >= N)
; // give error of some kind
return vec[pos];
}
// driver program
int main()
{
Vector<double, 10> v;
int i = 0;
double d = 0.0;
// set locations in vector
for (i = 0; i < 10; i++)
v.set(i, double(i * i));
// get location values from vector
for (i = 0; i < 10; i++)
d = v.get(i);
return 0;
}
Actual values are stored in a private vector of type T and length N. In a real Vector class we might overload operator[] to provide a natural sort of interface such as an actual vector has.
What would happen if we said something like:
Vector<char, -1000> v;
This is an example of code that is legal until the template is actually instantiated into a class. Because a member like:
char vec[-1000];
is not valid (you can't have arrays of negative or zero size), this usage will be flagged as an error when instantiation is done.
The process of instantiation itself is a bit tricky. If I have 10 translation units (source files), and each uses an instantiated class:
Vector<unsigned long, 250>
where does the code for the instantiated class's member functions go? The template definition itself resides most commonly in a header file, so that it can be accessed everywhere and because template code has some different properties than other source code.
This is an extremely hard problem for a compiler to solve. One solution is to make all template functions inline and duplicate the code for them per translation unit. This results in very fast but potentially bulky code.
Another approach, which works if you have control over the object file format and the linker, is to generate duplicate instantiations per object file and then use the linker to merge them.
Yet another approach is to create auxiliary files or directories ("repositories") that have a memory of what has been instantiated in which object file, and use that state file in conjunction with the compiler and linker to control the instantiation process.
There are also schemes for explicitly forcing instantiation to take place. We'll discuss these in a future issue. The instantiation issue is usually hidden from a programmer, but sometimes becomes visible, for example if the programmer notices that object file sizes seem bloated.
INTRODUCTION TO STREAM I/O PART 5 - STREAMBUF
In previous issues we talked about various ways of copying files using stream I/O, some of the ways of affecting I/O operations by specifying unit buffering or not and tying one stream to another, and so on.
Another way of copying input to output using stream I/O is to say:
#include <iostream.h>
int main()
{
int c;
while ((c = cin.rdbuf()->sbumpc()) != EOF)
cout.rdbuf()->sputc(c);
return 0;
}
This scheme uses what are known as streambufs, underlying buffers used in the stream I/O package. An expression:
cin.rdbuf()->sbumpc()
says "obtain the streambuf pointer for the standard input stream (cin) and grab the next character from it and then advance the internal pointer within the buffer". Similarly,
cout.rdbuf()->sputc(c)
adds a character to the output buffer.
Doing I/O in this way is lower-level than some other approaches, but correspondingly faster. If we summarize the four file-copying methods we've studied (see issues #008 and #009 for code examples of them), from slowest to fastest, they might be as follows.
Copy a character at a time with >> and <<:
cin.tie(0);
cin.unsetf(ios::skipws);
while (cin >> c)
cout << c;
Copy using get() and put():
ifstream ifs(argv[1], ios::in | ios::binary);
ofstream ofs(argv[2], ios::out | ios::binary);
while (ifs.get(c))
ofs.put(c);
Copy with streambufs (above):
while ((c = cin.rdbuf()->sbumpc()) != EOF)
cout.rdbuf()->sputc(c);
Copy with streambufs but explicit copying buried:
ifstream ifs(argv[1], ios::in | ios::binary);
ofstream ofs(argv[2], ios::out | ios::binary);
ofs << ifs.rdbuf();
A table of relative times, for one popular C++ compiler, comes out like so:
>>, << 100
get/put 72
streambuf 62
streambuf hidden 43
Actual times will vary for a given library. Perhaps the most critical factor is whether functions that are used in a given case are inlined or not. Note also that if you are copying binary files you need to be careful with the way copying is done.
Why the time differences? All of these methods use streambufs in some form. But the slowest method, using >> and <<, also does additional processing. For example, it calls internal functions like ipfx() and opfx() to handle unit buffering, elision of whitespace on input, and so on. get/put also call these functions.
The fastest two approaches do not worry about such processing, but simply allow one to manipulate the underlying buffer directly. They offer fewer services but are correspondingly faster.
USING C++ AS A BETTER C PART 10 - GENERAL INITIALIZERS
In C, usage like:
int f() {return 37;}
int i = 47;
int j;
for global variables is legal. Typically, in an object file and an executable program these types of declarations might be lumped into sections with names like "text", "data", and "bss", meaning "program code", "data with an initializer", and "data with no initializer".
When a program is loaded by the operating system for execution, a common scheme will have the text and data stored within the binary file on disk that represents the program, and the bss section simply stored as an entry in a symbol table and created and zeroed dynamically when the program is loaded.
There are variations on this scheme, such as shared libraries, that are not our concern here. Rather, we want to discuss the workings of an extension that C++ makes to this scheme, namely general initializers for globals. For example, I can say:
int f() {return 37;}
int i = 47;
int j = f() + i;
In some simple cases a clever compiler can compute the value that should go into j, but in general such values are not computable at compile time. Note also that sequences like:
class A {
public:
A();
~A();
};
A a;
are legal, with the global "a" object constructed before the program "really" starts, and destructed "after" the program terminates.
Since values cannot be computed at compile time, they must be computed at run time. How is this done? One way is to generate a dummy function per object file:
int f() {return 37;}
int i = 47;
int j; // = f() + i;
static void __startup()
{
j = f() + i;
}
and a similar function for shutdown as would be needed for calling destructors. Using a small tool that will modify binaries, and an auxiliary data structure generated by the compiler, it's possible to link all these __startup() function instances together in a linked list, that can be traversed when the program starts.
Typically this is done by immediately generating a call from within main() to a C++ library function _main() that iterates over all the __startup() functions. On program exit, similar magic takes place, typically tied to exit() function processing. This approach is used in some compilers but is not required; the standard mandates "what" rather than "how".
Some aspects of this processing have precedent in C. For example, when a program starts, standard I/O streams stdin, stdout, and stderr are established for doing I/O.
Within a given translation unit (source file), objects are initialized in the order of occurrence, and destructed in reverse order (last in first out). No ordering is imposed between files.
Some ambitious standards proposals have been made with regard to initialization ordering, but none have caught on. The draft standard says simply that all static objects in a translation unit (objects that persist for the life of the program) are zeroed, then constant initializers are applied (as in C), then dynamic general initializers are applied "before the first use of a function or object defined in that translation unit".
Calling the function abort() defined in the standard library will terminate the program without destructors for global static objects being called. Note that some libraries, for example stream I/O, rely on destruction of global class objects as a hook for flushing I/O buffers. You should not rely on any particular order of initialization of global objects, and using a startup() function called from main(), just as in C, still can make sense as a program structuring mechanism for initializing global objects.
PERFORMANCE - PER-CLASS NEW/DELETE
Some types of applications tend to use many small blocks of space for allocating nodes for particular types of data structures, small strings, and so on. In issue #002 we talked about a technique for efficiently allocating many small strings.
Another way of tackling this problem is to overload the new/delete operators on a per-class basis. That is, take over responsibility for allocating and deallocating the storage required by class objects. Here is an example of what this would look like for a class A:
#include <stddef.h>
#include <stdlib.h>
class A {
int data;
A* next;
#ifdef USE_ND
static A* freelist; // pointer to free list
#endif
public:
A();
~A();
#ifdef USE_ND
void* operator new(size_t); // overloaded new()
void operator delete(void*); // overloaded delete()
#endif
};
#ifdef USE_ND
A* A::freelist = 0;
inline void* A::operator new(size_t sz)
{
// get free node from freelist if any
if (freelist) {
A* p = freelist;
freelist = freelist->next;
return p;
}
// call malloc() otherwise
return malloc(sz);
}
inline void A::operator delete(void* vp)
{
A* p = (A*)vp;
// link freed node onto freelist
p->next = freelist;
freelist = p;
}
#endif
A::A() {}
A::~A() {}
#ifdef DRIVER
const int N = 1000;
A* aptr[N];
int main()
{
int i;
int j;
// repeatedly allocate / deallocate A objects
for (i = 1; i <= N; i++) {
for (j = 0; j < N; j++)
aptr[j] = new A();
for (j = 0; j < N; j++)
delete aptr[j];
}
return 0;
}
#endif
We've also included a driver program. For this example, that recycles the memory for object instances, the new approach is about 4-5X faster than the standard approach.
When new() is called for an A type, the overloaded function checks the free list to see if any old recycled instances are around, and if so one of them is used instead of calling malloc(). The free list is shared across all object instances (the freelist variable is static). delete() simply returns a no-longer-needed instance to the free list.
This technique is useful only for dynamically-created objects. For static or local objects, the storage has already been allocated (on the stack, for example).
We have again sidestepped the issue of whether a failure in new() should throw an exception instead of returning an error value. This is an area in transition in the language.
There are other issues with writing your own storage allocator. For example, you have to make sure that the memory for an object is aligned correctly. A double of 8-byte length may need to be aligned, say, on a 4-byte boundary for performance reasons or to avoid addressing exceptions ("bus error - core dumped" on a UNIX system). Other issues include fragmentation and support for program threads.
ACKNOWLEDGEMENTS
Thanks to Nathan Myers, Eric Nagler, David Nelson, Terry Rudd, Jonathan Schilling, and Clay Wilson for help with proofreading.
SUBSCRIPTION INFORMATION / BACK ISSUES
To subscribe to the newsletter, send mail to majordomo@world.std.com with this line as its message body:
subscribe c_plus_plus
Back issues are available via FTP from:
rmii.com /pub2/glenm/newslett
or on the Web at:
There is also a Java newsletter. To subscribe to it, say:
subscribe java_letter
using the same majordomo@world.std.com address.
-------------------------
Copyright (c) 1996 Glen McCluskey. All Rights Reserved.
This newsletter may be further distributed provided that it is copied in its entirety, including the newsletter number at the top and the copyright and contact information at the bottom.
Glen McCluskey & Associates
Professional C++ Consulting
Internet: glenm@glenmccl.com
Phone: (800) 722-1613 or (970) 490-2462
Fax: (970) 490-2463
FTP: rmii.com /pub2/glenm/newslett (for back issues)
Web: http://www.rmii.com/~glenm
