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 4563E7F6BB for ; Thu, 5 Dec 2013 22:09:16 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=pra; client-ip=212.159.14.18; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=mailfrom; client-ip=212.159.14.18; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@avasout06.plus.net) identity=helo; client-ip=212.159.14.18; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="postmaster@avasout06.plus.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsABAHPqoFLUnw4Sm2dsb2JhbABZDgiDKaZOepF5gRwWDgEBAQEBBgsLCRQogiUBAQQBCAIeEjQLBQcBAwIJDgMEAQEBDRoHGSMJAQkIAgQBEgsFAodeAwkKCboiAwqHGxeMb4E6VwcGhC0DjxyKKJNNP4Fp X-IPAS-Result: AsABAHPqoFLUnw4Sm2dsb2JhbABZDgiDKaZOepF5gRwWDgEBAQEBBgsLCRQogiUBAQQBCAIeEjQLBQcBAwIJDgMEAQEBDRoHGSMJAQkIAgQBEgsFAodeAwkKCboiAwqHGxeMb4E6VwcGhC0DjxyKKJNNP4Fp X-IronPort-AV: E=Sophos;i="4.93,835,1378850400"; d="scan'208";a="39523871" Received: from avasout06.plus.net ([212.159.14.18]) by mail3-smtp-sop.national.inria.fr with ESMTP; 05 Dec 2013 22:09:15 +0100 Received: from XPS ([91.125.196.37]) by avasout06 with smtp id xx9C1m0060otVUz01x9D32; Thu, 05 Dec 2013 21:09:14 +0000 X-CM-Score: 0.00 X-CNFS-Analysis: v=2.1 cv=T8a1EZ6Q c=1 sm=1 tr=0 a=7ZBr2+TFhQWw28TTjv1IhQ==:117 a=7ZBr2+TFhQWw28TTjv1IhQ==:17 a=0Bzu9jTXAAAA:8 a=waI2vsT-1KMA:10 a=Xub9RBUEA-sA:10 a=Kvk-SOs2Z7YA:10 a=kj9zAlcOel0A:10 a=r2vSxAw-AAAA:8 a=byhiMKDvd7QA:10 a=rZNwcSkxAAAA:8 a=mK_AVkanAAAA:8 a=ZOzjf2MOAAAA:8 a=CjxXgO3LAAAA:8 a=STSKuSkU1106Zf53IFoA:9 a=UlBPpmSp4fCxAady:21 a=Xx_AjWR7g4GT6G0k:21 a=CjuIK1q_8ugA:10 a=9xyTavCNlvEA:10 X-AUTH: jdh302:2500 Reply-To: From: "Jon Harrop" To: "'Michael Hicks'" , "'Tom Ridge'" Cc: "'OCaml Mailing List'" References: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp> In-Reply-To: Date: Thu, 5 Dec 2013 21:09:16 -0000 Organization: Flying Frog Consultancy Ltd. Message-ID: <005101cef1fe$42b9e7b0$c82db710$@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Outlook 14.0 Thread-Index: AQILtR6FePtFdpgRd7zHLdG0NxMsZgFSc6qdAWQGmOYCF4XjYpmmHWEw Content-Language: en-gb Subject: RE: [Caml-list] Question about garbage collection and impact on performance > ...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 wrote: > 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 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=