From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA21628; Mon, 8 Dec 2003 17:51:11 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA22632 for ; Mon, 8 Dec 2003 17:51:10 +0100 (MET) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hB8Gp9r08963 for ; Mon, 8 Dec 2003 17:51:09 +0100 (MET) Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id hB8GoqC22498; Mon, 8 Dec 2003 10:50:53 -0600 (CST) Date: Mon, 8 Dec 2003 11:51:35 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Jacques Garrigue , Ocaml Mailing List Subject: Re: [Caml-list] Object-oriented access bottleneck In-Reply-To: <20031208100725E.garrigue@kurims.kyoto-u.ac.jp> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 bottleneck:01 jacques:01 hashing:01 meets:99 hash:01 hash:01 vtable:01 vtable:01 hashtable:01 pointers:01 avoided:01 checker:01 hashing:01 sparse:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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