Re: [Caml-list] Question about garbage collection and impact on performance

[Malcolm Matalka <mmatalka@gmail.com>]

Perhaps posting some experiments would help people help you.  In
particular it would be nice to see:

- The actual timings of what you consider a good run and a bad run

- Those runs with verbose gc turned on

- Amount of memory consumption

- The timings for if you jack up the amount of memory that the runtime
  system is allowed to use on both a good run and a bad run to determine
  the system

In short, the answer to your question seems to be "maybe".  But enough
information has not been provided to suggest if it's responsible for
what you're seeing or just a theoretical possibility.

Tom Ridge <tom.j.ridge+list@googlemail.com> writes:

> On 5 December 2013 01:09, Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> wrote:
>> 2013/12/04 21:20, Tom Ridge <tom.j.ridge+list@googlemail.com>:
>>
>>> Dear caml-list,
>>>
>>> I have an OCaml program which I expect to run in time O((n^3) *
>>> (ln(n))) say. My expectations are based (unrealistically) on ignoring
>>> garbage collection completely. As inputs get large, the program
>>> performs worse than I expect.
>>>
>>> My question is: is it possible for OCaml's garbage collection to alter
>>> the time complexity of my program?
>>
>> I would say that, on a program that is already O(n^3), that would be very surprising.
>
> Surprising, but not impossible?
>
>> What kind of measure did you do?
>
> A rather basic measurement of the time the program takes (using /usr/bin/time).
>
>> If your program uses lots of memory, swapping may be a major slowdown,
>> using a GC or not (but a badly tuned GC may cause more swapping).
>
> Having played around with GC settings, I now get the expected
> behaviour. I don't think the previous version was swapping, but I'm
> not sure (and will look into this).
>
> I take Scherer's point that the question is not well-posed, so I am
> thinking about how to phrase the question better.
>
> I am slightly worried that, if the GC were mark and sweep (and OCaml's
> GC is partly mark and sweep, as I understand it) and if the GC is
> invoked sufficiently often, then indeed the performance may change.
> For example, a program that runs for n steps, and allocates a
> fixed-size chunk of memory (that is kept live) at each step, is
> naively O(n). If each step of the program is followed by a mark+sweep
> GC, then the time cost of the GC is roughly O(n^2). So with GC the
> program may perform as O(n^2). Of course, what actually happens is
> that GC does not run after each step, and a real analysis would be
> sensitive to the size of the live set (relative to the memory
> available), the amount of garbage produced etc.
>
> Are there any pointers to analyses (not specific to OCaml) along these lines?
>
>
>
>>
>> Jacques Garrigue