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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 11B767EE1D for ; Thu, 5 Dec 2013 12:21:37 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of tom.j.ridge@googlemail.com) identity=pra; client-ip=209.85.160.51; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="tom.j.ridge@googlemail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of tom.j.ridge@googlemail.com designates 209.85.160.51 as permitted sender) identity=mailfrom; client-ip=209.85.160.51; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="tom.j.ridge@googlemail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-pb0-f51.google.com) identity=helo; client-ip=209.85.160.51; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="postmaster@mail-pb0-f51.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqgCAPFgoFLRVaAzlGdsb2JhbABZDgiDKVOleZJzgREIFg4BAQEBBwsLCRIqgiUBAQVAAQEsCwEPAQoLAwoNISISAQUBChIGExKHXQEDDw2lHYsQhFIBBYQ7ChknAwqHGxEGjG+BOiSEbZgXgTCOdhgpgWWCMT88gS0 X-IPAS-Result: AqgCAPFgoFLRVaAzlGdsb2JhbABZDgiDKVOleZJzgREIFg4BAQEBBwsLCRIqgiUBAQVAAQEsCwEPAQoLAwoNISISAQUBChIGExKHXQEDDw2lHYsQhFIBBYQ7ChknAwqHGxEGjG+BOiSEbZgXgTCOdhgpgWWCMT88gS0 X-IronPort-AV: E=Sophos;i="4.93,832,1378850400"; d="scan'208";a="47111610" Received: from mail-pb0-f51.google.com ([209.85.160.51]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 05 Dec 2013 12:21:36 +0100 Received: by mail-pb0-f51.google.com with SMTP id up15so25535273pbc.24 for ; Thu, 05 Dec 2013 03:21:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type:content-transfer-encoding; bh=8iBywj7ky3KC0FYCmvejZVo8InDkntdP7WUbcFNHbWk=; b=iKZ0fuUU1mDMD0EjGtCjj3gBYtD8aSgxGj9c5BaAtHl0blvAtiLRHBL81qnHOlzoBX LqHE3nAj0KRSi5yk3lAZLy1YwCYOz4kgIczY6y12L8ME+S/Fc4o6Xi8mtgysvM0VW8Oc luG8DJmWPyizPUZXEKodnN+k4GP09GvQowJcSftMwtLbPXkf4HLN9eVUDzIgWUc/9WNI 9RLGi6C6EYCf8jSCBdq6wkQXL4Uayw5uOI4xABIuqmSIQSYAEoy8xJgUeEO4wRb3GnkV S24reJI/wAVYLYcjmMTyAjNZ7Ix6n/tK5X2gZoUlV82NbUnD+lxTVBh7fqKuGSfS2Rix F5iA== X-Received: by 10.68.136.105 with SMTP id pz9mr11877084pbb.100.1386242494419; Thu, 05 Dec 2013 03:21:34 -0800 (PST) MIME-Version: 1.0 Sender: tom.j.ridge@googlemail.com Received: by 10.70.79.136 with HTTP; Thu, 5 Dec 2013 03:21:14 -0800 (PST) In-Reply-To: References: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp> From: Tom Ridge Date: Thu, 5 Dec 2013 11:21:14 +0000 X-Google-Sender-Auth: fOFYuIUz_c6JMwbDzXrptD-VgOk Message-ID: To: Michael Hicks Cc: OCaml Mailing List Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] Question about garbage collection and impact on performance Yes, examples like this are what I'm worried about. Thanks! On 5 December 2013 10:48, Michael Hicks wrote: > 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 th= e data structures in your program. The basic idea is that in the limit if y= our GC is a trace, and your data structure is a single linked list, then pa= rallel 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 p= rogram 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 G= C 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 a= ccounting (treating all of the allocations as constant), and your particula= r program's execution is not sub linear, so perhaps it doesn't apply to you= r situation. But I suspect this is the kind of thing you were thinking abou= t? Note that my example assumes a O(live size) GC and not a O(heap size), b= ut the latter could make the situation worse, I'd guess. > > -Mike > > On Dec 5, 2013, at 5:08 AM, Tom Ridge w= rote: > >> On 5 December 2013 01:09, Jacques Garrigue wrote: >>> 2013/12/04 21:20, Tom Ridge : >>> >>>> 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 ve= ry 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 l= ines? >> >> >> >>> >>> 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 >