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

[Brian Hurt <bhurt@spnz.org>]

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