From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <maranget@yquem.inria.fr>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: by yquem.inria.fr (Postfix, from userid 18041)
	id 88978BB81; Mon, 28 Nov 2005 11:26:32 +0100 (CET)
Date: Mon, 28 Nov 2005 11:26:32 +0100
To: Jon Harrop <jon@ffconsultancy.com>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Efficency of varient types
Message-ID: <20051128102632.GA28969@yquem.inria.fr>
References: <c62c8d860511251553k782c574cg37fa1116d6fc3064@mail.gmail.com> <53c655920511272324w1630fe89y@mail.gmail.com> <20051128.164900.41199864.garrigue@math.nagoya-u.ac.jp> <200511281001.32158.jon@ffconsultancy.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <200511281001.32158.jon@ffconsultancy.com>
User-Agent: Mutt/1.5.9i
From: maranget@yquem.inria.fr (Luc Maranget)
X-Spam: no; 0.00; caml-list:01 maranget:01 maranget:01 variants:01 integers:01 variants:01 constructors:01 integers:01 translated:01 rec:01 fib:01 fib:01 rec:01 fob:98 wrote:01 
X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=-2.8 required=5.0 tests=ALL_TRUSTED 
	autolearn=disabled version=3.0.3

> On Monday 28 November 2005 07:49, Jacques Garrigue wrote:
> > More importantly, polymorphic variants are internally encoded as
> > integers, so there is no representation cost for constant tags.
> 
> Is pattern matching over constant ordinary variants not more efficient than 
> pattern matching over constant polymorphic variants when compiled to native 
> code?
> 
> -- 

As far as I understandteh question, constant constructors both in
ordinary variants and polymorphic variants are encoded as integers.

Hence matching over those are basically the same. However there is
one (small) difference.

Ordinary variants are translated into consecutive integers, starting
from zero, while polymorphic variant are more arbitrary integers.
As a result the final code uses some tricks more often in the first
case.

While obvious in particular cases, the resulting efficiency gain is,
well, difficult to assess in general.

Consider for instance :

let rec fib x = match x with
| 0|1 -> 1
| n -> fib (n-1) + fib (n-2)
  Compiled code for matching will consist in one (unsigned) test.

and

let rec fob x = match x with
| `ZeroIMean|`OneISay -> 1
| n -> ...
  Compiled code for matching will consist in two (equality) tests.

Your mileage may vary, of course.


-- Luc