From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <tom.j.ridge@googlemail.com>
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 841FF7EE6B
	for <caml-list@sympa.inria.fr>; Wed,  4 Dec 2013 13:20:54 +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.171;
  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.171 as
  permitted sender) identity=mailfrom;
  client-ip=209.85.192.171;
  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-f171.google.com) identity=helo;
  client-ip=209.85.192.171;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="tom.j.ridge@googlemail.com";
  x-sender="postmaster@mail-pd0-f171.google.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AigDAEcdn1LRVcCrlGdsb2JhbABahBK6BAgWDgEBAQEHCwsJEiqCbAEBOBAVXRIBBQEiiAIBAw+lLosQhFIBBYQ+ChknDYckBpM4mBeQJhgpgWWCcDw
X-IPAS-Result: AigDAEcdn1LRVcCrlGdsb2JhbABahBK6BAgWDgEBAQEHCwsJEiqCbAEBOBAVXRIBBQEiiAIBAw+lLosQhFIBBYQ+ChknDYckBpM4mBeQJhgpgWWCcDw
X-IronPort-AV: E=Sophos;i="4.93,824,1378850400"; 
   d="scan'208";a="46910555"
Received: from mail-pd0-f171.google.com ([209.85.192.171])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 04 Dec 2013 13:20:53 +0100
Received: by mail-pd0-f171.google.com with SMTP id z10so22279643pdj.30
        for <caml-list@inria.fr>; Wed, 04 Dec 2013 04:20:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlemail.com; s=20120113;
        h=mime-version:sender:from:date:message-id:subject:to:content-type;
        bh=R0upf3ewjeQyCutMTFK450sAWpFXYVWukmPyWmWOWdA=;
        b=CHi7vwoG9b4FP+2O1OyQkMv1DzhHv+cSYjfAWbnYpEwmr+7Ymfi39ph4juO79JtDJ7
         xF91Y29BgrT04WGcs9s/RoQ5jnfvIfy0X5t+sYC9bmfw6o4ex0snN2x0Q++74uqLXmg2
         KNiRMLAux0gJA3ra9Ncp4eXLf5wiNnQKpNKKCZKHkvpb9TxjJMlrk8GlTrzg0aklP+Qa
         CwuCG3wGZnkhvHZ3V9+BpbGDHiHsIfyChdYLXBM1LKSx4hlnR+oU55J5+EwF0/1gZ3gT
         WlhhrNxdkwASe6EuOGS2GB4ysCpBvgQjhZ6yaoKPQfexiIGZAeI7gwXDtHze518fcXmL
         vV+g==
X-Received: by 10.68.253.67 with SMTP id zy3mr45366476pbc.137.1386159651523;
 Wed, 04 Dec 2013 04:20:51 -0800 (PST)
MIME-Version: 1.0
Sender: tom.j.ridge@googlemail.com
Received: by 10.70.79.136 with HTTP; Wed, 4 Dec 2013 04:20:31 -0800 (PST)
From: Tom Ridge <tom.j.ridge+list@googlemail.com>
Date: Wed, 4 Dec 2013 12:20:31 +0000
X-Google-Sender-Auth: -lbWl4PABeHa9UkNFgVsrrqJOI8
Message-ID: <CABooLwP7eSJ5Zc=3uSwCqU4a8Yy6a8bSm_74fQEhN=ceEzpdVw@mail.gmail.com>
To: caml-list <caml-list@inria.fr>
Content-Type: text/plain; charset=ISO-8859-1
Subject: [Caml-list] Question about garbage collection and impact on
 performance

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?

If the answer is "yes", then are there any expectations I might have
about how bad this alteration might be? For example, (without thinking
about it too hard) it seems unreasonable for GC to turn a polytime
program into an exponential time program, but is this actually true
for OCaml's garbage collector?

I have read some material on OCaml's GC, but I did not form any
intuitions yet about the answers to these questions.

Thanks in advance

Tom