From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 4C0F2BC32 for ; Fri, 18 Mar 2005 19:45:01 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2IIj0ao013900 for ; Fri, 18 Mar 2005 19:45:01 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA05675 for ; Fri, 18 Mar 2005 19:45:00 +0100 (MET) Received: from qrnik.knm.org.pl (paf87.warszawa.sdi.tpnet.pl [217.96.225.87]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2IIiurM008892 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Fri, 18 Mar 2005 19:44:59 +0100 Received: from qrczak by qrnik.knm.org.pl with local (Exim 3.36 #1) id 1DCMSu-0002r5-00 for caml-list@inria.fr; Fri, 18 Mar 2005 19:44:56 +0100 To: caml-list@inria.fr Subject: Re: [Caml-list] OCaml troll on Slashdot X-Face: OW>RV&gN+&b-aiNY|U)f=S%w+/rK!);f>/W9IXg})]&F>ht.1Up8@04+_!gOp(_/l_-+E^. 2\vI)1=D,%HWiq)r(M/V~dr^5T^KF/[w5YZ4<0Sus3+O>l3uA/&W_21m?.s,Po8{pb0@ References: <20050316001819.GB347@first.in-berlin.de> <891bd33905031619484825e276@mail.gmail.com> <200503171016.18310.jon@ffconsultancy.com> <87acp213ui.fsf@qrnik.zagroda> From: "Marcin 'Qrczak' Kowalczyk" Mail-Followup-To: caml-list@inria.fr Date: Fri, 18 Mar 2005 19:44:56 +0100 In-Reply-To: (brogoff@speakeasy.net's message of "Fri, 18 Mar 2005 09:46:07 -0800 (PST)") Message-ID: <87br9gx07r.fsf@qrnik.zagroda> User-Agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: "Marcin 'Qrczak' Kowalczyk" X-Miltered: at nez-perce with ID 423B21AC.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 423B21A8.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 stack:01 recursion:01 recursion:01 heap:01 stack:01 heap:01 pointer:01 threads:01 sml:01 gc'ed:01 allocating:01 pointer:01 uncaught:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.2 X-Spam-Level: brogoff writes: >> It's not the fault of the mapping function but of the stack >> being non-extensible. A user-written recursion can blow it too. >> Functional programming is supposed to encourage recursion, and a >> non-tail-recursive 'map' is much more readable than alternatives. > > Interesting approach. Do you have any information as to how big the > performance hit is? No. I recall there was some paper which claimed that heap allocation is significantly more expensive than stack allocation even with the most clever GCs. I couldn't find it now. My stack frame allocation is very similar to heap allocation. What matters is not only the overhead of stack overflow checking itself, but the combined effect of several interdependent design choices. Even if I measured the cost of stack overflow checking in isolation, it would not give a meaningful answer because it requires and provides other things and thus the cost would be different if applied to an implementation with different properties. I implement a custom stack instead of using the system stack. Effects: - a C global variable is used for the stack pointer instead of a machine register, thus stack frame allocation and access to stack contents is slower (even if it was not checked for overflow) - checking for stack overflow adds overhead + tail call optimization is easier + scanning the stack by the GC is easier + portable green threads are easier + stack overflow is not fatal + triggering a context switch is done by faking the stack overflow condition, so it doesn't need an *additional* overhead (except that the stack limit is a volatile variable and allocation of a stack frame is one machine instruction longer because of that) > I've never used SML/NJ except for a few toy programs, but I recall > that it puts activation records on the Gc'ed heap (correct me if I'm > wrong someone) so that call/cc is more efficient, so stack overflows > shouldn't be a problem there either. Could you comment on why you > chose extensible stacks rather than the SMLNJ approach for Kogut. It should be slightly more efficient because allocating stack frames doesn't increase the frequency of GCs, because stack frames don't need to be copied by a copying GC, and because they don't need a link to the previous frame (they do have a "descriptor" pointer though, which stores their size and is also used to generate stack trace on uncaught exceptions). I haven't measured how large the efficiency difference is. It could even be negative, because I must deallocate a stack frame explicitly, but I doubt that. > What I think you intend is that you'd rather it be easy to write > safe code than that it be asy to write fast code, in the language. > I wouldn't mind that, as long as it isn't ridiculously hard or > impossible to do the latter in the language. It's hard to allow everything... The combined effect of dynamic typing, passing function arguments in C global variables, using a custom stack and stack overflow checking caused the Ackermann function to be 5 times slower than in C. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/