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 WAA09853; Fri, 3 Jan 2003 22:58:38 +0100 (MET) 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 WAA09848 for ; Fri, 3 Jan 2003 22:58:37 +0100 (MET) Received: from pheidippides.md.chalmers.se (pheidippides.md.chalmers.se [129.16.237.91]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h03Lwa507934 for ; Fri, 3 Jan 2003 22:58:36 +0100 (MET) Received: from muppet20.cs.chalmers.se (muppet20.cs.chalmers.se [129.16.226.71]) by pheidippides.md.chalmers.se (8.10.1/8.10.1) with ESMTP id h03LwZI07750 for ; Fri, 3 Jan 2003 22:58:35 +0100 (MET) Received: from localhost (gustavss@localhost) by muppet20.cs.chalmers.se (8.8.5/8.8.5) with ESMTP id WAA27814 for ; Fri, 3 Jan 2003 22:58:35 +0100 (MET) X-Authentication-Warning: muppet20.cs.chalmers.se: gustavss owned process doing -bs Date: Fri, 3 Jan 2003 22:58:34 +0100 (MET) From: =?ISO-8859-1?Q?J=F6rgen_Gustavsson?= To: Subject: [Caml-list] Memory management dominates running time Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hi, I have a performance problem with one of my ocaml programs: it seems as if the memory management asymptoticly dominates the running time. I.e., as the program runs the fraction of the time that is spent on memory management seems to go towards 100%. I believe that the problem is in the function fl_allocate in the ocaml runtime. I profiled my program with gprof on a moderately sized input which gave the following top ten time consumers. % cumulative self self total time seconds seconds calls ms/call ms/call name 55.5 63.29 63.29 fl_allocate [1] 11.0 75.79 12.50 mark_slice [2] 5.7 82.32 6.53 sweep_slice [3] 4.0 86.91 4.59 _brk_unlocked [4] 2.5 89.80 2.89 oldify_one [5] 2.3 92.42 2.62 oldify_mopup [6] 1.6 94.23 1.81 modify [7] 1.5 95.90 1.67 alloc_shr [8] 0.9 96.91 1.01 allocate_block [9] 0.9 97.90 0.99 compare_val [10] Judging from their names all top ten functions except compare_val and modify has to do with the memory management. In total roughly 85% of the time is spent on memory management. Unfortunately it gets worse when we increase the input size. % cumulative self self total time seconds seconds calls ms/call ms/call name 62.2 612.56 612.56 fl_allocate [1] 8.9 699.91 87.35 _brk_unlocked [2] 7.3 772.09 72.18 fl_add_block [3] 5.0 821.43 49.34 mark_slice [4] 3.7 857.90 36.47 oldify_local_roots [5] 2.6 883.93 26.03 sweep_slice [6] 1.2 895.87 11.94 add_to_heap [7] 1.0 905.92 10.05 oldify_one [8] 1.0 915.39 9.47 oldify_mopup [9] 0.6 921.78 6.39 alloc_shr [10] Now all top ten functions concern memory management and 95% of the time is spent on it. If I increase the input size even further it seems as if it gets even worse. I am not an expert on garbage collection but the only explanation that I can see for this behaviour is that the free list that fl_allocate searches grows as the program runs. If there are lots of small blocks in the begining of the free list then fl_allocate potentially has to search very far when it allocates somewhat larger blocks. This situation can occur, for example, if the program allocates many small blocks in the begining which are then reclaimed by the garbage collector and then later the program allocates mostly larger blocks. Does this explanation make any sense? One reason for why I doubt it, is that if it is correct then the ocaml memory management can asymptoticly dominate the running time. Is it really so? Finally, what can I do about this problem? Regards, Jörgen Gustavsson. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners