From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
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 0093D7EE6B
	for <caml-list@sympa.inria.fr>; Thu,  5 Dec 2013 02:09:02 +0100 (CET)
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  garrigue@math.nagoya-u.ac.jp) identity=pra;
  client-ip=133.6.130.5;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="garrigue@math.nagoya-u.ac.jp";
  x-sender="garrigue@math.nagoya-u.ac.jp";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  garrigue@math.nagoya-u.ac.jp) identity=mailfrom;
  client-ip=133.6.130.5;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="garrigue@math.nagoya-u.ac.jp";
  x-sender="garrigue@math.nagoya-u.ac.jp";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@mailhost.math.nagoya-u.ac.jp) identity=helo;
  client-ip=133.6.130.5;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="garrigue@math.nagoya-u.ac.jp";
  x-sender="postmaster@mailhost.math.nagoya-u.ac.jp";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AkcBAGzRn1KFBoIFnGdsb2JhbABZvHyBNQ4BAQEBAQgUCTyCJQEBBAFDATUCAwsLRlcGE4dwAwkFsE+EWAKFAg1XhkQQB4xtgV4zB4MggROJQ45UhkWPBi0
X-IPAS-Result: AkcBAGzRn1KFBoIFnGdsb2JhbABZvHyBNQ4BAQEBAQgUCTyCJQEBBAFDATUCAwsLRlcGE4dwAwkFsE+EWAKFAg1XhkQQB4xtgV4zB4MggROJQ45UhkWPBi0
X-IronPort-AV: E=Sophos;i="4.93,829,1378850400"; 
   d="scan'208";a="47012219"
Received: from rabbit.math.nagoya-u.ac.jp (HELO mailhost.math.nagoya-u.ac.jp) ([133.6.130.5])
  by mail2-smtp-roc.national.inria.fr with ESMTP; 05 Dec 2013 02:09:00 +0100
Received: from mailhost.math.nagoya-u.ac.jp (localhost [127.0.0.1])
	by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id BABD263E9;
	Thu,  5 Dec 2013 10:08:57 +0900 (JST)
Received: from mailhost.math.nagoya-u.ac.jp (localhost [127.0.0.1])
	by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id 8332A3974;
	Thu,  5 Dec 2013 10:08:57 +0900 (JST)
DomainKey-Signature: h=Received:Subject:Mime-Version:Content-Type:From:In-Reply-To:Date:Cc:Content-Transfer-Encoding:Message-Id:References:To:X-Mailer; b=; c=nofws; d=math.nagoya-u.ac.jp; q=; s=alpha
Received: from [192.168.1.23] (bsdserver10-alias1.math.nagoya-u.ac.jp [172.16.62.1])
	by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTPSA id 41FBA2532;
	Thu,  5 Dec 2013 10:08:57 +0900 (JST)
Mime-Version: 1.0 (Mac OS X Mail 7.0 \(1822\))
Content-Type: text/plain; charset=iso-8859-1
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <CABooLwP7eSJ5Zc=3uSwCqU4a8Yy6a8bSm_74fQEhN=ceEzpdVw@mail.gmail.com>
Date: Thu, 5 Dec 2013 10:09:00 +0900
Cc: OCaml Mailing List <caml-list@inria.fr>
Content-Transfer-Encoding: quoted-printable
Message-Id: <1711883A-1A24-45E1-A105-453BAAEEE119@math.nagoya-u.ac.jp>
References: <CABooLwP7eSJ5Zc=3uSwCqU4a8Yy6a8bSm_74fQEhN=ceEzpdVw@mail.gmail.com>
To: Tom Ridge <tom.j.ridge+list@googlemail.com>
X-Mailer: Apple Mail (2.1822)
Subject: Re: [Caml-list] Question about garbage collection and impact on
 performance

2013/12/04 21:20, Tom Ridge <tom.j.ridge+list@googlemail.com>:

> 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?

I would say that, on a program that is already O(n^3), that would be very s=
urprising.
What kind of measure did you do?
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).

Jacques Garrigue=