From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA16258; Sat, 15 Sep 2001 11:10:38 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA16422 for ; Sat, 15 Sep 2001 11:10:37 +0200 (MET DST) Received: from math.unifi.it (hermes.math.unifi.it [150.217.33.222]) by nez-perce.inria.fr (8.11.1/8.10.0) with SMTP id f8F9Abr03426 for ; Sat, 15 Sep 2001 11:10:37 +0200 (MET DST) Received: (qmail 7885 invoked from network); 15 Sep 2001 09:10:17 -0000 Received: from sisiphos.math.unifi.it (mail@150.217.33.46) by hermes.math.unifi.it with SMTP; 15 Sep 2001 09:10:17 -0000 Received: from maggesi by sisiphos.math.unifi.it with local (Exim 3.12 #1 (Debian)) id 15iBSr-0004Ml-00 for ; Sat, 15 Sep 2001 11:10:17 +0200 To: caml-list@inria.fr Subject: [Caml-list] mark_slice, sweep_slice, oldify From: Marco Maggesi Date: 15 Sep 2001 11:10:17 +0200 Message-ID: <877kv04y6e.fsf@sisiphos.math.unifi.it> User-Agent: Gnus/5.090001 (Oort Gnus v0.01) Emacs/20.7 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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