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 B06267EE1D for ; Thu, 5 Dec 2013 11:08:50 +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.192.173; 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.192.173 as permitted sender) identity=mailfrom; client-ip=209.85.192.173; 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-pd0-f173.google.com) identity=helo; client-ip=209.85.192.173; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="postmaster@mail-pd0-f173.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqYCAGNPoFLRVcCtlGdsb2JhbABZDoQEuXwIFg4BAQEBBwsLCRIqgiUBAQQBQAEBNwEECwEKCw0uIhIBBQEcBhOHbwEDCQalDYsQhFIBBYRDChknDYcbEQaMb4ZLmBeQJhgpgWWCMT88 X-IPAS-Result: AqYCAGNPoFLRVcCtlGdsb2JhbABZDoQEuXwIFg4BAQEBBwsLCRIqgiUBAQQBQAEBNwEECwEKCw0uIhIBBQEcBhOHbwEDCQalDYsQhFIBBYRDChknDYcbEQaMb4ZLmBeQJhgpgWWCMT88 X-IronPort-AV: E=Sophos;i="4.93,832,1378850400"; d="scan'208";a="47092340" Received: from mail-pd0-f173.google.com ([209.85.192.173]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 05 Dec 2013 11:08:49 +0100 Received: by mail-pd0-f173.google.com with SMTP id p10so24361059pdj.32 for ; Thu, 05 Dec 2013 02:08:48 -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; bh=teRONPJRzyMIFy00Ha2wyaEGhAD8JSZ+/3F7CsQIBho=; b=BkOWVP7src5FwVZh5PDtaqkl3kDCAZt1jyRfLXsGh3i9Zim2BFGbj+/GPm1n2IMWbf 8IAHvLfxTSkAKpT/vjBS0NXlmIo8FTLVAT+q2beRG6z80wr3MCB7ihIs3NWb5C/Pbo7N R9RiIGh5yIqQn7MRSefKTL3iuKNGjpiyh9ghceXZ4RKOmMA7HXrlzLNxijDbTK0Jvrl4 OhLDtowa8luXUZu/n21W8+pOxIOvp7r+Szs9l8UuFrP9/TUQA43Quu4ybeLxcgyx9hib D8FYlcXL6PgF0iGfFvagnBJIISZ7/EOTFmw52qd65Dso8+RwtMC6B8q2sUnY+ZAbJR4r Ccjg== X-Received: by 10.68.244.2 with SMTP id xc2mr51556041pbc.58.1386238128307; Thu, 05 Dec 2013 02:08:48 -0800 (PST) MIME-Version: 1.0 Sender: tom.j.ridge@googlemail.com Received: by 10.70.79.136 with HTTP; Thu, 5 Dec 2013 02:08:27 -0800 (PST) In-Reply-To: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp> References: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp> From: Tom Ridge Date: Thu, 5 Dec 2013 10:08:27 +0000 X-Google-Sender-Auth: tDhULkFLNf8Gtxt0ryELuXov2-Y Message-ID: To: Jacques Garrigue Cc: OCaml Mailing List Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Question about garbage collection and impact on performance 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