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

["Jon Harrop" <jon@ffconsultancy.com>]

> ...then parallel GC will get you nowhere...

The topology of the heap can impede scalability but OCaml's GC isn't
parallel so that's irrelevant.

> I wonder if the same is true in general

No. Scalability is nonsensical when you're only using one core.

OCaml's GC is incremental and it is careful to put enough effort into each
slice of major heap collection to make sure it keeps up. As I said before,
the only source of problems I'm aware of are deep stacks and arrays with
many elements.

Cheers,
Jon.

-----Original Message-----
From: caml-list-request@inria.fr [mailto:caml-list-request@inria.fr] On
Behalf Of Michael Hicks
Sent: 05 December 2013 10:49
To: Tom Ridge
Cc: OCaml Mailing List
Subject: Re: [Caml-list] Question about garbage collection and impact on
performance

I'm not sure whether this is useful or not, but Steve Blackburn recently
pointed me to a talk at ISMM'10 about the limits of parallel GC based on the
data structures in your program. The basic idea is that in the limit if your
GC is a trace, and your data structure is a single linked list, then
parallel GC will get you nowhere (unless you do something interesting). Here
are the slides:

http://www.cs.technion.ac.il/~erez/presentations/parallel-trace-ismm.ppt

I wonder if the same is true in general: that a GC that repeatedly has to
trace over a fixed-sized data structure will thwart the performance of a
program that would otherwise run in in sub linear time? For example, suppose
you execute M queries over a size-N data structure that each take time log
N. In between each query you do a "constant" number of allocations (i.e.,
independent of both N and M). But in each case you do enough to force the GC
to run. This run will be in time O(N) and so the overall running time of
your program will be O(MN) not O(M log N) as you'd expect. 

This analysis seems to work for a weird program and by doing some fishy
accounting (treating all of the allocations as constant), and your
particular program's execution is not sub linear, so perhaps it doesn't
apply to your situation. But I suspect this is the kind of thing you were
thinking about? Note that my example assumes a O(live size) GC and not a
O(heap size), but the latter could make the situation worse, I'd guess.

-Mike

On Dec 5, 2013, at 5:08 AM, Tom Ridge <tom.j.ridge+list@googlemail.com>
wrote:

> 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
> 
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs


-- 
Caml-list mailing list.  Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs=