[Caml-list] Garbage collection and caml_adjust_gc_speed

[Christopher Kauffman]

I am finishing up my first major research application written in OCaml. The code is a scientific
application which does a moderate amount of floating point computations for which I have employed
the Bigarray library and the Lacaml package.

I am attempting to tune the performance of the code and to that end, I have examined the native code
performance using gprof (OCaml manual section 17.4). The first thing that struck me on analyzing the
profile is that the function 'caml_adjust_gc_speed' is called a lot. The first few lines of the
profile are:

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
14.55 6.80 6.80 4841768 0.00 0.00 caml_adjust_gc_speed
14.41 13.53 6.73 bigarray_fill
6.87 16.74 3.21 lacaml_Dssqr_zero_stub
6.30 19.68 2.94 bigarray_offset
4.30 21.69 2.01 bigarray_slice
4.03 23.57 1.88 bigarray_get_N
2.68 24.82 1.25 1612 0.00 0.00 sweep_slice
2.63 26.05 1.23 24714254 0.00 0.00 caml_c_call
2.10 27.03 0.98 4972572 0.00 0.00 caml_alloc_shr
..

The actual runtime of the program is about 18 seconds so the gprof cumulative time is off by quite a
bit. What concerns me is the large overhead I seem to be getting from the first function,
'caml_adjust_gc_speed', which I assume is related to the garbage collector. Over 4 million calls to
this function seems a little much. I attempted to play with a garbage collection parameter, the
value of control.space_overhead in the Gc module. According to the manual, this affects the major GC
speed and increasing the value is supposed to cut down on the aggressiveness of the GC. Setting
space_overhead to 99 did not change number of calls to 'caml_adjust_gc_speed'.

I'm looking for someone with a bit more knowledge of the garbage collection in OCaml to enlighten me
on whether this overhead can be reduced or if it is an unavoidable side-effect of relying on the
garbage collector. I'd be happy to provide more details on the code if this would be helpful.

Cheers,
Chris

_______________________________________________
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

[Damien Doligez]

On 2006-08-29, at 06:16, Christopher Kauffman wrote:

> I am finishing up my first major research application written in
> OCaml. The code is a scientific application which does a moderate
> amount of floating point computations for which I have employed the
> Bigarray library and the Lacaml package.

[...]

> What concerns me is the large overhead I seem to be getting from
> the first function, 'caml_adjust_gc_speed', which I assume is
> related to the garbage collector. Over 4 million calls to this
> function seems a little much. I attempted to play with a garbage
> collection parameter, the value of control.space_overhead in the Gc
> module. According to the manual, this affects the major GC speed
> and increasing the value is supposed to cut down on the
> aggressiveness of the GC. Setting space_overhead to 99 did not
> change number of calls to 'caml_adjust_gc_speed'.

caml_adjust_gc_speed is called by caml_alloc_custom to tell it about
resources (in this case, memory) outside the heap that depend on the
allocated block.

None of the GC parameter can reduce this number. I guess your program
allocated over 4 million bigarrays.

What I find surprising is that this simple function would dominate
the run time of your program. I suspect some problem with gprof.
Could you give us more details about the computations performed by
your program?

-- Damien

[Christopher Kauffman]

> What I find surprising is that this simple function would dominate the run
> time of your program. I suspect some problem with gprof. Could you give us
> more details about the computations performed by your program?

The program is in the area of computational biology. It is intended to be used
to study approximations to protein folding. The main operations involve altering
N by 3 matrices representing the coordinates of atoms of the protein. I have
used Bigarrays for the data structures for efficiency and the Lacaml package for
most of these operations (multiply, add, etc.) as it leverages BLAS and LAPACK
library calls which are machine-tuned matrix operations.

Lacaml uses fortran_layout double arrays as the matrices on which it operates.
The style of Lacaml is to use optional label arguments so that space may be
re-used. For instance the following creates two N by 3 matrices for
multiplication and a 3 by 3 matrix to store the results. The two large matrices
are multiplied and the result is stored in the 3 by 3 matrix:

open Lacaml.D (* Use double precision matrix elements *)
let n = 100 in
let a = Mat.random n 3 in (* Create n by 3 matrix - Bigarray *)
let b = Mat.random n 3 in (* Create n by 3 matrix - Bigarray *)
let corr = Mat.make 3 3 in (* Create 3 by 3 matrix - Bigarray *)
let new_corr = gemm ~c:corr ~transa:`T a b in (* matrix multiply *)
..

This snippet multiplies 'a' and 'b' and stores the result in 'corr'. The final
line creates a new name for 'corr', 'new_corr' which should point to the same
space as the original 'corr'. This allows a pseudo-functional style of writing
the program while avoiding the need to create many new matrices. As an
alternative, the final line could be changed to

ignore(gemm ~c:corr ~transa:`T acpy bcpy);

and the name 'corr' used later. For convenience I have followed the style of the
first version in my program. I suppose it is possible that creating the aliased
name could affect the garbage collector (it might look like the allocation of
another Bigarray so I will experiment with the second style.

[Christopher Kauffman]

After some very helpful advice from Shivkumar Chandrasekaran, I have located the
source of the problem. In my code, a very frequent operation is to take a slice
of a matrix or array (a column of a matrix representing the X-coordinates of
some atoms for instance) and perform some operations on that slice. This is
supported in the Bigarray library with the 'slice_left' function (for
fortran_layout arrays) and in Lacaml with Mat.col function. Unfortunately, using
this operation results in the following sequence of underlying C-function calls
in ocaml-3.09.2/otherlibs/bigarray/bigarray_stubs.c:

bigarray_slice() -> alloc_bigarray() -> alloc_custom() -> caml_adjust_gc_speed()

So even though there is no allocation of new underlying data, taking a slice
creates custom data to manage the new alias which triggers GC adjustment. I am
certainly not familiar with the inner workings of the garbage collector, but
this seems like undesirable behavior as much efficiency is lost for no apparent
reason.

This now seems like an issue with the Bigarray library. Please advise me on the
protocol for submitting this issue that it might be considered for correction in
a future release.

Cheers,
Chris

PS - Thanks again to Shivkumar!

[David MENTRE]

Christopher Kauffman <kauf...@cs.umn.edu> writes:

> This now seems like an issue with the Bigarray library. Please advise me
> on the protocol for submitting this issue that it might be considered
> for correction in a future release.

Submit a bug report with as much details as possible on OCaml bug
tracker: http://caml.inria.fr/mantis/main_page.php

Best wishes,
d.
--
GPG/PGP key: A3AD7A2A David MENTRE <dme...@linux-france.org>
5996 CC46 4612 9CA4 3562 D7AC 6C67 9E96 A3AD 7A2A