Subj : Re: OO compilers and efficiency
To   : comp.programming
From : Chris Dollin
Date : Tue Jul 19 2005 06:21 pm

Brian wrote:

> OO seems like it must be very wasteful.

Does it?

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

Erm ... no. No, more often it means /replacing/ the effect of
some method with a different one (which may call the super-classes
definition, if it so chooses).

> So is this wrapping one stack frame on top of another?  First the
> subclasses method gets called then super's? 

Perhaps. And then again, perhaps not. How much OO code have you
written?

> Are compilers generally smart enough to inline the two calls into 
> one?

Pass - but were I writing a compiler (better, a JIT), I'd almost
certainly inline or do a cheap call.

> 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, or better yet, a
> register read.

It can't (in general) be a register read; instance variables aren't
(cannot-ish) be stored in registers, they're a slot in the instance
object. 

A JIT will almost certainly inline the code. Even so, your estimates 
for the cost of a call are wildly pessimistic. The code for the
getter is already available, so it can be annotated or analysed.
Consider first the code of the getter. It need only load the value
of the instance variable into the result register. (No, of *course*
you don't push it onto a stack.) Then it has to return. I make
that two instructions. Let's suppose (perfectly reasonably) that
we mark the getter as `destroys no caller-saves registers` [the
result register is the result register, not a caller-saves register].
When compiling the call, we see that no registers need be saved,
so we don't save any - except we need to note that this method must
save its return address, unless we're doing a tail-call - and just
call the getter. When it returns, the answer is in a known register.

So the cost is small, even if the getter isn't inlined.

This is no different from compiling non-OO code, of course. 

> 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.

There are so many assumptions buried there that I can only
mention a few.

* OO languages typically [ie, Java] come with GC. C doesn't. 
  This can make an enormous difference to the simplicity of OO
  code. That means that OO programs can tackle larger problems
  with the same-ish amount of engineering effort  - they can
  out-produce the C programmer before the code efficiency is
  an issue. (What the OO program loses in GC costs is roughly
  the same as what the C program loses in memory-management
  costs, eg copying.)

* The writers of OO compilers are not stupid and will make
  every effort to generate not-stupid code. The stronger
  semantics of OO languages (well, really, most not-C languages)
  give them greater manoeuvering power in their optimisations.

* When performance is a business issue, effort can be spent on
  improving performance. That effort includes profiling and
  concentrating on the bits that give a decent effort/payback
  tradeoff.

* The decoupling of a decent OO design may (or may not, depending
  on the language & implementation) cost a bit at runtime. On the
  other hand, it can make rearchitecting the program much easier;
  and that in itself can be a win.

> Does everyone drop into C for critical code?

Not everyone *has* critical code.

Here's a currently-anecdotal example. We want to improve the
query performance of Jena. It is, roughly speaking, a bunch
of nested loops, with generators and filters between the
stages.

It turns out that various of the filters can be eliminated,
or simplified, or computed at least partially in advance.
And the generators ditto. And the core iterators, which are
Set iterators, can be replaced by reimplementing Sets in
a way which allows you to push the filters and generators in
as far and as hard as you can. (And I suspect we can do even
better by replacing the iterators with map-over oeprations.)

A factor of two is easy. Three isn't hard. My colleague who
did most of the hard work got it up to a factor of *twenty*.
(We may, for maintainability reasons, forgo some of that.)

Going into C was never considered. Apart from anything else,
it would trash our portability.

> 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?

You over-estimate the cost and under-estimate the benefit.

-- 
Chris "electric hedgehog" Dollin
It's called *extreme* programming, not *stupid* programming.

.