GNU   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++ Free Stuff

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:

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:
| 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
Last modified: Sun Sep 25 16:11:43 NZDT 2016
Best viewed at 800x600 or above resolution.
© Copyright 1999-2016 Davin Pearson.
Please report any broken links to