From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id A21847EE6B for ; Wed, 4 Dec 2013 14:49:30 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.214.42; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.214.42 as permitted sender) identity=mailfrom; client-ip=209.85.214.42; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-bk0-f42.google.com) identity=helo; client-ip=209.85.214.42; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-bk0-f42.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AloEACYyn1LRVdYqlGdsb2JhbABagz9TpXSKI4hRgRoIFg4BAQEBBwsLCRIqgiUBAQQBQAEbEgsBAwELBgULGiEiAREBBQEKEgYTEoddAQMJBg2lNYxZgwmEUAoZJwMKZIYvEQEFDIxhgg0EB4QzA5gUgTCOdhgphFY7 X-IPAS-Result: AloEACYyn1LRVdYqlGdsb2JhbABagz9TpXSKI4hRgRoIFg4BAQEBBwsLCRIqgiUBAQQBQAEbEgsBAwELBgULGiEiAREBBQEKEgYTEoddAQMJBg2lNYxZgwmEUAoZJwMKZIYvEQEFDIxhgg0EB4QzA5gUgTCOdhgphFY7 X-IronPort-AV: E=Sophos;i="4.93,824,1378850400"; d="scan'208";a="39270559" Received: from mail-bk0-f42.google.com ([209.85.214.42]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 04 Dec 2013 14:49:29 +0100 Received: by mail-bk0-f42.google.com with SMTP id w11so6689250bkz.29 for ; Wed, 04 Dec 2013 05:49:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=+h34J8CfsBTgbNMdb07qgvO6o32ga4MOs3plR5URTw0=; b=T2iX+XGV2ObMOdDYlXl726Dw8DA1ZUFkp7OOHFKnws3nzIc2iCwwwrc2q7bw5L7c1q CjQpf0+abl8+Ac6t9hZyQrSbmia07KkkWojHtwHjxlkxwJQT5ZhM2CpiV8RV09fJNkWZ RV8/G/rEyMuDad7799Cu8sJkliowSd/9GcgZR+fRZwUJeNgqSRUA1UFD/yw9BM5VFY8V XQXex9V/e5hjAOJtxIwNDSIFVDLLQFy39+Cc+q1qDu5h7kItdKNHQoavwOBfzi4393Va uGqpjGcQLekoQpCb3EsMGR8GxZHjrqlosWG48/gv+OIB2v9e4qbPS+DGFuunzo+DRfsp nCoQ== X-Received: by 10.204.107.137 with SMTP id b9mr2058886bkp.46.1386164969373; Wed, 04 Dec 2013 05:49:29 -0800 (PST) MIME-Version: 1.0 Received: by 10.204.122.72 with HTTP; Wed, 4 Dec 2013 05:48:49 -0800 (PST) In-Reply-To: References: From: Gabriel Scherer Date: Wed, 4 Dec 2013 14:48:49 +0100 Message-ID: To: Tom Ridge Cc: caml-list Content-Type: multipart/alternative; boundary=089e013c611c99adad04ecb5ae0e Subject: Re: [Caml-list] Question about garbage collection and impact on performance --089e013c611c99adad04ecb5ae0e Content-Type: text/plain; charset=ISO-8859-1 This was the topic of the following discussion a few years ago: http://cstheory.stackexchange.com/questions/2720/can-the-cost-of-gc-be-neglected-when-analyzing-the-running-time-of-worst-case-da My personal impression is that the question is not that well-posed: - if you assume infinite memory, you don't actually need a GC (and for any input you can tweak the GC setting to make sure no collection happens) - if you assume finite memory, the notion of asymptotic behaviour breaks down unless you can prove your algorithm has a finite peak memory consumption that is below that bound - this is independent of whether or not your language using a GC; if your algorithm constantly allocates heap memory, you will run into compaction issues even with malloc/free that may degrade theoretical performances Neelk answer in the link I gave above is that if you can tune your GC to make sure collections happen infrequently enough, you can make collection amortized constant-time. But that means you have to accept some memory wasted (the runtime using significantly more memory than the size of the actually live data), possibly proportional to the running time of your program. On Wed, Dec 4, 2013 at 1:20 PM, Tom Ridge wrote: > 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 > --089e013c611c99adad04ecb5ae0e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
My personal impression is that the question is not that well-pose= d:
- if you assume infinite memory, you don't actually need a = GC (and for any input you can tweak the GC setting to make sure no collecti= on happens)
- if you assume finite memory, the notion of asymptotic behaviour bre= aks down unless you can prove your algorithm has a finite peak memory consu= mption that is below that bound
- this is independent of whether o= r not your language using a GC; if your algorithm constantly allocates heap= memory, you will run into compaction issues even with malloc/free that may= degrade theoretical performances

Neelk answer in the link I gave above is that if you can tune you= r GC to make sure collections happen infrequently enough, you can make coll= ection amortized constant-time. But that means you have to accept some memo= ry wasted (the runtime using significantly more memory than the size of the= actually live data), possibly proportional to the running time of your pro= gram.


On Wed, Dec 4, 2= 013 at 1:20 PM, Tom Ridge <tom.j.ridge+list@googlemail.com> wrote:
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<= br> the time complexity of my program?

If the answer is "yes", then are there any expectations I might h= ave
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. =A0Subscription management and archives:
ht= tps://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

--089e013c611c99adad04ecb5ae0e--