Re: [Caml-list] Object-oriented access bottleneck

[Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>]

OK, let's make a few things clear.

First to Brian Hurt:
I do not fully understand the details of your hashing approach, but be
assured that virtual method calls are already fast enough. Indeed
there is some hashing going around, and currently a two-level sparse
array vtable, such that you can find the method code just with 4 load
instructions starting from the object (one of them is to get the
method label from the environment). This is pretty optimal in terms of
performance.

When I said no serious optimization, I meant no known function call
(meaning that all method calls with arguments must go through an
indirection through caml_applyN, which adjusts the number of arguments
to the closure, and of course a big loss in path prediction), and no
inlining.
Depending on the architecture, a micro-benchmark gives between 30 and
50 cycles for a one-argument call (i.e. including the call to
caml_apply2).

And inlining matters, if you think of all these methods that are just
getting or setting an instance variable.

The next release will probably be a bit more efficient for intra-class
calls, but since the cost is not so much the method retrieval as the
call itself, do not expect any boost.

Next, to Nuutti Kotivuori:

> > As you remarked already, the object model chosen in ocaml makes
> > final methods mostly irrelevant. There is however one way to tell
> > the compiler that a specific method code should be used, but this
> > only works for calls inside a class: inherit c ... as super method p
> > = ... super#m ...  In this case, if we know statically the class c,
> > we exactly know the code referenced by super#m. However, this
> > information is not used currently (and is probably not what you want
> > for your own code). And there is no way to tell this for a method
> > defined in the same class.
> 
> Ah, right! So it would be possible to inline the "c"'s method "m" into
> the body of method "p" in class "a" - just that the compiler doesn't
> do that?

Yes. But not as easy as it sounds, as the current compilation scheme
for classes "hides" the actual code for methods deep inside the class
creation function.
In theory, this should be possible if there is a real incentive to do
that. Yet, to be really useful, this would require having final
methods too, since having to go through super is a bit far fetched.

> > If your problem requires objects, I'm interested if you can show me
> > some code: I'm in the process of making extensive changes to object
> > compilation, and I need serious performance sensitive benchmarks.
> > (All my programs using objects call them only a few times, so that
> > method calls could be 10 times slower and I wouldn't care)
> 
> This is mostly an academic problem for me right now, as I'm just
> getting into OCaml. So no actual production code is at hand.

That's where we are a bit in a chicken and egg problem: if there is no
program, there is nothing to optimize, but if it is not optimized,
nobody will write performance critical code to start with...
(Some people have sent me pointers to code I should look at)

> But here is a trivial example, as my weak OCaml skills could produce
> it:
> 
> ,----
> | class atom =
> | object (self : 'a)
> |   val mutable id = 0
> |   method get_id () = id
> |   method compare (x:'a) =
> |     let x_id = x#get_id () in
> |       if id < x_id then -1 else if id > x_id then 1 else 0
> | end;;
> | 
> | let atom_compare (x:#atom) (y:#atom) = x#compare y;;
> | 
> | let sort_atoms x = List.sort atom_compare x;;
> `----
> 
> Now, it should somehow be possible to translate this into a form where
> the body of sort_atoms would be fully inlined with no external
> function calls. As I take it, calling List.sort like that in a
> traditional program doesn't get inlined yet either? But you get the
> idea.

Unrelated points: why is "id" mutable? and you probably don't need the
unit argument to get_id.

Now, what can we hope to optimize/inline.
Here I would say: nothing. Due to ocaml's object model, calls to an
unknown object's method must go through the vtable, as the object
could be from any class sharing the same interface.

The only things that final methods would buy you would be:
   method final get_id () = id
   method compare (x:'a) =
     let x_id = x#get_id () and my_id = self#get_id () in
       if my_id < x_id then -1 else if my_id > x_id then 1 else 0
Here, we should be able to inline self#get_id.
Also,
   let a = new atom in
   a#get_id ()
Here we know the actual class of a, so a#get_id could (in
theory) be inlined.

As you can see, this is pretty limited.

> It's good to know that progress is being made on the object front,
> especially in terms of performance.

Not so much in terms of performance. The concern is more to get smaller
code, and to allow marshalling (in some cases). And of course, not to
degrade performance.

> Some of these might be doable, I just don't know how, but a few
> things that bugged me when I investigated were:
> 
>  - no way to specify the exact type for an argument - atleast not
>    without abstract types. If I type:
> 
>      let f (x:a) = x#m
> 
>    then f will accept any object that has exactly the interface of a.

This is the ocaml object model. "a" in types is not a class, just an
interface. Hard to change without obfuscating the language.

>  - no way to have a method/function inside a class that could be used
>    by several methods, would have access to class variables and would be
>    inlined. It would not need to be visible to the outside. Like
>    mentioned, this can be circumvented for non-mutable variables by just
>    giving them as parameters.

This one is theoretically possible.

>  - no standard way to have method call like invocation for normal
>    function calls. Consider for example:
> 
>      Udp.get_data (Ip.get_udp (Eth.get_ip (Packet.as_eth packet)))
> 
>    Against the same with a handy definition of let (-->) x f = f x:
> 
>      packet --> Packet.as_eth --> Eth.get_ip --> Ip.get_udp --> Udp.get_data
> 
>    Or, as actual method calls:
> 
>      packet # as_eth # get_ip # get_udp # get_data
> 
> Though I'm not sure if you were touching features or syntax at all :-)

What's wrong with your definition of (-->) ? It already works, isn't it?
And in native code it should be inlined.
I would prefer not to touch syntax at all.

Cheers,

Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners