From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <mmatalka@gmail.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 71E747EE6B
	for <caml-list@sympa.inria.fr>; Wed,  4 Dec 2013 13:43:55 +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.173;
  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.173 as permitted
  sender) identity=mailfrom; client-ip=209.85.212.173;
  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-f173.google.com) identity=helo;
  client-ip=209.85.212.173;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="mmatalka@gmail.com";
  x-sender="postmaster@mail-wi0-f173.google.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ah4DAEcjn1LRVdStlGdsb2JhbABagma6FYEjFg4BAQEBBwsLCRIqgiUBAQQBQAEbHQEDAQsGBQsWJQ8BBA8RAQUBIhOHbwEDCQYBBKUrjFmDCYRKChknDWSGLxEBBQyMYYIRB4QzA5gUkCZBhFU
X-IPAS-Result: Ah4DAEcjn1LRVdStlGdsb2JhbABagma6FYEjFg4BAQEBBwsLCRIqgiUBAQQBQAEbHQEDAQsGBQsWJQ8BBA8RAQUBIhOHbwEDCQYBBKUrjFmDCYRKChknDWSGLxEBBQyMYYIRB4QzA5gUkCZBhFU
X-IronPort-AV: E=Sophos;i="4.93,824,1378850400"; 
   d="scan'208";a="46913422"
Received: from mail-wi0-f173.google.com ([209.85.212.173])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 04 Dec 2013 13:43:41 +0100
Received: by mail-wi0-f173.google.com with SMTP id hn9so3767127wib.0
        for <caml-list@inria.fr>; Wed, 04 Dec 2013 04:43:40 -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=sZSfn5L/WaxiDDZB4IU9XrjN/LI9dQXynVQsjQbwBCg=;
        b=JzsA6fzOfJx5wLhk7yDBOd7yQ/r7RRhDpCQLcCfV/z64eW4v+Hc/km8/J47xZqVoeF
         IuohJTnbo2h4ngbnbmJj/LBBSkEtjGcKReVfZpS8GeHUCmd5sQ8k3rEChqnUUtC27+CV
         jTzHJT0Q+ynyDTCIZ7oKUmjKljOc8qkEsfTAfDxQuuD3pCCGNZ7a6EWHilMhnzjxMW+L
         XlEdz3ut5aen+z3Cz/2BBvKJ4iWzxVjD2r9BYzzzyE5xvWhxdGXruJxBeyvqBcc/4I5/
         +LRQiBphxdzJ5wuflaGqjmYikVQxR0fR/3AvW+ck0YZwp4KeDEgfl2j7EhQ+kZn34Sb9
         Uxww==
X-Received: by 10.180.95.105 with SMTP id dj9mr7156181wib.22.1386161020877;
        Wed, 04 Dec 2013 04:43:40 -0800 (PST)
Received: from localhost ([2a01:7e00::f03c:91ff:fe70:2696])
        by mx.google.com with ESMTPSA id o9sm6599657wib.10.2013.12.04.04.43.40
        for <multiple recipients>
        (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
        Wed, 04 Dec 2013 04:43:40 -0800 (PST)
From: Malcolm Matalka <mmatalka@gmail.com>
To: Tom Ridge <tom.j.ridge+list@googlemail.com>
Cc: caml-list <caml-list@inria.fr>
References: <CABooLwP7eSJ5Zc=3uSwCqU4a8Yy6a8bSm_74fQEhN=ceEzpdVw@mail.gmail.com>
Date: Wed, 04 Dec 2013 12:43:39 +0000
In-Reply-To: <CABooLwP7eSJ5Zc=3uSwCqU4a8Yy6a8bSm_74fQEhN=ceEzpdVw@mail.gmail.com>
	(Tom Ridge's message of "Wed, 4 Dec 2013 12:20:31 +0000")
Message-ID: <87eh5su6pw.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

Have you tried turning on verbose gc so you can determine how much of
your algorithm's time is actually spent in GC?

Tom Ridge <tom.j.ridge+list@googlemail.com> writes:

> 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