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