[Caml-list] Object-oriented access bottleneck

[Caml-list] Object-oriented access bottleneck

[Nuutti Kotivuori]

This message identical to the post I made to comp.lang.ml a while back
- but I think it will have a better audience over here, now that I
decided to join the list.

---

Lately I've been having a bit of a dilemma caused by a bottleneck from
object-oriented access in Ocaml. The problem derives from the
implementation of method calls through lazy binding.

Compiled languages which offer an object oriented system usually
provide a way for methods to short-circuit the lazy binding (or
virtual function table) system. In C++, non-virtual functions do this,
in Java, declaring a method final gives the compiler a hint about
this. In this case, the compiler can inline the method into the
caller.

Ocaml doesn't seem to be provide such a way. Upon closer inspection it
is obvious how this is so - if we allow subtyping by coercion, we have
no idea of the underlying implementation of the object given to the
function - where as when inheritance relationships are traditionally
forced in languages, we know that the implementation is composed of
the class atleast.

So, the obvious solution is to write the functions that do not need
the lazy binding outside the class itself, as normal functions. But
that doesn't help either - because there's no way to access data in
the object without going through a lazy binding call again.

What this all amounts to is that you cannot store data inside classes
at all, if some parts of it might require performance critical
work. The problem can be lessened by placing the data in a record,
which is only referenced from the object and passed around - or
something similar - but that adds complexity into the whole thing.

And theoretically if you absolutely *know* what type your object is
and that it isn't subtyped, you could use the direct field accesses in
Obj, but that amounts to major hackery already.

So - I am asking if I'm correct in my deductions here, or if I missed
some important point. Or if there's an alternative way to circumvent
this restriction.

To summarize - is there any way to have some function (or method or
whatever) that is able to access object member data, without the
overhead of a lazy binding function call? Preferably ofcourse such a
function should be eligible to be inlined.

Thanks in advance,
-- Naked

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

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

[Nicolas Cannasse]

[...]
> So - I am asking if I'm correct in my deductions here, or if I missed
> some important point. Or if there's an alternative way to circumvent
> this restriction.
>
> To summarize - is there any way to have some function (or method or
> whatever) that is able to access object member data, without the
> overhead of a lazy binding function call? Preferably ofcourse such a
> function should be eligible to be inlined.
>
> Thanks in advance,
> -- Naked

There is good way : don't use objects :-)
For most of the cases, modules should be powerful enough and offer far
better performances... and inlining.
Even if you need some specialisation, you can always handle it using a
closure.

Nicolas Cannasse

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

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

[Jacques Garrigue]

From: Nuutti Kotivuori <naked+caml@naked.iki.fi>

[...]
> What this all amounts to is that you cannot store data inside classes
> at all, if some parts of it might require performance critical
> work. The problem can be lessened by placing the data in a record,
> which is only referenced from the object and passed around - or
> something similar - but that adds complexity into the whole thing.
> 
> So - I am asking if I'm correct in my deductions here, or if I missed
> some important point. Or if there's an alternative way to circumvent
> this restriction.
> 
> To summarize - is there any way to have some function (or method or
> whatever) that is able to access object member data, without the
> overhead of a lazy binding function call? Preferably ofcourse such a
> function should be eligible to be inlined.

I think the correct name is "late binding".
But you're correct. Classes are not very good for performance, and
nothing serious is done for their optimization.

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.

The approach you suggest of using a record sounds like a good idea.
This will make the problem clearer: either you really need objects,
and external functions are just there for performance; or you didn't
need them anyway, and you will be able to rewrite everything as
functions with a record parameter.
Note also that this is not as clumsy as it looks: even without records,
you can already pass (by hand) all non-mutable fields to external
functions (labelled parameters handy there?)

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)

Regards,

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

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

[Benjamin Geer]

Nicolas Cannasse wrote:
> For most of the cases, modules should be powerful enough and offer far
> better performances... and inlining.
> Even if you need some specialisation, you can always handle it using a
> closure.

Could you give an example?

Ben

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

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

[Nicolas Cannasse]

> Nicolas Cannasse wrote:
> > For most of the cases, modules should be powerful enough and offer far
> > better performances... and inlining.
> > Even if you need some specialisation, you can always handle it using a
> > closure.
>
> Could you give an example?
>
> Ben
>

For example, you have a module A with a type t which have one or more
mutable fields where you can store user given closures that will perform
some specific tasks. Theses closures can be seen has type "methods" , and if
the type is visible, you can even do some runtime subclassing.

Nicolas Cannasse

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

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

[Nuutti Kotivuori]

Nicolas Cannasse wrote:
> [...]
>> So - I am asking if I'm correct in my deductions here, or if I
>> missed some important point. Or if there's an alternative way to
>> circumvent this restriction.
>>
>> To summarize - is there any way to have some function (or method or
>> whatever) that is able to access object member data, without the
>> overhead of a lazy binding function call? Preferably ofcourse such
>> a function should be eligible to be inlined.
>>
>> Thanks in advance,
>> -- Naked
>
> There is good way : don't use objects :-) For most of the cases,
> modules should be powerful enough and offer far better
> performances... and inlining.  Even if you need some specialisation,
> you can always handle it using a closure.

Yes, obviously :-) But when I do happen to need specialisation, I add
closures as variables in a record or something - and soon I'll be
adding several of them in a single one, then getting bothered that
they take up so much space in the object, then come up with having
special closure-only records that are shared between different records
and... well, as you can see, this only leads to reimplementing the
entire object model myself :-)

-- Naked

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

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

[Nuutti Kotivuori]

Brian Hurt wrote:
> I don't think there can be.  Consider the function:
>
> let f c = c#foo 3 ;;
>
> In O'caml, this has type: < foo : int -> 'a; .. > -> 'a which
> basically means it accepts any object with a foo member function.
>
> So what happens if we define two classes, which don't relate to each
> other except each has a foo member function.  Only in one class foo
> is a virtual function, and in the second class foo is a non-virtual

Yes, I mentioned this in the mail (in the part that was snipped). It
does not work for the general case - however if we do know the exact
type, it could be done.

> A better alternative would be, I think, to spend a little time
> optimizing virtual function calls, so that they are faster.

Well sure, that will help and is a good idea in general. But it will
never allow for inlining of the function body into the calling
function, and as such will never solve the underlying problem.

-- Naked

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

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

[Brian Hurt]

On Sun, 7 Dec 2003, Nuutti Kotivuori wrote:

> This message identical to the post I made to comp.lang.ml a while back
> - but I think it will have a better audience over here, now that I
> decided to join the list.
> 
> ---
> 
> Lately I've been having a bit of a dilemma caused by a bottleneck from
> object-oriented access in Ocaml. The problem derives from the
> implementation of method calls through lazy binding.
> 
> Compiled languages which offer an object oriented system usually
> provide a way for methods to short-circuit the lazy binding (or
> virtual function table) system. In C++, non-virtual functions do this,
> in Java, declaring a method final gives the compiler a hint about
> this. In this case, the compiler can inline the method into the
> caller.

I don't think there can be.  Consider the function:

let f c = c#foo 3 ;;

In O'caml, this has type:
< foo : int -> 'a; .. > -> 'a
which basically means it accepts any object with a foo member function.

So what happens if we define two classes, which don't relate to each other 
except each has a foo member function.  Only in one class foo is a virtual 
function, and in the second class foo is a non-virtual function.  How 
would you implement f in this case?

A better alternative would be, I think, to spend a little time optimizing 
virtual function calls, so that they are faster.

I like the idea of implementing virtual function tables as hash tables.
Require that every VFT is a power of two elements in size, and you could 
implement f above in C something like:

typedef unsigned long word_t;

typedef struct {
    word_t mask;
    struct {
        word_t hashval;
        word_t (*fun)();
    } table[1];
} vft_t;

word_t f(word_t c) {
    word_t * c_p = (word_t *) c; /* C is a pointer to an object */
    vft_t * vft_p = (word_t *) (c_p[-1]); /* VFT is at offset -1 */
    static word_t foo_hash = hash_value("foo"); /* never changes */
    word_t i = foo_hash & vft_p->mask;

    while (vft_p->table[i].hashval != foo_hash) {
        i = (i + 1) & vft_p->mask;
    }
    return vft_p->table[i].fun((word_t) 3);
}

Note that the type checker gaurentees the while loop exits- better than
half the time the while loop body won't execute at all.  The most likely
cost then is two loads, one branch, and one indirect call.  Biggest cost 
is likely to be the cache misses on the loads, followed by mispredicted 
branchs.  Virtual function calls won't be as fast as normal function 
calls, but they'll be close enough to stop worrying about them.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

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

[Brian Hurt]

On Sun, 7 Dec 2003, Nuutti Kotivuori wrote:

> Well sure, that will help and is a good idea in general. But it will
> never allow for inlining of the function body into the calling
> function, and as such will never solve the underlying problem.

I actually question the value of inlining as a performance improvement, 
unless it leads to other signifigant optimizations.  Function calls simply 
aren't that expensive anymore, on today's OOO super-scalar 
speculative-execution CPUs.  A direct call, i.e. one not through a 
function pointer, I benchmarked out at about 1.5 clocks on an AMD K6-3.  
Probably less on a more advanced CPU.  Indirect calls, i.e. through a 
function pointer, are slower only due to the load to use penalty.  If the 
pointer is in L1 cache, an indirect call is probably only 3-8 clocks.

Cache misses are the big cost.  Hitting L1 cache, the cheapest memory 
access, is generally 2-4 clocks.  L2 cache is generally 6-30 clocks.  
Missing cache entirely and having to go to main memory is 100-300+ clocks.  
Inlining expands the code size, and thus means you're likely having more 
expensive cache misses.  At 300 clocks/cache miss, it doesn't take all 
that many cache misses to totally overwhealm the small advantages gained 
by inlining functions.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

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

[Nuutti Kotivuori]

Jacques Garrigue wrote:
> I think the correct name is "late binding".

Ah, right. Thanks.

> But you're correct. Classes are not very good for performance, and
> nothing serious is done for their optimization.
>
> 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?

> The approach you suggest of using a record sounds like a good idea.
> This will make the problem clearer: either you really need objects,
> and external functions are just there for performance; or you didn't
> need them anyway, and you will be able to rewrite everything as
> functions with a record parameter.  Note also that this is not as
> clumsy as it looks: even without records, you can already pass (by
> hand) all non-mutable fields to external functions (labelled
> parameters handy there?)

Yeah, that will probably just fine. Just that, in OCaml, unlike for
example CLOS (where method calls look just like ordinary function
calls), normally exposes in an interface if things are objects or not
- obviously so if you are supposed to use method calls. So either I
commit to using objects, or commit to having a simple function-based
interface, which will have to wrap the method calls, if the
implementation ever becomes based on objects.

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

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.

It's good to know that progress is being made on the object front,
especially in terms of 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 = f#m x

   then f will accept any object that has method m. If I type:

     let f (x:#a) = f#m x

   then f will accept any object that has atleast the interface of
   a. If I type:

     let f (x:a) = f#m x

   then f will accept any object that has exactly the interface of a -
   if it's anything else, then it will have to be subtyped to a
   first. But I have no way of saying that accept only class a typed
   parameters, regardless of any subtyping or identical
   interfaces. Except, as said, by making the argument type abstract
   through an interface.

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

 - 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 :-)

Anyhow, that's it for now, thanks for listening,
-- Naked

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

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

[Abdulaziz Ghuloum]

Brian Hurt wrote:

>I actually question the value of inlining as a performance improvement, 
>unless it leads to other signifigant optimizations.  Function calls simply 
>aren't that expensive anymore, on today's OOO super-scalar 
>speculative-execution CPUs.  A direct call, i.e. one not through a 
>function pointer, I benchmarked out at about 1.5 clocks on an AMD K6-3.  
>Probably less on a more advanced CPU.  Indirect calls, i.e. through a 
>function pointer, are slower only due to the load to use penalty.  If the 
>pointer is in L1 cache, an indirect call is probably only 3-8 clocks.
>
>Cache misses are the big cost.  Hitting L1 cache, the cheapest memory 
>access, is generally 2-4 clocks.  L2 cache is generally 6-30 clocks.  
>Missing cache entirely and having to go to main memory is 100-300+ clocks.  
>Inlining expands the code size, and thus means you're likely having more 
>expensive cache misses.  At 300 clocks/cache miss, it doesn't take all 
>that many cache misses to totally overwhealm the small advantages gained 
>by inlining functions.
>  
>

Hello,

Do you happen to have a pointer to a document listing the (approximate) 
timing of the various instructions on todays hardware?  You have listed 
a few and I was wondering if you have a more comprehensive study.

You say "Inlining expands the code size and thus you're likely having 
more expensive cache misses".  I wonder how true that is.  For example, 
consider a simple expression such as {if p() e0 e1}.  If the compiler 
decides to inline p (in case p is small enough, leaf node, etc ...), 
then in addition to the benefits of inlining (no need to save your live 
variable, or restore them later, constant folding, copy propagation, 
...), you're also avoiding the jump to p.  Since p can be anywhere in 
memory, a cache miss is very probable.  If p was inlined, its location 
is now close and is less likely to cause a cache miss.  Not inlining 
causes the PC to be all over the place cauing more cache misses.  Am I 
missing something?

Aziz,,,


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

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

[Jacques Garrigue]

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

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

[Nuutti Kotivuori]

Brian Hurt wrote:
> I actually question the value of inlining as a performance
> improvement, unless it leads to other signifigant optimizations.

I'm sorry but I do not wish to discuss the relative merits or unmerits
of inlining.

But I'm sure you must agree that there are indeed atleast specific
cases where inlining does help. It would be nice if the language would
be flexible enough to allow the compiler the choice to inline, in
cases where it will result in better performance.

-- Naked

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

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

[Nuutti Kotivuori]

Jacques Garrigue wrote:
> First to Brian Hurt:

[...virtual calls...]

> This is pretty optimal in terms of performance.

When I read parts of the implementation of class system in OCaml, I
must say that I was pretty taken by the implementation of late binding
calls. It is not much slower than the C++ equivalent in the simple
case, it can actually be better in heavily inherited class compared to
C++ and it implements so simply the ability to call method "foo" from
any class anywhere that implements a method by that name.

> Next, to Nuutti Kotivuori:
>
>> 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.

Right. Well, at the moment I am more interested in the possibility to
do that than if it is cost-effective to do that now.

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

Yeah - that's the way with a lot of languages that have not yet
reached quite mainstream usage. Though in this particular case, the
question is more of whether the language design allows those
optimizations to be implemented, when they are needed, or if changing
the language itself is needed then.


[...]

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

Oh, just crud I came up with when coming up with the example. I was
going for a bit more extensive one, but then trimmed it down.

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

Yeah, indeed it is - and I see no need to change that behaviour. But,
if we could somehow say that every object _has_ to be exactly of type
atom, and not just adhering to the interface of atom (like we know the
case to be in your second example there), we could inline the whole
thing.

Ofcourse this isn't so useful if it doesn't work with inheritance -
since why would we be using objects if they are all going to be the
same type anyway - and making it work with inheritance again is not
possible without breaking the model somehow.

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

Well, it's still in the same ballpark.

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

Right. I don't know enough of things to really know how hard it would
be to have classes also be a strict type and to be able to require
that - or how much new syntax it would require.

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

Well, if method calls inside the class are cheap enough, or if they
can be inlined, this won't be needed.

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

Well, nothing as such - it already works. I guess it's remnants of C++
where I'd expect to be able to use objects for this sort of thing, and
have all the calls inlined all the way.

I did some naive tests on performance, and this is what I came up
with:

,----[ class.ml ]
| class atom =
| object
|   val mutable a = 0
|   method set_a x = a <- x
|   method get_a () = a
| end
| 
| let c = new atom;;
| 
| for i = 0 to 1000000000 do
|   c#set_a 3
| done;;
| 
| print_endline ("A: " ^ (string_of_int (c#get_a ())));;
`----

,----[ classfield.ml ]
| class atom =
| object
|   val mutable a = 0
|   method set_a x = a <- x
|   method get_a () = a
| end
| 
| let c = new atom;;
| 
| let rc = Obj.repr c;;
| let r3 = Obj.repr 3;;
| 
| for i = 0 to 1000000000 do
|   Obj.set_field rc 2 r3
| done;;
| 
| print_endline ("A: " ^ (string_of_int (c#get_a ())));;
`----

,----[ classrec.ml ]
| class atom =
| object
|   val mutable a = 0
|   method set_a x = a <- x
|   method get_a () = a
| end
| 
| type nr = {
|   mutable vtable : int;
|   mutable id : int;
|   mutable a : int;
| }
| 
| let c = new atom;;
| 
| let rc = Obj.magic c;;
| 
| for i = 0 to 1000000000 do
|   rc.a <- 3
| done;;
| 
| print_endline ("A: " ^ (string_of_int (c#get_a ())));;
`----

,----[ record.ml ]
| type atom = {
|   mutable a : int
| }
| 
| let set_a (a:atom) x = a.a <- x;;
| let get_a (a:atom) = a.a;;
| 
| let c = { a = 0 };;
| 
| for i = 0 to 1000000000 do
|   set_a c 3
| done;;
| 
| print_endline ("A: " ^ (string_of_int (get_a c)));;
`----

And the timing values I got over the different implementations:

,----[ class ]
| real    0m23.322s
| user    0m22.760s
| sys     0m0.110s
`----

,----[ classfield ]
| real    0m25.685s
| user    0m25.150s
| sys     0m0.100s
`----

,----[ classrec ]
| real    0m4.433s
| user    0m4.330s
| sys     0m0.010s
`----

,----[ record ]
| real    0m5.540s
| user    0m5.510s
| sys     0m0.030s
`----

So it seems pretty clear that the two last ones were able to inline
the calls, and the two first ones weren't. So, if I can be 100%
certain the class given in is of the exact type I'm expecting it to
be, I can just magically make it a record and access the fields
directly, and get the performance improvements.

Anyhow, thanks for your time - I'm probably trying to investigate more
and learn more of OCaml before going further into this - as many of my
comments are probably just due to inexperience in OCaml.

-- Naked

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

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

[Richard Jones]

Any chance of adding an unsafe way to call a method on a class where
the name is only known at runtime? eg. To Obj or Oo?

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://freshmeat.net/users/rwmj
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
"One serious obstacle to the adoption of good programming languages is
the notion that everything has to be sacrificed for speed. In computer
languages as in life, speed kills." -- Mike Vanier

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

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

[Brian Hurt]

On Sun, 7 Dec 2003, Abdulaziz Ghuloum wrote:

> Brian Hurt wrote:
> 
> >I actually question the value of inlining as a performance improvement, 
> >unless it leads to other signifigant optimizations.  Function calls simply 
> >aren't that expensive anymore, on today's OOO super-scalar 
> >speculative-execution CPUs.  A direct call, i.e. one not through a 
> >function pointer, I benchmarked out at about 1.5 clocks on an AMD K6-3.  
> >Probably less on a more advanced CPU.  Indirect calls, i.e. through a 
> >function pointer, are slower only due to the load to use penalty.  If the 
> >pointer is in L1 cache, an indirect call is probably only 3-8 clocks.
> >
> >Cache misses are the big cost.  Hitting L1 cache, the cheapest memory 
> >access, is generally 2-4 clocks.  L2 cache is generally 6-30 clocks.  
> >Missing cache entirely and having to go to main memory is 100-300+ clocks.  
> >Inlining expands the code size, and thus means you're likely having more 
> >expensive cache misses.  At 300 clocks/cache miss, it doesn't take all 
> >that many cache misses to totally overwhealm the small advantages gained 
> >by inlining functions.
> >  
> >
> 
> Hello,
> 
> Do you happen to have a pointer to a document listing the (approximate) 
> timing of the various instructions on todays hardware?  You have listed 
> a few and I was wondering if you have a more comprehensive study.

Not really, because the biggest cost (accessing main memory) is too 
dependent upon specific system costs.  For example, switching from DDR233 
to DDR333 will greatly reduce the latency costs of accessing main memory.  
Which Northbridge chipset you're using can also change things.  Also, the 
pattern to the memory accesses can change things- for example, of the P4, 
accessing memory in a linear fasion that the CPU can predict allows the 
CPU to preload cache lines, lowering the cost of a cache miss to ~100 
clocks.  But if you're accessing things randomly, or in a way the CPU 
can't predict, a cache miss is ~300 clocks.  Also, since I'm measuring 
everything in clocks, changing the clock rate of your CPU changes the 
measurement.

Where I get this information is a couple of years of reading Ace's 
Hardware (http://www.aceshardware.com/).  Google the site for "memory 
latency".

> 
> You say "Inlining expands the code size and thus you're likely having 
> more expensive cache misses".  I wonder how true that is.  For example, 
> consider a simple expression such as {if p() e0 e1}.  If the compiler 
> decides to inline p (in case p is small enough, leaf node, etc ...), 
> then in addition to the benefits of inlining (no need to save your live 
> variable, or restore them later, constant folding, copy propagation, 
> ...), you're also avoiding the jump to p.  Since p can be anywhere in 
> memory, a cache miss is very probable.  If p was inlined, its location 
> is now close and is less likely to cause a cache miss.  Not inlining 
> causes the PC to be all over the place cauing more cache misses.  Am I 
> missing something?

Yes:

A) The function p being small enough to not cause code size increases by 
inlining it is very small.  p needs to be really trivial.  On the x86 
(32-bit) a direct call is 5 bytes worth of instruction.  p() needs to be 
at more 2-3 small instructions after inlining to fit.  Going through a 
virtual function table increases the size of the call, but not by huge 
amounts.  The only place where you are likely to win on a regular basis is 
accessor functions.  IIRC, Ocaml allows you to have member variables be 
public.  If accessor functions are a problem, consider using public 
variables.

B) Most of the time your code is executing in a loop.  So the first time 
through the loop you load all your code into cache and then execute from 
cache from there on out.  The only problem is when the total size of the 
code is larger than cache.  Not inlining code makes the total code size of 
the loop smaller (generally)- but even if the non-inlined version of the 
code still doesn't fit into cache, it's often better performance.  Imagine 
a whole bunch of straight line code that doesn't fit into cache, but calls 
p() multiple times.  If there is only a single (non-inlined) copy of p(), 
then p() is likely to remain in cache because it keeps being used.  If 
there are instead multiple different copies of p(), executing on copy of 
p() is likely to push another copy of p() out of cache.

C) More programming sins are committed in the name of performance than any 
other reason, including stupidity.  Get the code working first, then 
benchmark, then profile.  That will tell you where your performance 
problems are.  Then go back and improve your algorithms.  We are down to 
worrying about clock cycles here (even hundreds of clock cycles)- the 
point at which you start wondering if the code should be written in C or 
assembler.  I love Ocaml not because it's efficient on the clock cycle 
level, but because it makes it easier for me to see and work with the high 
level stuff- algorithms and design issues.  Which is where the big savings 
are to be found.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

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

[Brian Hurt]

On Mon, 8 Dec 2003, Jacques Garrigue wrote:

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

There's less there than meets the eye.  It's basically a single-level hash 
table.  The compiler can compute the hash of the function call at compile 
time.  Every object has a vtable pointer stored in it.  The vtable is the
size of the vtable, plus the hashtable, an array of tuples of hash values 
plus function pointers.  Note that I require all function tables to be a 
power of two, so that I store the size - 1, and the modulo becomes an and.
An object having "extra" functions is no problem- the extra functions are 
just ignored.  A lot of error conditions are avoided by the type checker, 
and so simply not checked for.  Actually, instead of storing the hash 
value, the name as a string should be stored- this deals with the case of 
two member functions which hash to the same value.

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

How much slower is a member function call compared to a non-member 
function call?  I was given the impression that it was signifigantly 
slower, but you're making it sound like it isn't.

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

That's about the only place inlining matters.

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

I'm writting a place and route program in Ocaml, and hitting a lot of 
places where I'd like to express things as objects.  The code isn't very 
sensitive to the cost of member function calls, but it is mildly 
sensitive.  If member function calls aren't much more expensive (and 4 
loads qualifies as not much more expensive), then I'm going to be using a 
lot more objects.

But it sounds like this is already the case.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

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

[brogoff]

On Mon, 8 Dec 2003, Brian Hurt wrote:
> I'm writting a place and route program in Ocaml, and hitting a lot of
> places where I'd like to express things as objects.

Now there's an interesting discussion! Where in your design do you
want objects, if you don't mind my asking? What design style (custom,
standard cell,  FPGA, ...) is your P&R program intended to address?

My admittedly narrow minded bias based EDA tasks is that I'd rather have
a more powerful system of records than what OCaml currently has, instead
of classes, and that when I do write code with classes, it's not really using
late-binding/open-recursion.

If you're into EDA though, there are quite a few APIs based on C++ and now
Java and Python (I'm thinking of OpenAccess here) which may pressure anyone
writing OCaml bindings into a "me tOO" design.

-- Brian


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

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

[Nuutti Kotivuori]

Brian Hurt wrote:
> The only place where you are likely to win on a regular basis is
> accessor functions.  IIRC, Ocaml allows you to have member variables
> be public.  If accessor functions are a problem, consider using
> public variables.

I do not believe OCaml allows for member variable access outside the
class.

-- Naked

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

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

[Xavier Leroy]

> How much slower is a member function call compared to a non-member 
> function call?  I was given the impression that it was signifigantly 
> slower, but you're making it sound like it isn't.

In the non-member case, it depends very much whether the function
being called is statically known or is computed at run-time.  In the
first case, a call to a static address is generated.  In the latter
case, a call to a function pointer is generated.

Here are some figures I collected circa 1998 on a PowerPC 603 processor:

   type of call              cost of call

inlined function               0 cycles
call to known function         4 cycles
call to unknown function      11 cycles
method invocation             18 cycles

I'm pretty sure that more modern processors have a bigger gap between
the "call to known function" and "call to unknown function" cases.

So, as you can see, method invocation isn't much more expensive than a
call to an unknown function, but is significantly more expensive than
a call to a known function.  

In source-level terms, replacing an object by a record of functions
isn't going to make a major performance difference (the applications
of the functions fetched from the record fall in the "call to unknown
function" case), while getting rid of dynamic dispatch entirely and
just call known functions is a much bigger improvement.

Hope this clarifies the issue.

- Xavier Leroy

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

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

[skaller]

On Mon, 2003-12-08 at 06:30, Brian Hurt wrote:
> On Sun, 7 Dec 2003, Nuutti Kotivuori wrote:

> I actually question the value of inlining as a performance improvement, 
> unless it leads to other signifigant optimizations. 

Hmm. A block of n instructions containing a call to a block
of m instructions is typically n + 1 + m + 1 instructions:
at least a call and return are saved, even with no parameters.

I guess your analysis might be right if a function is
called more than once .. but for a single call,
inlining surely must be better.

In C++ there is no doubt that inlining is not just
an optimisation but a mandatory feature: several
classes of code, including wrappers 
(eg smart pointers) and of course constructors,
require inlining or the coding style is useless.

Of course, this is at a higher level than machine
code subroutine inlining .. a lot more than
just 2 instructions are saved (for example,
default constructors are often NOPs ..)


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

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

[Brian Hurt]

On Mon, 8 Dec 2003 brogoff@speakeasy.net wrote:

> On Mon, 8 Dec 2003, Brian Hurt wrote:
> > I'm writting a place and route program in Ocaml, and hitting a lot of
> > places where I'd like to express things as objects.
> 
> Now there's an interesting discussion! Where in your design do you
> want objects, if you don't mind my asking? What design style (custom,
> standard cell,  FPGA, ...) is your P&R program intended to address?

Initially targeting Virtex II FPGAs, but I'm keeping an eye open for 
supporting other FPGAs, CPLDs, and possibly even standard or custom cell 
placement.  The core algorithm is a genetic algorithm.  At the level of 
the genetic algorithm genomes are a class, as I don't care much how the 
genome is structured.  At this level, performance of member function calls 
is almost irrelevent.  But within a given genome, I have places where 
using objects would be helpfull.

A genome is three things: a set of cells to place, a mapping of how those 
cells are placed into the FPGA, and a cost function.  The cost function is 
at heart a set of "constraints" (I don't like that word, but can think of 
a better one).  The obvious constraint is that several cells are on a 
shared net.  The cost function is then determined by the size of bounding 
box.  Other constraints would be that cell uses a TSB (only two per CLB), 
etc.  There is an obvious object interface at the constraint level.

The mappings are also an opportunity to have a class interface.  I might 
want to have multiple levels of mappings- one mapping handling IOBs, 
another CLBs, another multipliers, etc.  This way I only map IOBs to IOBs, 
and don't have to worry about what happens if I try to put an IOB in a 
CLB.  The top level mapping is then the sum of the sub-mappings.

Maybe I'm not seeing how to do this with not-objects.  

> 
> My admittedly narrow minded bias based EDA tasks is that I'd rather have
> a more powerful system of records than what OCaml currently has, instead
> of classes, and that when I do write code with classes, it's not really using
> late-binding/open-recursion.

What I want to do is to be able to hand some code a hunk of state and 
several functions to act on that state.  The number of functions is large 
enough, and the functions are complex enough, that shared context is 
clumsy.  And I can't think of a way to pass in a reference to a module.

> 
> If you're into EDA though, there are quite a few APIs based on C++ and now
> Java and Python (I'm thinking of OpenAccess here) which may pressure anyone
> writing OCaml bindings into a "me tOO" design.
> 

I'm not working at that level yet.  If worse comes to worse, I'll write a 
small interface program in Java or whatever to deal with the translation.  
Have the Ocaml spit out into a pipe some internal format of the solution, 
and the Java program just parses the solution and passes it along to the 
API.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

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

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

[Nuutti Kotivuori]

Brian Hurt wrote:
> - Despite my best efforts, ocaml inlined (and removed) the call to
> foo.  In general this is good, but it did defeat my efforts to time
> how long a direct function call took.  For some reason it didn't
> also eliminate the for loops.  If I had to guess, Ocaml's call to a
> known function is about the same speed as C's.

I am not certain what it does, but did you try 'ocamlopt -inline -1 ...'?

For me, that seemed to prevent some inlining atleast.

-- Naked

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

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

[Brian Hurt]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 4711 bytes --]

On Mon, 8 Dec 2003, Xavier Leroy wrote:

> > How much slower is a member function call compared to a non-member 
> > function call?  I was given the impression that it was signifigantly 
> > slower, but you're making it sound like it isn't.
> 
> In the non-member case, it depends very much whether the function
> being called is statically known or is computed at run-time.  In the
> first case, a call to a static address is generated.  In the latter
> case, a call to a function pointer is generated.
> 
> Here are some figures I collected circa 1998 on a PowerPC 603 processor:
> 
>    type of call              cost of call
> 
> inlined function               0 cycles
> call to known function         4 cycles
> call to unknown function      11 cycles
> method invocation             18 cycles

Attached is some microbenchmarking code I just whomped together.  It gives 
both C and Ocaml timings on tight loops of functions calls.  The results:

$ ./fcall2
time0: 1000000000 loops in 1.680000 seconds = 1.680000 nanoseconds/loop
time1: 1000000000 loops in 1.680000 seconds = 1.680000 nanoseconds/loop
time2: 1000000000 loops in 5.700000 seconds = 5.700000 nanoseconds/loop
time3: 1000000000 loops in 10.110000 seconds = 10.110000 nanoseconds/loop
$ ./fcall
time0(): 1000000000 loops in 2.570000 seconds = 2.570000 nanoseconds/loops
time1(): 1000000000 loops in 5.170000 seconds = 5.170000 nanoseconds/loops
time2(): 1000000000 loops in 5.860000 seconds = 5.860000 nanoseconds/loops
$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man 
--infodir=/usr/share/info --enable-shared --enable-threads=posix 
--disable-checking --with-system-zlib --enable-__cxa_atexit 
--host=i386-redhat-linux
Thread model: posix
gcc version 3.2.2 20030222 (Red Hat Linux 3.2.2-5)
$ ocamlopt -v
The Objective Caml native-code compiler, version 3.07
Standard library directory: /usr/local/lib/ocaml
$ cat /proc/cpuinfo
processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 6
model           : 8
model name      : AMD Athlon(tm) XP 2200+
stepping        : 1
cpu MHz         : 1800.109
cache size      : 256 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca 
cmov
pat pse36 mmx fxsr sse syscall mmxext 3dnowext 3dnow
bogomips        : 3591.37
$

My conclusions:

- Despite my best efforts, ocaml inlined (and removed) the call to foo.  
In general this is good, but it did defeat my efforts to time how long a 
direct function call took.  For some reason it didn't also eliminate the 
for loops.  If I had to guess, Ocaml's call to a known function is about 
the same speed as C's.

- Ocaml loops faster than C.  Go figure.

- Ocaml's call to an unknown function (passed in via argument) is a little 
slower than C's call via function pointer, by maybe 2 clocks.  Not 
signifigant.

- Ocaml's call to a member function is slower than a call to an unknown 
function by a factor of about 2.

- All of these times are small enough to be insignifigant.  By comparison, 
on this CPU a mispredicted branch costs about 8ns (~14 clocks).  Outside 
of a microbenchmark, they are unlikely to be noticable, as other factors 
are likely to overwhealm the minor costs shown here (garbage collection, 
cache performance, etc.).

- 4 loads at 2 clocks apeice (they hit cache) is about 4.4ns- the vast
majority of the difference between a call to an unknown function and a 
call to a member function.  As such, signifigant improvements are highly 
unlikely.  Even my design for a hash table uses three loads, and would 
only be 1.1ns or so faster (at best).

- Ocaml is surprisingly fast.

- This thread devolved into pendancy several posts ago :-).

> 
> I'm pretty sure that more modern processors have a bigger gap between
> the "call to known function" and "call to unknown function" cases.

Actually, no.  The 603 did a little bit of speculation, but not much.  
Modern CPUs speculate aggressively.  The biggest problem with call via 
pointer is the load to use penalty- in a direct call, the address it's 
jumping to is right there.  With a call through a pointer, it's got to 
load the pointer before it knows where to jump.  But even then, some CPUs 
do data speculation.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

[-- Attachment #2: Type: APPLICATION/x-gzip, Size: 1002 bytes --]

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

[malc]

On Mon, 8 Dec 2003, Brian Hurt wrote:

> Attached is some microbenchmarking code I just whomped together.  It gives
> both C and Ocaml timings on tight loops of functions calls.  The results:
>
> My conclusions:
>
> - Despite my best efforts, ocaml inlined (and removed) the call to foo.
> In general this is good, but it did defeat my efforts to time how long a
> direct function call took.  For some reason it didn't also eliminate the
> for loops.  If I had to guess, Ocaml's call to a known function is about
> the same speed as C's.

Make foo recursive (as in 'let rec foo' vs 'let foo'), OCaml will not
inline it.

-- 
mailto:malc@pulsesoft.com

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

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

[Nicolas Cannasse]

> Any chance of adding an unsafe way to call a method on a class where
> the name is only known at runtime? eg. To Obj or Oo?
>
> Rich.

Obj is unsafe, just try something like :

Obj.set_field (Obj.repr (Some 0)) 1000000 (Obj.repr ())

But I'm quite surprise that's it's not inlined and slower than setting a
record field (according to the bench results)... and even slower than
calling method (???)

Nicolas Cannasse

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

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

[Nuutti Kotivuori]

Nicolas Cannasse wrote:
> Obj.set_field (Obj.repr (Some 0)) 1000000 (Obj.repr ())
>
> But I'm quite surprise that's it's not inlined and slower than
> setting a record field (according to the bench results)... and even
> slower than calling method (???)

The implementation of Obj.set_field is:

  external set_field : t -> int -> t -> unit = "%obj_set_field"

Where %obj_set_field is merely:

  Parraysetu Pgenarray;

from the primitives_table, which is pretty generic.

I am not sure why it isn't inlined either. It doesn't get inlined even
when having the declaration in the same source file.

-- Naked

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

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

[Olivier Andrieu]

 Nuutti Kotivuori [Tuesday 9 December 2003] :
 >
 > Nicolas Cannasse wrote:
 > > Obj.set_field (Obj.repr (Some 0)) 1000000 (Obj.repr ())
 > >
 > > But I'm quite surprise that's it's not inlined and slower than
 > > setting a record field (according to the bench results)... and even
 > > slower than calling method (???)
 > 
 > The implementation of Obj.set_field is:
 > 
 >   external set_field : t -> int -> t -> unit = "%obj_set_field"
 > 
 > Where %obj_set_field is merely:
 > 
 >   Parraysetu Pgenarray;
 > 
 > from the primitives_table, which is pretty generic.
 > 
 > I am not sure why it isn't inlined either. It doesn't get inlined even
 > when having the declaration in the same source file.

What are you talking about ? 
The Obj module and in particular Obj.set_field is about modifying caml
values (records, variants, tuples, whatever), not caml objects.

Access to instance variable in objects is not inlined because you
can't statically known in which slot is the variable. Ex:

  class foo = object val x = 0 end
  class bar = object val y = 1 inherit foo end

In an object foo, x is in slot 0, but in an object bar, x is in slot
1. (Actually that's not 0 and 1 but 2 and 3 because the object stores
other stuff in the first two slots).

-- 
   Olivier

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

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

[Nuutti Kotivuori]

Olivier Andrieu wrote:
> What are you talking about ? The Obj module and in particular
> Obj.set_field is about modifying caml values (records, variants,
> tuples, whatever), not caml objects.

Yes, this is understood.

> Access to instance variable in objects is not inlined because you
> can't statically known in which slot is the variable. Ex:
>
> class foo = object val x = 0 end
> class bar = object val y = 1 inherit foo end
>
> In an object foo, x is in slot 0, but in an object bar, x is in slot
> 1. (Actually that's not 0 and 1 but 2 and 3 because the object
> stores other stuff in the first two slots).

Yes, quite so. But if we _do_ know the exact implementation of the
object, and we know in which order the variables in the object are, we
can *abuse* Obj.set_field to manipulate those values directly. So
that's about as close to the definition of unsafe as you can get.

As for your example about inheriting - there would have to be quite
some trickery to be done to be able to this working with
inheritance. In C++, with equivalent declarations, a typecast from bar
pointer to a foo pointer actually returns a different pointer value -
one that is at the start of class foo inside bar. This obviously
wouldn't work in OCaml, because of the block headers and all that.

-- Naked

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