Virtual Overhead

When designing a library, declaring virtual methods in a base class comes from time to time. But do we exactly know what is the overhead associated with that decision.

There are various overheads:

• Size : The instances of such classes take more space
  
• Time : Calling virtual methods takes time
  

I am going to measure both. First I am going to take a look at the size overhead.

Consider the code below:

using namespace std;

class VirtualObject
{
public:
virtual int foo (int i, int j) = 0;
virtual ~VirtualObject()
{

}
};

class DerivedVirtual : public VirtualObject
{
private:
int x;
public:
int foo (int i, int j) {
++j;
return j;
}
};

class ConcreteObject
{
public:
int foo (int i, int j)
{
return j;
}
};

class DerivedConcrete : public ConcreteObject
{
private:
int x;
public:
int foo (int i, int j) {
++j;
return j;
}
};

void test_virtual_object_size ()
{
cout << "sizeof(VirtualObject): " ;
cout << sizeof(VirtualObject) << endl;
cout << "sizeof(DerivedVirtual): " ;
cout << sizeof(DerivedVirtual) << endl;
cout << "sizeof(ConcreteObject): " ;
cout << sizeof(ConcreteObject) << endl;
cout << "sizeof(DerivedConcrete): " ;
cout << sizeof(DerivedConcrete) << endl;
}

#define TEST_INNER_LOOP 1000000
#define TEST_OUTER_LOOP 100

void test_virtual_call_overhead ()
{
Core::Timer timer;
long long x;

x = 0;
DerivedVirtual dv;
VirtualObject & vo = dv;
timer.start();
for ( int i=0; i < TEST_OUTER_LOOP; ++i )
{
for ( int j=0; j < TEST_INNER_LOOP; ++j )
{
x += vo.foo(i,j);
}
}
cout << "DerivedVirtual::foo() " << x << " " << timer.elapsedTimeInSeconds() << endl;


x = 0;
DerivedConcrete dc;
timer.start();
for ( int i=0; i < TEST_OUTER_LOOP; ++i )
{
for ( int j=0; j < TEST_INNER_LOOP; ++j )
{
x += dc.foo(j,i);
}
}
cout << "DerivedConcrete::foo() " << x << " " << timer.elapsedTimeInSeconds() << endl;
}


 

In my system I get the following output for test_virtual_object_size

sizeof(VirtualObject): 4
sizeof(DerivedVirtual): 8
sizeof(ConcreteObject): 1
sizeof(DerivedConcrete): 4

This essentially means 4 byte for each object. It can be a significant overhead especially for small size objects.

For virtual call overhead this is what I get on release mode:
DerivedVirtual::foo() 50000050000000 0.423278
DerivedConcrete::foo() 5050000000 1e-06

But on debug mode this is what I get:
DerivedVirtual::foo() 50000050000000 0.832059
DerivedConcrete::foo() 5050000000 0.710893

The difference is mostly because of inlining. The compiler can not inline virtual functions, thus the overhead becomes significant in release mode.

One last note is that you incur the virtual call overhead only if you call the virtual function through a pointer or reference. This is important. If we used dv, instead of vo within the loop we would have identical results as the non-virtual function call. However, notice that dv is a DerivedVirtual object, not a pointer. If you write a function like the following, you will again incur the virtual call overhead.

void test1 ( DerivedVirtual & pdv )
{
Core::Timer timer;
long long x;

x = 0;
timer.start();
for ( int i=0; i < TEST_OUTER_LOOP; ++i )
{
for ( int j=0; j < TEST_INNER_LOOP; ++j )
{
x += pdv.foo(i,j);
}
}
cout << "DerivedVirtual::foo() " << x << " " << timer.elapsedTimeInMilliSeconds() << endl;


} 

In this case, we would incur the virtual function overhead. Instead of using a reference to DerivedVirtual, if we had used a DerivedVirtual object we would not have the virtual call overhead.

If C++ had a facility to declare a class as final or sealed, the compiler could have used that information to optimize these virtual calls, since pdv.foo had to be the DerivedVirtual's foo and nothing else. Even though there is no other class deriving from DerivedVirtual, we still see the virtual call overhead.

Set of coding guidelines

Over the years coding teaches you to set certain guidelines about various aspects of coding. Some of this is about style, some of them is about naming etc...

In this post I will try to list my own guidelines, and I will update them as I add new guidelines or change my idea.

Use PascalCase for class names. e.g. String, Environment, etc...

For data fields of classes use camelCase, e.g. counter, length, numOfItems

For private and protected data fields also use an underscore "_" at the end of the name , e.g. counter_, length_ , numOfItems_

In general, to get a value of a data field, use get_FieldName. e.g. get_Length(), get_NumOfItems()

There could be exceptions: e.g. length(), size()

Static member functions should be PascalCase e.g. Convert::ToInt(...)

Always call static member functions through classes, not through objects. e.g. Convert::ToInt(...)

Always use Exception suffix in exception class names. e.g. FileFormatException, NetworkException

Use PascalCase to name namespaces. e.g. System

For acronyms that is 2 letters, use upper case, e.g. IO, instead of io, but when the acronym is more than 2 letters use PascalCase. e.g. Html

For parameters use camelCase, e.g. void f ( int sizeOfArray) ;

Put the public interface of a class first, and later protected and private interface. e.g.
class X {
public:
//public interface
protected:
//protected interface
private:
//private interface
}

If necessary, you can use a different header file for public consumption vs. private use, though this might be more difficult to maintain, especially if the class is not very stable yet.

size_t, ptrdiff_t and off_t

Imagine you are writing a library to be used on all sorts of platforms. In this library you have a vector-like class with an index operator [], let's call this class MyArray. What should be the type of index? int comes to mind, but think again. int is 32 bits on both 64-bit platforms and 32-bit platforms (at least on Linux). This means, even though you can create a MyArray object holding number of objects that is larger than the maximum int, you can't index to portions of it because of your choice of int type. There must be a portable way of resolving this issue.

Say hello to size_t and ptrdiff_t.

size_t is the "the unsigned integer type of of the result of the sizeof operator"
ptrdiff_t is the "signed integer type of the result of subtracting two pointers"

These two types are not supposed to be same size all the time, but mostly on all systems I care about they are. They differ based on 64-bit and 32-bit systems. e.g. on 32-bits they are both 32-bits, but on 64-bits they are 64-bits integers.

How to use these types? size_t can represent the number of items you store in MyArray. ptrdiff_t can be used for iterator arithmetic for MyArray's iterators. For example MyArray may provide random access iterators which should support things like ptr-= where can be negative. To be able to fully use the memory space we have available in any platform ptrdiff_t is the ideal choice for the type of .


What's off_t doing in this post? Well, it is a type used to pass offset to various file related functions, such as ftell etc... In 32-bit systems usually it is declared as 32-bit signed integer, since we might want to give a negative offset compared to current file position. But this prevents us to open files larger than 2GB, or at least we can't we can't read from offsets larger than 2GB. To solve this problem many systems define another type called off64_t and related functions. e.g. in addition to pread, they define pread64. In such systems, we either need to use the regular open function with O_LARGEFILE flag or directly use open64 function.

C++ Code to HTML

If you are wondering how I convert C++ code to HTML, pay a visit to C++2HTML page.

Forward Declarations

From time to time we need to declare a class earlier than its definition. Consider the following example. To be able to define Object class I need to first declare String, otherwise the compiler will complain about the method that returns String.

//I need forward declaration here
class String;

class Object
{
public:
  //toString return a String object
    String toString();
};

//Now the definition comes
class String : public Object
{

};

What about forward declaration of a template class?

template <typename T>
class SmartPtr;

class Object
{
 public:
   SmartPtr<Object> clone();
};

//Now the definition comes
template <typename T>
class SmartPtr : public Object
{

};