Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile

[Jon Harrop <jon@ffconsultancy.com>]

On Wednesday 11 July 2007 01:10:02 Jacques Garrigue wrote:
> Seems you're lucky. The fix I did yesterday after reading your first
> mail, combined with the fixes following the previous discussion,
> solved the problem. Compilation times are now about 7s using less than
> 7MB, for all of the 3 files, using ocamlc (bytecode). Of course, you
> can still expect quadratic behaviour if your types grow more...

Isn't it a really bad idea to autogenerate polymorphic variant type 
constructors anyway because, sooner or later, you'll get a hash clash? In 
fact, wouldn't that be platform specific?

I would recommend factoring the sum type by the argument types of the 
contructors in this case. Looking at Sam's files, this is trivial. Just 
replace this:

type ('a,'b) t1 = [
| `t1_a of 'a option
| `t1_b of 'b list
| `t1_a0 of 'a option
...
| `t1_a9 of 'a option
| `t1_a10 of 'a option
...
| `t1_a1000 of 'a option

with this:

type t1 = [
| `t1_int of [
  | `a
  | `a0
  | `a10000 ] * int
| `t1_float of [`b] * float
]

and this:

let f ~fa ~fb = function
  | `t1_a a -> fa a
  | `t1_b b -> fb b
  | `t1_a0 a -> fa a
...
  | `t1_a1000 a -> fa a

with this:

let f ~fa ~fb = function
| `t1_int(_, a) -> fa a
| `t1_float(_, b) -> fb b

The following code autogenerates an equivalent to small1.ml and it compiles 
100x faster:

open Printf

let () =
  printf "type t1 = [\n";
  printf "| `t1_int of [\n| `a\n";
  for i=0 to 1000 do
    printf "  | `a%d\n" i
  done;
  printf "] * int\n";
  printf "| `t1_float of [`b] * float\n";
  printf "]\n";
  printf "let f ~fa ~fb = function\n";
  printf "| `t1_int(_, a) -> fa a\n";
  printf "| `t1_float(_, b) -> fb b\n";

Doing the same for small2.ml and small.ml, the final compilation time is 
0.09s.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e