This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] mark_slice, sweep_slice, oldify
• Marco Maggesi
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Marco Maggesi Subject: [Caml-list] mark_slice, sweep_slice, oldify

Hi,

I am writing a library for computing basic algebraic operations on
polynomials in multiple indeterminates (my ideal goal would be to
implement the Buchberger algorithm for Groebner Basis).

With the aid of gprof I noticed that my program spends most of the time
of the computation in three functions `mark_slice', `sweep_slice' and
`oldify' (see below the output of gprof obtained after the computation
of some products of polynomials).

What does this exactly mean?  This is the generational garbage
collector, right?  May I low the cost of GC?

I do not want to bore you with the details of my program (I can make
the code available if someone wants), let me simply say that I tried
to represent polynomial as binary trees (both mutable and non mutable)
where each node is a term.  In any test I do the main CPU costs is
alwais in GC.  (I also tried to represent polynomials as sorted lists
of terms, but then I have a bad complexity in terms of number of
comparisons and products of terms).

I do not pretend a precise answer.  Simply tell me what I have to look
or study to understand which operation stress the GC more and which not.

Thanks, Marco

Each sample counts as 0.01 seconds.
%   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
25.25      2.24     2.24      908     2.47     2.47  mark_slice
19.84      4.00     1.76      754     2.33     2.35  sweep_slice
16.69      5.48     1.48   172210     0.01     0.01  oldify
8.46      6.23     0.75  4075593     0.00     0.00  Monomial_mul_56
4.85      6.66     0.43  6151035     0.00     0.00  alloc_shr
4.85      7.09     0.43     2831     0.15     2.93  Tpoly_mul_term_iter_212
4.51      7.49     0.40  1022415     0.00     0.00  Tpoly_mul_term_iter_216
2.82      7.74     0.25  4075593     0.00     0.00  Ring_mul_88
2.37      7.95     0.21  3444124     0.00     0.00  Monomial_lex_102
2.03      8.13     0.18  6151535     0.00     0.00  fl_allocate
1.92      8.30     0.17  6151035     0.00     0.00  allocate_block
1.58      8.44     0.14      500     0.28     0.28  add_to_heap
1.24      8.55     0.11  1360897     0.00     0.00  Ring_add_80
1.01      8.64     0.09  8880614     0.00     0.00  caml_apply2
1.01      8.73     0.09     1662     0.05     1.50  oldify_local_roots
0.90      8.81     0.08     9333     0.01     0.06  Tpoly_add_104
0.34      8.84     0.03     2831     0.01     0.13  Tpoly_mul_term_iter_191
0.11      8.85     0.01   376392     0.00     0.00  fl_merge_block
0.11      8.86     0.01   339844     0.00     0.00  Ring_is_zero_95
0.11      8.87     0.01    12657     0.00     0.00  gc_message
0.00      8.87     0.00   233068     0.00     0.00  Tpoly_make_node_92
0.00      8.87     0.00     3324     0.00     0.75  empty_minor_heap
0.00      8.87     0.00     3324     0.00     0.00  final_empty_young
0.00      8.87     0.00     2926     0.00     0.00  darken
0.00      8.87     0.00     2831     0.00     0.00  Tpoly_mul_term2_rlist_205
0.00      8.87     0.00     1662     0.00     3.92  caml_call_gc
0.00      8.87     0.00     1662     0.00     0.00  final_do_calls
0.00      8.87     0.00     1662     0.00     0.00  final_do_young_roots
0.00      8.87     0.00     1662     0.00     3.92  garbage_collection
0.00      8.87     0.00     1662     0.00     2.42  major_collection_slice
0.00      8.87     0.00     1662     0.00     3.92  minor_collection
0.00      8.87     0.00      501     0.00     0.00  aligned_malloc
0.00      8.87     0.00      501     0.00     0.00  round_heap_chunk_size
0.00      8.87     0.00      500     0.00     0.00  alloc_for_heap
0.00      8.87     0.00      500     0.00     0.28  expand_heap
0.00      8.87     0.00      500     0.00     0.00  fl_add_block

[...]
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr