From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE 
	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 5D1A3BC6C
	for <caml-list@yquem.inria.fr>; Tue, 10 Jul 2007 09:32:06 +0200 (CEST)
Received: from rabbit.math.nagoya-u.ac.jp (rabbit.math.nagoya-u.ac.jp [133.6.130.5])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6A7W4cQ010778
	for <caml-list@inria.fr>; Tue, 10 Jul 2007 09:32:05 +0200
Received: from localhost (rabbit-172 [172.16.254.254])
	by rabbit.math.nagoya-u.ac.jp (8.12.11/3.7W) with ESMTP id l6A7W38q029151;
	Tue, 10 Jul 2007 16:32:03 +0900 (JST)
Date: Tue, 10 Jul 2007 16:31:42 +0900 (JST)
Message-Id: <20070710.163142.68036861.garrigue@math.nagoya-u.ac.jp>
To: christophe.raffalli@univ-savoie.fr
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] large parametrized polymorphic variant type
 combinations take forever to compile
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <469330B3.4080005@univ-savoie.fr>
References: <4692991E.8040205@gnu.org>
	<20070710.083733.116353766.garrigue@math.nagoya-u.ac.jp>
	<469330B3.4080005@univ-savoie.fr>
X-Mailer: Mew version 4.2 on Emacs 21.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Miltered: at concorde with ID 469335F4.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; parametrized:01 christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 ocaml:01 ocaml:01 foo:01 foo:01 1.6:98 cvs:01 cvs:01 polymorphic:01 polymorphic:01 

From: Christophe Raffalli <christophe.raffalli@univ-savoie.fr>
> > Are you using the CVS 3.10 version?
> > Performance has been been improved, but as I already answerred you,
> > complexity for polymorphic variant pattern-matching is still O(n*n),
> 
> This looks strange: OCaml compute useless cases and incomplete pattern
> and since you can encode SAT in that, I would think that OCaml
> pattern matching (with monomorphic or polymorphic variant) would be
> exponential ...  OK, this is for large patterns, not just case analysis.

I didn't express myself correctly. I was talking about the complexity
of _typing_ a pattern matching. The completeness check can be of
course much more expensive, if you check for a combination of
patterns, like in you example.
Something like:
let f =
  function
      `A, `A -> ()
    | #Foo.t as x, `A -> Foo.conv x
    | `A, (#Foo.t as x) -> Foo.conv x
    | #Foo.t as x, (#Foo.t as y) -> Foo.conv x; Foo.conv y
where Foo.t is composed of 600 constant cases,
takes 90s in the already improved CVS version,
while
let f =
  function #Foo.t as x -> Foo.conv x | #Foo.t as x -> Foo.conv x
just takes 1.6s

Fortunately it seems that people who use huge types do not check for
combinations of patterns, but just discriminate on a single variant
type...

Jacques Garrigue