From: Robin Holmes on
Writing code with objects and virtual functions allows for faster
program construction and often code with less bugs and code that is
easier to change. But many virtual function calls can cause some
performance degradation for some kinds of code. For JIT compilation, I
have created this new technique, called ROD, that you can use to
speedup performance of some virtual calls in some kinds of programs.

http://www.pacificv.prophp.us/rod.php

http://juke.googlecode.com/files/ROD_100.pdf

If you understand VM and JIT, please get back to me with your
thoughts . I would like to get some info on how you will integrate it
with your own VM or if you think it would break your JIT code.
From: Dmitry A. Kazakov on
On Mon, 25 Jan 2010 05:33:17 -0800 (PST), Robin Holmes wrote:

> Writing code with objects and virtual functions allows for faster
> program construction and often code with less bugs and code that is
> easier to change. But many virtual function calls can cause some
> performance degradation for some kinds of code.

This is not an issue in a properly typed language, for example, in Ada,
which statically distinguishes the class type (a closure of types derived
from some root) and the concrete type (a member of the class). So dispatch
never happens when the object's type is known. Especially no re-dispatch
happens if not explicitly requested, because types of all arguments are
known in the bodies.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
From: S Perryman on
Dmitry A. Kazakov wrote:

> On Mon, 25 Jan 2010 05:33:17 -0800 (PST), Robin Holmes wrote:

>>Writing code with objects and virtual functions allows for faster
>>program construction and often code with less bugs and code that is
>>easier to change. But many virtual function calls can cause some
>>performance degradation for some kinds of code.

> This is not an issue in a properly typed language, for example, in Ada,
> which statically distinguishes the class type (a closure of types derived
> from some root) and the concrete type (a member of the class). So dispatch
> never happens when the object's type is known. Especially no re-dispatch
> happens if not explicitly requested, because types of all arguments are
> known in the bodies.

You can guarantee (for single dispatch) a fixed performance bound of one
indirection before the op invocation.

Which is a useful target env option for systems that do not have reams of
object instances with reams of virtual ops. But not practical for the
general case.


Regards,
Steven Perryman
From: Robin Holmes on
Thanks for the replies. Go through the specification slowly at
pacificv.prophp.us/rod.php . What I am talking about is much bigger
for some purposes than static devirtualization based on class
analysis. This object devirtualization is a specific attribute for
specific functions like the root of a file parser, the process
function of a VST etc... The actual devirt function itself is not
inlined, but instead inlines just about as much as it can that is in
the execution path of itself, because it knows the actual objects it
will be using.

You need to think here of massive inlining, like hundreds or thousands
of inlined functions and direct memory references to fields. The
output machine code for one properly devirted function can be huge(BUT
RUN TWICE AS FAST IN SOME THEORYS).

For example:

class TObject {
devirt void devirtFunction() { }
}
class TObjectA : public TObject {
devirt void devirtFunction() {
//
}
}
class TObjectB {
devirt TObjectA* fieldX;
devirt void devirtFunction() {
// because we know the allocated instance of the this parameter
when we devirt
// this function, we also know the allocated instance of fieldX,
thus
// allowing direct memory references to it and its children, as
well as
// being able to just inline any virtual functions on it because
we already know
// the type.
fieldX->someVirtualMethod();// This can just be inlined no matter
its class
}
}

void callDevirt(TObject* obj) {
// This call here on a type of TObject* is where the devirt happens.
// It is not inlining this call itself, but instead building one
massive function
// that actually uses the runtime allocated instance of obj to do
the JIT, instead
// of normal JIT where method JIT is using static class types to do
the JIT. In other
// words one function per instance is JITTED for each different obj
passed to
// this function
obj->devirtFunction();

// The point is that JIT compiling and knowing the exact object used
for
// the specific call will allow you to inline a lot more than you
could with
// static analysis of type information. The speedup of some code
made
// using normal OOP and some well placed devirt attributes can be
enormous.
}

TObject* instanceA = new TObjectA();
TObject* instanceB = new TObjectB();

callDevirt(instanceA);
callDevirt(instanceB);

So if we have a VST plugin that must generate audio, or an SQL
statement that must run quick, we can program as usual the things
inside, such as string comparers, Select statements, DSP filters,
rounding functions and so on. In other words program like with objects
and virtual functions. Then by placing the devirt keywords carefully
we can get the JIT to do all the inlining an optimization often better
and much faster than could be done with hand optimized machine code.

The main points are:
Its Object devirtualization, not based on static type analysis
Its not good for just any virtual function(except for once you are
actually doing a devirt)
Its good for code that uses lots of virtual functions and fields
inside a repeated base function call like the process function of a
VST plugin, or the compile function of an SQL statement object(or a C+
+ parser or tokenizer object for example).

By following all the virtual calls in such code constructs, and all
the field references, it can be proven that large amounts of code can
be removed, specifically stack frames, ret statements, double derefs
to get at fields in objects, call statements etc...

The trick to understanding it is thinking differently about the LDTHIS
instruction in your JIT. When you encounter LDTHIS, dont load and work
with only the static assumed type of the this parameter, but pass the
JIT the actual runtime object of the this parameter and use that
instead when you hit a LDTHIS. Once you have that on the pseudo stack,
then go further and get the actual runtime object for fields of the
this parameter and even fields of those fields.

So once you get like a CALLVIRT instruction on the loaded LDTHIS
result on the pseudo stack, you can inline the virtual function
because you already know the exact object you will be using,.
From: Dmitry A. Kazakov on
On Tue, 26 Jan 2010 08:02:46 -0800 (PST), Robin Holmes wrote:

> Thanks for the replies. Go through the specification slowly at
> pacificv.prophp.us/rod.php . What I am talking about is much bigger
> for some purposes than static devirtualization based on class
> analysis. This object devirtualization is a specific attribute for
> specific functions like the root of a file parser, the process
> function of a VST etc...

I think the conventional naming for this is polymorphic vs. non-polymorphic
object/type/operation.

[...]
> // because we know the allocated instance of the this parameter when we devirt
> // this function, we also know the allocated instance of fieldX, thus
> // allowing direct memory references to it and its children, as well as
> // being able to just inline any virtual functions on it because we already know
> // the type.
> fieldX->someVirtualMethod();// This can just be inlined no matter its class
> }
> }

This is the point, when the type is known it must be *properly* attributed.
The problem you address simply does not exist in a properly typed language
that *distinguishes* classes and types, thus polymorphic and
non-polymorphic things become distinguishable as well. Your example written
in Ada:

type T is tagged private;
procedure Foo (X : in out T;

type S is new T with private;
overriding procedure Foo (X : in out T);

type Q is record
X : S;
end record;
procedure Bar (Y : in out Q);

procedure Bar (Y : in out Q) is
begin
Y.X.Foo; -- Or Foo (Y.X), no matter
end Bar;

Since the type of X is stated as S, it is statically known to be S and
nothing else. A call to Y.X.Foo will be statically resolved and can be
inlined if there is a desire to do so.

BTW, no pointers are needed as the type and thus the object's size is known
too. So you put S into Q and save overhead of memory and performance.

This is possible because S and S'Class are distinct types. An instance of S
is non-polymorphic, it is always S. An instance of S'Class is polymorphic
and can "contain" S or any type derived from it.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de