Optimization for OOP
sgke...@gmail.com
I'm in the beginning of writing an optimizer for an object oriented
programming language. At the moment I'm working on developing a list
of possible optimizations that can be performed on the code. The
language runs on a virtual machine.
While I have a fairly good list of optimizations possible I seem to be
drawing a blank on what to do to optimize objects and classes in the
language. I was wondering if anyone could point me in the right
direction for OOP optimization resources (for example... detailed info
on what Java does to optimize classes and objects at compile time).
In addition I am looking for some good books or articles pertaining to
common subexpression elimination. I've read a few things on it and
understand the general concept and implementation, but would like
additional information if possible.
Thanks :)
Torben Ægidius Mogensen
> I'm in the beginning of writing an optimizer for an object oriented
> programming language. At the moment I'm working on developing a list
> of possible optimizations that can be performed on the code. The
> language runs on a virtual machine.
The most important optimisation is to get rid of dynamic method calls.
This can, however, be quite tricky as you can't tell if a method can
be overridden without knowing the whole program, so it plays havoc
with separate compilation. A compromise is to allow methods to be
declared "final", which ensures it is never overridden.
If you design your own language, you can make "final" the default, so
you would have to write explicitly if a method is allowed to be
overridden. In many cases, methods are final, but the programmers are
just to lazy to declare this, or think "yeah, maybe, I will in the
future override this, so I'll just leave this possibility open", and
then they never override it anyway.
Torben
Dmitry A. Kazakov
> The most important optimisation is to get rid of dynamic method calls.
>
> This can, however, be quite tricky as you can't tell if a method can
> be overridden without knowing the whole program, so it plays havoc
> with separate compilation. A compromise is to allow methods to be
> declared "final", which ensures it is never overridden.
I think a consistent types system would be a better way. In Ada it is
always known if a call is dispatching or not. That is because of
proper typing. When an object is of a specific type, its methods never
dispatch, for that obvious reason, that the type is known to be
specific.
For the same reason in Ada there is no implicit re-dispatch from the
method bodies. A method always deals with a specific type, it has
dispatched before. Therefore any further calls from there to other
methods never dispatch again. The compiler knows their targets
statically, it can inline them etc.
--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
Tony Finch
>
>The most important optimisation is to get rid of dynamic method calls.
>This can, however, be quite tricky as you can't tell if a method can
>be overridden without knowing the whole program, so it plays havoc
>with separate compilation.
The Self papers have some good descriptions of optimisation techniques
for a pure OO language. http://research.sun.com/self/papers/papers.html
In a VM-based language you can implement a tracing JIT which naturally
specializes away dynamic dispatch. Mike Pall wrote a short description
of how this works in the second half of his post to the Lua list
linked below, with some references to papers.
http://lua-users.org/lists/lua-l/2008-02/msg00051.html
Tony.
--
f.anthony.n.finch <d...@dotat.at> http://dotat.at/
FITZROY SOLE: VARIABLE 4 IN EAST, OTHERWISE SOUTHERLY 5 TO 7, OCCASIONALLY
GALE 8 IN WEST SOLE. ROUGH OR VERY ROUGH IN WEST, SLIGHT OR MODERATE IN EAST.
SHOWERS, WITH FOG PATCHES IN EAST. MODERATE OR GOOD, OCCASIONALLY VERY POOR.
lucr...@lycos.co.uk
wrote:
> I think a consistent types system would be a better way. In Ada it
> is always known if a call is dispatching or not. That is because of
> proper typing. When an object is of a specific type, its methods
> never dispatch, for that obvious reason, that the type is known to
> be specific.
From what I've read about it, in Ada you can actually statically or
dynamically dispatch depending on *how* you call the subprogram. I've
not tried this BTW, but would love to see an example :D
Luke.
Dmitry A. Kazakov
Strictly speaking it does not depend on "how", it depends on "what", i.e.
on the object's type:
type T is tagged null record; -- a type
procedure Foo (X : T); -- a method of T
type S is new T with null record; -- a derived type
procedure Foo (X : S); -- Foo gets overridden for S
O1 : T; -- the type is specific T
O2 : S; -- the type is specific S
O3 : T'Class := O1; -- the type is unspecific, any derived from T
O4 : T'Class := O2; -- like above
Foo (O1); -- statically resolved to Foo of T
Foo (O2); -- statically resolved to Foo of S
Foo (O3); -- dispatches to Foo of T
Foo (O4); -- dispatches to Foo of S
O3 and O4 are polymorphic objects (Ada uses the term "class-wide"). IFF a
method (Ada calls it "primitive operation") of some type T is called on a
polymorphic object from the class of T, that dispatches according to the
type tag of the object.
The types of polymorphic and specific objects are different in Ada. They
are T'Class and T respectively. This eliminates re-dispatch in methods and,
though Ada does not go that far, potentially allows an implementation of
multiple dispatch, as well as classes of small scalar types with value
semantics, like Boolean and Integer (without space/performance overhead).
sgke...@gmail.com
Anyway, the final Idea is good, it will allow me some more knowledge
about what the programmer feels a function should be doing. And thus
allow the optimizer to know what it can do. However, the problem is,
because of the way the optimizer is set up (basically the way in which
it sits between the compiler and executer, something which I have no
control over) I can only analyze one source file at a time, and can
NOT keep track of information from file to file. Obviously this is a
huge disadvantage for optimization, but its all that I can do.
Some of the stuff I was considering for objects is as follows:
1) perform checking of interfaces at optimization time and prevent
this from needing to happen at execution time IF the interface is in
the same file. (otherwise it is outside the scope I can work on and it
is possible that the interface may be different from compiling to
compiling)
2) perform inlining of small private methods and of small final
methods
3) convert small get/set type functions for private data members into
direct accesses of the data members
Unfortunately the way in which OOP is implemented in the language
makes it nearly impossible for me to put any good optimizations in at
compile time as its fairly unlikely that the optimizer will know much
if anything substantial about a class at compile time. I suppose it
may be possible to write a heavy weight compile time optimizer and a
VERY light weight execution time that attempts to quickly make pre-
targeted replacements and optimizations if appropriate. However, an
execution time optimizer is a slippery slope since there is a good
chance if the optimizations are good and done quickly then it could
actually slow down the execution.
Another model which I have been considering is the use of a profiler
based optimization system. In which I could embed a profiler into the
VM, the profiler could attempt to detect bottle necks and in order to
improve OOP try to figure out the cases that classes *usually* resolve
to (i.e figure out if class A in file a always makes use of abstract
class B in file b). This information could then either be used by a
compile time optimizer to re-optimize the code OR by an execution time
optimizer to better target areas of highest execution time
optimization in order to keep the execution time optimizer costs to a
minimum. Obviously, the profiler should try to turn itself off at some
point (or allow the user to turn it off) in order to attempt for a
zero or close to zero impact from the hooks to the profiler. In other
words... collect data for a while, either re-optimize with profiler
data or build better execution time optimizer targets, and then shut
the profiler down in order to make further execution even faster. It
should be noted that the optimized code would be saved for possibly
thousands of executions, therefore... it may make sense to put a
performance hit on say the first 100 executions in order to detect how
the next 1000+ executions could be done better and faster.
This of course is all speculative and the actual implementation is
probably not in the near future. At the moment I'm just finishing up
the peephole optimizations, and I plan on tackling areas such as loops
long before I tackle complex OOP optimizations (though, hopefully they
should show a good deal of improvement for execution).
Anyway, this post really just turned into a brain dump of where I am
with the OOP optimization stuff right now.