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 C29FB7EE1D for ; Thu, 5 Dec 2013 11:48:43 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of mwh@cs.umd.edu) identity=pra; client-ip=128.8.127.44; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mwh@cs.umd.edu"; x-sender="mwh@cs.umd.edu"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of mwh@cs.umd.edu designates 128.8.127.44 as permitted sender) identity=mailfrom; client-ip=128.8.127.44; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mwh@cs.umd.edu"; x-sender="mwh@cs.umd.edu"; 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@egg.cs.umd.edu) identity=helo; client-ip=128.8.127.44; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mwh@cs.umd.edu"; x-sender="postmaster@egg.cs.umd.edu"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhwUAJJZoFKACH8sSWdsb2JhbABZFoJxOKQ9A4IMknOBGBYDAQEWFQU/giUBAQQBQAEBLAsBBAsLGA0hQwISBhMSh14DCQYNsCWEUgEFhQwDCleGRBEGjG+BOiQzB4MggROJRZAChRWPFYFL X-IPAS-Result: AhwUAJJZoFKACH8sSWdsb2JhbABZFoJxOKQ9A4IMknOBGBYDAQEWFQU/giUBAQQBQAEBLAsBBAsLGA0hQwISBhMSh14DCQYNsCWEUgEFhQwDCleGRBEGjG+BOiQzB4MggROJRZAChRWPFYFL X-IronPort-AV: E=Sophos;i="4.93,832,1378850400"; d="scan'208";a="39430162" Received: from egg.cs.umd.edu ([128.8.127.44]) by mail3-smtp-sop.national.inria.fr with ESMTP; 05 Dec 2013 11:48:42 +0100 Received: from [10.0.1.9] (pool-173-79-38-163.washdc.fios.verizon.net [173.79.38.163]) (Authenticated sender: mwh) by egg.cs.umd.edu (Postfix) with ESMTPSA id 4D486682ABD; Thu, 5 Dec 2013 05:48:40 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=cs.umd.edu; s=csmx; t=1386240520; bh=ybvkvdFOSs4+PJc1n0vIUbJcvaQEnpNq5spoOEZlQAQ=; h=Subject:From:In-Reply-To:Date:Cc:References:To; b=o0Ky7KPN5/PmY5M/8A7Bvryp1MsZhP3eitF32wyBbLkJ0hIBpSH9YkcnmyM3foYfa 7UAKRbhodFhXFY39WwPI/0C//IX+TMxdrbQmtWvXTdjmcYLCVLtkmt5UUbyIj2n4jA 2BiO8b7XXuMsydK2fCQMgmvcO5DXJQndh130h0ec= Content-Type: text/plain; charset=iso-8859-1 Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\)) From: Michael Hicks In-Reply-To: Date: Thu, 5 Dec 2013 05:48:36 -0500 Cc: OCaml Mailing List Content-Transfer-Encoding: quoted-printable Message-Id: References: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp> To: Tom Ridge X-Mailer: Apple Mail (2.1510) X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.3.8 (egg.cs.umd.edu [0.0.0.0]); Thu, 05 Dec 2013 05:48:40 -0500 (EST) X-CSD-MailScanner-ID: 4D486682ABD.A7B2E X-CSD-MailScanner: Found to be clean X-CSD-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-49.99, required 5, autolearn=not spam, ALL_TRUSTED -50.00, T_DKIM_INVALID 0.01) X-CSD-MailScanner-From: mwh@cs.umd.edu X-CSD-MailScanner-Watermark: 1386845321.34378@FmRsAL0hvoibI2K1IHicZQ 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 po= inted 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 you= r GC is a trace, and your data structure is a single linked list, then para= llel GC will get you nowhere (unless you do something interesting). Here ar= e 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 t= race over a fixed-sized data structure will thwart the performance of a pro= gram that would otherwise run in in sub linear time? For example, suppose y= ou 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., in= dependent 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 yo= ur program will be O(MN) not O(M log N) as you'd expect.=20 This analysis seems to work for a weird program and by doing some fishy acc= ounting (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 wro= te: > On 5 December 2013 01:09, Jacques Garrigue = wrote: >> 2013/12/04 21:20, Tom Ridge : >>=20 >>> Dear caml-list, >>>=20 >>> 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. >>>=20 >>> My question is: is it possible for OCaml's garbage collection to alter >>> the time complexity of my program? >>=20 >> I would say that, on a program that is already O(n^3), that would be ver= y surprising. >=20 > Surprising, but not impossible? >=20 >> What kind of measure did you do? >=20 > A rather basic measurement of the time the program takes (using /usr/bin/= time). >=20 >> 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). >=20 > 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). >=20 > I take Scherer's point that the question is not well-posed, so I am > thinking about how to phrase the question better. >=20 > 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. >=20 > Are there any pointers to analyses (not specific to OCaml) along these li= nes? >=20 >=20 >=20 >>=20 >> Jacques Garrigue >=20 > --=20 > 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