Re: [Caml-list] Very slow compilation

Re: [Caml-list] Very slow compilation

[tools]

[-- Attachment #1: Type: text/plain, Size: 742 bytes --]

Yo,
I don't know if this helps, but I can create arbitrary compilation times with very small code samples:

let sink (a,f) = f a

let base = ()
let finish () = ()

let step () = ()

let fold (a,f) g = g (a,f)
let step0 h (a,f) = fold (h a,f)

let f z = fold (base, finish) z

let a z = step0 step z

let () = 
  let () = f 
    a a a a 
    a a a a 
    a a a a 
    a a a a 
    a a a a 
    a a a 
    sink 
  in
  ();;

$> time ocamlc vararg.ml
real    1m9.372s
user    1m9.264s
sys    0m0.044s



Try adding a few a's and see what that gives.

have fun,
Romain.

PS

I'm quite clueless about what's going on exactly. I just stumbled onto this tinkering around with MLton's fold vararg solutions.

[-- Attachment #2: Type: text/html, Size: 1286 bytes --]

Re: [Caml-list] Very slow compilation

[Pierre Chambart]

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

Re: [Caml-list] Very slow compilation

[Gabriel Scherer]

This heavily depends on the structure of the code, and different
shapes of code will cause trouble to the type-checker or the backend.
Left-nesting lets (let x = let y = let z = .... in ... in ... in ...)
can generate known exponential worse case for type inference. Nesting
loops (I recently encountered code written by a student that had
innocently nested 20 for loops from 0 to 1...) can trouble ocamlopt
compilation passes.

Long code can be fine (linear compilation time or, in the bad cases,
polynomial), it's when a particularly vicious kind of nesting causes
exponential compile times that you're in trouble. But when the problem
is in the backend, splitting some things into independent functions
should be a very effective workaround.

On Tue, Mar 13, 2012 at 11:46 PM, Gerd Stolpmann <info@gerd-stolpmann.de> wrote:
>
>>> When working with ocamlduce (a few years ago) the same problem was
>>> raised. A simple thing that can greatly reduce typing time is putting
>>> explicit type annotations. Although the verbosity is increased it is
>>> not that much of a burden if the annotated parts do not evolve too
>>> much.
>>
>> In my experience, ocamlduceopt/ocamlduceopt.opt slows down regularly when
>> the source file approaches 1000 lines of OCamlDuce code.  The compilation
>> time then grows rapidly: in this machine (Thinkpad R5000) 1000 lines
>> took 20 seconds, 2000 lines 2 minutes, 3000 lines hanged the system.
>> Only OCamlDuce code causes slowdown, pure OCaml is compiled rapidly even
>> by OCamlDuce compilers.
>>
>> However, it is not typechecking that takes time.  The time-consuming
>> step appears to be register allocation.  Try:
>
> I've observed the same problem with code generated by the Hydro RPC
> library (using standard ocamlopt). This library can generate a very long
> set of mutually recursive functions, and the time spent by ocamlopt seemed
> to explode (compilation took minutes). ocamlc was not affected.
>
> The fix was to change the code generator, and to break the recursion into
> smaller pieces.
>
>> 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.
>
> Gerd
>
>>
>> - Matti Jokinen
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa-roc.inria.fr/wws/info/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>>
>>
>
>
> --
> Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
> Creator of GODI and camlcity.org.
> Contact details:        http://www.camlcity.org/contact.html
> Company homepage:       http://www.gerd-stolpmann.de
> *** Searching for new projects! Need consulting for system
> *** programming in Ocaml? Gerd Stolpmann can help you.
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Very slow compilation

[Gerd Stolpmann]

>> When working with ocamlduce (a few years ago) the same problem was
>> raised. A simple thing that can greatly reduce typing time is putting
>> explicit type annotations. Although the verbosity is increased it is
>> not that much of a burden if the annotated parts do not evolve too
>> much.
>
> In my experience, ocamlduceopt/ocamlduceopt.opt slows down regularly when
> the source file approaches 1000 lines of OCamlDuce code.  The compilation
> time then grows rapidly: in this machine (Thinkpad R5000) 1000 lines
> took 20 seconds, 2000 lines 2 minutes, 3000 lines hanged the system.
> Only OCamlDuce code causes slowdown, pure OCaml is compiled rapidly even
> by OCamlDuce compilers.
>
> However, it is not typechecking that takes time.  The time-consuming
> step appears to be register allocation.  Try:

I've observed the same problem with code generated by the Hydro RPC
library (using standard ocamlopt). This library can generate a very long
set of mutually recursive functions, and the time spent by ocamlopt seemed
to explode (compilation took minutes). ocamlc was not affected.

The fix was to change the code generator, and to break the recursion into
smaller pieces.

> 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.

Gerd

>
> - Matti Jokinen
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>
>


-- 
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.

Re: [Caml-list] Very slow compilation

[Matti Jokinen]

> When working with ocamlduce (a few years ago) the same problem was
> raised. A simple thing that can greatly reduce typing time is putting
> explicit type annotations. Although the verbosity is increased it is
> not that much of a burden if the annotated parts do not evolve too
> much.

In my experience, ocamlduceopt/ocamlduceopt.opt slows down regularly when
the source file approaches 1000 lines of OCamlDuce code.  The compilation
time then grows rapidly: in this machine (Thinkpad R5000) 1000 lines
took 20 seconds, 2000 lines 2 minutes, 3000 lines hanged the system.
Only OCamlDuce code causes slowdown, pure OCaml is compiled rapidly even
by OCamlDuce compilers.

However, it is not typechecking that takes time.  The time-consuming
step appears to be register allocation.  Try:

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.

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.

- Matti Jokinen

Re: [Caml-list] Very slow compilation

[Richard W.M. Jones]

On Sun, Mar 11, 2012 at 12:11:51PM +0400, SerP wrote:
> We encountered a problem of a slow compilation. When the project grew up,
> the time of compilation increased considerably. We have many classes and
> objects, and the type checking of objects and classes performs very slowly.
> I have Core i3 3GHz iMac, and the average compilation time of one module is
> 7-13 seconds. The entire projet is compiled within 10-15 minutes. The major
> part of the time is taken by "Typemod.type_implementation", which include
> many calls of Ctype.unify (80% of compilation time). Now, it is getting
> hard and slow to develop the projetct, are there any ways to accelarate it?
> It is difficult to get all fine points, but I wish I could make the process
> faster. Thanks for any help or comments. Looking forward to your reply

I have seen slow compilation with OCaml, but for me it only happened
for very large (generated) source files, about 60,000 lines of code.

Avoiding very large source files may help.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Very slow compilation

[Raphael Proust]

When working with ocamlduce (a few years ago) the same problem was
raised. A simple thing that can greatly reduce typing time is putting
explicit type annotations. Although the verbosity is increased it is
not that much of a burden if the annotated parts do not evolve too
much.

The same probably applies with plain ocaml. (It might be that
objects/classes typing is more complicated due to sub-typing, although
someone with insider knowledge would know better.)

On Sun, Mar 11, 2012 at 9:39 AM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
> I can't comment on the type-checker internals, but a general first
> step would be to make sure that you don't recompile things that you
> don't need to.
>
> If you change the *implementation* of a module without changing its
> interface, you should not have to recompile any other module, at least
> when using bytecode compilation. You need not recompile even the
> modules that depend on this -- there is only an
> interface-dependency. With native compilation, the compiler can
> inspect depending modules to perform some cross-module optimizations,
> so there will be an implementation-dependency by default, but you can
> disable it -- the .cmx for bar.ml won't depend on its dependency
> foo.ml if foo.cmx is not available at compile time. It's simpler to
> just use ocamlc for development. It's also faster at code generation,
> but apparently your bottleneck is typing.
>
> To fully benefit from separate compilation, you may want to have
> a slightly more fine-grained separation of you program into
> compilation units. If a given module interface can be split in two
> parts, one that evolves slowly and on which a lot of modules depend,
> and one that is little used outside but changes frequently, it's a big
> win to split it into two separate module interfaces -- when you can,
> eg. the whole thing is not encapsulated as a functor.
>
> On Sun, Mar 11, 2012 at 9:11 AM, SerP <serp256@gmail.com> wrote:
>> We encountered a problem of a slow compilation. When the project grew up,
>> the time of compilation increased considerably. We have many classes and
>> objects, and the type checking of objects and classes performs very slowly.
>> I have Core i3 3GHz iMac, and the average compilation time of one module is
>> 7-13 seconds. The entire projet is compiled within 10-15 minutes. The major
>> part of the time is taken by "Typemod.type_implementation", which include
>> many calls of Ctype.unify (80% of compilation time). Now, it is getting hard
>> and slow to develop the projetct, are there any ways to accelarate it? It is
>> difficult to get all fine points, but I wish I could make the process
>> faster. Thanks for any help or comments. Looking forward to your reply
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
_______
Raphael

Re: [Caml-list] Very slow compilation

[Adrien]

Hi,

On 11/03/2012, Gabriel Scherer <gabriel.scherer@gmail.com> wrote:
> I can't comment on the type-checker internals, but a general first
> step would be to make sure that you don't recompile things that you
> don't need to.

There's another "easy" thing to try: using .opt version of the ocaml
binaries. It's not often done by default and I've sometimes noticed 5
to 6 times faster builds with them (of course, on files which were
slow to build).

Hope this helps,
Adrien Nader

Re: [Caml-list] Very slow compilation

[Gabriel Scherer]

I can't comment on the type-checker internals, but a general first
step would be to make sure that you don't recompile things that you
don't need to.

If you change the *implementation* of a module without changing its
interface, you should not have to recompile any other module, at least
when using bytecode compilation. You need not recompile even the
modules that depend on this -- there is only an
interface-dependency. With native compilation, the compiler can
inspect depending modules to perform some cross-module optimizations,
so there will be an implementation-dependency by default, but you can
disable it -- the .cmx for bar.ml won't depend on its dependency
foo.ml if foo.cmx is not available at compile time. It's simpler to
just use ocamlc for development. It's also faster at code generation,
but apparently your bottleneck is typing.

To fully benefit from separate compilation, you may want to have
a slightly more fine-grained separation of you program into
compilation units. If a given module interface can be split in two
parts, one that evolves slowly and on which a lot of modules depend,
and one that is little used outside but changes frequently, it's a big
win to split it into two separate module interfaces -- when you can,
eg. the whole thing is not encapsulated as a functor.

On Sun, Mar 11, 2012 at 9:11 AM, SerP <serp256@gmail.com> wrote:
> We encountered a problem of a slow compilation. When the project grew up,
> the time of compilation increased considerably. We have many classes and
> objects, and the type checking of objects and classes performs very slowly.
> I have Core i3 3GHz iMac, and the average compilation time of one module is
> 7-13 seconds. The entire projet is compiled within 10-15 minutes. The major
> part of the time is taken by "Typemod.type_implementation", which include
> many calls of Ctype.unify (80% of compilation time). Now, it is getting hard
> and slow to develop the projetct, are there any ways to accelarate it? It is
> difficult to get all fine points, but I wish I could make the process
> faster. Thanks for any help or comments. Looking forward to your reply

[Caml-list] Very slow compilation

[SerP]

[-- Attachment #1: Type: text/plain, Size: 744 bytes --]

We encountered a problem of a slow compilation. When the project grew up,
the time of compilation increased considerably. We have many classes and
objects, and the type checking of objects and classes performs very slowly.
I have Core i3 3GHz iMac, and the average compilation time of one module is
7-13 seconds. The entire projet is compiled within 10-15 minutes. The major
part of the time is taken by "Typemod.type_implementation", which include
many calls of Ctype.unify (80% of compilation time). Now, it is getting
hard and slow to develop the projetct, are there any ways to accelarate it?
It is difficult to get all fine points, but I wish I could make the process
faster. Thanks for any help or comments. Looking forward to your reply

[-- Attachment #2: Type: text/html, Size: 789 bytes --]