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 SAA02046 for caml-red; Thu, 11 Jan 2001 18:30:51 +0100 (MET)
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 LAA00649 for <caml-list@pauillac.inria.fr>; Thu, 11 Jan 2001 11:40:08 +0100 (MET)
Received: from nef.ens.fr (nef.ens.fr [129.199.96.32])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f0BAe7j15297
	for <caml-list@inria.fr>; Thu, 11 Jan 2001 11:40:07 +0100 (MET)
Received: from clipper.ens.fr (clipper-gw.ens.fr [129.199.1.22])
          by nef.ens.fr (8.10.1/1.01.28121999) with ESMTP id f0BAe6M64482
          ; Thu, 11 Jan 2001 11:40:06 +0100 (CET)
Received: from localhost (frisch@localhost) by clipper.ens.fr (8.9.2/jb-1.1)
	id LAA03104 ; Thu, 11 Jan 2001 11:40:06 +0100 (MET)
Date: Thu, 11 Jan 2001 11:40:05 +0100 (MET)
From: Alain Frisch <frisch@clipper.ens.fr>
To: Sven LUTHER <luther@dpt-info.u-strasbg.fr>
cc: caml-list@inria.fr
Subject: Re: Cost of polymorphic variants over normal ones.
In-Reply-To: <20010111101703.A3683@lambda.u-strasbg.fr>
Message-ID: <Pine.GSO.4.04.10101111120260.18041-100000@clipper.ens.fr>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: weis@pauillac.inria.fr

On Thu, 11 Jan 2001, Sven LUTHER wrote:

> A (somewhat) related question would be, what is the cost of polymorphic
> variants compared to noarmal ones ?
> 
> The normal variants are coded as integers, and using them is fast, while
> polymorphic variants use some kind of hash functionn, but very simple.

AFAIK, the hashing is done only during the compilation (or explicitly
by external C functions). For instance (output of ocaml -dinstr):
# function `ABC -> 10 | `DEF -> 20;;
        closure L1, 0
        return 1
L1:     const 3247170
        push
        acc 1
        eqint
        branchifnot L2
        const 10
        return 1
L2:     const 20
        return 1

> If i use a datatype that i will be pattern matching very often and i want it
> to be quick, how much is the overhead of using polymorphic patterns over
> noraml ones ?

There may be a small overhead because the variants tags are large, so
the compiler can't use the "switch" instruction of the abstract machine.
Compare with (type t = ABC | DEF):
# function ABC -> 10 | DEF -> 20;;
        closure L1, 0
        return 1
L1:     acc 0
        switch 3 2/
L3:     const 10
        return 1
L2:     const 20
        return 1

For the native code, the difference is less visible (ocamlopt -S):
.L102:
        cmpl    $6494341, %eax
        jne     .L101
        movl    $21, %eax
        ret
.L101:
        movl    $41, %eax
        ret

and:

.L105:
        sarl    $1, %eax
        testl   %eax, %eax
        je      .L104
        movl    $41, %eax
        ret
.L104:
        movl    $21, %eax
        ret

(I think the new compilation scheme for pattern matching doesn't affect
these cases).

For more complex case, small value for tags allow optimizations. (see for
instance the assembler code produced for:
function `ABC -> 10 | `DEF -> 20 | `GHI -> 30;;
type t = ABC | DEF | GHI;;
function ABC -> 10 | DEF -> 20 | GHI -> 30;;
)


-- 
  Alain Frisch