From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p9O9xO3p002563 for ; Mon, 24 Oct 2011 11:59:25 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AokBAMY2pU5KfVK2kGdsb2JhbABDqQkIIgEBAQEJCQ0HFAQhgW4BAQEBAxICLAEbEAgCAwEDDAYFCw0uIQEBEQEFARwGEyKeYQqLT4JghEg9iG4CBQqINgSUCYozgnw9g3E X-IronPort-AV: E=Sophos;i="4.69,397,1315173600"; d="scan'208";a="114196293" Received: from mail-wy0-f182.google.com ([74.125.82.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 24 Oct 2011 11:59:09 +0200 Received: by wyi40 with SMTP id 40so10557553wyi.27 for ; Mon, 24 Oct 2011 02:59:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=FFR2KwYI8H1Nb3jnLIwP6kVQj79cbCBLlw4yS4KCWTQ=; b=jeG6iqSmb5/ZeGvLiiEzaQRbBFHcDEccvjM+hXEL1hUgLc87fKQG2pdEXLJOJUSkh5 k5+AVciET+O0AVDnRb3wmTDjLwn7AcOCGG3lwOttgWslFyjm9gOtI5aLOaSk4St8rLuG f8rpyHi5qZOjse5vDVjT+tRRQT8qQ5z9r+0ck= Received: by 10.227.36.229 with SMTP id u37mr3485083wbd.21.1319450349107; Mon, 24 Oct 2011 02:59:09 -0700 (PDT) MIME-Version: 1.0 Received: by 10.227.175.12 with HTTP; Mon, 24 Oct 2011 02:58:49 -0700 (PDT) In-Reply-To: References: From: Gabriel Scherer Date: Mon, 24 Oct 2011 11:58:49 +0200 Message-ID: To: Diego Olivier Fernandez Pons Cc: caml-list Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p9O9xO3p002563 Subject: Re: [Caml-list] How to write an efficient interpreter Even staying at the "interpreter" stage, you can probably improve your performance seriously by being careful about your implementation : use efficient data structure (what is your implementation of variable lookup?), avoid unnecessary allocation, use tail-recursive functions where possible, etc. Try to find a time-consuming script example that exercise the type of computations you'll usually perform, and profile your interpreter with gprof (compiled natively), try to optimize the parts that show high in the profile, rinse and repeat. The natural next step is to use a bytecode instead of interpreting an AST directly. You can probably find something relatively simple and yet have a net efficiency gain over direct interpretation, because the bytecode structure is more linear and can be interpreted more efficiently; in a way, you compiled away the tree traversal. At this level, you become quite sensible to micro-optimisation : bytecode interpreters written in C have access to efficiency tricks (direct threaded code and the like, or even pinning registers directly) that are difficult or impossible to emulate in OCaml, even if you can get something reasonable with mutually tail-recursive functions. As a single point of measure, I spent a few hours hacking an OCaml bytecode interpreter for a very small subset of Caml recently, and got within 5x-10x slower than the OCaml bytecode interpreter itself for favorable cases. It's not very good, or not very bad, depending on what you expect (but definitely slower than the ocaml native compiler, or even the various JIT projects). Of course, if possible, you could also target an existing bytecode or intermediate representation, or even compile to an existing language with a rich enough runtime. If you're familiar, for example, with either JVM or LLVM, those are the popular choices these days. I don't know how that would mix with inline Javascript, though (I suppose both environments have a javascript interpreter). You could also compile to OCaml code or Javascript directly, and reuse their implementation, GC, etc. With the current Javascript engines, you can get very good performances if you compile in a way that resemble the ugly Javascript code they're trying to optimize. For example, js_of_ocaml compiles OCaml bytecode into Javascript and the result performs better than using OCaml bytecode interpreter (written in C and well designed for efficiency) directly. That's already quite a lot more work, however, than a good interpreter or a simple home-made bytecode. On Mon, Oct 24, 2011 at 11:10 AM, Diego Olivier Fernandez Pons wrote: >     Caml-list, > I have to write an interpreter for a datatype rich purely applicative > language. I have already written a naive interpreter (like in programming > languages class) and was wondering what where the options for writing > something that would perform better while keeping it maintainable by a > single person < 5% dedicated and preferably only in core-ML (no C code or > fancy ML extensions). > The language could be described as a rich datastructure typed SQL with a > programming language syntax > - first class sets, arrays, dictionaries, lists and their corresponding > comprehensions > - tuples and records merged into a single concept (accessible per position > like in (x, y) = ... or per label like in for t in tupleSet if t.label == 3 > then) > - only applicative functions (no lambda operator, no partial application) > - simple types are int, double and string > - only user declared types are tuples-records > It is mainly used for data transformation : take a list of countries, > extract from an database the international airports of those countries, > geolocalize them using city/location table, generate a distance table using > a great-circle distance, assign to each size of plane the legs they can do > based on their maximum fight range, etc. > The language has a JavaScript inline capability >     execute JavaScript { >         //write your javascript code here >     } > that's typically used to define functions, unroll comprehensions to make > them more efficient and to call external libraries (JavaScript has full > visibility on all the language objects and can read/write directly inside, > probably the existing interpreter was written in JavaScript), so I am > considering allowing those features in the core language and only supporting > a very slow JavaScript deprecated compatibility mode. > >          Diego Olivier