[Caml-list] How to profile compiler's performance

[Caml-list] How to profile compiler's performance

[Hongbo Zhang]

Hi List,
    I have a file which is only 410 lines, the compilation process takes 
nearly 1 minutes. Before my refactoring, it's compiled very fast.
    Is there a way to know which part the compiler spend most time in ?
    Many Thanks

Re: [Caml-list] How to profile compiler's performance

[Gabriel Scherer]

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

You could try compiling a native OCaml compiler executable with profiling
option (-p) (setting that up might be a pain, though).

Before that you could try to only typecheck the file (option "-i") to know
whether it's the type-checking or code generation that is problematic. (-i
causes type printing as well, so for very large types that are internally
shared it can be its own source of slowness)

If it was in code generation, that would most likely only occur during when
compiling to native code. Have you noticed the performance bottleneck with
compilation to bytecode as well?

(Of course using the natively-compiled versions of your compilers will also
speed up performance, but if your generated code hits one of the source of
exponential behavior of the compiler you're out of luck anyway.)

On Sun, Aug 26, 2012 at 4:20 PM, Hongbo Zhang <bobzhang1988@gmail.com>wrote:

> Hi List,
>    I have a file which is only 410 lines, the compilation process takes
> nearly 1 minutes. Before my refactoring, it's compiled very fast.
>    Is there a way to know which part the compiler spend most time in ?
>    Many Thanks
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/**wws/info/caml-list<https://sympa-roc.inria.fr/wws/info/caml-list>
> Beginner's list: http://groups.yahoo.com/group/**ocaml_beginners<http://groups.yahoo.com/group/ocaml_beginners>
> Bug reports: http://caml.inria.fr/bin/caml-**bugs<http://caml.inria.fr/bin/caml-bugs>
>
>

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

Re: [Caml-list] How to profile compiler's performance

[oliver]

On Sun, Aug 26, 2012 at 05:05:55PM +0200, Gabriel Scherer wrote:
[...]
> (Of course using the natively-compiled versions of your compilers will also
> speed up performance, but if your generated code hits one of the source of
> exponential behavior of the compiler you're out of luck anyway.)
[...]

Which are the sources of this behaviour?

Is this documented somewhere?


Ciao,
   Oliver

Re: [Caml-list] How to profile compiler's performance

[Gabriel Scherer]

> Is this documented somewhere?

Not to my knowledge -- but if people answer this thread we might be
able to gather enough data points.

Have a look at this previous discussion which may give a few ideas:
  http://old.nabble.com/Very-slow-compilation-td33479980.html#a33480123

I also remember a discussion where the problem was the number of
nested "for" loops : ocamlopt compilation time can be exponential in
this nesting number.

The bugtracker also has some example (some of which havebeen fixed
since reporting):
  http://caml.inria.fr/mantis/print_bug_page.php?bug_id=4905
  http://caml.inria.fr/mantis/print_bug_page.php?bug_id=2470

> I have an .ml file that takes more than 50 CPU seconds to compile on my
> 700 MHz computer with ocamlopt.opt version 3.07. The .ml file is
> 3253 lines long and machine-generated (more than 650 short functions
> that look similar).

Those were the times...

If Hongbo wished to share his source file, we may see where the time
is spent in his particular case.


On Sun, Aug 26, 2012 at 9:10 PM, oliver <oliver@first.in-berlin.de> wrote:
> On Sun, Aug 26, 2012 at 05:05:55PM +0200, Gabriel Scherer wrote:
> [...]
>> (Of course using the natively-compiled versions of your compilers will also
>> speed up performance, but if your generated code hits one of the source of
>> exponential behavior of the compiler you're out of luck anyway.)
> [...]
>
> Which are the sources of this behaviour?
>
> Is this documented somewhere?
>
>
> Ciao,
>    Oliver

Re: [Caml-list] How to profile compiler's performance

[Daniel Bünzli]

Le dimanche, 26 août 2012 à 21:10, oliver a écrit :
> Which are the sources of this behaviour?
Type inference can be exponential but is rarely so in practice.

> Is this documented somewhere?
A. J. Kfoury, J. Tiuryn, P. Urzyczyn. ML typability is Dexptime-complete. CAAP'90. 1990
http://dx.doi.org/10.1007/3-540-52590-4_50

Harry G. Mairson. Deciding ML typability is complete for deterministic exponential time. POPL'90. 1990
http://dx.doi.org/10.1145/96709.96748

Example program, from Mairson, as found in Pierce's Types and Programming languages:

let f0 = fun x -> (x, x) in
let f1 = fun y -> f0 (f0 y) in
let f2 = fun y -> f1 (f1 y) in
let f3 = fun y -> f2 (f2 y) in
let f4 = fun y -> f3 (f3 y) in
let f5 = fun y -> f4 (f4 y) in
f5 (fun z -> z)
;;

(Start compilation and go make the coffee)

Best,

Daniel

Re: [Caml-list] How to profile compiler's performance

[oliver]

On Sun, Aug 26, 2012 at 09:59:24PM +0200, Daniel Bünzli wrote:
[...]
> Example program, from Mairson, as found in Pierce's Types and Programming languages:
> 
> let f0 = fun x -> (x, x) in
> let f1 = fun y -> f0 (f0 y) in
> let f2 = fun y -> f1 (f1 y) in
> let f3 = fun y -> f2 (f2 y) in
> let f4 = fun y -> f3 (f3 y) in
> let f5 = fun y -> f4 (f4 y) in
> f5 (fun z -> z)
> ;;
[...]

Oh.

> 
> (Start compilation and go make the coffee)

I do like coffee.... but the circumstances for this one aren't
a pleasure.

Nevertheless thanks for the example code.

(Do you have an estimation if it will take hours, days or weeks to get that parsed?)

Ciao,
   Oliver

Re: [Caml-list] How to profile compiler's performance

[oliver]

On Sun, Aug 26, 2012 at 10:52:07PM +0200, oliver wrote:
> On Sun, Aug 26, 2012 at 09:59:24PM +0200, Daniel Bünzli wrote:
> [...]
> > Example program, from Mairson, as found in Pierce's Types and Programming languages:
> > 
> > let f0 = fun x -> (x, x) in
> > let f1 = fun y -> f0 (f0 y) in
> > let f2 = fun y -> f1 (f1 y) in
> > let f3 = fun y -> f2 (f2 y) in
> > let f4 = fun y -> f3 (f3 y) in
> > let f5 = fun y -> f4 (f4 y) in
> > f5 (fun z -> z)
> > ;;
> [...]
> 
> Oh.
> 
> > 
> > (Start compilation and go make the coffee)
> 
> I do like coffee.... but the circumstances for this one aren't
> a pleasure.
> 
> Nevertheless thanks for the example code.
> 
> (Do you have an estimation if it will take hours, days or weeks to get that
> parsed?)
[...]

top - 02:12:24 up  5:06,  6 users,  load average: 1.66, 1.50, 1.46
[...]
 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND 
2471 oliver    20   0 15604 3268  692 R 82.0  0.2 160:24.91 ocaml
[...]


Time to kill that process....

...nice working example. :-)


Ciao,
   Oliver

Re: [Caml-list] How to profile compiler's performance

[Markus Weißmann]

On 2012-08-27 02:14, oliver wrote:
> On Sun, Aug 26, 2012 at 10:52:07PM +0200, oliver wrote:
>> On Sun, Aug 26, 2012 at 09:59:24PM +0200, Daniel Bünzli wrote:
>> [...]
>> > Example program, from Mairson, as found in Pierce's Types and 
>> Programming languages:
>> >
>> > let f0 = fun x -> (x, x) in
>> > let f1 = fun y -> f0 (f0 y) in
>> > let f2 = fun y -> f1 (f1 y) in
>> > let f3 = fun y -> f2 (f2 y) in
>> > let f4 = fun y -> f3 (f3 y) in
>> > let f5 = fun y -> f4 (f4 y) in
>> > f5 (fun z -> z)
>> > ;;
>> [...]
>>
>> Oh.
>>
>> >
>> > (Start compilation and go make the coffee)
>>
[...]
>> (Do you have an estimation if it will take hours, days or weeks to 
>> get that
>> parsed?)

on a Xeon E5630 it took ~58 minutes - with probably the whole process 
fitting in its 12 MB cache..


regards

-Markus

-- 
Markus Weißmann, M.Sc.
Technische Universität München
Institut für Informatik
Boltzmannstr. 3
D-85748 Garching
Germany
http://wwwknoll.in.tum.de/

Re: [Caml-list] How to profile compiler's performance

[Hongbo Zhang]

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

On 8/26/12 11:05 AM, Gabriel Scherer wrote:
Hi Gabriel,
   Sorry for the noise, it turns out that I upgraded my ocalmfind, and 
forget to modify findlib.conf.
ocamlfind still picks 'ocamlc' instead of 'ocamlc.opt'.
   There's a huge performance difference(10x) between ocamlc.opt and ocamlc.
Thanks!
> You could try compiling a native OCaml compiler executable with 
> profiling option (-p) (setting that up might be a pain, though).
>
> Before that you could try to only typecheck the file (option "-i") to 
> know whether it's the type-checking or code generation that is 
> problematic. (-i causes type printing as well, so for very large types 
> that are internally shared it can be its own source of slowness)
>
> If it was in code generation, that would most likely only occur during 
> when compiling to native code. Have you noticed the performance 
> bottleneck with compilation to bytecode as well?
>
> (Of course using the natively-compiled versions of your compilers will 
> also speed up performance, but if your generated code hits one of the 
> source of exponential behavior of the compiler you're out of luck anyway.)
>
> On Sun, Aug 26, 2012 at 4:20 PM, Hongbo Zhang <bobzhang1988@gmail.com 
> <mailto:bobzhang1988@gmail.com>> wrote:
>
>     Hi List,
>        I have a file which is only 410 lines, the compilation process
>     takes nearly 1 minutes. Before my refactoring, it's compiled very
>     fast.
>        Is there a way to know which part the compiler spend most time in ?
>        Many Thanks
>
>     -- 
>     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
>
>


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

Re: [Caml-list] How to profile compiler's performance

[Fabrice Le Fessant]

Did you notice the same time behavior for both ocamlc.opt and 
ocamlopt.opt ? If yes, the problem comes during typing or 
pattern-matching compilation. If no, it comes from native code 
generation, probably register allocation (after inlining of small 
functions, some functions can become huge, with many variables 
interfering).

Benedikt Meurer submitted a linear scan allocator at some point, you 
might want to try to compile your file with his compiler to see if it 
goes faster.

--Fabrice

On 08/26/2012 04:20 PM, Hongbo Zhang wrote:
> Hi List,
>     I have a file which is only 410 lines, the compilation process takes
> nearly 1 minutes. Before my refactoring, it's compiled very fast.
>     Is there a way to know which part the compiler spend most time in ?
>     Many Thanks
>

Re: [Caml-list] How to profile compiler's performance

[oliver]

On Sun, Aug 26, 2012 at 10:05:18PM +0200, Fabrice Le Fessant wrote:
[...]
> Benedikt Meurer submitted a linear scan allocator at some point, you
> might want to try to compile your file with his compiler to see if
> it goes faster.
[...]


Will this become part of the standard installation?

Ciao,
   Oliver

Re: [Caml-list] How to profile compiler's performance

[Benedikt Meurer]

On Aug 26, 2012, at 22:54 , oliver wrote:

> On Sun, Aug 26, 2012 at 10:05:18PM +0200, Fabrice Le Fessant wrote:
> [...]
>> Benedikt Meurer submitted a linear scan allocator at some point, you
>> might want to try to compile your file with his compiler to see if
>> it goes faster.
> [...]

To be exact, it was submitted by Marcell Fischbach who did this as part of his diploma thesis, supervised by me.

> Will this become part of the standard installation?

Probably not, Xavier suggested to improve the existing graph coloring allocator instead.

> Ciao,
>   Oliver

greets,
Benedikt