davin.50webs.com/research
Bringing to you notes for the ages

Main Menu	Research Projects	Photo Album	Curriculum Vitae	The Greatest Artists
Email Address	Computer Games	Web Design	Java Training Wheels	The Fly (A Story)
Political Activism	Scruff the Cat	My Life Story	Smoking Cessation	Other Links
Debugging Macros	String Class I	Linked List System I	Java for C Programmers	Naming Convention
String Class II	How I use m4	Strings III	Symmetrical I/O	Linked Lists II
Run-Time Type Info	Virtual Methods	An Array System	Science & Religion	Submodes
Nested Packages	Memory Leaks	Garbage Collection	Internet & Poverty	What is Knowledge?
Limits of Evolution	Emacs Additions	Function Plotter	Romantic Love	The Next Big Thing
Science Fiction	Faster Compilation	Theory of Morality	Elisp Scoping	Elisp Advice
S.O.G.M. Pattern	Safe Properties	School Bullying	Charisma Control	Life and Death
Splitting Java	Multiple Ctors	Religious Beliefs	Conversation 1	Conversation 2
J.T.W. Language	Emacs Additions II	Build Counter	Relation Plotter	Lisp++ Language
Memory Leaks II	Super Constructors	CRUD Implementation	Order a Website Form	There Is An Afterlife
More Occam's Razor	C to Java Translator	Theory of Morality II

Efficient calls to virtual methods in C++

Abstract

If a C++ method foo of a class B is virtual and it is known at compile-time that no method of any subclass of B overrides foo or that B has no subclasses, then assuming an intelligent compiler, calls to foo should result in either:

A non-virtual method call, or given optimisation
An inlined method call.

This article presents a design pattern that guarantees this result, even with a dumb compiler.

1. The Design Pattern

Consider the following C++ code:

#include <iostream>

class B
{
public:
   virtual void foo()
   {
      std::cout << "I am B's foo\n";
   }
};

void bar(B* b)
{
   // *** Checkpoint 1
   b->foo(); // PRINTS OUT: "I am B's foo"
}

int main()
{
   // ALLOCATION:
   B* b = new B;

   bar(b);

   // DEALLOCATION:
   delete b;
}

If no subclasses of B (direct or indirect) overrides foo then the call to b->foo() at checkpoint 1 should result in either a non-virtual method call or with optimisation, an inlined method call. However if no subclasses of B override foo then there is no point in having foo as a virtual method. Therefore the design pattern is not applicable in this case.

However if the class B is a subclass of another class called (say) A and no subclass of B overrides foo then the design pattern can be used to achieve the above result. Consider the following code:

#include <iostream>

class A
{
public:
   virtual void foo()
   {
      std::cout << "I am A's foo\n";
   }
};

class B : public A
{
public:
   virtual void foo()
   {
      std::cout << "I am B's foo\n";
   }
};

void bar(B* b)
{
   // *** Checkpoint 1
   b->foo(); // PRINTS OUT: "I am B's foo"
}

int main()
{
   // ALLOCATION:
   B* b = new B;

   bar(b);

   // DEALLOCATION:
   delete b;
}

Examining the assembler output of GNU C++ shows that even under -O3 strength optimisation, a virtual method call is generated at checkpoint 1. Removing the virtual keyword from B's foo method makes no difference in the code that is generated. To improve this result we need to rearrange the code to what follows:

#include <iostream>

class A
{
public:
   virtual void virtual_foo()
   {
      std::cout << "I am A's foo\n";
   }
};

class B : public A
{
public:
   void foo()
   {
      std::cout << "I am B's foo\n";
   }
   virtual void virtual_foo()
   {
      foo();
   }
};

void bar(B* b)
{
   // *** Checkpoint 1
   b->foo(); // PRINTS OUT: "I am B's foo"
}

int main()
{
   // ALLOCATION:
   B* b = new B;

   bar(b);

   // DEALLOCATION:
   delete b;
}

Examining the assembler output of GNU C++ on the above, calling b->foo() at checkpoint 1 results in a non-virtual method call under no optimisation and an inlined method call under optimisation. Because B has has no subclasses, this is the same result as calling b->virtual_foo(), only the latter generates a virtual method call and is therefore less efficient.

Unfortunately in C++ there is no way to guarantee that a method is not overridden in any subclass (direct or indirect) of a given class, so this design pattern must be used with care. In Java, classes and methods can be marked as final and either of these would ensure that this is the case.

2. Applying the Design Pattern to an I/O System

Consider the following simplified code snippet of the I/O system described in an earlier article. Actually the string, string_buffer and string_buffer2 classes were one and the same thing in the earlier article but this difference is of no significance.

// Class for readonly strings
class string {
   // Method for compatibility with C strings
   const char* const_char_star() const;
   // Rest of class definition omitted...
};

// Abstract class for stream output
class Writer
{
public:
   virtual ~Writer() {}
   virtual Writer& operator << (char ch)       = null;
   virtual Writer& operator << (int i)         = null;
   virtual Writer& operator << (double d)      = null;
   virtual Writer& operator << (const char* s) = null;
   Writer& operator << (const string& s)       { *this << s.const_char_star(); return *this; }
};

// Class for readable writable strings
class string_buffer : public Writer , public string
{
public:
   virtual Writer& operator << (char ch);
   virtual Writer& operator << (int i);
   virtual Writer& operator << (double d);
   virtual Writer& operator << (const char* s);
};

// Class for efficient anonymous strings
class string_buffer2 : public string_buffer
{
   // Code omitted
};

// Class for writing to files
class File_Writer : public Writer
{
private:
   FILE* f;
   bool ours_to_close;

public:
   File_Writer(string filename);
   File_Writer(FILE* f);
   ~File_Writer();

   virtual Writer& operator << (char ch);
   virtual Writer& operator << (int i);
   virtual Writer& operator << (double d);
   virtual Writer& operator << (const char* s);
};

int main()
{
   {
      string_buffer sb;
      sb << "apple ";           // *** Appends "apple "  to sb
      sb << "banana ";          // *** Appends "banana " to sb
      sb << "carrot ";          // *** Appends "carrot " to sb
      cout << sb;               // Outputs "apple banana carrot" to the standard output stream
   }
   {
      File_Writer fw("output-1.el");
      fw << "apple ";           // *** Appends "apple "  to file "output-1.el"
      fw << "banana ";          // *** Appends "banana " to file "output-1.el"
      fw << "carrot ";          // *** Appends "carrot " to file "output-1.el"
   }
   {
      string_buffer sb;
      Writer& w = sb;
      w << "apple ";            // ??? Appends "apple "  to w
      w << "banana ";           // ??? Appends "banana " to w
      w << "carrot ";           // ??? Appends "carrot " to w
      cout << sb;               // Outputs "apple banana carrot" to the standard output stream
   }
   {
      File_Writer fw("output-2.el");
      Writer& w = fw;
      w << "apple ";            // ??? Appends "apple "  to file "output-2.el"
      w << "banana ";           // ??? Appends "banana " to file "output-2.el"
      w << "carrot ";           // ??? Appends "carrot " to file "output-2.el"
   }
}

The code labelled as ??? above would most probably result in virtual method calls. Because the string_buffer2 subclass of string_buffer doesn't override any of the methods of string_buffer and class File_Writer has no subclasses, one would hope that the code labelled as *** above would result in non-virtual method calls. To guarantee this result, we need to rearrange the code in the above classes to what follows:

// Class for readonly strings
class string {
   // Method for compatibility with C strings
   const char* const_char_star() const;
   // Rest of class definition omitted...
};

// Abstract class for stream output
class Writer
{
public:
   virtual ~Writer() {}

private:
   virtual void write(char ch)       = null;
   virtual void write(int i)         = null;
   virtual void write(double d)      = null;
   virtual void write(const char* s) = null;

public:
   Writer& operator << (char ch)          { this->write(ch); return *this; }
   Writer& operator << (int i)            { this->write(i);  return *this; }
   Writer& operator << (double d)         { this->write(d);  return *this; }
   Writer& operator << (const char* s)    { this->write(s);  return *this; }
   Writer& operator << (const string& s); { this->write(s.const_char_star()); return *this; }
};

// Class for readable writable strings
class string_buffer : public Writer , public string
{
public:
   string_buffer& operator << (char ch);
   string_buffer& operator << (int i);
   string_buffer& operator << (double d);
   string_buffer& operator << (const char* s);

private:
   virtual void write(char ch)       { *this << ch; }
   virtual void write(int i)         { *this << i;  }
   virtual void write(double d)      { *this << d;  }
   virtual void write(const char* s) { *this << s;  }
};

// Class for efficient anonymous strings
class string_buffer2 : public string_buffer
{
   // Code omitted
};

// Class for writing to files
class File_Writer : public Writer
{
private:
   FILE* f;
   bool ours_to_close;

public:
   File_Writer(string filename);
   File_Writer(FILE* f);
   ~File_Writer();

   File_Writer& operator << (char ch);
   File_Writer& operator << (int i);
   File_Writer& operator << (double d);
   File_Writer& operator << (const char* s);

private:
   virtual void write(char ch)       { *this << ch; }
   virtual void write(int i)         { *this << i;  }
   virtual void write(double d)      { *this << d;  }
   virtual void write(const char* s) { *this << s;  }
};

int main()
{
   {
      string_buffer sb;
      sb << "apple ";           // *** Appends "apple "  to sb
      sb << "banana ";          // *** Appends "banana " to sb
      sb << "carrot ";          // *** Appends "carrot " to sb
      cout << sb;               // Outputs "apple banana carrot" to the standard output stream
   }
   {
      File_Writer fw("output-1.el");
      fw << "apple ";           // *** Appends "apple "  to file "output-1.el"
      fw << "banana ";          // *** Appends "banana " to file "output-1.el"
      fw << "carrot ";          // *** Appends "carrot " to file "output-1.el"
   }
   {
      string_buffer sb;
      Writer& w = sb;
      w << "apple ";            // ??? Appends "apple "  to w
      w << "banana ";           // ??? Appends "banana " to w
      w << "carrot ";           // ??? Appends "carrot " to w
      cout << sb;               // Outputs "apple banana carrot" to the standard output stream
   }
   {
      File_Writer fw("output-2.el");
      Writer& w = fw;
      w << "apple ";            // ??? Appends "apple "  to file "output-2.el"
      w << "banana ";           // ??? Appends "banana " to file "output-2.el"
      w << "carrot ";           // ??? Appends "carrot " to file "output-2.el"
   }
}

With the above definitions in force, the function calls labelled as *** above can be guaranteed to generate non-virtual method calls. I use this design pattern in my non-standard I/O library presented on two earlier articles (1 and 2).

Back to Research Projects

This page has the following hit count: