[Caml-list] mark_slice, sweep_slice, oldify

[Marco Maggesi <maggesi@math.unifi.it>]

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