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 DEEE67EE1D for ; Thu, 5 Dec 2013 11:37:13 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of mmatalka@gmail.com) identity=pra; client-ip=209.85.212.175; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="mmatalka@gmail.com"; x-sender="mmatalka@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of mmatalka@gmail.com designates 209.85.212.175 as permitted sender) identity=mailfrom; client-ip=209.85.212.175; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="mmatalka@gmail.com"; x-sender="mmatalka@gmail.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-wi0-f175.google.com) identity=helo; client-ip=209.85.212.175; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="mmatalka@gmail.com"; x-sender="postmaster@mail-wi0-f175.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqYCAGRWoFLRVdSvlGdsb2JhbABZgma6GIEYFg4BAQEBBwsLCRIqgiUBAQQBQAEbHQEDAQsGBQsNCSUPAQQPEQEFASITh28BAwkGAQSlFIxZgwmESgoZJw1khjcRAQUMjGOCEQeEMwOYFJAmQYRV X-IPAS-Result: AqYCAGRWoFLRVdSvlGdsb2JhbABZgma6GIEYFg4BAQEBBwsLCRIqgiUBAQQBQAEbHQEDAQsGBQsNCSUPAQQPEQEFASITh28BAwkGAQSlFIxZgwmESgoZJw1khjcRAQUMjGOCEQeEMwOYFJAmQYRV X-IronPort-AV: E=Sophos;i="4.93,832,1378850400"; d="scan'208";a="47099824" Received: from mail-wi0-f175.google.com ([209.85.212.175]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 05 Dec 2013 11:37:13 +0100 Received: by mail-wi0-f175.google.com with SMTP id hi5so9667284wib.14 for ; Thu, 05 Dec 2013 02:37:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=oIFutcw16Py3dlmoy2MoMuT2MWwKEH0EZZRURcvLbwc=; b=PfeLpVOr4hQoNHlHZ0qGi7pT9YIxcyvRirSn3wCnj7t1/gCi4qwl7brEH+1AJZ2xSj bZJ4/A1QqNTA9n/rkBCCXqpY8SbLDR4WqE6dpuPSqBv5Th2YE3IhsZNOL0YBDB1aMMJW YsDCMKOj0s70SpoCAzJR3V+RR15dFGdXLKD5+ZpBQ2Rh2BGaMjwh0ZTEWMCIgjAWNmsC xifnS9h/4Sq9hNCRFUoOXfQ4wfigXx6geDSi9A9VoAvBjimIJdl+fuQiIJrGoU2F4Ehy oSGGmhlcSWwIQkVrTaes/u9SBegb4R83zdPSJUn0EGcVVmpg7lNjz43xo7Zkq6rMdY+0 8wzA== X-Received: by 10.194.143.100 with SMTP id sd4mr11770535wjb.69.1386239833016; Thu, 05 Dec 2013 02:37:13 -0800 (PST) Received: from localhost ([2a01:7e00::f03c:91ff:fe70:2696]) by mx.google.com with ESMTPSA id fu1sm4972997wib.8.2013.12.05.02.37.12 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 05 Dec 2013 02:37:12 -0800 (PST) From: Malcolm Matalka To: Tom Ridge Cc: Jacques Garrigue , OCaml Mailing List References: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp> Date: Thu, 05 Dec 2013 10:37:11 +0000 In-Reply-To: (Tom Ridge's message of "Thu, 5 Dec 2013 10:08:27 +0000") Message-ID: <87pppbr3c8.fsf@gmail.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain Subject: Re: [Caml-list] Question about garbage collection and impact on performance Perhaps posting some experiments would help people help you. In particular it would be nice to see: - The actual timings of what you consider a good run and a bad run - Those runs with verbose gc turned on - Amount of memory consumption - The timings for if you jack up the amount of memory that the runtime system is allowed to use on both a good run and a bad run to determine the system In short, the answer to your question seems to be "maybe". But enough information has not been provided to suggest if it's responsible for what you're seeing or just a theoretical possibility. Tom Ridge writes: > 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