From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA13281 for caml-redistribution; Thu, 2 Sep 1999 20:45:45 +0200 (MET DST) 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 BAA26500 for ; Thu, 2 Sep 1999 01:13:04 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id BAA16089; Thu, 2 Sep 1999 01:09:39 +0200 (MET DST) Received: (from vouillon@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id BAA25278; Thu, 2 Sep 1999 01:09:39 +0200 (MET DST) Message-ID: <19990902010939.12962@pauillac.inria.fr> Date: Thu, 2 Sep 1999 01:09:39 +0200 From: Jerome Vouillon To: chet@watson.ibm.com, Jerome Vouillon Cc: caml-list@inria.fr, blo.b@infonie.fr Subject: Re: Efficency in OCaml References: <7qj9lv$aa9$1@goldenapple.srv.cs.cmu.edu> <199909011840.OAA01846@bismarck.chet.org> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 0.89.1 In-Reply-To: <199909011840.OAA01846@bismarck.chet.org>; from chet@watson.ibm.com on Wed, Sep 01, 1999 at 02:40:21PM -0400 Sender: weis On Wed, Sep 01, 1999 at 02:40:21PM -0400, chet@watson.ibm.com wrote: > Is there a description of the Ocaml object and > "virtual-function-table" format? I have not written any description but I can explain it rapidly here. Objective Caml uses a scheme which is also used in the Gnu Objective C compiler. Each object holds a table containing its methods (the table is shared among all objets of a same class). A unique integer is assigned at run-time to each method name of a program. This integer is used as an index in this table to find the method. As the table is rather sparse, it is implemented as a two-level array (an array of arrays of functions). So, a method call "object#m e1 ... en" is compile in something that looks like "object.(0).(idx mod N).(idx / N) objet e1 ... en" where idx is the integer associated to the method name "m". This scheme is very flexible and rather efficient. It would be hard to improve it actually. Indeed, one will always need one indirection to know what class the object belongs to and another indirection to retrieve the method. So one could only gain one indirection (the arithmetics is more or less free, as it can be done in parallel). Actually, there is yet another indirection, not shown here, to retrieve a pointer to the code from the method closure. This indirection could probably be optimize a bit (by doing it in parallel with the retrieval of the closure). A great part of the cost of a method call also comes from the fact that calling an unknown function is more expansive than calling a know function : there is a check to see if the function is called with less arguments than it needs, more arguments or exactly the right number of arguments. The only way to optimize this would be to make a global analyze of the program during the compilation. This analyze would determine whether at a given method invocation location "x#m" all methods that could possibly be called are called with the right number of arguments, and would also check whether the method invocation could be replaced by a function call (that is, whether only one method can be called from this location). In order to provide more opportunities for optimization, one would also probably need to do some partial evaluation. Implementing all this would require a lot of work... > Also, well, I think there's been some recent work on analyzing the > path-length of O-O code, and the conclusion has been that in fact, > methods do just "call one other" a lot. > > That is, while C code is characterized by lots of tests and longer > path-lengths per function-body, C++ (and Java, *especially* -- geez, > it seems like Java code is all method-calls!) code tends to be short > code-bodies, with branches implemented effectively by calling virtual > functions. OCaml is first a functional langage so I think (I hope) that people do not use objects as heavily as in Java, and for instance use pattern matching rather than only method calls for implementing branches. -- Jérôme