From: Bruce Hoult Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: expensive procedure calls References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net> User-Agent: MT-NewsWatcher/3.0 (PPC) Message-ID: Lines: 22 Date: Tue, 26 Feb 2002 14:04:30 +1300 NNTP-Posting-Host: 203.79.84.98 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1014685470 203.79.84.98 (Tue, 26 Feb 2002 14:04:30 NZDT) NNTP-Posting-Date: Tue, 26 Feb 2002 14:04:30 NZDT Organization: TelstraClear Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!enews.sgi.com!news.xtra.co.nz!newsfeed01.tsnz.net!news02.tsnz.net!bruce Xref: chonsp.franklin.ch alt.folklore.computers:102784 In article , name99@mac.com (Maynard Handley) wrote: > Ah, once again the "blindingly fast because of no function call overhead" > claim. If you look at any decent RISC machine (like a PPC) there IS no > function call "overhead". The set of things that are done on a function > call is exactly the same as the set of things that are done in a set of > goto's faking a function call. This is even more true when you have a compiler that supports tail-call elimination. See Guy Steele's 1977 paper: "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977. http://library.readscheme.org/page1.html ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-443.pdf It's about the PDP-10, but the same things apply to modern RISCs too. -- Bruce ###### From: jmfbahciv@aol.com Newsgroups: alt.folklore.computers Subject: Re: expensive procedure calls Date: Thu, 28 Feb 02 09:40:18 GMT Organization: UltraNet Communications, Inc. Lines: 15 Message-ID: References: <3C72FD44.2058A1ED@ev1.net>

<3C7D021B.2EF21467@hda.hydro.com>Organization: LJK Software X-Trace: UmFuZG9tSVaJK+fwXdBkfHGdsIbidaSm2Tl6YU0vQgJjBP7FwIDrat0JkUAAHi0t X-Complaints-To: abuse@rcn.com NNTP-Posting-Date: 28 Feb 2002 11:56:30 GMT X-Newsreader: News Xpress Version 1.0 Beta #4 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!news.stealth.net!dc1.nntp.concentric.net!newsfeed.concentric.net!feed2.news.rcn.net!feed1.news.rcn.net!rcn!208-59-181-106 Xref: chonsp.franklin.ch alt.folklore.computers:102847 [get rid of all those newsgroups] In article , Kilgallen@SpamCop.net (Larry Kilgallen) wrote: >Or Ada95. I have been lobotomized :-(. When I read this phrase, I thought "Misoft is doing ADA now?" /BAH Subtract a hundred and four for e-mail. ###### From: Alberto Moreira Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Wed, 27 Feb 2002 09:27:57 -0500 Organization: MV Communications, Inc. Lines: 43 Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: bnh-5-07.mv.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: pyrite.mv.net 1014819795 821 199.125.98.7 (27 Feb 2002 14:23:15 GMT) X-Complaints-To: abuse@mv.com NNTP-Posting-Date: 27 Feb 2002 14:23:15 GMT X-Newsreader: Forte Agent 1.9/32.560 X-No-Archive: yes Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!newsfeed.stanford.edu!headwall.stanford.edu!unlnews.unl.edu!newsreader.wustl.edu!news.mv.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102773 Bruce Hoult said: >In article , name99@mac.com >(Maynard Handley) wrote: > >> Ah, once again the "blindingly fast because of no function call overhead" >> claim. If you look at any decent RISC machine (like a PPC) there IS no >> function call "overhead". The set of things that are done on a function >> call is exactly the same as the set of things that are done in a set of >> goto's faking a function call. > >This is even more true when you have a compiler that supports tail-call >elimination. Converting a program to tail form is basically a process of recursion elimination: replace your calls with gotos by making every recursion a tail recursion and using the concept of continuation to make sure that once you goto a piece of code you never need to come back. It's a cool way of doing things ! Read, for example, Andrew Appel's "Compiling with Continuations". The problem is, the compiler has to change the user program to do that, maybe pretty deeply, and that can be a problem for debuggers. Scheme compilers do that as a matter of fact, but then, go try to single step through code, on a line by line basis, and you'll see how hard things can get. Dr. Scheme, for example, has a pretty good debugger, but once you get out of beginner mode and use the language to its fullest, debugging capabilities fast decrease. Also, the semantics of your programming language must be amenable to tail-form conversion. If the semantics of the language demands that you keep multiply nested stack frames with linkages to both statically and dynamically nested contexts, like Pascal for example, I'm not even sure conversion to tail form is feasible. You may also get in trouble if your programming language requires a call-by-name semantics, like Algol for example. Dynamic binding will also cause grief. Object orientation may require virtual functions and other complex semantics that may not be easily amenable to a tail-form treatment. So, yes, there can be such a thing as a procedure call overhead. Alberto. ###### From: Sander Vesik Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Wed, 27 Feb 2002 15:44:18 +0000 (UTC) Organization: ERA/EKI FO Lines: 40 Message-ID: <1014824655.920433@haldjas.folklore.ee> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: haldjas.folklore.ee X-Trace: kadri.ut.ee 1014824658 3800 193.40.6.121 (27 Feb 2002 15:44:18 GMT) X-Complaints-To: usenet@kadri.ut.ee NNTP-Posting-Date: Wed, 27 Feb 2002 15:44:18 +0000 (UTC) User-Agent: tin/1.5.9-20010723 ("Chord of Souls") (UNIX) (FreeBSD/4.3-RELEASE (i386)) Cache-Post-Path: haldjas.folklore.ee!unknown@localhost X-Cache: nntpcache 2.3.2 (see http://www.nntpcache.org/) Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!logbridge.uoregon.edu!gestalt.direcpc.com!news.stealth.net!newsfeed.song.fi!news.cs.hut.fi!newsfeed2.funet.fi!newsfeed1.funet.fi!newsfeeds.funet.fi!newsfeed.uninet.ee!news.ut.ee!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102701 In comp.arch Alberto Moreira wrote: > Bruce Hoult said: > >>In article , name99@mac.com >>(Maynard Handley) wrote: >> >>> Ah, once again the "blindingly fast because of no function call overhead" >>> claim. If you look at any decent RISC machine (like a PPC) there IS no >>> function call "overhead". The set of things that are done on a function >>> call is exactly the same as the set of things that are done in a set of >>> goto's faking a function call. >> >>This is even more true when you have a compiler that supports tail-call >>elimination. > > Converting a program to tail form is basically a process of recursion > elimination: replace your calls with gotos by making every recursion a > tail recursion and using the concept of continuation to make sure that > once you goto a piece of code you never need to come back. It's a cool > way of doing things ! Read, for example, Andrew Appel's "Compiling > with Continuations". The problem is, the compiler has to change the No, you can in principle apply it to vanilla C - see for example http://www.sics.se/~psm/sparcstack.html it just depends on how your architecture looks like, what assumptions are being made and similar. Also, in many processors, there is no such thing as a "procedure call" there are just jumps and som conventions on how registers are treated and where you jump to when finished. Which definately allows you to do tail-call elimination, unles sthe conventions specifcly disallow that. > > Alberto. > -- Sander +++ Out of cheese error +++ ###### From: Terje Mathisen Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Wed, 27 Feb 2002 16:58:19 +0100 Organization: Hydro Lines: 15 Message-ID: <3C7D021B.2EF21467@hda.hydro.com> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: 136.164.29.33 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.78 [en] (Windows NT 5.0; U) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!fr.usenet-edu.net!usenet-edu.net!news.tele.dk!small.news.tele.dk!193.213.112.26!newsfeed1.ulv.nextra.no!nextra.com!hydro.com!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102650 Alberto Moreira wrote: > Also, the semantics of your programming language must be amenable to > tail-form conversion. If the semantics of the language demands that > you keep multiply nested stack frames with linkages to both statically > and dynamically nested contexts, like Pascal for example, I'm not even > sure conversion to tail form is feasible. You may also get in trouble There's absolutely nothing that stops a Pascal compiler from generating C-style code as long as the source code doesn't use any variables from linked contexts, right? Terje -- - "almost all programming can be viewed as an exercise in caching" ###### From: nmm1@cus.cam.ac.uk (Nick Maclaren) Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 27 Feb 2002 16:19:26 GMT Organization: University of Cambridge, England Lines: 24 Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<3C7D021B.2EF21467@hda.hydro.com> NNTP-Posting-Host: libra.cus.cam.ac.uk Originator: nmm1@libra.cus.cam.ac.uk Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!fu-berlin.de!server1.netnews.ja.net!pegasus.csx.cam.ac.uk!nmm1 Xref: chonsp.franklin.ch alt.folklore.computers:102730 In article <3C7D021B.2EF21467@hda.hydro.com>, Terje Mathisen writes: |> Alberto Moreira wrote: |> > Also, the semantics of your programming language must be amenable to |> > tail-form conversion. If the semantics of the language demands that |> > you keep multiply nested stack frames with linkages to both statically |> > and dynamically nested contexts, like Pascal for example, I'm not even |> > sure conversion to tail form is feasible. You may also get in trouble |> |> There's absolutely nothing that stops a Pascal compiler from generating |> C-style code as long as the source code doesn't use any variables from |> linked contexts, right? Yes, but that is only one such constraint. Consider a language with automatic destructors at function return (e.g. alloca). Regards, Nick Maclaren, University of Cambridge Computing Service, New Museums Site, Pembroke Street, Cambridge CB2 3QH, England. Email: nmm1@cam.ac.uk Tel.: +44 1223 334761 Fax: +44 1223 334679 ###### Message-ID: <3C7D0938.A5925904@yahoo.com> From: CBFalconer Reply-To: cbfalconer@worldnet.att.net Organization: Ched Research X-Mailer: Mozilla 4.75 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 52 Date: Wed, 27 Feb 2002 16:38:49 GMT NNTP-Posting-Host: 12.90.183.94 X-Complaints-To: abuse@worldnet.att.net X-Trace: bgtnsc04-news.ops.worldnet.att.net 1014827929 12.90.183.94 (Wed, 27 Feb 2002 16:38:49 GMT) NNTP-Posting-Date: Wed, 27 Feb 2002 16:38:49 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!feedme.news.mediaways.net!netnews.com!howland.erols.net!news-out.worldnet.att.net.MISMATCH!wn3feed!worldnet.att.net!135.173.83.71!wnfilter1!worldnet-localpost!bgtnsc04-news.ops.worldnet.att.net.POSTED!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102808 Alberto Moreira wrote: > ... snip ... > > Also, the semantics of your programming language must be amenable to > tail-form conversion. If the semantics of the language demands that > you keep multiply nested stack frames with linkages to both statically > and dynamically nested contexts, like Pascal for example, I'm not even > sure conversion to tail form is feasible. You may also get in trouble > if your programming language requires a call-by-name semantics, like > Algol for example. Dynamic binding will also cause grief. Object > orientation may require virtual functions and other complex semantics > that may not be easily amenable to a tail-form treatment. In Pascal, I often write something like: FUNCTION doit(what : whatever) : whatnot; FUNCTION recurse(control : integer); BEGIN IF control > 0 THEN recurse = what + recurse(control - 1); ELSE recurse = 0; END; BEGIN doit = recurse(what); END; and the inner can be easily recast in terms of an iteration, something like: result : integer; result = 0; WHILE control > 0 DO BEGIN result = result + what; control = control - 1; END; Which is especially useful to avoid access problems to what. Notice that the breakup avoids having to redundantly pass what. The coding is probably nonsense, just something to get the ideas across. -- Chuck F (cbfalconer@yahoo.com) (cbfalconer@XXXXworldnet.att.net) Available for consulting/temporary embedded and systems. (Remove "XXXX" from reply address. yahoo works unmodified) mailto:uce@ftc.gov (for spambots to harvest) ###### From: Kilgallen@SpamCop.net (Larry Kilgallen) Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 27 Feb 2002 10:39:39 -0600 Organization: Berbee Information Networks Corporation Lines: 19 Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<3C7D021B.2EF21467@hda.hydro.com> Organization: LJK Software NNTP-Posting-Host: eisner.encompasserve.org X-Trace: grandcanyon.binc.net 1014827982 31861 192.135.80.34 (27 Feb 2002 16:39:42 GMT) X-Complaints-To: abuse@binc.net NNTP-Posting-Date: Wed, 27 Feb 2002 16:39:42 +0000 (UTC) Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!iad-peer.news.verio.net!news.verio.net!washdc3-snh1.gtei.net!chcgil2-snf1.gtei.net!news.gtei.net!news.binc.net!kilgallen Xref: chonsp.franklin.ch alt.folklore.computers:102765 In article , nmm1@cus.cam.ac.uk (Nick Maclaren) writes: > > In article <3C7D021B.2EF21467@hda.hydro.com>, > Terje Mathisen writes: > |> Alberto Moreira wrote: > |> > Also, the semantics of your programming language must be amenable to > |> > tail-form conversion. If the semantics of the language demands that > |> > you keep multiply nested stack frames with linkages to both statically > |> > and dynamically nested contexts, like Pascal for example, I'm not even > |> > sure conversion to tail form is feasible. You may also get in trouble > |> > |> There's absolutely nothing that stops a Pascal compiler from generating > |> C-style code as long as the source code doesn't use any variables from > |> linked contexts, right? > > Yes, but that is only one such constraint. Consider a language > with automatic destructors at function return (e.g. alloca). Or Ada95. ###### From: Bruce Hoult Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

User-Agent: MT-NewsWatcher/3.0 (PPC) Message-ID: Lines: 144 Date: Thu, 28 Feb 2002 12:26:20 +1300 NNTP-Posting-Host: 203.79.124.177 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1014852376 203.79.124.177 (Thu, 28 Feb 2002 12:26:16 NZDT) NNTP-Posting-Date: Thu, 28 Feb 2002 12:26:16 NZDT Organization: TelstraClear Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!hub1.nntpserver.com!nntp-relay.ihug.net!usenet.net.nz!newsfeeds.ihug.co.nz!ihug.co.nz!newsfeed01.tsnz.net!news02.tsnz.net!bruce Xref: chonsp.franklin.ch alt.folklore.computers:102886 In article , Alberto Moreira wrote: > Bruce Hoult said: > > >In article , name99@mac.com > >(Maynard Handley) wrote: > > > >> Ah, once again the "blindingly fast because of no function call > >> overhead" > >> claim. If you look at any decent RISC machine (like a PPC) there IS no > >> function call "overhead". The set of things that are done on a > >> function > >> call is exactly the same as the set of things that are done in a set > >> of goto's faking a function call. > > > >This is even more true when you have a compiler that supports tail-call > >elimination. > > Converting a program to tail form is basically a process of recursion > elimination: replace your calls with gotos by making every recursion a > tail recursion and using the concept of continuation to make sure that > once you goto a piece of code you never need to come back. It's a cool > way of doing things ! Read, for example, Andrew Appel's "Compiling > with Continuations". An old book, and out of date with respect to how modern ML compilers work, but still enlightening. > The problem is, the compiler has to change the > user program to do that, maybe pretty deeply, and that can be a > problem for debuggers. Scheme compilers do that as a matter of fact, > but then, go try to single step through code, on a line by line basis, > and you'll see how hard things can get. There are many things that god compilers do in production mode that make debugging harder. That's why you have debugging and production modes. Note that a program compiled with tail-call elimination is *exactly* as hard (or easy) to debug as a program written with loops in the first place. Take, for example, a silly factorial program. With a tail-recursive function: define method factorial(n :: ) local fact(n, prod) if (n = 0) prod else fact(n - 1, n * prod) end end fact; fact(n, 1) end factorial; With a loop: define method factorial1(n :: ) let prod = 1; while (n != 0) prod := n * prod; n := n - 1; end; prod; end factorial1; With a compiler doing tail-call elimination these two functions produce *identical* machine code. The debugability is the same in both cases. But, turn off the tail-call elimination and the first version becomes *more* debuggable, because you can examine the entire history of the computation by stepping up and down the stack frames. > Also, the semantics of your programming language must be amenable to > tail-form conversion. If the semantics of the language demands that > you keep multiply nested stack frames with linkages to both statically > and dynamically nested contexts, like Pascal for example, I'm not even > sure conversion to tail form is feasible. Pascal is identical to Scheme, Dylan and Common Lisp in this regard. All are lexically scoped. In fact, if you think about it you'll find that tail-call elimination would make this *easier* in Pascal, because it means that you don't have to skip over the stack frames of intermediate recursive invocations of the current function -- they've all been collapsed into a single stack frame. BTW, modern lexically-scoped language implementations don't use either of the methods commonly used when Pascal was developed (maintaining a static link in each stack frame, or maintaining a "display"). Instead each function is passed an environment structure containing a pointer to each uplevel variable that it uses. This is needed to implement closures (which Pascal doesn't have), but is more efficient overall anyway. > You may also get in trouble > if your programming language requires a call-by-name semantics, like > Algol for example. Call-by-name is just the passing of a function (a closure actually) that accesses the appropriate value. You can express this directly in many modern languages -- generally precisely those which have tail-call elimination, as it happens :-) > Dynamic binding will also cause grief. Dynamic binding is evil for many reasons :-) The most common implementation these days (e.g. in Common Lisp's "special" variables, and Perl's "local" variables) is to use a single global varable and have each function save the original global value and restore it prior to returning. This "restoring before returning" makes a function, by definition, not suitable for tail-call elimination, though if the function is otherwise self-recursive a compiler can collapse multiple levels of restoring into one, since most of the restored values are never used anwyay. > Object orientation may require virtual functions and other complex > semantics that may not be easily amenable to a tail-form treatment. Arbitrarily compilicated dispatch functions present no problem for tail-call elimination, provided that they don't need to do any cleanup after the called virtual function returns. This is normally the case, with the only exceptions I know of being when Common Lisp's method combination facility is being used. > So, yes, there can be such a thing as a procedure call overhead. Yes, but fortunately the cases where it is a significant proportion of the total runtime are usually exactly those where it can be reduced or eliminated :-) -- Bruce ###### From: Bruce Hoult Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<3C7D021B.2EF21467@hda.hydro.com> User-Agent: MT-NewsWatcher/3.0 (PPC) Message-ID: Lines: 19 Date: Thu, 28 Feb 2002 12:28:58 +1300 NNTP-Posting-Host: 203.79.124.177 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1014852534 203.79.124.177 (Thu, 28 Feb 2002 12:28:54 NZDT) NNTP-Posting-Date: Thu, 28 Feb 2002 12:28:54 NZDT Organization: TelstraClear Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!logbridge.uoregon.edu!nntp-relay.ihug.net!newsfeeds.ihug.co.nz!ihug.co.nz!newsfeed01.tsnz.net!news02.tsnz.net!bruce Xref: chonsp.franklin.ch alt.folklore.computers:102888 In article <3C7D021B.2EF21467@hda.hydro.com>, Terje Mathisen wrote: > Alberto Moreira wrote: > > Also, the semantics of your programming language must be amenable to > > tail-form conversion. If the semantics of the language demands that > > you keep multiply nested stack frames with linkages to both statically > > and dynamically nested contexts, like Pascal for example, I'm not even > > sure conversion to tail form is feasible. You may also get in trouble > > There's absolutely nothing that stops a Pascal compiler from generating > C-style code as long as the source code doesn't use any variables from > linked contexts, right? That's right. And when you do need it, the compiler can pass in such variables (or pointers to them) as extra arguments, or gathered together in a struct as a single argument. -- Bruce ###### From: Tim Bradshaw Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 28 Feb 2002 00:28:54 +0000 Organization: The autonomous system Sender: tfb@lostwithiel Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: lostwithiel.cley.com X-NNTP-Posting-Host: lostwithiel.cley.com:212.240.242.98 X-Trace: news.demon.co.uk 1014865370 nnrp-10:15112 NO-IDENT lostwithiel.cley.com:212.240.242.98 X-Complaints-To: abuse@demon.net User-Agent: Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.1 (Cuyahoga Valley) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Lines: 49 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news2.euro.net!dispose.news.demon.net!news.demon.co.uk!demon!lostwithiel.cley.com!lostwithiel!nobody Xref: chonsp.franklin.ch alt.folklore.computers:102817 * Bruce Hoult wrote: > Dynamic binding is evil for many reasons :-) The most common > implementation these days (e.g. in Common Lisp's "special" variables, > and Perl's "local" variables) is to use a single global varable and have > each function save the original global value and restore it prior to > returning. I kind of hope that this is not how most systems do it as it's absolutely toxic to multithreaded systems that genuinely use more than one processor (assuming you don't want dynamic bindings to be visible from other threads). For systems that don't it merely makes context switching expensive. In order to do this right you pretty much need a stack of values (deep binding vs your shallow binding). An interim solution (which I think I made up but someone is probably using it) would be to have a sort-of two-level shallow-binding scheme: each process has a little table of bound variables. When dynamically binding you check if you are about to clobber the real global value, and if you are put the value in the table. Further bindings within the thread can just clobber the value in the table as in shallow binding. This means you only ever need to do a two-level lookup for the value. I rather doubt that dynamic binding is used heavily enough and in performance-critical places nowadays (outside elisp) to make this worth the implementation effort. On the other hand it's incredibly useful when you do want it, so ... I'd be interested in knowing if anyone has ever implemented this two-level scheme. > This "restoring before returning" makes a function, by definition, not > suitable for tail-call elimination, though if the function is otherwise > self-recursive a compiler can collapse multiple levels of restoring into > one, since most of the restored values are never used anwyay. Yes. > Arbitrarily compilicated dispatch functions present no problem for > tail-call elimination, provided that they don't need to do any cleanup > after the called virtual function returns. This is normally the case, > with the only exceptions I know of being when Common Lisp's method > combination facility is being used. I think this must be right, although I think that in CL systems what generally happens is an effective-method gets computed (once, and cached), and then called, this call is then a tail call, but the `user' methods which went to make up the effective method may not be being tail called because of after methods & so on. --tim ###### From: Bruce Hoult Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

User-Agent: MT-NewsWatcher/3.0 (PPC) Message-ID: Lines: 42 Date: Thu, 28 Feb 2002 16:46:26 +1300 NNTP-Posting-Host: 203.79.124.177 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1014867987 203.79.124.177 (Thu, 28 Feb 2002 16:46:27 NZDT) NNTP-Posting-Date: Thu, 28 Feb 2002 16:46:27 NZDT Organization: TelstraClear Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!cyclone2.usenetserver.com!usenetserver.com!news02.tsnz.net!bruce Xref: chonsp.franklin.ch alt.folklore.computers:102891 In article , Tim Bradshaw wrote: > * Bruce Hoult wrote: > > > Dynamic binding is evil for many reasons :-) The most common > > implementation these days (e.g. in Common Lisp's "special" variables, > > and Perl's "local" variables) is to use a single global varable and > > have each function save the original global value and restore it prior > > to returning. > > I kind of hope that this is not how most systems do it as it's > absolutely toxic to multithreaded systems that genuinely use more than > one processor (assuming you don't want dynamic bindings to be visible > from other threads). For systems that don't it merely makes context > switching expensive. True. Where I said "single global variable" I probably could have said "single *thread* global variable". One of those little things that you gloss over when trying to explain specialized things in newsgroups not devoted to that speciality -- no doubt anyone who is that interested can get the real oil in comp.lang.lisp. > > Arbitrarily compilicated dispatch functions present no problem for > > tail-call elimination, provided that they don't need to do any cleanup > > after the called virtual function returns. This is normally the case, > > with the only exceptions I know of being when Common Lisp's method > > combination facility is being used. > > I think this must be right, although I think that in CL systems what > generally happens is an effective-method gets computed (once, and > cached), and then called, this call is then a tail call, but the > `user' methods which went to make up the effective method may not be > being tail called because of after methods & so on. Right. The net effect is that if the user function is written to make tail-recursive calls to the Generic Function ("virtual" function to C++ people) then you can't get tail-call elimination from the user function and back through the effective method. -- Bruce ###### From: Terje Mathisen Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Thu, 28 Feb 2002 09:45:57 +0100 Organization: Hydro Lines: 103 Message-ID: <3C7DEE45.C1F8A4BA@hda.hydro.com> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: no115350c8.hda.hydro.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.78 [en] (Windows NT 5.0; U) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.algonet.se!algonet!news.tele.dk!small.news.tele.dk!193.213.112.26!newsfeed1.ulv.nextra.no!nextra.com!hydro.com!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102826 Bruce Hoult wrote: > > In article , Alberto > Moreira wrote: > > So, yes, there can be such a thing as a procedure call overhead. > > Yes, but fortunately the cases where it is a significant proportion of > the total runtime are usually exactly those where it can be reduced or > eliminated :-) I've done something almost unheard of in this regard: I've actually tried multiple different implementation methods, all written in both C and asm to get full control, and then timed them, just to find the fastest method. Yeah, I know that this is bad 'cause it can stop a nice discussion, but I wanted to win a competition, so please excuse me. :-) What I had was a classic recursive function, with a known maximum call depth (11 or 12, depending upon how it was setup). The recursive function was working with a set of 4 parameters, the last of them was the call depth counter to determine when to exit, and the three first was combined into a 96-bit bitmask. I tried full unrolling, which got rid of the fourth parameter, as well as manual stack handling, but the fastest approach was plain CALL/PUSHA/.../POPA/RET recursion, saving _all_ registers on entry to the function, and restoring them on the way out. Later on I improved this by a few percent by splitting the function into two: One that worked like the one above, but without any checking to see if the innermost level was reached: Instead it called a smaller version of itself when it was possible to determine that only 64 or less bits was still active in that bitmask. A few years later the C version of this code, which was written to be as portable as possible, was entered (not by me, I only learned about it in a Google search a short while ago! :-) in a similar competition in France, where it was also twice as fast as the second-fastest entry. Anyway, the important part is that plain recursion can indeed be very fast, in my case it was almost certainly due to keeping the code working set really small, since the data was the same for all versions. Terje PS. Here's the original (simplified) C version, notice the enormous amount of comments! :-) Anyone wants to guess what it does? void bTry(ul b0, ul b1, ul b2, int piecesleft) { int p; ul *pbm, bm; while (((long) b0) < 0) { b0 += b0 + (b1 >> 31); b1 += b1 + (b2 >> 31); b2 += b2; } p = --piecesleft; do { pbm = bPieces[p]; bPieces[p] = bPieces[piecesleft]; bPieces[piecesleft] = pbm; bm = *pbm++; do { if ((bm & b0) == 0) { b0 |= bm; bsoltab[piecesleft] = bm; if (piecesleft == 0) goto haveSolution; bTry(b0, b1, b2, piecesleft); b0 ^= bm; } bm = *pbm++; } while (bm); pbm = bPieces[p]; bPieces[p] = bPieces[piecesleft]; bPieces[piecesleft] = pbm; } while (--p >= 0); return; haveSolution: bsaveSol(); return; } Here's -- - "almost all programming can be viewed as an exercise in caching" ###### From: Alberto Moreira Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Thu, 28 Feb 2002 09:47:59 -0500 Organization: MV Communications, Inc. Lines: 23 Message-ID: <7lgs7uco27h35bur5mmo00ihatal1hdmlv@4ax.com> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<1014824655.920433@haldjas.folklore.ee> NNTP-Posting-Host: bnh-5-29.mv.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: pyrite.mv.net 1014907396 14704 199.125.98.29 (28 Feb 2002 14:43:16 GMT) X-Complaints-To: abuse@mv.com NNTP-Posting-Date: 28 Feb 2002 14:43:16 GMT X-Newsreader: Forte Agent 1.9/32.560 X-No-Archive: yes Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!iad-peer.news.verio.net!news.verio.net!newsfeed.cwix.com!newsfeed1.cidera.com!Cidera!news.mv.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102895 Sander Vesik said: >No, you can in principle apply it to vanilla C - see for example > http://www.sics.se/~psm/sparcstack.html > >it just depends on how your architecture looks like, what >assumptions are being made and similar. Also, in many processors, >there is no such thing as a "procedure call" there are just jumps >and som conventions on how registers are treated and where you jump >to when finished. Which definately allows you to do tail-call >elimination, unles sthe conventions specifcly disallow that. Can't convert to tail form without doing what's in effect rewriting the source. That applies to any language, C included. Hence the issue with debugging. Try this: write a Quicksort algorithm in C, then convert it to tail form, and put the two pieces of source code side by side. Alberto. ###### From: Alberto Moreira Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Thu, 28 Feb 2002 10:12:30 -0500 Organization: MV Communications, Inc. Lines: 48 Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<3C7D021B.2EF21467@hda.hydro.com> NNTP-Posting-Host: bnh-5-29.mv.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: pyrite.mv.net 1014908867 17799 199.125.98.29 (28 Feb 2002 15:07:47 GMT) X-Complaints-To: abuse@mv.com NNTP-Posting-Date: 28 Feb 2002 15:07:47 GMT X-Newsreader: Forte Agent 1.9/32.560 X-No-Archive: yes Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!iad-peer.news.verio.net!news.verio.net!newsfeed.cwix.com!newsfeed1.cidera.com!Cidera!news.mv.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102885 Terje Mathisen said: >Alberto Moreira wrote: >> Also, the semantics of your programming language must be amenable to >> tail-form conversion. If the semantics of the language demands that >> you keep multiply nested stack frames with linkages to both statically >> and dynamically nested contexts, like Pascal for example, I'm not even >> sure conversion to tail form is feasible. You may also get in trouble > >There's absolutely nothing that stops a Pascal compiler from generating >C-style code as long as the source code doesn't use any variables from >linked contexts, right? If a Pascal program is written to stay within the limits of the C semantics, sure, no problem. But try, for example, this: PROCEDURE ReadOneWord ( ........ ) VAR c : char ; PROCEDURE GetFirstNonBlank PROCEDURE IsItBlank BEGIN ...... END BEGIN if (ItsBlank) GetFirstNonBlank; c = ........ END BEGIN GetFirstNonBlank ( ) ..... END END And you're already doing things that C doesn't do; all of a sudden, the semantics of that maligned ENTER/LEAVE instructions becomes relevant ! Alberto. ###### From: Alberto Moreira Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: Thu, 28 Feb 2002 10:30:41 -0500 Organization: MV Communications, Inc. Lines: 90 Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: bnh-5-29.mv.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: pyrite.mv.net 1014909959 20292 199.125.98.29 (28 Feb 2002 15:25:59 GMT) X-Complaints-To: abuse@mv.com NNTP-Posting-Date: 28 Feb 2002 15:25:59 GMT X-Newsreader: Forte Agent 1.9/32.560 X-No-Archive: yes Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.cwix.com!newsfeed1.cidera.com!Cidera!news.mv.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:102896 Bruce Hoult said: >Note that a program compiled with tail-call elimination is *exactly* as >hard (or easy) to debug as a program written with loops in the first >place. Yes, of course. But the problem still remains, that we sometimes want to debug on a stepping basis at source line level. Transforming a program into tail form makes that nearly impossible. >With a compiler doing tail-call elimination these two functions produce >*identical* machine code. The debugability is the same in both cases. Not if I'm stepping at source level and not looking at object code. >But, turn off the tail-call elimination and the first version becomes >*more* debuggable, because you can examine the entire history of the >computation by stepping up and down the stack frames. That's another aspect: the semantics of the object program follows that of the source code, and that makes debugging easier. >Pascal is identical to Scheme, Dylan and Common Lisp in this regard. >All are lexically scoped. I forget which flavor of Lisp is dynamically scoped, that changes things. And you don't have callcc in Pascal ! >BTW, modern lexically-scoped language implementations don't use either >of the methods commonly used when Pascal was developed (maintaining a >static link in each stack frame, or maintaining a "display"). Instead >each function is passed an environment structure containing a pointer to >each uplevel variable that it uses. This is needed to implement >closures (which Pascal doesn't have), but is more efficient overall >anyway. Yes, that's the Scheme way. But you see, a closure is packing a procedure definition with the environment in effect at the time of the definition - because in Scheme, we must keep bindings that were in effect at the time the procedure was created. So, a free variable inside a procedure is resolved against the original environment(s) in effect at the time the procedure was created - but in Pascal, free variables are resolved with the environment(s) at the time they are *used*. Hence, no need for closures in Pascal. >Call-by-name is just the passing of a function (a closure actually) that >accesses the appropriate value. You can express this directly in many >modern languages -- generally precisely those which have tail-call >elimination, as it happens :-) Yes, that's true. >Dynamic binding is evil for many reasons :-) The most common >implementation these days (e.g. in Common Lisp's "special" variables, >and Perl's "local" variables) is to use a single global varable and have >each function save the original global value and restore it prior to >returning. > >This "restoring before returning" makes a function, by definition, not >suitable for tail-call elimination, though if the function is otherwise >self-recursive a compiler can collapse multiple levels of restoring into >one, since most of the restored values are never used anwyay. That's true too. >Arbitrarily compilicated dispatch functions present no problem for >tail-call elimination, provided that they don't need to do any cleanup >after the called virtual function returns. This is normally the case, >with the only exceptions I know of being when Common Lisp's method >combination facility is being used. I'm curious to see Tail Form conversion generally applied to OO languages. It's been a few years I stopped reading papers in that area, so I'm not familiar with the latest developments. But I look at my C++ programs, and I don't know, I somehow doubt that anybody could effectively convert them to tail form ! :-) >Yes, but fortunately the cases where it is a significant proportion of >the total runtime are usually exactly those where it can be reduced or >eliminated :-) I don't know, I don't know. There's still difficulties in the way. The debugging issue is, as I see it, a major one ! Alberto. ###### From: Maneki Neko <{spamtrap}@erewhon.demon.co.uk> Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 28 Feb 2002 17:23:49 +0000 Message-ID: <878z9dr04a.fsf@erewhon.demon.co.uk> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

Reply-To: Maneki Neko NNTP-Posting-Host: erewhon.demon.co.uk X-NNTP-Posting-Host: erewhon.demon.co.uk:193.237.124.135 X-Trace: news.demon.co.uk 1014919533 nnrp-10:6587 NO-IDENT erewhon.demon.co.uk:193.237.124.135 X-Complaints-To: abuse@demon.net User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Lines: 15 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news2.euro.net!dispose.news.demon.net!news.demon.co.uk!demon!erewhon.demon.co.uk!nobody Xref: chonsp.franklin.ch alt.folklore.computers:102872 Alberto Moreira writes: [snip] > Read, for example, Andrew Appel's "Compiling with Continuations". [snip] > Also, the semantics of your programming language must be amenable to > tail-form conversion. If the semantics of the language demands that > you keep multiply nested stack frames with linkages to both statically > and dynamically nested contexts, like Pascal for example, I'm not even > sure conversion to tail form is feasible. IIRC Appel's book has a reference to a continuation passing style Pascal compiler in its bibliography. -- Battery chickens are not rechargable. ###### From: Bruce Hoult Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<3C7D021B.2EF21467@hda.hydro.com> User-Agent: MT-NewsWatcher/3.0 (PPC) Message-ID: Lines: 75 Date: Fri, 01 Mar 2002 09:52:00 +1300 NNTP-Posting-Host: 203.79.84.9 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1014929525 203.79.84.9 (Fri, 01 Mar 2002 09:52:05 NZDT) NNTP-Posting-Date: Fri, 01 Mar 2002 09:52:05 NZDT Organization: TelstraClear Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!news1.optus.net.au!optus!intgwlon.nntp.telstra.net!news.telstra.net!newsfeed01.tsnz.net!news02.tsnz.net!bruce Xref: chonsp.franklin.ch alt.folklore.computers:102913 In article , Alberto Moreira wrote: > Terje Mathisen said: > > >Alberto Moreira wrote: > >> Also, the semantics of your programming language must be amenable to > >> tail-form conversion. If the semantics of the language demands that > >> you keep multiply nested stack frames with linkages to both statically > >> and dynamically nested contexts, like Pascal for example, I'm not even > >> sure conversion to tail form is feasible. You may also get in trouble > > > >There's absolutely nothing that stops a Pascal compiler from generating > >C-style code as long as the source code doesn't use any variables from > >linked contexts, right? > > If a Pascal program is written to stay within the limits of the C > semantics, sure, no problem. But try, for example, this: > > PROCEDURE ReadOneWord ( ........ ) > > VAR c : char ; > > PROCEDURE GetFirstNonBlank > > PROCEDURE IsItBlank > BEGIN > ...... > END > > BEGIN > if (ItsBlank) GetFirstNonBlank; > c = ........ > END > > BEGIN > GetFirstNonBlank ( ) > ..... > END > > END > > And you're already doing things that C doesn't do; all of a sudden, > the semantics of that maligned ENTER/LEAVE instructions becomes > relevant ! I guess you didn't read the previous messages :-) You compile it like this: void ReadOneWord(...){ char c; GetFirstNonBlank(c); ... } void GetFirstNonBlank(char &c){ if (IsItBlank(c)) GetFirstNonBlank(c); c = ...; } bool IsItBlank(char &c){ ... } Each uplevel variable used is passed as a reference. If there are "too many" of them then pass them all in a struct instead of as individual arguments. If you really want I can show the actual input and output of a Dylan compiler doing exactly this. -- Bruce ###### From: "Stefan Monnier " Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 28 Feb 2002 22:16:57 -0500 Organization: Yale University Lines: 14 Sender: monnier@rum.cs.yale.edu Message-ID: <5lsn7lkmdy.fsf@rum.cs.yale.edu> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: rum.cs.yale.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2.50 X-Original-NNTP-Posting-Host: rum.cs.yale.edu X-Original-Trace: 28 Feb 2002 22:16:59 -0500, rum.cs.yale.edu Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newscore.univie.ac.at!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!news-hog.berkeley.edu!ucberkeley!news.ycc.yale.edu!rum.cs.yale.edu!rum.cs.yale.edu Xref: chonsp.franklin.ch alt.folklore.computers:102978 >>>>> "Alberto" == Alberto Moreira writes: > I'm curious to see Tail Form conversion generally applied to OO > languages. It's been a few years I stopped reading papers in that > area, so I'm not familiar with the latest developments. But I look at > my C++ programs, and I don't know, I somehow doubt that anybody could > effectively convert them to tail form ! :-) The difference between SSA-form and continuation-passing-style (i.e. using tail-calls only) is mostly limited to notational differences, so it's quite likely that your C++ compiler turns your programs into something that looks a lot like "Tail Form". Stefan ###### Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers From: alexc@world.std.com (Alex Colvin) Subject: Re: expensive procedure calls Organization: The World Public Access UNIX, Brookline, MA Message-ID: References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<5lsn7lkmdy.fsf@rum.cs.yale.edu> Date: Fri, 1 Mar 2002 15:23:14 GMT Lines: 9 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!dispose.news.demon.net!demon!news2.euro.net!uunet!ash.uu.net!world!alexc Xref: chonsp.franklin.ch alt.folklore.computers:102927 >The difference between SSA-form and continuation-passing-style (i.e. >using tail-calls only) is mostly limited to notational differences, I thought SSA was all about intra-procedure data flow, not inter-procedural. -- mac the na�f ###### From: "Stefan Monnier " Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 01 Mar 2002 16:39:39 -0500 Organization: Yale University Lines: 13 Sender: monnier@rum.cs.yale.edu Message-ID: <5l7kowklwk.fsf@rum.cs.yale.edu> References: <1013375511snz@dsl.co.uk> <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<5lsn7lkmdy.fsf@rum.cs.yale.edu> NNTP-Posting-Host: rum.cs.yale.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2.50 X-Original-NNTP-Posting-Host: rum.cs.yale.edu X-Original-Trace: 1 Mar 2002 16:39:40 -0500, rum.cs.yale.edu Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!news-hog.berkeley.edu!ucberkeley!news.ycc.yale.edu!rum.cs.yale.edu!rum.cs.yale.edu Xref: chonsp.franklin.ch alt.folklore.computers:102980 >>>>> "Alex" == Alex Colvin writes: >> The difference between SSA-form and continuation-passing-style (i.e. >> using tail-calls only) is mostly limited to notational differences, > I thought SSA was all about intra-procedure data flow, > not inter-procedural. Yes, so CPS is more general than SSA, but within a procedure, SSA and CPS look very much the same. As for why there's CPS within a procedure, it's because in CPS every flow-control operation is a tail-call (i.e. tail-call is goto and goto is tail-call). Stefan ###### From: stremler@rohan.sdsu.edu Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 4 Mar 2002 01:32:56 GMT Organization: San Diego State University Lines: 17 Message-ID: References: <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: rohan.sdsu.edu X-Trace: gondor.sdsu.edu 1015205576 19213 130.191.3.100 (4 Mar 2002 01:32:56 GMT) X-Complaints-To: news@newshub.sdsu.edu NNTP-Posting-Date: 4 Mar 2002 01:32:56 GMT User-Agent: tin/1.4.2-20000123 ("Polish") (UNIX) (SunOS/5.8 (sun4u)) Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!newsfeed1.cidera.com!Cidera!torn!sunqbc.risq.qc.ca!news-hog.berkeley.edu!ucberkeley!newshub.sdsu.edu!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:103084 In alt.folklore.computers Bruce Hoult wrote: [snip] > Pascal is identical to Scheme, Dylan and Common Lisp in this regard. > All are lexically scoped. And here I with the impression that one of the key differences between Scheme and Common Lisp was the scheme was lexically scoped and Common Lisp was not. (I do not know much about Lisp at all, much less Common Lisp.) What version(s) of Lisp were dynamically scoped, versus lexically scoped? -- ----------------------------------------------------------------------------- "I know something you don't know. . . ." | stremler@rohan.sdsu.edu -Inigo (_The Princess Bride_) | Stewart Stremler ###### From: Bruce Hoult Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls References: <3C6759E1.929AADDF@ev1.net> <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

User-Agent: MT-NewsWatcher/3.2 (PPC Mac OS X) Message-ID: Lines: 31 Date: Mon, 04 Mar 2002 15:40:55 +1300 NNTP-Posting-Host: 203.79.124.137 X-Complaints-To: abuse@tsnz.net X-Trace: news02.tsnz.net 1015209655 203.79.124.137 (Mon, 04 Mar 2002 15:40:55 NZDT) NNTP-Posting-Date: Mon, 04 Mar 2002 15:40:55 NZDT Organization: TelstraClear Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!fr.clara.net!heighliner.fr.clara.net!fr.usenet-edu.net!usenet-edu.net!proxad.net!enews.sgi.com!news.xtra.co.nz!newsfeed01.tsnz.net!news02.tsnz.net!bruce Xref: chonsp.franklin.ch alt.folklore.computers:103161 In article , stremler@rohan.sdsu.edu wrote: > In alt.folklore.computers Bruce Hoult wrote: > [snip] > > Pascal is identical to Scheme, Dylan and Common Lisp in this regard. > > All are lexically scoped. > > And here I with the impression that one of the key differences between > Scheme and Common Lisp was the scheme was lexically scoped and Common > Lisp was not. > > (I do not know much about Lisp at all, much less Common Lisp.) > > What version(s) of Lisp were dynamically scoped, versus lexically scoped? All Lisps were dynamically scoped until Steele showed in the late 70's that lexical scoping was more predictable, equally efficient, could do things that dynamic scoping couldn't do (e.g. closures), and could emulate dynamic scoping if need be. Scheme was the first lexically scoped Lisp, it started spreading to other Lisps by the mid 80's, and Common Lisp has always been lexically scoped. As far as I know, the only dynamically scoped Lisp still in common use is Emacs Lisp. And pretty much everyone (including RMS) would like to change that. Common Lisp does still have the ability to declare particular variables to be dynamically scoped (as does Perl, using 'local'). -- Bruce ###### From: fox@crisp.demon.co.uk (Paul D Fox) Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Date: 7 Mar 2002 08:43:58 -0800 Organization: http://groups.google.com/ Lines: 41 Message-ID: <772053ad.0203070843.6343da89@posting.google.com> References: <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

NNTP-Posting-Host: 194.205.246.146 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1015519439 26589 127.0.0.1 (7 Mar 2002 16:43:59 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 7 Mar 2002 16:43:59 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:103332 Bruce Hoult wrote in message news:... > As far as I know, the only dynamically scoped Lisp still in common use > is Emacs Lisp. And pretty much everyone (including RMS) would like to > change that. > > Common Lisp does still have the ability to declare particular variables > to be dynamically scoped (as does Perl, using 'local'). I have my own language, called crunch, which is part of the CRiSP editor suite, which supports dynamic scoping...and I wish it didnt! crunch evolved from a Lisp-like language (lots of (..) ) into an ANSI/ISO-C like interpreted language. At the time, adding dynamic symbol evaluation was about 3 lines of code - nice and easy. But its a maintainance nightmare - it produces 'surprising' behaviour (in 100,000 lines of code its maybe used 10 times, so one tends to miss this fact). It also makes it very difficult to optimise. The virtual machine architecture is not brilliant, but this mechanism means that it is difficult to produce a JVM style byte code interpreter. There are ways around it. It can be a very poweful feature, but from my own experience, it wasnt 'thought out enough' to see the pitfalls, and I think the evaluation and addressing modes of modern languages (designed by people much better than myself), show its not a good thing. The primary reason for the languages existance was that Lisp-code is a pain to read and debug, especially when mixing languages (CRiSP is written in C). Ones mind gets caught by those brackets. Interestingly, a language like C or C++ - probably has no more brackets than Lisp, its just that they are mixed ( '()' and '{}' and '[]') so the brain doesnt see a huge forest of brackets, but can group the elements together more easily, making it easier to comprehend at a higher level. At the end of the day, all the languages are equivalent - the main difference is emphasis on different layout styles and personal expertise in writing and deciphering other peoples code. ###### From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.os.vms,comp.arch,comp.sys.intel,alt.folklore.computers Subject: Re: expensive procedure calls Followup-To: comp.arch Date: 9 Mar 2002 20:28:35 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 193 Sender: anton@a0.complang.tuwien.ac.at (Anton Ertl) Message-ID: References: <3C67AA4C.6ED4E587@hda.hydro.com> <3cacbc12.480804889@news.btopenworld.com> <3C6E87A1.260E5D93@attbi.com> <3C72FD44.2058A1ED@ev1.net>

<3C7DEE45.C1F8A4BA@hda.hydro.com> NNTP-Posting-Host: a0.complang.tuwien.ac.at X-Newsreader: xrn 9.02 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.icl.net!news.maxwell.syr.edu!newsfeed1.uni2.dk!newscore.univie.ac.at!aconews-feed.univie.ac.at!news.tuwien.ac.at!a0.complang.tuwien.ac.at!anton Xref: chonsp.franklin.ch alt.folklore.computers:103545 In article <3C7DEE45.C1F8A4BA@hda.hydro.com>, Terje Mathisen writes: >I've done something almost unheard of in this regard: > >I've actually tried multiple different implementation methods, all >written in both C and asm to get full control, and then timed them, just >to find the fastest method. > >Yeah, I know that this is bad 'cause it can stop a nice discussion, but >I wanted to win a competition, so please excuse me. :-) ... >Anyway, the important part is that plain recursion can indeed be very >fast, in my case it was almost certainly due to keeping the code working >set really small, since the data was the same for all versions. Ok, in this spirit I coded up a number of variants of tree-walking, because that was the example discussed elsewhere in this thread, and measured their performance. You can find the source code below, here are some explanatory comments: I used node-counting instead of node-printing, because node-printing is very likely dominated by printing and not by tree-walking. I think I did preserve the order of visits (depth-first left-to-right) in all variants, though. The code does not build a full tree, but a minimal DAG with n nodes for simulating a tree with 2^n-1 nodes. The various variants are: 1) The straightforward node-counting function is not tail-recursive (it performs an add after the second call). 2) It can be converted into a tail-recursive function by rearranging the computation with an additional parameter; gcc (with the options I used) eliminates the tail recursion in this case. 3) Tail recursion eliminated by hand. 4) Complete recursion elimination. This uses a stack remembering the spine of right-child nodes; the stack is fixed-size, which would not work in general; a general version with a growable stack would probably be somewhat slower. 5) This is 4), optimized by checking the right child earlier (analogous optimizations should also speed up all other variants, at the expense of more complexity). I guess the perceptive readers will find some errors in the code, but at least the output in the benchmark case is correct, so I hope the errors don't affect the results. I used the following timing script: for i in 1 2 3 4 5; do gcc -O3 -fomit-frame-pointer -DOPT=$i tree-walk.c; echo "OPT=$i:"; perfex -e 4100c0 a.out 20; done The timings (cycle results) on my Athlon-1200 show quite a bit of variation, but most speed differences are larger than these variations (except the speed differences between 2 and 3); the output of 6 repetitions was massaged into the following table: run 1 run 2 run 3 run 4 run 5 run 6 OPT=1: nodes = 1048575 cycles : 30339154 30361572 30217474 30939957 30182402 30783846 instructions : 34938295 34938295 34938294 34938294 34938294 34938294 OPT=2: nodes = 1048575 cycles : 22274720 21604934 21070969 21106644 22821884 22516939 instructions : 24452545 24452544 24452545 24452545 24452545 24452545 OPT=3: nodes = 1048575 cycles : 20311913 19708046 21274829 19942656 22096462 20135104 instructions : 23403970 23403971 23403971 23403971 23403971 23403970 OPT=4: nodes = 1048575 cycles : 13830580 13087445 12958420 13356717 12746190 12471338 instructions : 14491094 14491095 14491093 14491093 14491095 14491093 OPT=5: nodes = 1048575 cycles : 10992514 11753863 10990741 11310144 11019757 11570805 instructions : 10821077 10821077 10821076 10821076 10821077 10821077 So, it seems like eliminating recursion still pays off. I guess the speed difference between 2 and 3 is caused by the additional parameter in the recursive calls in 2. Followups set to comp.arch. - anton And here's the code: #include #include typedef struct node { struct node *left, *right; } node; int count_nodes(node *n); int main(int argc, char **argv) { unsigned depth; int i; node nodes[40]; if (argc!=2) { fprintf(stderr, "Usage: %s depth\n", argv[0]); exit(1); } depth=atoi(argv[1]); /* build a dag of depth depth */ nodes[0].left = nodes[0].right = NULL; for (i=1; ileft) + countnodes(n->right) + 1; } #elif OPT==2 int countnodes2(node *n, int c) { if (n==NULL) return c; c += countnodes2(n->left,0)+1; return countnodes2(n->right,c); } int countnodes(node *n) { return countnodes2(n,0); } #elif OPT==3 int countnodes(node *n) { int c=0; for (; n!=NULL; n=n->right) c+=countnodes(n->left)+1; return c; } #elif OPT==4 int countnodes(node *n) { node *stack[40]; node **sp=stack; int c = 0; *sp++ = n; while (sp>stack) for (n = *--sp; n!=NULL; n=n->left) { *sp++ = n->right; c++; } return c; } #elif OPT==5 int countnodes(node *n) { node *stack[40]; node **sp=stack; int c = 0; if (n==NULL) return 0; *sp++ = n; while (sp>stack) for (n = *--sp; ;) { if (n->right) *sp++ = n->right; c++; n=n->left; if (n==NULL) break; } return c; } #endif - anton -- M. Anton Ertl Some things have to be seen to be believed anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen http://www.complang.tuwien.ac.at/anton/home.html