From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q2E8qoEo031595
	for <caml-list@sympa-roc.inria.fr>; Wed, 14 Mar 2012 09:52:50 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: ApoCABNcYE/B/UPkmGdsb2JhbABDgwyzLgEBAQEBCAkNBxQnggoBBTIBRQEQCw4TFg8JAwIBAgFFBg0BBwKICrxNkHgEm0GNIg
X-IronPort-AV: E=Sophos;i="4.73,583,1325458800"; 
   d="scan'208";a="135980764"
Received: from smtpout3.laposte.net (HELO smtpout.laposte.net) ([193.253.67.228])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 14 Mar 2012 09:52:49 +0100
Received: from [192.168.0.41] ([81.64.133.129])
	by mwinf8505-out with ME
	id lLsn1i0092ng9LH03Lsndf; Wed, 14 Mar 2012 09:52:48 +0100
Message-ID: <4F605C5F.3020802@laposte.net>
Date: Wed, 14 Mar 2012 09:52:47 +0100
From: Pierre Chambart <pierre.chambart@laposte.net>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20120216 Icedove/8.0
MIME-Version: 1.0
To: Gerd Stolpmann <info@gerd-stolpmann.de>
CC: Matti Jokinen <moj@tanssi.net>, Raphael Proust <raphlalou@gmail.com>,
        SerP <serp256@gmail.com>, caml-list <caml-list@inria.fr>
References: <CAHgca+_m7iw8iFDb+23m3UgWMFM5j__ctY3o1oTyJ-HKP_57yQ@mail.gmail.com>    <CAPFanBHsBUkAh8-rJJdC=uv9pXnef7duxQ-gHL0FOtvceuwTPQ@mail.gmail.com>    <CAAmHUA=m1Vtiksi7LTEaGHG2NiDZpwsWRb+UTdQL+Ne5-Eg98Q@mail.gmail.com>    <20120313220202.GA29196@kiuru> <f86bae946250d577ed05410c3845d1e4.squirrel@gps.dynxs.de>
In-Reply-To: <f86bae946250d577ed05410c3845d1e4.squirrel@gps.dynxs.de>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Subject: Re: [Caml-list] Very slow compilation

Le 13/03/2012 23:46, Gerd Stolpmann a écrit :
>> ocamldebug /usr/bin/ocamlduceopt -c big_ocamlduce_module.ml
>> run
>> ... wait about two minutes and press control-C
>>
>> You will probably find the compiler executing a function from modules
>> such as Interf, Coloring or Spill, or a lower level function called
>> from these modules.
> This was also my observation.
>
>> I have never observed anything similar in OCaml, but ocamlduceopt
>> appears to use unmodified ocamlopt code generation modules.  I wonder
>> what is the critical difference between OCamlDuce code and typical
>> OCaml code at this level.
> I guess the only difference is the length of the code passed at once to
> the backend, since you can generate code showing this problem for standard
> ocamlopt, as in my Hydro case.
>
I had a similar case where (handwritten) code took a long time to do
register allocation.
After looking more closely it seems that all declarations in modules
have effects that
interfere: in the coloring graph, every vertex corresponding to the
effect of affecting
the function to the field of the module has an edge to every other such
vertex. Since
the graph is represented by a set of edges, it is something like a
n².log(n) complexity
for creating the graph.

Notice that it doesn't occur for values declared at toplevel.

A simple trick to circumvent that is to split the module in submodules
and include
them later.

module M = struct
    let a1 x = x
    ...
    let an x = x
    let b1 x = x
    ...
    let bn x = x
    ...
end

is replaced by

module M = struct
    module A = struct
    let a1 x = x
    ...
    let an x = x
    end
    module B = struct
    let b1 x = x
    ...
    let bn x = x
    end
    ...

    include A
    include B
    ...
end
-- 
Pierre