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 CAA14557; Mon, 8 Dec 2003 02:06:47 +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 CAA15197 for ; Mon, 8 Dec 2003 02:06:46 +0100 (MET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hB816gr09036 for ; Mon, 8 Dec 2003 02:06:43 +0100 (MET) Received: from localhost (suiren.kurims.kyoto-u.ac.jp [130.54.16.25]) by kurims.kurims.kyoto-u.ac.jp (8.9.3p2-20030924/3.7W) with ESMTP id KAA12528; Mon, 8 Dec 2003 10:06:31 +0900 (JST) To: bhurt@spnz.org, naked+caml@naked.iki.fi Cc: caml-list@inria.fr Subject: Re: [Caml-list] Object-oriented access bottleneck In-Reply-To: <87brqkcsxf.fsf@iki.fi> References: <871xrhe4hb.fsf@iki.fi> <20031207192702D.garrigue@kurims.kyoto-u.ac.jp> <87brqkcsxf.fsf@iki.fi> X-Mailer: Mew version 1.94.2 on Emacs 21.2 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <20031208100725E.garrigue@kurims.kyoto-u.ac.jp> Date: Mon, 08 Dec 2003 10:07:25 +0900 From: Jacques Garrigue X-Dispatcher: imput version 20000228(IM140) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 bottleneck:01 jacques:01 hashing:01 hashing:01 sparse:01 vtable:01 indirection:01 inlining:01 inlining:01 retrieval:99 model:01 statically:01 hides:01 slower:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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