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

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

> is it possible for OCaml's garbage collection to alter the time complexity
of my program?

Yes.

> If the answer is "yes", then are there any expectations I might have about
how bad this alteration might be?

I observed List.map taking O(n^2) time for large "n" because it leaks stack
space and the GC traverses the O(n)-deep stack O(n) times during its
execution.

> For example, (without thinking about it too hard) it seems unreasonable
for GC to turn a polytime program into an exponential time program, but is
this actually true for OCaml's garbage collector?

I think you can just get an extra O(n). I'd also look out for very large
arrays on the heap which, IIRC, cause O(n) pause.

I haven't used OCaml in anger for a few years so take this with a grain of
salt... :-)

Cheers,
Jon.

-----Original Message-----
From: tom.j.ridge@googlemail.com [mailto:tom.j.ridge@googlemail.com] On
Behalf Of Tom Ridge
Sent: 04 December 2013 12:21
To: caml-list
Subject: [Caml-list] Question about garbage collection and impact on
performance

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?

If the answer is "yes", then are there any expectations I might have about
how bad this alteration might be? For example, (without thinking about it
too hard) it seems unreasonable for GC to turn a polytime program into an
exponential time program, but is this actually true for OCaml's garbage
collector?

I have read some material on OCaml's GC, but I did not form any intuitions
yet about the answers to these questions.

Thanks in advance

Tom

--
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