Which function is consing?

Which function is consing?

[Joel Reymont]

Folks,

There's apparently no way to determine what function is consing using  
the profiler.

How do you get around this limitation in your production code?

	Thanks, Joel

--
http://topdog.cc      - EasyLanguage to C# compiler
http://wagerlabs.com  - Blog

Re: [Caml-list] Which function is consing?

[Christopher L Conway]

Joel,

I'm not sure I understand you correctly, but it's highly doubtful that
consing is the hotspot in your program. If you're problem is
interpreting the mangled function names that show up in gprof, it's
sometimes possible to correlate execution count with source locations
using ocamlcp. See here:
http://procrastiblog.blogspot.com/2007/04/profiling-ocaml-revealed.html

This won't let you figure out "which function is consing" unless you
rename ::, e.g.,
let mycons x xs = x :: xs

Chris

On 7/4/07, Joel Reymont <joelr1@gmail.com> wrote:
> Folks,
>
> There's apparently no way to determine what function is consing using
> the profiler.
>
> How do you get around this limitation in your production code?
>
>         Thanks, Joel
>
> --
> http://topdog.cc      - EasyLanguage to C# compiler
> http://wagerlabs.com  - Blog
>
>
>
>
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Which function is consing?

[Jon Harrop]

On Wednesday 04 July 2007 15:12:38 Christopher L Conway wrote:
> I'm not sure I understand you correctly, but it's highly doubtful that
> consing is the hotspot in your program.

The garbage collector often takes 30% of the CPU but when it is taking 90% of 
the CPU time you want to know where all of the garbage is coming from in 
order to optimize away its allocation. This is typically by avoiding 
overly-eager recomputation or by memoizing results. I believe Joel 
means "allocation" when he says "consing", so he isn't just referring to list 
construction.

To solve this problem you need to know which functions in the call tree are 
allocating heavily. The GC module provides the necessary statistics but 
(AFAIK) there are no tools to automate this for OCaml as there are for F# and 
other languages.

So the simple solution is to wrap your functions in checks by hand and log the 
results. This is very tedious. Perhaps someone would like to write a camlp4 
macro that wraps all top-level function definitions with memory profiling 
calls?

So:

  let f x = ...

is supplemented with:

  let f x = ...

  let f x =
    let __ = (Gc.stat()).Gc.major_words in
    let f_x = f x in
    gc_log "f" ((Gc.stat()).Gc.major_words - __);
    f_x

How does that sound?

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

Re: [Caml-list] Which function is consing?

[Markus E.L.]

> Folks,
>
> There's apparently no way to determine what function is consing using
> the profiler.
>
> How do you get around this limitation in your production code?

I'm not sure I understand what you mean -- but if you're looking for
the function call(s) generated when a::as is compiled: There is no
such function AFAIK: :: is a constructor (like 'Some') not a
function (like (+)) and the construction process is completely inlined (using
ocaml -dinstr I see a makeblock in this instances, I assume that's
it).

Regards -- Markus

Re: [Caml-list] Which function is consing?

[Joel Reymont]

What I would like to find out is how much memory each function  
allocates. I would like to minimize memory allocations as they put  
pressure on the garbage collector.

This type of info is reported for Lisp functions, for example.

	Thanks, Joel

On Jul 4, 2007, at 3:29 PM, Markus E.L. wrote:

> I'm not sure I understand what you mean -- but if you're looking for
> the function call(s) generated when a::as is compiled: There is no
> such function AFAIK: :: is a constructor (like 'Some') not a
> function (like (+)) and the construction process is completely  
> inlined (using
> ocaml -dinstr I see a makeblock in this instances, I assume that's
> it).
>
--
http://topdog.cc      - EasyLanguage to C# compiler
http://wagerlabs.com  - Blog

Re: [Caml-list] Which function is consing?

[Bünzli Daniel]

You wrap your call in a higher-order function that compares the  
Gc.stat () before and after your call, see discussion here [1] and  
here [2].

This is only a half solution since it is a very manual one. However  
if you have a hint on where you allocate a lot this may be usefull to  
compare different implementations and their memory usage.

Daniel


[1] http://caml.inria.fr/pub/ml-archives/caml-list/ 
2003/11/34f26b24813463c04244b74a889dc2a3.fr.html
[2] http://caml.inria.fr/pub/ml-archives/caml-list/2003/11/ 
f5ceb88194f4324b692f89b6f3398ff2.fr.html

Re: [Caml-list] Which function is consing?

[Jon Harrop]

On Wednesday 04 July 2007 15:45:17 Bünzli Daniel wrote:
> This is only a half solution since it is a very manual one.

If I wrote an automatic memory profiler for OCaml, would anyone be interested 
in buying it for under £100?

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

Re: [Caml-list] Which function is consing?

[Brian Hurt]

On Wed, 4 Jul 2007, Joel Reymont wrote:

> What I would like to find out is how much memory each function allocates. I 
> would like to minimize memory allocations as they put pressure on the garbage 
> collector.

Are you trying to track down a specific performance problem, or just 
trying to avoid allocation in general?

If it's the former, I've had good luck just hand analyzing functions. 
Once you know the boxing rules, each block allocated in memory has one tag 
word associated with it.  So if I see "x :: lst" in my code, I know that 
just allocated 3 words- a tag word for the list block, plus a value and a 
next pointer.  And so on.  One of the nice things about Ocaml vr.s Haskell 
is that this sort of analysis is much easier to do in Ocaml.

If you're just trying to reduce memory allocation in general, my advice is 
to not bother, unless you have evidence that 1) performance isn't 
acceptable, 2) higher level optimizations (for example, replacing O(N^2) 
operations with O(N log N) operations) either cannot be applied or would 
be ineffective, and 3) garbage collection costs from excessive allocation 
is the problem.

One comment I will make: it's not unusual for C/C++ programs to spend 
considerable amount of time allocating and deallocating objects as well, 
see:
ftp://ftp.cs.colorado.edu/pub/techreports/zorn/CU-CS-665-93.ps.Z

And note that this study does not include any overhead of deciding if an 
object is freeable, which Ocaml's GC does as well.  C/C++ allocate and 
deallocate a heck of a lot less, but the cost of allocating and 
deallocating is a heck of a lot higher.  The difference is that in Ocaml, 
all of these costs are reported as one big number- "hey, you're spending 
30% of your time in GC!"  While if you were spending 30% of your time in 
destructors deciding which objects can be freed yet or not, since that 
time is spread over a bunch of different functions, it's much less 
obvious.

Brian