You are currently browsing the Sticky Bits blog archives for May, 2010.

Polymorphism in C++

May 21st, 2010

The term polymorphism is central to most discussions in and around object oriented design and programming. However I find that many people are still confused or don’t have a complete understanding of the advantages and disadvantages of using polymorphism.

I have heard many different simplified definitions of the root term for polymorphism, usually relating to chemistry or biology. Rather than trying to justify the name, I’ll give you my very simplistic definition from a software perspective.  Simply put polymorphism means:

Multiple functions with the same name.

Yep, as simple as that.

Most C programmers don’t realise they have been using polymorphic operations since they started programming. Take, for example, the following code:

b + c

That’s a polymorphic expression. Why?  Well we know nothing about the types of b and c. If b and c are of type int then the code generated is significantly different to if they are double.

But, I hear to shout, what about virtual functions and all that?

So herein lies on of the main problems. When most people use the term polymorphism they are actually referring to Dynamic Polymorphism. The expression b + c is related to Static Polymorphism.

With static polymorphism, the actual code to run (or the function to call) is known at compile time. C++ Overloading is static polymorphic, e.g.

void swap(int* a, int* b);
void swap(double* a, double *b);
int main()
{
   int x = 10, y = 20;
   double a = 1.2, b = 3.4;
   swap(&x, &y);            // swap(int,int)
   swap(&a, &b);            // swap(double, double)
}

Here the compile, based on the number and type of arguments, can determine which function to call.

Dynamic polymorphism, which in C++ is called Overriding, allows us to determine the actual function method to be executed at run-time rather than compile time.

For example, if we are using the  uC/OS-II RTOS and have developed a Mutex class, e.g.

class uCMutex
{
public:
   uCMutex();
   void lock();
   void unlock();
private:
   OS_EVENT* hSem;
   INT8U err;
   // not implemented
   uCMutex( const uCMutex& copyMe );
   uCMutex& operator=( const uCMutex& rhs );
};

And have also implemented  a very simple stack class (note this code is just for explanation purposes and has many shortcomings) that requires mutual exclusion, it may look something along the flowing lines:

class myStack
{
public:
   myStack();
   bool push(int val);
   int pop();
private:
   static const int sz = 10;
   int m_stack[sz];
   unsigned int count;
   uCMutex tm;   // uCMutex Object
};
myStack::myStack(iMutex& m):count(0), tm(m)
{
   memset(m_stack,0,sizeof(m_stack));
}
bool myStack::push(int val)
{
   bool retval = false;
   tm.lock();    // LOCK
   if (count < sz) {
      m_stack[count++] = val;
      retval = true
   }
   tm.unlock();     // UNLOCK
   return retval;
}
int myStack::pop()
{
   int val = -1;
   tm.lock();       // LOCK
   if (count != 0) {
      val = m_stack[--count];
   }
   tm.unlock();     // UNLOCK
   return val;
}

If, then, in our new design we are going to use VxWorks rather than uC/OS-II, our stack class would require reworking, thus:

class VxMutex
{
public:
   VxMutex();
   void lock();
   void unlock();
private:
   …
};
class myStack
{
private:
   ...
   VxMutex tm;
};

Even though the change from the uC/OS-II mutex to the VxWorks mutex class is within the private part of the stack class, this still has many detrimental knock on effects. Significantly, we have changed the stack class’s definition, so all files that use the stack now need recompiling. This, then, has a knock on effect to the amount of regression testing that is required.

An alternative strategy is to use dynamic polymorphism and interfaces to make our code more testable and reusable.  So, by defining an interface class for the mutex abstraction:

class iMutex
{
public:
   iMutex(){}
   virtual ~iMutex(){}
   virtual void lock() = 0;      // pure virtual function
   virtual void unlock() = 0;    // pure virtual function
private:
   // not implemented
   iMutex( const iMutex&);
   iMutex& operator=( const iMutex&);
};

We can alter the stack code so the mutex object is passed in as a constructor parameter (also the mutex classes require changes to inherit from the iMutex interface):

class uCMutex : public iMutex
{
}
class VxMutex : public iMutex
{
}
class myStack
{
public:
   explicit myStack(iMutex& m);
   bool push(int val);
   int pop();
private:
   static const int sz = 10;
   int m_stack[sz];
   unsigned int count;
   iMutex& tm;   // Mutex Reference
};

Our main code now becomes:

uCMutex ucm;
myStack ms(ucm);

or

VxMutex vxm;
myStack ms(vxm);

This is dynamic polymorphism in operation. Depending on the actual object passed (vxm or ucm), the actual code called when

tm.lock();

is executed, will either be VxMutex::lock() or uCMutex::lock().

Dynamic polymorphism is an incredibly powerful construct and, used well, creates code that can easily be adapted in the face of changing requirements with minimal impact.

However it all comes at a cost. The run-time lookup for virtual functions requires additional code and data. Each dynamic polymorphic class requires a virtual table (v-table), and each object of that type a v-table pointer (vtptr). To call the polymorphic function the run-time system requires indexing into the v-table via the object’s vtptr to actually call the function. In certain environments this can be twice as slow as a normal function call.

So how can we get the benefits of dynamic polymorphism, allowing us to abstract the code from how we’re doing it (e.g. VxWork’s lock call) to what we’re doing (Mutex lock call), but not have to extra overhead of virtual functions.

Well we have C++ templates. So modifying the stack class to become:

template <typename mutex_t>
class myStack
{
public:
   myStack();
   bool push(int val);
   int pop();
private:
   static const int sz = 10;
   int m_stack[sz];
   unsigned int count;
   mutex_t tm;   // Mutex Template Instance
};

and main becomes

 myStack<uCMutex> ms;
 ms.push(10);

With template based code we revert back to static polymorphism from dynamic polymorphism, as the actual call to tm.lock() will be compile time resolved at the possible expense of code readability and complexity.

Finally, I have found that the terms for polymorphism have a number of different names, e.g.

Dynamic Polymorphism

  • Subtype polymorphism
  • Overriding
  • Late binding

Static Polymorphism

  • Parametric polymorphism
  • Overloading
  • Early binding
%d bloggers like this: