Subj : Re: OO compilers and efficiency
To   : comp.programming
From : Rob Thorpe
Date : Tue Jul 19 2005 01:19 pm

Brian wrote:
> Is there a good approachable book that covers OO compilers?  Something
> like a Red Dragon for the ages?

Search the web/usenet for "object-orientated" "compiler" and "book".
It brings up a few things, I have no idea whether any are good.
If you asked comp.compilers they could recommend one.

> OO seems like it must be very wasteful.

It often is.  People use it normally because they believe that they
derive benefits in coding and design from the technique.  Often they
think that is more important than what they lose.

Efficiency doesn't matter that much anymore.  I haven't written
anything where processor speed has been an issue in years.

>  Extending a class usually
> means taking the super class' existing method and tacking on some
> new secret sauce stuff.

A method replaces the method of the class it inherits from.  Inside
that new method the super-classes corresponding method may be called,
or it may not be called.  If it is called then that's another function
call.

Compiled OO languages generally work using a vtable or virtual-method
table.  It adds some extra overhead not seen in procedural programs.
It's described here:
http://en.wikipedia.org/wiki/Virtual_table

The same overhead would be seen in a procedural program if it had to
use function pointers to achieve the same thing the equivalent OO
program does with virtual methods.

> So is this wrapping one stack frame on top of another?  First the
> subclasses method gets called then super's? Are compilers generally
> smart enough to inline the two calls into one?

One function is called from inside another.  It happens the same way it
does in a procedural language.  The only difference being that the
function calls may happen through a vtable.

In a statically compiled language, if the compiler can prove that the
inlining is correct, and it is likely to make the program faster then
it may do it.

If a method call is to a base class then part of the base class could
be inlined inside the sub-class.  Though it often isn't possible the
other way around.

Even if it is technically possible to inline like this it often doesn't
happen.  In C++ for example the compiler often compiles file by file.
It's difficult for a compiler of this type to inline code from another
file, this is one reason why it's possible for the programmer to put
inlined functions straight into class declarations in C++.  If you have
a compiler that can optimize whole-programs though, then the compiler
can do this.

In a JIT compiled language things are much better.  The JIT has a
dynamic view of the program and can inline whatever it likes.  If it
hits a situation like this it can inline it.

> Getter and setter functions are another simple example of what seems
> to be waste.  The method call works like this.  The existing register
> states are pushed onto the stack.  The call is made.  The getter
> method returns a simple value on the stack.  The call is returned.
> The registers are popped.  That must be about 20 instructions for
> what might only take one, a simple memory read,

In some static language the answer could be at least 20, assuming you
haven't gone through the vtable, it could be worse.  In others the
overhead of the call can be reduced in the ways Chris Dollin mentions,
assuming the function call interface of the system allows those things
to be done.

In a JIT compiled system, again see Chris's comment, it may be very
cheap indeed.

> or better yet, a
> register read.

No compiler of any language I know of would put a global or
module-local variable in a register.

> What happens if a getter or setter is right in the middle of a
> tight loop?  Let's say the loop has 200 instructions.  All of a
> sudden the loop is 10% less efficient.
>
> I guess it could be argued that this has other penalties.  The
> stack frames may be forcing unnecessary cache movement or invalidating
> CPU pipeline flow.

There isn't much difference in static frames here than in procedural
programs.  C++ object-orientated programs do though often have large
amounts of calls through the vtable.  These are not easy to predict
causing problems with modern pipelined microprocessors when they
mispredict them.

> Anyway, those are some of the things that kind of nag at me.
> I think it's a safe statement to say C can beat any OO compiled
> program pound for pound given the same programmer skill and
> adherence to language goals.

I expect that's probably true.  It's not that relevant these days
though since there aren't so many things that need speed as once there
were.

> Does everyone drop into C for critical code?

It's done sometimes when speed is of interest.  In C++ more often OO
paradigms are ignored for speed critical code and it is written as
though it were C.
Sometimes people improve the algorithms they use instead, as Chris
mentions.

> Or am I the only one who worries about this stuff?  Is it a
> concern or should I kind of push it back into the recesses
> of my mind and say the wastefulness is part of the tradeoff
> for programming OO code?

Personally, I think object-orientation is useful for graphics but not
useful for very many other things.  But the wastefulness of OO is not a
very strong reason against it anymore.

.