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

[Brian Hurt <bhurt@spnz.org>]

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