Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.arch > #4284 > unrolled thread
| Started by | timcaffrey@aol.com (Tim McCaffrey) |
|---|---|
| First post | 2011-10-20 19:51 +0000 |
| Last post | 2011-10-26 14:12 -0700 |
| Articles | 20 on this page of 175 — 34 participants |
Back to article view | Back to comp.arch
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
Page 7 of 9 — ← Prev page 1 2 3 4 5 6 [7] 8 9 Next page →
| From | torbenm@diku.dk (Torben Ægidius Mogensen) |
|---|---|
| Date | 2011-11-15 10:26 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <7zaa7xka8n.fsf@ask.diku.dk> |
| In reply to | #4762 |
BGB <cr88192@hotmail.com> writes:
> On 11/14/2011 2:45 AM, Anton Ertl wrote:
>> Terje Mathisen<"terje.mathisen at tmsw.no"> writes:
>> There is no tail recursion in
>>
>> function fib(x:int):int
>> {
>> if(x>2)return(fib(x-2)+fib(x-1));
>> else return(1);
>> }
>>
>> There is an addition after the recursion.
>>
>>
>> However, gcc manages to transform code like this into a loop that
>> contains only one recursion (possibly by transforming it into a
>> tail-recursive version as an intermediate step);
>
> if this case 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.
I don't think gcc converts it into the linear-time form -- that would
require rather sophisticated rewriting. It is more likely to convert it
into something like:
int fib(int x)
{
int acc = 1, i;
for (i=3; i<=x; i++)
acc = fib(i-2) + acc;
return(acc);
}
which is still exponential.
Torben
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-15 09:41 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <j9u4nr$n63$1@news.albasani.net> |
| In reply to | #4763 |
On 11/15/2011 2:26 AM, Torben Ægidius Mogensen wrote:
> BGB<cr88192@hotmail.com> writes:
>
>> On 11/14/2011 2:45 AM, Anton Ertl wrote:
>>> Terje Mathisen<"terje.mathisen at tmsw.no"> writes:
>>> There is no tail recursion in
>>>
>>> function fib(x:int):int
>>> {
>>> if(x>2)return(fib(x-2)+fib(x-1));
>>> else return(1);
>>> }
>>>
>>> There is an addition after the recursion.
>>>
>>>
>>> However, gcc manages to transform code like this into a loop that
>>> contains only one recursion (possibly by transforming it into a
>>> tail-recursive version as an intermediate step);
>>
>> if this case 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.
>
> I don't think gcc converts it into the linear-time form -- that would
> require rather sophisticated rewriting. It is more likely to convert it
> into something like:
>
> int fib(int x)
> {
> int acc = 1, i;
> for (i=3; i<=x; i++)
> acc = fib(i-2) + acc;
> return(acc);
> }
>
> which is still exponential.
>
ok.
well, at least this retains its important feature as "a function which
runs very slowly...".
random:
I am off trying to write a spec for my VM's bytecode.
I am left to note that as-is, it is a fairly crufty format (with
inconsistent opcode naming, arbitrary limitations, special cases,
partially-redundant opcodes, ...). it also has a largish number of
opcodes (~352 opcodes, numbered up to 540, with about 188 unused spots).
also resisting the temptation to "improve" it to make it more
presentable, at the cost of having to fiddle around a bunch in the
interpreter and compiler code (changing things around) and probably
introduce bugs or break stuff. (may still make a few minor
notational/definitional improvements though).
brief: it is a high-level lexically-scoped stack-machine model, with
"blocks" representing many structures (function/method/closure bodies,
ifdef/ifndef blocks, ...).
some number of opcodes are for things which would be API calls in other
VMs (cons/car/cdr/tostring/clone/...).
another big chunk of opcodes is related to micro-optimizing operations
on fixnum and flonum types.
but, oh well, it developed over time, and it works, probably good enough.
or such...
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2011-11-15 16:40 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <2011Nov15.174016@mips.complang.tuwien.ac.at> |
| In reply to | #4763 |
torbenm@diku.dk (Torben Ægidius Mogensen) writes:
>BGB <cr88192@hotmail.com> writes:
>
>> On 11/14/2011 2:45 AM, Anton Ertl wrote:
>>> Terje Mathisen<"terje.mathisen at tmsw.no"> writes:
>>> There is no tail recursion in
>>>
>>> function fib(x:int):int
>>> {
>>> if(x>2)return(fib(x-2)+fib(x-1));
>>> else return(1);
>>> }
...
>I don't think gcc converts it into the linear-time form -- that would
>require rather sophisticated rewriting. It is more likely to convert it
>into something like:
>
>int fib(int x)
>{
> int acc = 1, i;
> for (i=3; i<=x; i++)
> acc = fib(i-2) + acc;
> return(acc);
>}
>
>which is still exponential.
Yes. I found that gcc generates the same code (modulo register and
stack allocation) from
unsigned fib(unsigned n) { return n < 2 ? n : fib(n-2) + fib(n-1); }
and
unsigned fib(unsigned n)
{
unsigned accum=0;
for (; n>1; n--)
accum += fib(n-2);
return n+accum;
}
- 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
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-15 12:44 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <nuv9p8-gpk1.ln1@ntp6.tmsw.no> |
| In reply to | #4762 |
BGB wrote: > if this case 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. > > given, however, that the time-ratio between my interpreter running this > function and an MSVC compiled version seems reasonably close to > constant, it seems unlikely MSVC is performing such an optimization. That's correct, as I showed the MSVC 64-bit code was a very vanilla translation, complete with dual recursive calls. Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-15 09:01 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <j9u2cj$hqd$1@news.albasani.net> |
| In reply to | #4770 |
On 11/15/2011 4:44 AM, Terje Mathisen wrote: > BGB wrote: >> if this case 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. >> >> given, however, that the time-ratio between my interpreter running this >> function and an MSVC compiled version seems reasonably close to >> constant, it seems unlikely MSVC is performing such an optimization. > > That's correct, as I showed the MSVC 64-bit code was a very vanilla > translation, complete with dual recursive calls. > yeah. MSVC seems to fairly often use fairly direct, and sometimes naive, translations. sometimes it generates funky/dubious-looking output. but, none the less, its output tends to perform adequately well. GCC often makes much more elaborate translations. my C compiler had introduced some of its own funkiness, likely partially due to it internally rewriting programs into RPN form (I tend to use stack-machine ILs), prior to emitting the output machine code. a few times I had noted similarities between my output and MSVC's output, making me wonder a few times if maybe they use stack machines as well or something... (and maybe optimize in many cases by partially rewriting the ASM post-emission?...). just guesses here, based on the appearance of some of its output. or such...
[toc] | [prev] | [next] | [standalone]
| From | Chris Gray <cg@GraySage.com> |
|---|---|
| Date | 2011-11-15 15:18 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <87aa7xni6m.fsf@GraySage.com> |
| In reply to | #4762 |
BGB <cr88192@hotmail.com> writes:
[This is fun, and I'll even throw in a comp.arch tidbit at the end.]
> there is an approx 112x speed difference (~ 143x without 'int' type
> annotations).
On my desktop, "X" = 5000:
gcc selsort.c: 0.23s
gcc -O3 selsort.c: 0.14s
Zed, gcc: 10.4s
Zed, gcc -O3: 5.8s
So, a factor of about 40 - 45. One big cost that I plan to reduce as much
as is reasonable is array bounds checking.
Another poster recalled using gcc's "computed goto's" in a machine
emulator. That recalled something to me. Checking... Yep, I still have it,
but it likely wouldn't run on this X86-64. How quickly can comp.arch
readers identify the machine? :-)
;
; main instruction emulation loop
;
next:
mov bl,[di] ; get next op-code
lea di,1[di] ; increment pc by 1
mov bh,0
mov si,bx
mov bx,itable[bx+si] ; index into itable without
jmp bx ; changing the status flags
;
; the table of offsets to code interpretation portions
;
rb offset $ and 1 ; align table on word boundary
itable:
dw offset next ; nop
dw offset ilxib
dw offset istaxb
dw offset iinxb
dw offset iinrb
dw offset idcrb
dw offset imvib
dw offset irlc
dw offset ibad ; illegal
...
;
; load immediate instructions
;
ilxib:
mov bx,[di]
lea di,2[di]
mov bcreg,bx
jmp next
--
Chris Gray
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-15 21:56 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <j9vfqv$m3l$1@news.albasani.net> |
| In reply to | #4779 |
On 11/15/2011 3:18 PM, Chris Gray wrote: > BGB<cr88192@hotmail.com> writes: > > [This is fun, and I'll even throw in a comp.arch tidbit at the end.] > >> there is an approx 112x speed difference (~ 143x without 'int' type >> annotations). > > On my desktop, "X" = 5000: > > gcc selsort.c: 0.23s > gcc -O3 selsort.c: 0.14s > > Zed, gcc: 10.4s > Zed, gcc -O3: 5.8s > > So, a factor of about 40 - 45. One big cost that I plan to reduce as much > as is reasonable is array bounds checking. > well, then again, my interpreter is not exactly fast... for the selection sort test, the top of the profiler list is apparently the function for fetching the value from a lexical variable (essentially a counted walk over a linked list). elsewhere, "strcmp" is also a significant time user (along with a type-check function, which calls "strcmp"), apparently this is related to type-checking the array. elsewhere, is another function, apparently involved with fetching object vtables (not entirely sure why the vtables are being fetched). > > > Another poster recalled using gcc's "computed goto's" in a machine > emulator. That recalled something to me. Checking... Yep, I still have it, > but it likely wouldn't run on this X86-64. How quickly can comp.arch > readers identify the machine? :-) > > ; > ; main instruction emulation loop > ; > next: > mov bl,[di] ; get next op-code > lea di,1[di] ; increment pc by 1 > mov bh,0 > mov si,bx > mov bx,itable[bx+si] ; index into itable without > jmp bx ; changing the status flags > ; > ; the table of offsets to code interpretation portions > ; > rb offset $ and 1 ; align table on word boundary > itable: > dw offset next ; nop > dw offset ilxib > dw offset istaxb > dw offset iinxb > dw offset iinrb > dw offset idcrb > dw offset imvib > dw offset irlc > > dw offset ibad ; illegal > ... > > ; > ; load immediate instructions > ; > ilxib: > mov bx,[di] > lea di,2[di] > mov bcreg,bx > jmp next > looks like 16-bit x86, nothing obviously machine specific (could probably run on an 8088 or similar). having trouble identifying the assembler used. best guess at the moment is a 16-bit version of FASM or similar. > -- > Chris Gray
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-16 09:21 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <hd8cp8-bdp1.ln1@ntp6.tmsw.no> |
| In reply to | #4779 |
Chris Gray wrote: > Another poster recalled using gcc's "computed goto's" in a machine > emulator. That recalled something to me. Checking... Yep, I still have it, > but it likely wouldn't run on this X86-64. How quickly can comp.arch > readers identify the machine? :-) Looks like 8080/Z80 asm code? > ; > rb offset $ and 1 ; align table on word boundary What is the rb directive supposed to do? Similar to ALIGN? > itable: > dw offset next ; nop Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2011-11-16 09:30 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <2011Nov16.103008@mips.complang.tuwien.ac.at> |
| In reply to | #4779 |
Chris Gray <cg@GraySage.com> writes: >Yep, I still have it, >but it likely wouldn't run on this X86-64. How quickly can comp.arch >readers identify the machine? :-) > >; >; main instruction emulation loop >; >next: > mov bl,[di] ; get next op-code Looks like plain 8086 code to me. Why shouldn't it run on your AMD64 machine? Yes, you might have to install an appropriate OS, but apart from that? - 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
[toc] | [prev] | [next] | [standalone]
| From | John Levine <johnl@iecc.com> |
|---|---|
| Date | 2011-11-16 10:05 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja01so$15tv$1@leila.iecc.com> |
| In reply to | #4785 |
>>next: >> mov bl,[di] ; get next op-code > >Looks like plain 8086 code to me. Why shouldn't it run on your AMD64 >machine? Yes, you might have to install an appropriate OS, but apart >from that? It's 16 bit code. You need an OS that can run code in real mode emulation. I suppose it might run in 286 protected mode, but I think it's more likely to be DOS code than OS/2 code. R's, John
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-16 11:08 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <nlecp8-kkp1.ln1@ntp6.tmsw.no> |
| In reply to | #4785 |
Anton Ertl wrote: > Chris Gray<cg@GraySage.com> writes: >> Yep, I still have it, >> but it likely wouldn't run on this X86-64. How quickly can comp.arch >> readers identify the machine? :-) >> >> ; >> ; main instruction emulation loop >> ; >> next: >> mov bl,[di] ; get next op-code > > Looks like plain 8086 code to me. Why shouldn't it run on your AMD64 > machine? Yes, you might have to install an appropriate OS, but apart > from that? The emulator asm code is of course 16-bit x86, the machine being emulated looks like 8080-something! Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
[toc] | [prev] | [next] | [standalone]
| From | Chris Gray <cg@GraySage.com> |
|---|---|
| Date | 2011-11-16 16:29 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <8739dnodcs.fsf@GraySage.com> |
| In reply to | #4788 |
Terje Mathisen <"terje.mathisen at tmsw.no"> writes: > The emulator asm code is of course 16-bit x86, the machine being > emulated looks like 8080-something! Yes. It was a few selected lines from my CP/M-80 emulator written for CP/M-86. Long long ago I had a dual-CPU S100 card with 8085 and 8088. Software for CP/M-80, but little for CP/M-86, so I wrote the emulator to allow me to do more. All of my own stuff worked, but a commercial full-screen editor didn't - I expect I wasn't emulating the low-memory stuff (128 bytes of "OS" stuff) properly. Could also have been instructions my stuff didn't use, of course. -- Chris Gray
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-16 11:22 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja0v1d$q99$1@news.albasani.net> |
| In reply to | #4785 |
On 11/16/2011 2:30 AM, Anton Ertl wrote: > Chris Gray<cg@GraySage.com> writes: >> Yep, I still have it, >> but it likely wouldn't run on this X86-64. How quickly can comp.arch >> readers identify the machine? :-) >> >> ; >> ; main instruction emulation loop >> ; >> next: >> mov bl,[di] ; get next op-code > Looks like plain 8086 code to me. Why shouldn't it run on your AMD64 > machine? Yes, you might have to install an appropriate OS, but apart > from that? 16-bit code wont run directly in 64-bit long-mode. one would need some sort of emulation (or virtualization) layer to make it work. I have wondered though why MS couldn't have made a secondary level of emulation, but then proxy this against the newer OS. say: 16-bit code and some 32-bit code run in an emulator / VM, partly shared with real 32-bit code running within WoW64. parts of the 16-bit and 32-bit operating environment is then faked, and then using a UI mapping layer (maps windows, input events, clipboard, ...) to interface between the real GUI and the windows under the control of the emulated apps. if done well, it could have been mostly transparent, unlike the added hassles of things like XPMode and DOSBox (which essentially run a whole damn virtualized OS, and do a generally crappy job at UI mapping and sharing the filesystem). even if a whole OS was run, presumably at least there could have been more effort to map the UI and filesystems more transparently (IMO, running in a window or as some sort of crappy-looking overlay with the mapped drives as network shares is just crappy...). drive mapping could have been done presumably by a special FS driver that automatically maps drives 1:1, with the virtualized OS looking for an unused drive-letter for its virtual OS drive (Q or Y or whatever...). potentially, it could have its own registry, but use the external (real) HDD for installed apps and application data. or such...
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2011-11-17 13:27 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <2011Nov17.142732@mips.complang.tuwien.ac.at> |
| In reply to | #4794 |
BGB <cr88192@hotmail.com> writes: >On 11/16/2011 2:30 AM, Anton Ertl wrote: >> Looks like plain 8086 code to me. Why shouldn't it run on your AMD64 >> machine? Yes, you might have to install an appropriate OS, but apart >> from that? > >16-bit code wont run directly in 64-bit long-mode. No, and neither will IA-32 code. However, all AMD64 machines support a 32-bit mode (I forget its name: maybe "compatibility mode") with a 16-bit sub-mode, and you can run this code in that mode. And all common OSs support executing IA-32 code on AMD64 machines. >one would need some sort of emulation (or virtualization) layer to make >it work. No. Just run it in the appropriate mode. - 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
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-17 10:30 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja3gbl$uds$1@news.albasani.net> |
| In reply to | #4799 |
On 11/17/2011 6:27 AM, Anton Ertl wrote: > BGB<cr88192@hotmail.com> writes: >> On 11/16/2011 2:30 AM, Anton Ertl wrote: >>> Looks like plain 8086 code to me. Why shouldn't it run on your AMD64 >>> machine? Yes, you might have to install an appropriate OS, but apart >>> from that? >> >> 16-bit code wont run directly in 64-bit long-mode. > > No, and neither will IA-32 code. However, all AMD64 machines support > a 32-bit mode (I forget its name: maybe "compatibility mode") with a > 16-bit sub-mode, and you can run this code in that mode. And all > common OSs support executing IA-32 code on AMD64 machines. > Windows, yes. Linux, theoretically, but it (Fedora at least) seems prone to not install any 32-bit libraries by default, so one may still have to build/use 64-bit apps (or probably go install the relevant packages?...). >> one would need some sort of emulation (or virtualization) layer to make >> it work. > > No. Just run it in the appropriate mode. > ok. the general claim though was that long-mode would not support 16-bit code (in general), and this was why neither DOS-mode nor Win16 apps would work. either way, MS didn't do it, and just left everyone with the current non-working apps and need to use XPMode crap... admittedly, one is almost better off just installing a plain Windows XP in VMware Player though, as VMware seems a lot more stable (and higher performance) than Virtual PC (which is used as the basic VM by XPMode).
[toc] | [prev] | [next] | [standalone]
| From | torbenm@diku.dk (Torben Ægidius Mogensen) |
|---|---|
| Date | 2011-11-17 11:21 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <7zaa7vkq1r.fsf@ask.diku.dk> |
| In reply to | #4762 |
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
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-17 11:56 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <rs5fp8-t1t1.ln1@ntp6.tmsw.no> |
| In reply to | #4797 |
Torben Ægidius Mogensen wrote:
> 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.
I very vaguely recollect that article, clueless author and editor both.
:-)
> 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.
Wouldn't just having memoisation be sufficient to make it O(n), although
with a fairly high constant factor?
my @fibtab = ();
sub fib
{
my ($n) = @_;
return $fibtab[$n] if (defined($fibtab[$n]));
if ($n < 2) {
$fibtab[$n] = $n;
return $n;
}
my $res = fib($n-1) + fib($n-2);
$fibtab[$n] = $res;
return $res;
}
The first n recursive calls will fill in the table, all the rest (and
there will only be (n-1) of them, will return in O(1) time, right?
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
[toc] | [prev] | [next] | [standalone]
| From | timcaffrey@aol.com (Tim McCaffrey) |
|---|---|
| Date | 2011-11-17 20:27 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja3qnf$46s$1@USTR-NEWS.TR.UNISYS.COM> |
| In reply to | #4798 |
Here is one way to do it: (Microsoft MASM syntax) fib_add MACRO a,b,c LEVEL&a& = LEVEL&b& + LEVEL&c& ENDM fib MACRO n LOCAL val1 LOCAL val2 IF n LE 2 LEVEL&n& = 1 ELSE fib %(n-1) fib %(n-2) fib_add n,%(n-1),%(n-2) ENDIF ENDM LEVEL&n& FIB 1000000 .DATA DWORD LEVEL1000000 I leave it as an excercise for the reader to write the actual function... :) Advantage is exection time is O(k) :) - Tim
[toc] | [prev] | [next] | [standalone]
| From | torbenm@diku.dk (Torben Ægidius Mogensen) |
|---|---|
| Date | 2011-11-18 10:57 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <7zwrax92j0.fsf@ask.diku.dk> |
| In reply to | #4798 |
Terje Mathisen <"terje.mathisen at tmsw.no"> writes: > Torben Ægidius Mogensen wrote: >> 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. > > Wouldn't just having memoisation be sufficient to make it O(n), > although with a fairly high constant factor? Yes. That was what I meant. But to recognise that memoisation is useful, you need to identify that there are multiple recursive calls that might eventually overlap. Torben
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-17 10:42 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja3h3h$9v$1@news.albasani.net> |
| In reply to | #4797 |
On 11/17/2011 3:21 AM, Torben Ægidius Mogensen wrote: > 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. > yes, but sadly, I have no particular "realistic" code for which I have both a C and a BGBScript version (which are nearly identical apart from the choice of language). so, this mostly means small/artificial benchmarks. granted, most serve to point out "hey, your interpreter performs kind-of like crap", so, alas... better yet would be if there were some good/nice way to help find all the bugs, besides maybe writing little tests or randomly stumbling on them (my technology is sadly a bit unreliable, for all the bugs I have not yet found, and the ones I have found but have been unable to effectively localize or fix). at least it is probably a little better than with my C compiler, which was buggy, but sufficiently complicated that it was very difficult trying to locate the bugs (and the codegen was a big and complicated mess and not easily amendable to automated tests). > 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. > yep.
[toc] | [prev] | [next] | [standalone]
Page 7 of 9 — ← Prev page 1 2 3 4 5 6 [7] 8 9 Next page →
Back to top | Article view | comp.arch
csiph-web