[Caml-list] Memory management dominates running time

["Jörgen Gustavsson" <gustavss@cs.chalmers.se>]

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