Thursday, December 11, 2014

Virtual Method Table

Today I'm going to blog about something called a "virtual method table".  I randomly caught a talk where the speaker was saying that teaching someone to sling code is not sufficient. The student has to also understand the theory and fundamentals behind what they are learning.  A great analogy he used was that a "plumber should know what's going on underneath the sink."  He then randomly threw out some computer science terms and concepts; and let me tell you, it was refreshing.

So often we see those "learn to code" websites where they promise to teach you how to program in XX hours.  Reminds me of a great Abstruse Goose comic:

Love this comic

It's a little dated in that it references the old "Sam's Teach Yourself C++ in 21 Days" book but for those of you who don't remember this series:

Oh the lies

I remember this well because I actually had this book.  And I remember I felt like such a failure when I'd take me multiple hours to get through a single "1 hr" lesson.  Frustrated I remember throwing the book aside.

The book that really taught me how to program was:

A Beast of a Book

I forget exactly which edition, but I won't forget the name of the book.  This particular edition is a whopping 984 pages of text and weighs 3.4 pounds.  It was a beast back then, and it's a beast now.  But it's that large b/c the examples are so thorough and the explainations so in depth (at least my particular version was, I can only assume the core of the book is still the same for the fifth edition).

I really enjoyed this book, which is why I wanted to highlight it today.  Ok enough aside, onto the content.

What is a virtual method table?  For that matter, what is a virtual method?  It's really simple.  A virtual method is just a function that can be overriden by an inheriting class.  Basic rules apply, like you need to have the same signature, but it's not much more complicated conceptually than that.  Virtual methods are a core part of object oriented programming.  They can help allow things like polymorphism to happen, a key of OOP.  (There's more to polymorphism than just this, but that discussion is out of scope right now.)

So how are virtual methods implemented?  That's where we get into virtual method tables.  A typical function is bound at compile time.  In other words, when you compile your language, you compile in the location of where your function will live.  So when your program runs, it's a simple jump instruction to the spot in memory where your function resides.  Your program keeps track of where you came from, so when your function is done, you just hop right back where you came from.

Virtual methods on the other hand cannot compile in the memory location, because, you the programmer, could have created an inherited class that overrides that method.  So the compiler cannot figure out during compile time, which exact implementation to jump to.  As a result, the compiler (or runtime, depending on the language/implementation) will create a bit of indirection, called a 'virtual method table' (one table for each class) that acts as a lookup to the proper implementation that should be invoked.  Each instance of your class will have a pointer to this special virtual method table so that when the virtual method is called, the virtual method table can be checked to see which method implementation we actually want to invoke.  Because we don't know precisely the location until runtime (when we check the table), this is called "late" binding (as opposed to compile time, or "early" binding).

Virtual method tables are awesome because it allows us to be flexible in the behavior of our program.  Nothing in life is free though.  This table takes up memory and because of the added hop to the table, then to the actual method, the performance is also slower than an early bound method.  So in C++, you have to explicitly declare which ones of your methods will be virtual by using the keyword...virtual.  Shocking name, I know.  In Java, every method is virtual by default, unless you declare that method to be final or static.

That is the basic concept.  A relatively simple solution to a simple problem.  You'll often hear these concepts refered to by a bunch of various names, but it all refers to the same thing.  A virtual method table is also called a virtual function table, or a virtual call table, or vtable.  But tomato tomato (works better when you say that part aloud).

Hopefully this teaches you something, or at the very least refreshes your memory on a topic you probably don't have to deal with daily.  Take care and happy holidays :)