From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 8DC15BC69 for ; Wed, 15 Aug 2007 15:13:01 +0200 (CEST) Received: from pih-relay06.plus.net (pih-relay06.plus.net [212.159.14.133]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l7FDCwcm004079 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Wed, 15 Aug 2007 15:13:01 +0200 Received: from [80.229.56.224] (helo=beast.local) by pih-relay06.plus.net with esmtp (Exim) id 1ILIgC-0007zk-RJ for caml-list@yquem.inria.fr; Wed, 15 Aug 2007 14:12:57 +0100 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] High-performance bytecode interpreter in OCaml Date: Wed, 15 Aug 2007 14:01:40 +0100 User-Agent: KMail/1.9.7 References: <2B9157A5-ECA0-46EE-B628-840689224ACC@gmail.com> In-Reply-To: <2B9157A5-ECA0-46EE-B628-840689224ACC@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200708151401.41091.jon@ffconsultancy.com> X-Miltered: at concorde with ID 46C2FBDA.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; bytecode:01 ocaml:01 ocaml:01 bytecode:01 compilation:01 arrays:01 locality:01 inlined:01 inlined:01 inlining:01 crank:98 frog:98 imho:01 wrote:01 ideally:01 On Wednesday 15 August 2007 12:49:31 Joel Reymont wrote: > Folks, > > I would like to write a high-performance VM in OCaml. I understand > that OCaml itself uses either a threaded interpreter or a switch- > style one. The performance of interpreters is heavily dependent upon what exactly you're evaluating (both language and program properties). If you start with a naive term-level interpreter or rewriter then you can get an order of magnitude in performance by optimizing the interpreter without leaving OCaml or moving to (real) bytecode compilation. > What's the most efficient way to write a bytecode interpreter in > OCaml itself, though? I would start with a simple term-level interpreter, optimize that by avoiding lookups as much as possible. Then maybe switch to arrays of instructions. Finally, maybe something that generated OCaml bytecode and dynamically loaded it. However, you get diminishing returns and the latter is difficult and might well be no faster. The main advantage of a real bytecode is locality: the instructions and data are stored together in a contiguous array. This is ideally suited to a simple C interpreter. A bytecode in OCaml would be a string and, IMHO, OCaml is not very efficient at string munging. > Would CPS style be inlined if I were to write a threaded interpreter > this way? Quite a bit can be usefully inlined if you crank up the command line argument and write in a certain style. However, this is of limited use in interpreters of general purpose languages as their evaluation requires loops and so forth. Also, increasing global inlining often degrades the performance of symbolic code. Depending upon your requirements, my recommendations are probably: 1. Optimize your term-level interpreter first and then consider compiling to a lower-level instruction array. 2. Don't bother compiling to OCaml bytecode. 3. Consider compiling to native code or doing something more sophisticated with your interpreter, like gathering statistics on the most common sequences of instructions and making the interpreter optimize itself. If you send me the source I'll have a look over it and tell you any obvious optimizations I can think of. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e