Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #4797

Re: cost of prolog/epilog

From torbenm@diku.dk (Torben Ægidius Mogensen)
Newsgroups comp.arch
Subject Re: cost of prolog/epilog
References (11 earlier) <jpm2p8-k571.ln1@ntp6.tmsw.no> <874ny93voz.fsf_-_@Niukka.kon.iki.fi> <l563p8-n081.ln1@ntp6.tmsw.no> <2011Nov14.104535@mips.complang.tuwien.ac.at> <j9sa38$mna$1@news.albasani.net>
Date 2011-11-17 11:21 +0100
Message-ID <7zaa7vkq1r.fsf@ask.diku.dk> (permalink)
Organization SunSITE.dk - Supporting Open source

Show all headers | View raw

BGB <cr88192@hotmail.com> writes:


> if [Fibonacci] can be optimized into a tail recursive form, this
> doesn't speak as well of its use as a benchmarking tool, where in
> particular it is assumed to have a high complexity and thus take a
> long time to execute.

This reminds me of an article BYTE that I read in 1987 or 1988: The
article was about benchmarking Pascal compilers for the PC.  One of the
benchmarks was the recursive Fibonacci function (used for the purpose of
testing the speed of function calls).  The author of the article thought
it would be nice to compare the speed of function calls to the speed of
loops, and rewrote (by hand) the benchmark to use a loop.  He was much
surprised by the enormous difference in speed and concluded that
function calls must be very expensive indeed.

While this mainly shows the cluelessness of the author, it does,
hpwever, bring up a valid point: A benchmark should not use an
unrealistically suboptimal algorithm, as a compiler could do simple
pattern-matching to rewrite it to a better algorithm and get enormous
speed-ups.  In other words, benchmarks should use realistic code (and
preferably "real" programs).  This is mostly the case these days, but in
the 80s, benchmark programs were mostly small, artificial programs that
each stressed a particular language feature.

While no C compilers that I know of can transform the exponential
Fibonacci function into linear form, there are well-known program
transformation techniques that can.  The simplest would be to recognize
that there are multiple recursive calls with smaller parameters and add
memoisation.  This does not increase the space usage much (as the
recursion stack is proportional to the memo table).  More advanced
techniques can get linear-time without using memoisation.

	Torben

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-20 19:51 +0000
  Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-20 22:35 +0200
    Re: big-little Mark Thorson <nospam@sonic.net> - 2011-10-20 14:18 -0800
      Re: big-little nmm1@cam.ac.uk - 2011-10-21 07:54 +0100
        Re: big-little David Kanter <dkanter@gmail.com> - 2011-11-09 01:06 -0800
          Re: big-little nmm1@cam.ac.uk - 2011-11-09 11:07 +0000
      Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-21 09:25 +0200
      Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-21 11:07 -0400
        Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-21 16:28 +0000
          Re: big-little nmm1@cam.ac.uk - 2011-10-21 17:07 +0100
          Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-21 13:25 -0400
            Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-21 19:45 +0000
              Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-22 14:44 -0400
          Re: big-little ChrisQ <meru@devnull.com> - 2011-10-22 16:57 +0000
            Re: big-little nmm1@cam.ac.uk - 2011-10-22 17:40 +0100
              Re: big-little ChrisQ <meru@devnull.com> - 2011-10-23 14:39 +0000
                Re: big-little nmm1@cam.ac.uk - 2011-10-23 16:11 +0100
                Re: big-little ChrisQ <meru@devnull.com> - 2011-10-23 17:44 +0000
                Re: big-little nmm1@cam.ac.uk - 2011-10-23 18:46 +0100
                Re: big-little Thomas Womack <twomack@chiark.greenend.org.uk> - 2011-10-23 19:30 +0100
                Re: big-little nmm1@cam.ac.uk - 2011-10-23 19:59 +0100
                Re: big-little BGB <cr88192@hotmail.com> - 2011-10-23 13:21 -0700
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-23 20:38 +0200
                Re: big-little nmm1@cam.ac.uk - 2011-10-23 22:38 +0100
                Re: big-little BGB <cr88192@hotmail.com> - 2011-10-23 17:56 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-24 07:58 +0100
                Re: big-little BGB <cr88192@hotmail.com> - 2011-10-24 16:34 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-25 08:09 +0100
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-25 14:52 +0200
                Re: big-little nmm1@cam.ac.uk - 2011-10-25 17:28 +0100
                Re: big-little BGB <cr88192@hotmail.com> - 2011-10-25 13:06 -0700
                Re: big-little BGB <cr88192@hotmail.com> - 2011-10-25 15:22 -0700
                Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-25 19:47 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-26 08:09 +0100
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-26 12:06 +0200
                Re: big-little nmm1@cam.ac.uk - 2011-10-26 10:47 +0100
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-26 11:58 +0200
                Re: big-little nmm1@cam.ac.uk - 2011-10-26 10:44 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 03:45 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-26 11:45 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 09:15 -0700
                Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-26 12:51 -0700
                Re: big-little Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-26 11:45 +0000
                Re: big-little nmm1@cam.ac.uk - 2011-10-26 15:42 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 09:07 -0700
                Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-26 12:53 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-26 21:05 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 13:20 -0700
                Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-26 17:55 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-27 09:10 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 01:34 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-27 10:29 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 04:28 -0700
                Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-27 12:22 -0400
                Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-27 18:08 +0000
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 11:50 -0700
                Re: big-little Jean-Marc Bourguet <jm@bourguet.org> - 2011-10-27 14:10 +0200
                Re: big-little nmm1@cam.ac.uk - 2011-10-27 17:58 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 13:15 -0700
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 04:10 -0700
                Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-10-27 14:04 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-27 23:07 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 15:58 -0700
                Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-27 22:57 +0000
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 16:39 -0700
                Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-28 00:16 +0000
                Re: big-little nmm1@cam.ac.uk - 2011-10-28 09:52 +0100
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-28 07:01 -0700
                Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-28 16:45 +0000
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-29 13:13 -0700
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-30 03:36 -0700
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-30 03:55 -0700
                Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-10-28 11:15 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-28 20:01 +0100
                Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-29 17:46 +0000
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-29 11:30 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-29 20:02 +0100
                Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-10-29 13:09 -0700
                Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-29 17:42 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-10-30 08:16 +0000
                Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-11-04 10:06 -0700
                Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-11-04 15:19 -0700
                Re: big-little nmm1@cam.ac.uk - 2011-11-05 09:13 +0000
                Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-11-05 09:03 -0700
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 13:38 -0700
                Re: big-little Robert Wessel <robertwessel2@yahoo.com> - 2011-10-26 18:44 -0500
                Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 17:05 -0700
                Re: big-little Robert Wessel <robertwessel2@yahoo.com> - 2011-10-26 21:03 -0500
                Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-26 14:37 -0400
                Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-26 15:38 -0400
                Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-26 16:06 -0400
                Re: big-little BGB <cr88192@hotmail.com> - 2011-10-27 00:15 -0700
                Re: big-little Morten Reistad <first@last.name> - 2011-11-03 17:30 +0100
                Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-11-03 20:45 -0700
                Re: big-little Thomas Womack <twomack@chiark.greenend.org.uk> - 2011-11-04 11:13 +0000
                Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-11-04 10:12 -0700
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-04 09:26 -0700
                Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-11-05 11:32 -0400
                Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-11-05 11:55 -0400
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-05 09:58 -0700
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-05 18:39 +0100
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-05 15:00 -0700
                Re: big-little wclodius@lost-alamos.pet (William Clodius) - 2011-11-05 18:43 -0600
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-05 19:46 -0700
                Re: big-little ChrisQ <meru@devnull.com> - 2011-11-11 12:31 +0000
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-11 12:39 -0700
                Re: big-little Chris Gray <cg@GraySage.com> - 2011-11-11 13:28 -0700
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-11 18:03 -0700
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-12 18:25 +0100
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-12 12:02 -0700
                cost of prolog/epilog (was: big-little) Kalle Olavi Niemitalo <kon@iki.fi> - 2011-11-12 22:57 +0200
                Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-12 22:47 +0100
                Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-14 09:45 +0000
                Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-14 12:28 +0100
                Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-15 16:48 +0000
                Re: cost of prolog/epilog Stefan Monnier <monnier@iro.umontreal.ca> - 2011-11-15 21:35 -0500
                Re: cost of prolog/epilog Bakul Shah <usenet@bitblocks.com> - 2011-11-16 02:41 -0800
                Re: cost of prolog/epilog nmm1@cam.ac.uk - 2011-11-16 18:14 +0000
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-16 16:50 -0700
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-14 17:00 -0700
                Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-15 10:26 +0100
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-15 09:41 -0700
                Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-15 16:40 +0000
                Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-15 12:44 +0100
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-15 09:01 -0700
                Re: cost of prolog/epilog Chris Gray <cg@GraySage.com> - 2011-11-15 15:18 -0700
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-15 21:56 -0700
                Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-16 09:21 +0100
                Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-16 09:30 +0000
                Re: cost of prolog/epilog John Levine <johnl@iecc.com> - 2011-11-16 10:05 +0000
                Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-16 11:08 +0100
                Re: cost of prolog/epilog Chris Gray <cg@GraySage.com> - 2011-11-16 16:29 -0700
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-16 11:22 -0700
                Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-17 13:27 +0000
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-17 10:30 -0700
                Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-17 11:21 +0100
                Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-17 11:56 +0100
                Re: cost of prolog/epilog timcaffrey@aol.com (Tim McCaffrey) - 2011-11-17 20:27 +0000
                Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-18 10:57 +0100
                Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-17 10:42 -0700
                Re: cost of prolog/epilog (was: big-little) "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-11-12 14:05 -0800
                Re: cost of prolog/epilog (was: big-little) Bernd Paysan <bernd.paysan@gmx.de> - 2011-11-18 02:39 +0100
                Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-18 10:59 +0100
                Re: cost of prolog/epilog Bernd Paysan <bernd.paysan@gmx.de> - 2011-11-18 22:06 +0100
                Re: cost of prolog/epilog (was: big-little) mac <acolvin@efunct.com> - 2011-11-20 23:01 +0000
                Re: cost of prolog/epilog Chris Gray <cg@GraySage.com> - 2011-11-13 13:35 -0700
                Re: big-little wclodius@lost-alamos.pet (William Clodius) - 2011-11-11 22:13 -0700
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-11 23:43 -0700
                Re: big-little Chris Gray <cg@GraySage.com> - 2011-11-12 14:08 -0700
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-12 19:10 -0700
                Re: big-little Chris Gray <cg@GraySage.com> - 2011-11-13 13:40 -0700
                Re: big-little Bakul Shah <usenet@bitblocks.com> - 2011-11-13 14:49 -0800
                Re: big-little BGB <cr88192@hotmail.com> - 2011-11-13 18:51 -0700
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-24 10:12 +0200
                Re: big-little Stefan Monnier <monnier@iro.umontreal.ca> - 2011-10-24 12:11 -0400
                Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-24 10:28 -0700
                Re: big-little nospam@ab-katrinedal.dk (Niels Jørgen Kruse) - 2011-10-24 19:38 +0200
                Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-24 21:02 +0200
                Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-23 12:02 -0700
        Re: big-little Morten Reistad <first@last.name> - 2011-11-03 00:51 +0100
    Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-20 16:59 -0700
      Re: big-little Anne & Lynn Wheeler <lynn@garlic.com> - 2011-10-20 21:13 -0400
      Re: big-little nmm1@cam.ac.uk - 2011-10-21 08:01 +0100
        Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-21 05:39 -0700
        Re: big-little torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-10-24 10:18 +0200
      Re: big-little Pedro Pereira <ppereira@grupopie.com> - 2011-10-21 10:40 +0100
        Re: big-little Paul Gotch <paulg@at-cantab-dot.net> - 2011-10-21 12:42 +0100
    Re: big-little nik Simpson <nik_s@knology.net> - 2011-10-21 11:00 -0500
  Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-20 21:13 +0000
    Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-20 21:43 +0000
    Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-21 09:23 +0200
      Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-21 14:35 +0200
        Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-21 17:15 +0000
      Re: big-little BGB <cr88192@hotmail.com> - 2011-10-21 16:41 -0700
  Re: big-little jacko <jackokring@gmail.com> - 2011-10-26 14:12 -0700

csiph-web