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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id D4B927EE6B for ; Wed, 4 Dec 2013 19:09:34 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=pra; client-ip=212.159.14.19; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jon@ffconsultancy.com) identity=mailfrom; client-ip=212.159.14.19; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="jon@ffconsultancy.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@avasout04.plus.net) identity=helo; client-ip=212.159.14.19; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jon@ffconsultancy.com"; x-sender="postmaster@avasout04.plus.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjADAItvn1LUnw4TlGdsb2JhbABagz+mQpJ0gSQWDgEBAQEHCwsJEiqCJQEBBAEIAh4SNBAHAQMCCREEAQEOGgcZIwkBCQgCBAESCwUCh14DCQoJukYDCocqjG2CGAaELQOPHIoolAw X-IPAS-Result: AjADAItvn1LUnw4TlGdsb2JhbABagz+mQpJ0gSQWDgEBAQEHCwsJEiqCJQEBBAEIAh4SNBAHAQMCCREEAQEOGgcZIwkBCQgCBAESCwUCh14DCQoJukYDCocqjG2CGAaELQOPHIoolAw X-IronPort-AV: E=Sophos;i="4.93,826,1378850400"; d="scan'208";a="39311263" Received: from avasout04.plus.net ([212.159.14.19]) by mail3-smtp-sop.national.inria.fr with ESMTP; 04 Dec 2013 19:09:34 +0100 Received: from XPS ([84.93.170.155]) by avasout04 with smtp id xW9X1m0023MWtks01W9Yqr; Wed, 04 Dec 2013 18:09:32 +0000 X-CM-Score: 0.00 X-CNFS-Analysis: v=2.1 cv=C6LQl2/+ c=1 sm=1 tr=0 a=6JWhQFVz1iwHKz4NtC63lQ==:117 a=6JWhQFVz1iwHKz4NtC63lQ==:17 a=0Bzu9jTXAAAA:8 a=waI2vsT-1KMA:10 a=Xub9RBUEA-sA:10 a=Kvk-SOs2Z7YA:10 a=kj9zAlcOel0A:10 a=r2vSxAw-AAAA:8 a=byhiMKDvd7QA:10 a=mK_AVkanAAAA:8 a=ZOzjf2MOAAAA:8 a=CjxXgO3LAAAA:8 a=l-VERuP2cdrX9BBF-0EA:9 a=7SbqrheNMZKq_GUl:21 a=cwBrSCvCq3V3ITXJ:21 a=CjuIK1q_8ugA:10 a=9xyTavCNlvEA:10 X-AUTH: jdh302:2500 Reply-To: From: "Jon Harrop" To: "'Tom Ridge'" , "'caml-list'" References: In-Reply-To: Date: Wed, 4 Dec 2013 18:09:31 -0000 Organization: Flying Frog Consultancy Ltd. Message-ID: <00cd01cef11b$fbe6c8e0$f3b45aa0$@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Outlook 14.0 Thread-Index: AQILtR6FePtFdpgRd7zHLdG0NxMsZpnKzTlw Content-Language: en-gb Subject: RE: [Caml-list] Question about garbage collection and impact on performance > is it possible for OCaml's garbage collection to alter the time complexity of my program? Yes. > If the answer is "yes", then are there any expectations I might have about how bad this alteration might be? I observed List.map taking O(n^2) time for large "n" because it leaks stack space and the GC traverses the O(n)-deep stack O(n) times during its execution. > 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 think you can just get an extra O(n). I'd also look out for very large arrays on the heap which, IIRC, cause O(n) pause. I haven't used OCaml in anger for a few years so take this with a grain of salt... :-) Cheers, Jon. -----Original Message----- From: tom.j.ridge@googlemail.com [mailto:tom.j.ridge@googlemail.com] On Behalf Of Tom Ridge Sent: 04 December 2013 12:21 To: caml-list 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 -- Caml-list mailing list. Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs