The Way of C/C++

Working with objects or pointers (Micro-benchmark)

2008-09-17T14:15:00.003+02:00

I needed to keep track of a list of objects, and the question is what is most efficient: keeping a list of the objects, or allocating the object on the heap and storing that in the vector. What speaks for pushing the pointer is that it is easy to copy (usually just as easy to copy as an integer), and should therefore be fast. What speaks against it (and for actually storing the object in the array) is that it requires allocating memory on the heap, and a subsequent delete.

To decide, I wrote a quick measure program and ran it, and the results can be seen in the diagram to the right.

Observe that this micro-benchmark measures the time to insert (and delete) N unique objects into a vector. It does not talk about searching the array. However, searching the array should not be that different in performance since it just involves an extra dereferencing. You should note that the width of the cache lines might affect the performance of the algorithms, so for objects that are narrower than the cache line have a bigger chance of landing fully in the cache line, which in turn will improve performance.

As you can see, there seems to be a break-even in the range 16-20 fields, so for any objects that have less than 16 fields (of int size), it seems to pay off to work with the actual objects instead of pointers to objects.

The program allocates objects consisting of arrays of int. I picked int since that is the natural size for the processor (usually the size of the register), so using a smaller granularity is bound to generate a lot of extra work for the processor to no practical use for us. The use of an array might affect performance since base objects are copied member-by-member, and copying an array have to do the equivalent of a memcpy, while using base types as members of the structure might allow the compiler to generate a single instruction for each field, effectively inlining the member-by-member copying.

To get an object of the correct size (counted in number of int), I constructed a template class:

template <int N> struct obj { int x[N]; };

After that it is easy to define the two classes to perform each operation as two classes. Each class has an execute() function to handle what is actually measured. You can see the full source code below.

Push pointer	Push object
template <int N> class PushPtr { public: typedef obj<N> ObjType; typedef std::vector<ObjType> Vector; PushPtr(int c) : count(c) { my_list.reserve(c); } void execute() { for (int c = 0 ; c < count ; ++c) { ObjType obj = new ObjType; my_list.push_back(obj); } typename Vector::iterator ii = my_list.begin(); for ( ; ii != my_list.end() ; ++ii) delete ii; my_list.clear(); } private: int const count; Vector my_list; };	template <int N> class PushCpy { public: typedef obj<N> ObjType; typedef vector<ObjType> Vector; PushCpy(int c) : count(c) { my_list.reserve(c); } void execute() { for (int c = 0 ; c < count ; ++c) { ObjType obj; my_list.push_back(obj); } } private: int const count; Vector my_list; };

Push pointer

Push object

template <int N> class PushPtr {
public:
  typedef obj<N> ObjType;
  typedef std::vector<ObjType> Vector;

  PushPtr(int c) : count(c) {
    my_list.reserve(c);
  }

  void execute() {
    for (int c = 0 ; c < count ; ++c) {
      ObjType *obj = new ObjType;
      my_list.push_back(obj);
    }

    typename Vector::iterator
      ii = my_list.begin();
    for ( ; ii != my_list.end() ; ++ii)
      delete *ii;
    my_list.clear();
  }

private:
  int const count;
  Vector my_list;
};

template <int N> class PushCpy {
public:
  typedef obj<N> ObjType;
  typedef vector<ObjType> Vector;

  PushCpy(int c) : count(c) {
    my_list.reserve(c);
  }

  void execute() {
    for (int c = 0 ; c < count ; ++c) {
      ObjType obj;
      my_list.push_back(obj);
    }
  }

private:
  int const count;
  Vector my_list;
};

Measurements

Number of seconds to push 100 objects 20000 times to an array
Size	PushPtr	PushCpy	Size	PushPtr	PushCpy
1	0.156009	0.020002	21	0.160010	0.176011
2	0.104006	0.004000	22	0.164010	0.160010
3	0.100007	0.040002	23	0.160010	0.200013
4	0.104007	0.028001	24	0.168010	0.228014
5	0.100007	0.016001	25	0.164011	0.216013
6	0.100006	0.044003	26	0.164010	0.220014
7	0.104006	0.040003	27	0.168011	0.196012
8	0.104006	0.064004	28	0.168010	0.168011
9	0.100006	0.056004	29	0.172011	0.204012
10	0.100006	0.060004	30	0.160010	0.180012
11	0.104006	0.076005	31	0.164010	0.264016
12	0.100006	0.076005	32	0.168011	0.216013
13	0.100006	0.088006	33	0.168011	0.216013
14	0.100006	0.080005	34	0.164011	0.264016
15	0.104007	0.092005	35	0.164010	0.252016
16	0.104007	0.140009	36	0.160010	0.228014
17	0.096006	0.132008	37	0.168011	0.252016
18	0.160010	0.128008	38	0.160010	0.292018
19	0.164010	0.116007	39	0.164010	0.284018
20	0.168011	0.176011	40	0.164010	0.300019

Source Code: `push_pointer_or_copy.cc`

#include <cstdlib>
#include <sys/time.h>
#include <sys/resource.h>
#include <vector>

// Here's an object to push, we're using ints since that is usually
// the natural type for storing in a register
template <int N> struct obj { int x[N]; };

template <int N> class PushPtr {
public:
  typedef obj<N> ObjType;
  typedef std::vector<ObjType*> Vector;

  PushPtr(int c) : count(c) { my_list.reserve(c); }

  void execute() {
    // This is the actual code to create a new object and push the
    // pointer into the container.
    for (int c = 0 ; c < count ; ++c) {
      ObjType *obj = new ObjType;
      my_list.push_back(obj);
    }

    // We need to delete all the allocated objects as part of the
    // measurement to get a comparable figure.
    typename Vector::iterator ii = my_list.begin();
    for ( ; ii != my_list.end() ; ++ii)
      delete *ii;
    my_list.clear();
  }

private:
  int const count;
  Vector my_list;
};


template <int N> class PushCpy {
public:
  typedef obj<N> ObjType;
  typedef std::vector<ObjType> Vector;

  PushCpy(int c) : count(c) { my_list.reserve(c); }

  void execute() {
    // This is the actual code to create an object and push a copy of
    // it into the container.
    for (int c = 0 ; c < count ; ++c) {
      ObjType obj;
      my_list.push_back(obj);
    }
  }

private:
  int const count;
  Vector my_list;
};


// Define an substraction operator to make it easy to compute the
// difference.
double operator-(rusage const& a, rusage const& b) {
  double result = (a.ru_utime.tv_usec - b.ru_utime.tv_usec) / 1.0e6;
  result += (a.ru_utime.tv_sec - b.ru_utime.tv_sec);
  return result;
}


// Function to measure 'count' executions of the function doing N
// pushes onto the end of the container.
template <int N, template <int> class Func>
double measure(const int count, const int laps) {
  Func<N> func(count);
  rusage before, after;

  getrusage(RUSAGE_SELF, &before);
  for (int lap = 0 ; lap < laps ; ++lap)
    func.execute();
  getrusage(RUSAGE_SELF, &after);
  return after - before;
}


// Template class that will measure and print the result objects in
// the range [M,M+N], i.e., objects of size M, M+1, ..., M+N.
template <int N, int M> struct Measurer;

template <int N>
struct Measurer<1,N>
{
  static void measure_and_print(const int count, const int laps) {
    double push_ptr = measure<N,PushPtr>(count, laps);
    double push_cpy = measure<N,PushCpy>(count, laps);
    printf("%10d %10d %10f %10f %10f\n",
           N, count, push_ptr, push_cpy, push_cpy / push_ptr );
  }
};

template <int N, int M>
struct Measurer
{
  typedef Measurer<1,M> First;
  typedef Measurer<N-1, M+1> Rest;

  static void measure_and_print(const int count, const int laps) {
    First::measure_and_print(count,laps);
    Rest::measure_and_print(count,laps);
  }
};


int main() {
  int const count = 100;
  int const laps = 20000;

  printf("%10s %10s %10s %10s %10s\n",
         "Size", "Count", "PushPtr", "PushCpy", "PC/PP");

  Measurer<40,1>::measure_and_print(count,laps);
}

Merging this blog with mysqlmusings.blogspot.com

2008-08-14T18:31:00.004+02:00

Since it appears that the C++ things I do interleave with what I do at MySQL, it seems to be no point in keeping separate blogs. So, in the future you will see my C and C++ blogging in mysqlmusings.blogspot.com and not here. Update: I've discovered that there are a few issues I might talk about that might end up here as well.

Portability of array indexing types

2008-06-23T10:07:00.003+02:00

A while ago, Serg approached me regarding a bug and a patch that was supposed to solve the problem (I just didn't write the post until now).

To explain the situation, I construct a similar setup, but simplify the issue significantly to demonstrate what the problem is, why the patch really solves the problem, and what the real solution is.

Suppose that we have a structure defined in the following manner and a function that is used to find a substring in a larger string. (Now, don't start complaining that I should use strstr(3) instead. It is true, but this is just an example and the real fulltext search does a lot more than this.)

typedef struct match {
  unsigned int beg;
  unsigned int end;
} match;

match find_substr(char const *str, char const *substr);

The match structure hold the positions of the beginning and the end of the substring found, and since the position is guaranteed to be positive, it is declared as unsigned.

Inside the fulltext search code, we have something that looks like this, which is used to decide if this is the beginning of a word or just something that is inside a word:

if (... && !isalnum(p0[m[1].beg - 1])) {
  /*
    Do something if the character before the first one that matched is
    not a word character.
  */
}

Now, when running on a 64-bit machine... and under certain circumstances... MySQL BUG#11392 was triggered. After some investigations, the following patch was committed which proved to solve the problem (I've highlighted the changed part of the line):

- if (... && !isalnum(p0[m[1].beg - 1])) {
+ if (... && !isalnum(*(p0 + m[1].beg - 1))) {

Everybody who's a little familiar with C knows that ptr[expr] is just another way to write *(ptr + expr), so this could should not really change anything at all and could therefore not fix the bug. Right?

Wrong.

The expression ptr[expr] is equivalent to the expression *(ptr + (expr)), and please note the additional parentheses around the expression. This seems to be quite obvious, but please bear with me for a little while more.

The special quirk on the compiler of this 64-bit machine is that pointers are of size 8 (bytes), while sizeof(unsigned int) is 4. (I can't know for sure why the compiler is implemented this way, but my guess is that it is so that each of the sizes 1, 2, 4, and 8 (bytes) can be represented with a basic type in C89. Remember that long long does not exist in C89.)

While doing the searching, the start position of the match ended up at (unsigned) zero. For machines where the size of a pointer is the same as the size of an unsigned int (and where negative integers are represented using two-complement numbers, but as far as I know that is ubiquitous), p0[0U-1] == *(p0 + (0U - 1)) == *(p0 + UINT_MAX) == p0[-1], so all is well (in this case, *(p0 - 1) was a valid memory location).

However, for this 64 bit machine where the pointers are 64 bits instead of 32 while the unsigned int is 32 bits, the addition before the patch ends up very far away into the array (in this case far out of the allocated memory), so there were a segmentation fault. However, for the patched code we have *(p0 + 0U - 1) == *((p0 + 0U) - 1) == *(p0 - 1), so it works even on this machine with this compiler.

So, the basic problem is that an unsigned integral type is used to index the array, and that integral type is smaller than the size of the pointer. In that case, it is important in what order the computations are made. Since the natural approach is to use array index notation, we need to find a type for beg that is good for this use on any machine, so what to pick? We need a signed integral type, since we need to ensure that -1 really becomes -1 and does not cause a wraparound as unsigned arithmetics do. We also need it to be large enough to move backwards and forwards from any position in an object to any other position in an object.

The immediate candidate for this is ptrdiff_t, which is supposed to be able to represent the difference between two pointers. So what does the standard say regarding this? Well... not much actually. From 7.1.7 (the TC3 draft is available as ISO/IEC 9899:TC3 on www.open-std.org), we have:

ptrdiff_t [...] is the signed integer type of the result of subtracting two pointers

So that seems to be all well and good, however, from 6.5.6 §9, we have (emphasis is mine):

When two pointers are subtracted [...] the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h>; header. If the result is not representable in an object of that type, the behavior is undefined. In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i-j provided the value fits in an object of type ptrdiff_t.

So, in essence, the type ptrdiff_t is a signed integral type that might be able to represent the difference between two pointer, so we cannot rely on ptrdiff_t. This leaves size_t, which is an unsigned integral type large enough to hold the size of any object. Now, it seems strange that I advocate using an unsigned type when I pointed out a problem with it above, but the problem is that the wraparound caused by using an unsigned integer that is smaller than the pointer size caused the problem. So, if sizeof(X*) == sizeof(size_t), all will work as expected.

Now, as usual when it comes to standard issues, there are some caveats. For machines with segmented memory (like 80486, but there are others), the compilers have different of memory types and hence different kinds of pointers. For example __far,__near, and __huge. So, to illustrate the problem, we assume we have a 16-bit machine with 8-bit segment number and the pointers are __far pointers, i.e., each pointer is the address within the segment plus a segment address. This means that sizeof(void*) == 3. For this memory model, it is usually the case that any object defined has to fit within a single segment and may not border two segments. This means that sizeof(size_t) == 2. Since sizeof(size_t) is less than sizeof(void*), we have the same problem again.

So, what is the moral of the story? Well... if you need to have a type to represent an index into an array, use size_t and make sure that sizeof(size_t) == sizeof(void*).

If sizeof(size_t) < sizeof(void*), you have three (not necessarily exclusive) options:

Scream and curse
Pick a signed integral type strictly larger than size_t. It will be horribly inefficient, but it will work
Make sure that any expression used for array indexing never become negative by expanding the array indexing manually as was done in the patch above.

What is really a POD class?

2008-05-29T22:33:00.002+02:00

For a project at hand, I'm using the offsetof() macro with a C++ class, and in an attempt to avoid a warning, I stumbled over the following, to my eyes, strange behavior.

Let's start with the following code:

class MyClass {
public:
  MyClass() { ... }

  size_t get_offset() { return offsetof(MyClass, y); }  // Gives warning
private:
  int x,y,z;
};

When compiling, I get the warning

offsetof.cc: In member function ‘int MyClass::get_offset() const’:
offsetof.cc:14: warning: invalid access to non-static data member ‘MyClass::y’ of NULL object
offsetof.cc:14: warning: (perhaps the ‘offsetof’ macro was used incorrectly)

The source of the problem is that offsetof() macro can only be used with POD structures, i.e., from Chapter 9 paragraph 4 in ISO/IEC 14882: 2003:

A POD-struct is an aggregate class that has no non-static data members of type non-POD-struct, non-POD-union (or array of such types) or reference, and has no user-defined copy assignment operator and no user-defined destructor.

Cool, so let's move all the members to a base class and inherit from it instead. That will make the base class a POD, so we can get the offset of the member from there and just add the other stuff in the subclass.

struct Base {
  int x,y,z;
};

class MyClass : public MyBase {
public:
  MyClass() { ... }

  size_t get_offset() { return offsetof(MyBase, y); }
};

... and as a result, I got no warnings! Very nice.

Aw, shoot, I cannot have x, y, and z public, I'd better make them protected so that MyClass can work with them, but they are not available to anybody else (encapsuling the state like a good programmer):

struct Base {
protected:
  int x,y,z;
};

class MyClass : public MyBase {
public:
  MyClass() { ... }

  size_t get_offset() { return offsetof(MyBase, y); }
};

... and then let's just compile it and off we go:

$ g++ -ggdb -Wall -ansi -pedantic    offsetof.cc   -o offsetof
offsetof.cc: In member function ‘int MyClass::get_offset() const’:
offsetof.cc:8: error: ‘int MyBase::y’ is protected
offsetof.cc:16: error: within this context
offsetof.cc:16: warning: invalid access to non-static data member ‘MyBase::y’ of NULL object
offsetof.cc:16: warning: (perhaps the ‘offsetof’ macro was used incorrectly)

Hey! What is going on now! Just making the member variables protected does not make the struct non-POD... or? Well, it turns out that it actually does, let us read that paragraph again (with the boldface emphasis added by me):

A POD-struct is an aggregate class that has no non-static data members of type non-POD-struct, non-POD-union (or array of such types) or reference, and has no user-defined copy assignment operator and no user-defined destructor.

So, what is an aggregate class then? Moving on to 8.5.1/1, we have:

An aggregate is an array or a class with no use-declared constructors, no private or protected non-static data members, no base classes, and no virtual functions.

So, making the members protected actually made the base class non-POD. Shoot... now what? Well, that restriction only applies to the MyBase class, not to the way we inherit from that class, so by just using protected inheritance, I will make the member variables protected within MyClass while MyBase is a POD, like this:

struct MyBase {
  int x,y,z;
};

class MyClass : protected MyBase {
public:
  MyClass() { x = 1; y = 2; z = 3; }

  int get_offset() const {
    return offsetof(MyBase, y);
  }

};

This also means that I finally found a good reason for protected inheritance, which is one of the language gadgets I really never have not seen any use for until now.

Counting bits: efficiency by eliminating memory lookups

2008-04-22T21:19:00.002+02:00

I just came back from MySQL Conference & Expo and since that means spending at least 14 hours on plane, I usually bring something to read. This time I brought Hacker's Delight by Henry S. Warren, Jr.: a book with (among other things) C versions of good old programming tricks from the HAKMEM of 1972. I just love these gems of low-level programming tricks and since I have a background as a compiler implementer, I have used many of the HAKMEM tricks to generate code for various C constructions.

Table 1. Table lookup-based functions for population count

8-bit lookup table

int tpop8(ulong v) {
  static unsigned char bits[256] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    ...
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  };
  int result = bits[v & 0xFF];
  int i;
  for (i = 0 ; i < 3 ; i++) {
    v >>= 8;
    result += bits[v & 0xFF];
  }
  return result;
}

4-bit lookup table

int tpop4(ulong v) {
  static unsigned char bits[16] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  };
  int result = bits[v & 0xF];
  for (int i = 0 ; i < 7 ; i++) {
    v >>= 4;
    result += bits[v & 0xF];
  }
  return result;
}

Table 2. Shift-add based functions for population count

Divide-and-conquer

int pop1(ulong v) {
  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  v = (v + (v >> 4)) & 0x0F0F0F0F;
  v = v + (v >> 8);
  v = v + (v >> 16);
  return v & 0x3F;
}

Parallel sub-field sum

int pop2(ulong v) {
  ulong n;
  n = (v >> 1) & 0x77777777;
  v = v - n;
  n = (n >> 1) & 0x77777777;
  v = v - n;
  n = (n >> 1) & 0x77777777;
  v = v - n;
  v = (v + (v >> 4)) & 0x0F0F0F0F;
  v = v * 0x01010101;
  return v >> 24;
}

These programming techniques often rely heavily on using registers to perform the calculations. The reason was mainly to reduce the number of instructions necessary to perform the computation and many of these techniques have gone out of fashion since code size what not that important and processor speed reduced the need for low-level optimizations. However, with the introduction of multi-level caches and multi-core machines, these techniques are again gaining importance since memory access is very expensive on these architectures. Traditional techniques for speeding up computations is to use lookup tables, but when you have caches, pipelines, and multiple cores, it might actually be more efficient to repeat the computation to avoid taking a memory hit. In this post, we will study the effects of table lookup-based techniques and compare them with techniques that perform the computations of values without utilizing any memory except the registers by studying a common primitive for many algorithms: counting the number of set bits in a word (a.k.a., population count).

A function for population count can trivially be implemented as a table lookup function, which is the common case, or by using shifts and adds to operate on subfields of the bitfield. In this post, we will implement two table lookup-based functions and two shift-add based functions to see how they compare in various setups.

The first two functions are table lookup-based and I use one version with an 8-bit table and one version with a 4-bit table. The reason is that it is conceivable that the 4-bit version might be more efficient because it relies on less memory, hence potentially can be in cache all the time. The two functions of shift-add type perform the work by computing the number of bits in sub-fields of the integer, and then summing them together to form bigger fields within the integer. I picked these two since both are based on masking and shifting the full integer, in contrast with several of the other algorithms that are dependent on the existance of specific instructions to operate efficiently.

The second version counts the number of bits in each 4-bit field in parallel and then computes the sum of all the fields. It can potentially be more efficient on machines that are two-address, since in that case, the first lines of the function can be executed with only one instruction. I won't go into detail how these functions work, since my main interest in measuring the effectivness of them on modern architectures.

For the first measurements, we executed each of the functions a number of times, measured the runtime, and compared them. We used the parallel subfield-sum function as reference, and measured all the other functions relative to that (why will become evident in a minute). Basically, we used the following function as measurement function:

double measure(int count, int (*popf)(ulong)) {
  unsigned int pop_sum = 0;
  struct rusage before, after;

  getrusage(RUSAGE_SELF, &before);
  for (int i = 0 ; i < count ; i++) {
    pop_sum += popf(i);
  }
  getrusage(RUSAGE_SELF, &after);
  sink(pop_sum);

  return difftime(after, before);
}

The sink() function and pop_sum is only there to avoid the optimizer from optimizing away the loop and is not part of the measurement. All functions are compiled with maximum optimization (-O4 flag to gcc), and the results of the measurements are seen in Table 3, and surprisingly enough show that the 8-bit table lookup-based version is faster than the divide-and-conquer version.

**Measuring runtime for a single call per loop iteration**
Count	`pop1`	`pop2`	`tpop4`	`tpop8`
2000000	0.044 (122%)	0.036 (100%)	0.016 ( 44%)	0.008 ( 22%)
4000000	0.028 (140%)	0.020 (100%)	0.036 (180%)	0.012 ( 60%)
8000000	0.056 (140%)	0.040 (100%)	0.072 (180%)	0.028 ( 69%)
16000000	0.104 (123%)	0.084 (100%)	0.140 (166%)	0.064 ( 76%)
32000000	0.212 (123%)	0.172 (100%)	0.284 (165%)	0.120 ( 69%)
64000000	0.432 (124%)	0.348 (100%)	0.556 (159%)	0.252 ( 72%)
128000000	0.852 (123%)	0.688 (100%)	1.112 (161%)	0.500 ( 72%)
256000000	1.692 (124%)	1.364 (100%)	2.244 (164%)	1.000 ( 73%)
512000000	3.352 (121%)	2.768 (100%)	4.136 (149%)	1.964 ( 70%)
1024000000	6.796 (125%)	5.432 (100%)	8.897 (163%)	3.980 ( 73%)
2048000000	13.317 (123%)	10.809 (100%)	17.433 (161%)	7.812 ( 72%)

The reason for this is that since the functions are quite small and put inside a loop, each iteration will cause a pipeline stall. In other words, it could be the case that the apparent advantage of the table-based lookup function is an artifact of the measuring technique resulting from the fact that we only have a single call inside the loop. In order to check if that is really the case, we unroll the loop inside to reduce the number of pipeline stalls, and get a more appropriate results. When doing such an unroll 8 times within a loop, we get the measurements of Table 4.

**Measuring runtime when unrolling several calls inside the loop**
Count	`pop1`	`pop2`	`tpop4`	`tpop8`
2000000	0.008 ( 99%)	0.008 (100%)	0.016 (199%)	0.008 ( 99%)
4000000	0.016 (133%)	0.012 (100%)	0.024 (199%)	0.004 ( 33%)
8000000	0.012 (149%)	0.008 (100%)	0.016 (199%)	0.008 ( 99%)
16000000	0.020 (125%)	0.016 (100%)	0.032 (200%)	0.020 (124%)
32000000	0.040 (142%)	0.028 (100%)	0.068 (242%)	0.036 (128%)
64000000	0.080 (133%)	0.060 (100%)	0.136 (226%)	0.072 (120%)
128000000	0.152 (126%)	0.120 (100%)	0.276 (230%)	0.144 (120%)
256000000	0.308 (130%)	0.236 (100%)	0.544 (230%)	0.296 (125%)
512000000	0.600 (127%)	0.472 (100%)	1.096 (232%)	0.592 (125%)
1024000000	1.212 (129%)	0.936 (100%)	2.176 (232%)	1.168 (124%)
2048000000	2.404 (128%)	1.872 (100%)	4.476 (239%)	2.376 (126%)

Concluding remarks

We compared two table lookup-based techniques for and two register-based techniques for computing a population count of a bit field and concluded that the register-based techniques are as fast as or faster than the fastest of the table lookup-based techniques. The register-based techniques are very efficient because they operate on registers only and does not contain any branches, hence they were are able to utilize the pipeline efficiently. The experiments did not measure the impact on cache usage, but since the register-based techniques are at least as efficient as table lookup-based techniques, they should be used even in multi-core environments to avoid dependencies on the cache.

Alternative ways to implement downcasts

2007-09-11T13:27:00.001+02:00

To perform a downcast is to cast a pointer to a class into a pointer to a subclass. The three standard ways of doing it are:

In the remaining section, we will use source class to denote the class being cast from and target class to denote the class that we are casting to.

Using `dynamic_cast`

Of the three methods, using a dynamic_cast is the simplest one. Unfortunately, on the systems measured, it is also the slowest way of performing a downcast. To use dynamic cast, the compiler has to generate code for RTTI and the class has to contain at least one virtual function. If you are going to inherit from a class, you should make the destructor virtual, so that is automatically solved. The code to perform the downcast is:

if (Derived* d = dynamic_cast<Derived*>(b)) {
  ...
}

Advantages:

The class does not have to be designed in any special way.

Disadvantages:

Requires RTTI to be compiled in

Using virtual function

To use a virtual function to perform the downcast, we require each the base class to define a virtual function for the target class of the downcast, and then the target class overrides this function and returns itself. The following code illustrates how to do this:

class Derived;         // Forward declaration

class Base {
public:
  virtual Derived* IsDerived() { return 0; }
};

class Derived : public Base {
public:
  virtual Derived* IsDerived() { return this; }
};

To perform a downcast using this method, we can then use the following code:

Base* b = ...;
  .
  .
  .
if (Derived* d = b->IsDerived()) {
  ...
}

Advantages:

Does not require RTTI
Easy to get right

Disadvantages:

Requires defining virtual functions for every subclass that can be the target of a downcast.

Using type tags and `static_cast`

The fastest of the methods for performing a downcast is by handling the type tags yourself by using an enum and a static_cast. It is also the method that is the least flexible and which requires the most from the programmer. The following code illustrates how to implement this method:

class Base {
public:
  enum Type { BASE, DERIVED };
  Type type() const { return mType; }

  Base() : mType(BASE) { }

  enum { TAG = BASE };       // For the down_cast function below

protected:
  // Protected since it's only intended for subclasses
  Base(Type t) : mType(t) { }

private:
  Type mType;
};

class Derived : public Base {
public:
  Derived() : Base(Base::DERIVED) { }

  enum { TAG = DERIVED };    // For the down_cast function below
};

The method can then be used in the following manner:

Base* b = ...;
  .
  .
  .
Derived* d = b->type() == DERIVED ? static_cast<Derived*>(b) : 0;

To simplify the usage, we can introduce the following template function to do the job:

template <class Target, class Source>
Target* down_cast(Source* s) {
  return s->type() == Target::TAG ? static_cast<Target*>(s) : 0;
}

Then we can use it in almost the same way that you use the other casts:

if (Derived* d = down_cast<Derived>(b)) {
 ...
}

It is possible to make it look exactly like the other casts, but that requires some more work with templates. See the afternote below for the source code for that.

Advantages:

Does not require RTTI

Disadvantages:

Requires extending an enum with a new type tag for each class that can be the target of a downcast.
Hard to maintain for large number of subclasses

Measurements

All measurements done are on an Intel(R) Pentium(R) M processor 1.60GHz using GCC with -O3 optimization level (mainly to get function inlining).

Downcasting (execution time)
	Down-cast method			Factor
Length	dynamic_cast	virtual call	static_cast	DC/VC	VC/SC	DC/SC
2000	0.16	0.02	0.01	6.62	2.67	17.67
4000	0.32	0.05	0.02	6.53	2.72	17.78
6000	0.48	0.07	0.03	6.50	2.64	17.18
8000	0.63	0.10	0.04	6.48	2.58	16.71
10000	0.80	0.12	0.05	6.39	2.72	17.37
12000	0.97	0.15	0.06	6.58	2.58	16.96
14000	1.11	0.17	0.07	6.56	2.58	16.89
16000	1.28	0.20	0.08	6.48	2.61	16.88
18000	1.43	0.22	0.08	6.50	2.59	16.84
20000	1.61	0.25	0.10	6.51	2.57	16.74

Summary

Of the three methods to perform a down cast, using a type tag and a static cast is by far the most efficient way: about 17 times faster than using dynamic_cast and almost 3 times as efficient as using a virtual function. There is an added advantage that only non-virtual functions are used to perform the cast, which potentially affects the surrounding code since it allows the compiler to take advantage of the fact that the function is inlined and the internals available to the optimizer.

Afternote: implementation of `down_cast`

In order to make the down_cast above appear as a normal cast, we have to use different code depending on whether we are casting to a pointer or to a reference. Casting to a value is not meaningful for this use, so we elect to only implement casting a pointer and a reference downwards in a class hierarchy. To handle that, we introduce a helper class down_caster, and then use a template function to let the compiler figure out the proper type to use for the values.

template <class, class> struct down_caster;

template <class To, class From>
struct down_caster<To*, From*> {
  static To* cast(From* from) {
    return from->type() == To::TAG ? static_cast<To*>(from) : 0;
  }
};

template <class To, class From>
struct down_caster<To&, From>
{
  static To& cast(From& from) {
    if (from.type() == To::TAG)
      return static_cast<To&>(from);
    else
      throw std::bad_cast();
  }
};

template <class To, class From>
struct down_caster<const To*, From*> {
  static const To* cast(From* from) {
    return from->type() == To::TAG ? static_cast<const To*>(from) : 0;
  }
};

template <class To, class From>
struct down_caster<const To&, From>
{
  static const To& cast(From& from) {
    if (from.type() == To::TAG)
      return static_cast<const To&>(from);
    else
      throw std::bad_cast();
  }
};

Especially note the From when casting to a reference type. The reason for this can best be explained through an example. Consider this code:

Derived& foo(Base *pbase) {
  return down_cast<Derived&>(*pbase);
}

The code is legal and will resolve the second template parameter of down_cast to be Base. If we used the template parameter From&, it would not match Base and generate a compile error, even though the code above is reasonable and shall compile (compare it with how dynamic_cast would behave).

The Alleged Virtual Function Overhead

2006-05-03T08:59:00.000+02:00

There is a common fallacy to proclaim that there is a "virtual function call overhead" associated with calling a virtual function in C++. The fallacy is that you are comparing apples and oranges, that is: it is said that there is an overhead in calling a virtual function when compared with an ordinary function call. This is true, but that is because they serve different purposes: a virtual function can dispatch the call based on the actual type of the object, while for an ordinary (member) function call the given function that is called is based on the static type.

Instead, virtual function calls should be compared with similar constructions solving the same problem: namely calling a function containing a switch on the actual type of the object. Since the problem is actually related to executing different code depending on the dynamic "type" of an object, we hereafter call this dynamic dispatch regardless of whether it is in C or C++.

Setting the Scene

To illustrate the traditional solutions in C and C++, we assume that we wish to implement a simple virtual machine and demonstrate how it is done in a typical C manner and in a typical C++ manner. In both cases we use C++ syntax to write the code, so there are some minor differences compared to how it would look in standard C.

For simplicity, we assume that all instruction have one constant and manipulate the accumulator. The instruction we will implement are, in Z80-like notation:

Virtual machine instructions
Instruction	Description
`LD A, c`	Load accumulator with constant value c
`ADD A, c`	Add constant c to value in accumulator
`SUB A, c`	Substract value c from value in accumulator

We define a structure to represent a state as:

struct state {
    int acc;
};

Call + Switch

For the "C solution", we introduce a structure to represent an instruction and an enumeration with constants for the instructions:

enum enum_kind { LOAD_INSTR, ADD_INSTR, SUB_INSTR };

struct instr {
    enum_kind kind;
    int val;
};

The C code to implement dynamic dispatch then look like this:

void execute(instr* i, state* s) {
    switch (i->kind) {
        case LOAD_INSTR:
            s->acc = i->val;
            break;
        case ADD_INSTR:
            s->acc += i->val;
            break;
        case SUB_INSTR:
            s->acc -= i->val;
            break;
    }
}

We call this approach the call+switch method.

Advantages:

Less code to write (than the C++ solution)
Can be inlined if the execute() function is small.

Disadvantages:

Not in accordance with the Open-Closed Principle: the code cannot be extended with new instructions without changing existing code.
Slower than using virtual function calls [sic], unless the function is inlined

The function pointer structure

An alternative, and quite common, way to imlement virtual dispatch is to use a structure with function pointers, where the function pointer is set to the apropriate function. To handle this, we create the following structure:

struct instr {
    void (*execute)(instr*, state*);
    int val;
};

void load(instr* i, state* s) { s->acc = i->val; }
void add(instr* i, state* s) { s->acc += i->val; }
void sub(instr* i, state* s) { s->acc -= i->val; }

To perform the virtual dispatch, the following code is then used:

program[pc]->execute(program[pc], &state);

We call this the function pointer method.

Advantages:

In accordance with the Open-Closed Principle: the code is open for extension with new instruction but closed to changes since it doesn't require changing existing code.

Disadvantages:

More code to write
Larger structures: one function pointer is required for each method
Cannot be inlined

Virtual functions

The corresponding construction in C++ using virtual functions look something like this:

class Instruction {
protected:
    int m_val;
public:
    Instruction(int v = 0) : m_val(v) { }
    virtual void execute(state&) const = 0;
};

class Add : public Instruction {
public:
    Add(int v) : Instruction(v) { ; }
    virtual void execute(state& s) const { s.acc += m_val; }
};

class Sub : public Instruction {
public:
    Sub(int v) : Instruction(v) { ; }
    virtual void execute(state& s) const { s.acc -= m_val; }
};

class Load : public Instruction {
public:
    Load(int v) : Instruction(v) { ; }
    virtual void execute(state& s) const { s.acc = m_val; }
};

We call this approach the virtual call method.

Advantages:

In accordance with the Open-Closed Principle: the code can be extended with new instruction without changing existing code.

Disadvantage:

More code to write
Cannot be inlined

Measurements

All measurements done are on an Intel(R) Pentium(R) M processor 1.60GHz and using gcc 3.0 with -O3.

To measure the execution time of the two pieces of code, we create a random program of length length and execute it 20000 times. To avoid any randomization problems, we use the same sequence of instructions for both the call+switch, function pointer, and virtual call versions when we measure. In addition, the call+switch function is placed in a separate translation unit to prevent automatic inlining: this would be the normal case, since the function would be to large to inline.

Virtual dispatch (execution time)
length	call+switch (CS)	funcptr (FP)	virtual (VF)	CS/FP	FP/VF
2000	1.08	0.82	1.49	1.31	0.55
4000	2.09	1.64	1.64	1.27	1.00
6000	3.12	2.50	2.46	1.25	1.01
8000	4.16	3.30	3.28	1.26	1.01
10000	5.22	4.13	4.09	1.26	1.01
12000	6.26	4.97	4.97	1.26	1.00
14000	7.31	5.84	5.79	1.25	1.01
16000	8.45	6.84	6.75	1.23	1.01
18000	9.52	7.59	7.55	1.26	1.00
20000	10.53	8.49	8.47	1.24	1.00

Summary

As can be seen in the table, the virtual call and function pointer methods takes approximately 80% of the call+switch method. Worth noting, however, is that if the call+switch function is inlined, the execution time is several factors faster than the other methods (in this specific example). So for small switches inside functions that are inlined, the call+switch method might significantly improve performance.

The Way of C/C++

Working with objects or pointers (Micro-benchmark)

Measurements

Source Code: push_pointer_or_copy.cc

Merging this blog with mysqlmusings.blogspot.com

Portability of array indexing types

What is really a POD class?

Counting bits: efficiency by eliminating memory lookups

Concluding remarks

Alternative ways to implement downcasts

Using dynamic_cast

Using virtual function

Using type tags and static_cast

Measurements

Summary

Afternote: implementation of down_cast

The Alleged Virtual Function Overhead

Setting the Scene

Call + Switch

The function pointer structure

Virtual functions

Measurements

Summary

Source Code: `push_pointer_or_copy.cc`

Using `dynamic_cast`

Using type tags and `static_cast`

Afternote: implementation of `down_cast`