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 6 of 9 — ← Prev page 1 2 3 4 5 [6] 7 8 9 Next page →
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-05 18:39 +0100 |
| Message-ID | <0v8go8-jqg1.ln1@ntp6.tmsw.no> |
| In reply to | #4645 |
BGB wrote: > granted, I am expecting that a translator would likely have much better > performance than my interpreter (which had an approx 70x slowdown, due > in large-part to virtual-address translation and similar). 70x? Ouch! 10x is a more common value for a pure interpreter... JIT seems to lead to code in the 2x to 1.5x range, depending upon the source and target platforms... OTOH, those numbers above is most commonly quoted in the context of Java byte code, which is designed be easy to interpret. :-) 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-05 15:00 -0700 |
| Message-ID | <j94bmk$rq3$1@news.albasani.net> |
| In reply to | #4647 |
On 11/5/2011 10:39 AM, Terje Mathisen wrote: > BGB wrote: >> granted, I am expecting that a translator would likely have much better >> performance than my interpreter (which had an approx 70x slowdown, due >> in large-part to virtual-address translation and similar). > > 70x? > > Ouch! > > 10x is a more common value for a pure interpreter... > actually, 10x is on the faster end of interpreters (IME, it is hard to break about 15x or so with a "while-loop and switch()" strategy). if one is dealing with a dynamically-typed language, 100x to 1000x is more common. yes, but then again, interpreting x86 involves a lot of extra funkiness, such as having to translate in-interpreter virtual-addresses into host-process virtual addresses, which according to the profiler, was where most of the time was going. typically this involved partial page-table mapping, and then looking up the appropriate mapped memory spans (one mapped "physical memory" into the interpreter as a number of spans). > JIT seems to lead to code in the 2x to 1.5x range, depending upon the > source and target platforms... > > OTOH, those numbers above is most commonly quoted in the context of Java > byte code, which is designed be easy to interpret. :-) > yes. JBC is sort of a very easy case for an interpreter. they are simple opcodes, and are statically typed, ... a problem with many machine-code formats is that they are much less well suited to be efficiently interpreted. one has to deal with things like the fact that AL/AH/AX/EAX all overlap, and that accessing a sub register may involve shifts, masking, ... also, there are a lot of little detail things one has to worry about, such as updating EFLAGS and similar. if ones' interpreter is just written straightforwardly in C, one may note the lack of any convenient way to perform arithmetic and get status flags, meaning that one has to manually calculate them (via lots of shifts and bitwise operations). as well, there is a prevalence of complex memory-addressing calculations (ModRM fun). so, all things considered, a 70x slowdown to interpret x86 machine code probably isn't all that bad. granted, a JIT could probably do somewhat better here... that or someone being willing to put a lot of time into optimizing the interpreter (my design wasn't particularly optimized). I did use threaded-code though, because prior to this point, the instruction decoder (essentially a string-based pattern-matcher) made it significantly slower. or such...
[toc] | [prev] | [next] | [standalone]
| From | wclodius@lost-alamos.pet (William Clodius) |
|---|---|
| Date | 2011-11-05 18:43 -0600 |
| Message-ID | <1ka9v9g.1jhyz5n1o6blj4N%wclodius@lost-alamos.pet> |
| In reply to | #4649 |
BGB <cr88192@hotmail.com> wrote: > On 11/5/2011 10:39 AM, Terje Mathisen wrote: > > BGB wrote: > >> granted, I am expecting that a translator would likely have much better > >> performance than my interpreter (which had an approx 70x slowdown, due > >> in large-part to virtual-address translation and similar). > > > > 70x? > > > > Ouch! > > > > 10x is a more common value for a pure interpreter... > > > > actually, 10x is on the faster end of interpreters (IME, it is hard to > break about 15x or so with a "while-loop and switch()" strategy). It depends on the problem domain of the interpreter and the application it is being used on. If there is a good match between the domain and the problem, then much of the syntax will often be syntacitic sugar for operations on large collections. If you are using an array oriented language on large arrays then A+B should not cause your interpretter to invoke a separate iteration of your virtual machine for each pair of elements of the two arrays. Similarly for a string oriented language (e.g. many scripting languages). You do get the slow as molasses in January effect for the least interesting part of the code and Amdahl's law is more apparent in such interpreters, but the feel (and the reality) is not that bad. It does require the conscious decision to restrict the domain of the language and careful thought and follow though to take advantage of that restriction. > > if one is dealing with a dynamically-typed language, 100x to 1000x is > more common. > > > yes, but then again, interpreting x86 involves a lot of extra funkiness, > such as having to translate in-interpreter virtual-addresses into > host-process virtual addresses, which according to the profiler, was > where most of the time was going. > > typically this involved partial page-table mapping, and then looking up > the appropriate mapped memory spans (one mapped "physical memory" into > the interpreter as a number of spans). > > > > JIT seems to lead to code in the 2x to 1.5x range, depending upon the > > source and target platforms... > > > > OTOH, those numbers above is most commonly quoted in the context of Java > > byte code, which is designed be easy to interpret. :-) > > > > yes. > > JBC is sort of a very easy case for an interpreter. > > they are simple opcodes, and are statically typed, ... > > > a problem with many machine-code formats is that they are much less well > suited to be efficiently interpreted. > > one has to deal with things like the fact that AL/AH/AX/EAX all overlap, > and that accessing a sub register may involve shifts, masking, ... > > also, there are a lot of little detail things one has to worry about, > such as updating EFLAGS and similar. > > if ones' interpreter is just written straightforwardly in C, one may > note the lack of any convenient way to perform arithmetic and get status > flags, meaning that one has to manually calculate them (via lots of > shifts and bitwise operations). > > as well, there is a prevalence of complex memory-addressing calculations > (ModRM fun). > > > so, all things considered, a 70x slowdown to interpret x86 machine code > probably isn't all that bad. > > > granted, a JIT could probably do somewhat better here... > > that or someone being willing to put a lot of time into optimizing the > interpreter (my design wasn't particularly optimized). > > I did use threaded-code though, because prior to this point, the > instruction decoder (essentially a string-based pattern-matcher) made it > significantly slower. > > > or such... -- Bill Clodius los the lost and net the pet to email
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-05 19:46 -0700 |
| Message-ID | <j94sfn$dma$1@news.albasani.net> |
| In reply to | #4650 |
On 11/5/2011 5:43 PM, William Clodius wrote:
> BGB<cr88192@hotmail.com> wrote:
>
>> On 11/5/2011 10:39 AM, Terje Mathisen wrote:
>>> BGB wrote:
>>>> granted, I am expecting that a translator would likely have much better
>>>> performance than my interpreter (which had an approx 70x slowdown, due
>>>> in large-part to virtual-address translation and similar).
>>>
>>> 70x?
>>>
>>> Ouch!
>>>
>>> 10x is a more common value for a pure interpreter...
>>>
>>
>> actually, 10x is on the faster end of interpreters (IME, it is hard to
>> break about 15x or so with a "while-loop and switch()" strategy).
>
> It depends on the problem domain of the interpreter and the application
> it is being used on. If there is a good match between the domain and the
> problem, then much of the syntax will often be syntacitic sugar for
> operations on large collections. If you are using an array oriented
> language on large arrays then A+B should not cause your interpretter to
> invoke a separate iteration of your virtual machine for each pair of
> elements of the two arrays. Similarly for a string oriented language
> (e.g. many scripting languages). You do get the slow as molasses in
> January effect for the least interesting part of the code and Amdahl's
> law is more apparent in such interpreters, but the feel (and the
> reality) is not that bad. It does require the conscious decision to
> restrict the domain of the language and careful thought and follow
> though to take advantage of that restriction.
usually, the way I test the speed of interpreters is to have a loop or
similar which does arithmetic calculations.
a common example is the recursive Fibonacci sequence.
so, one does a recursive Fibonacci in the interpreter and in native
code, and compares them.
other tests would include things like calculating hashes or checksums,
using bubble-sort or ripple sort or similar on arrays, ...
how I got the 70x figure was by running the tests on the real CPU, and
comparing it against the test as being run in an x86 interpreter (in
both cases, the code was in C and was compiled with GCC).
with an interpreter for an HLL or similar, the difference is often
smaller. more so, a typical higher-level interpreter will leave a lot
more to be done by native code.
more so, if one is using a lot of natively-compiled library code, the
difference will be much smaller (in real use, the slowdown is often not
terribly severe).
also, most "real world" problems don't really take the form of "how
quickly can you calculate fib(40) via a recursive function?".
FWIW, the fib function as expressed in my scripting language (BGBScript):
function fib(x:int):int
{
if(x>2)return(fib(x-2)+fib(x-1));
else return(1);
}
or such...
[toc] | [prev] | [next] | [standalone]
| From | ChrisQ <meru@devnull.com> |
|---|---|
| Date | 2011-11-11 12:31 +0000 |
| Message-ID | <Uz8vq.7593$0%4.5604@newsfe12.ams2> |
| In reply to | #4653 |
On 11/06/11 02:46, BGB wrote:
> usually, the way I test the speed of interpreters is to have a loop or
> similar which does arithmetic calculations.
>
> a common example is the recursive Fibonacci sequence.
>
> so, one does a recursive Fibonacci in the interpreter and in native
> code, and compares them.
>
> other tests would include things like calculating hashes or checksums,
> using bubble-sort or ripple sort or similar on arrays, ...
>
>
> how I got the 70x figure was by running the tests on the real CPU, and
> comparing it against the test as being run in an x86 interpreter (in
> both cases, the code was in C and was compiled with GCC).
>
>
> with an interpreter for an HLL or similar, the difference is often
> smaller. more so, a typical higher-level interpreter will leave a lot
> more to be done by native code.
>
> more so, if one is using a lot of natively-compiled library code, the
> difference will be much smaller (in real use, the slowdown is often not
> terribly severe).
>
>
> also, most "real world" problems don't really take the form of "how
> quickly can you calculate fib(40) via a recursive function?".
>
> FWIW, the fib function as expressed in my scripting language (BGBScript):
> function fib(x:int):int
> {
> if(x>2)return(fib(x-2)+fib(x-1));
> else return(1);
> }
>
> or such...
Not that translators are my area, but wonder if you instrumented the
code to see where
it was spending all it's time, or just accepted the compiler optimised
output ?...
Regards,
Chris
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-11 12:39 -0700 |
| Message-ID | <j9jtlf$ffk$1@news.albasani.net> |
| In reply to | #4718 |
On 11/11/2011 5:31 AM, ChrisQ wrote:
> On 11/06/11 02:46, BGB wrote:
>
>> usually, the way I test the speed of interpreters is to have a loop or
>> similar which does arithmetic calculations.
>>
>> a common example is the recursive Fibonacci sequence.
>>
>> so, one does a recursive Fibonacci in the interpreter and in native
>> code, and compares them.
>>
>> other tests would include things like calculating hashes or checksums,
>> using bubble-sort or ripple sort or similar on arrays, ...
>>
>>
>> how I got the 70x figure was by running the tests on the real CPU, and
>> comparing it against the test as being run in an x86 interpreter (in
>> both cases, the code was in C and was compiled with GCC).
>>
>>
>> with an interpreter for an HLL or similar, the difference is often
>> smaller. more so, a typical higher-level interpreter will leave a lot
>> more to be done by native code.
>>
>> more so, if one is using a lot of natively-compiled library code, the
>> difference will be much smaller (in real use, the slowdown is often not
>> terribly severe).
>>
>>
>> also, most "real world" problems don't really take the form of "how
>> quickly can you calculate fib(40) via a recursive function?".
>>
>> FWIW, the fib function as expressed in my scripting language (BGBScript):
>> function fib(x:int):int
>> {
>> if(x>2)return(fib(x-2)+fib(x-1));
>> else return(1);
>> }
>>
>> or such...
>
> Not that translators are my area, but wonder if you instrumented the
> code to see where
> it was spending all it's time, or just accepted the compiler optimised
> output ?...
>
I didn't do anything "fancy" with the code, in both cases it was generic
compiler output (including for the interpreter itself).
I had analyzed the interpreter some using CodeAnalyst, so optimized the
interpreter itself in many places.
although, FWIW, I was recently testing, and my BGBScript interpreter is
233x slower than native WRT the test... ("fib(38)" currently takes about
69s).
so, in this sense, the x86 interpreter outperforms my scripting
interpreter... (granted... said script interpreter is also largely
dynamically typed...).
granted, I am annoyed some with CodeAnalyst and AMD, because apparently
AMD is being unable to effectively debug their stupid profiler...
or such...
[toc] | [prev] | [next] | [standalone]
| From | Chris Gray <cg@GraySage.com> |
|---|---|
| Date | 2011-11-11 13:28 -0700 |
| Message-ID | <87y5vmo130.fsf@GraySage.com> |
| In reply to | #4720 |
BGB <cr88192@hotmail.com> writes:
> although, FWIW, I was recently testing, and my BGBScript interpreter
> is 233x slower than native WRT the test... ("fib(38)" currently takes
> about 69s).
I can't recall, but I think you said you had a byte code engine?
I just tried it on my Zed one. With unoptimized engine, the time is a bit
under 24s. With "gcc -O3", it is a bit over 13s. Given the extra
conditional branches you'll need for dynamic type testing (Zed is statically
typed, except for explicit tests), I'd say you are doing pretty good.
--
Chris Gray
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-11 18:03 -0700 |
| Message-ID | <j9kgmc$so0$1@news.albasani.net> |
| In reply to | #4722 |
On 11/11/2011 1:28 PM, Chris Gray wrote:
> BGB<cr88192@hotmail.com> writes:
>
>> although, FWIW, I was recently testing, and my BGBScript interpreter
>> is 233x slower than native WRT the test... ("fib(38)" currently takes
>> about 69s).
>
> I can't recall, but I think you said you had a byte code engine?
>
yes.
it was partially modified more recently though (a matter of days ago) to
use a variant of threaded code, which is built from the bytecode. this
was more for flexibility reasons than performance ones though.
the interpreter itself is written mostly in plain C.
> I just tried it on my Zed one. With unoptimized engine, the time is a bit
> under 24s. With "gcc -O3", it is a bit over 13s. Given the extra
> conditional branches you'll need for dynamic type testing (Zed is statically
> typed, except for explicit tests), I'd say you are doing pretty good.
>
yep.
actually, the typesystem is not particularly efficient either, as it is
mostly built on memory-object lookups (the pointer can be to nearly
anything, managed heap or otherwise, and need not point at the start of
the object) and returning the type-name as a string.
so, it was a typesystem more built to be convenient than to be efficient.
FWIW: I have used tagger-references in the past, and although they can
generally be much more efficient, they are also generally more awkward
to work with. likewise goes for things like dealing with type-numbers or
similar (it is easier to assign types a name).
yes, "strcmp()" is not the fastest possible type-checking around.
granted, I have made much faster interpreters in the past, but it mostly
the matter of balancing performance against convenience (and a scripting
language which runs at near native speeds, but is very painful to
interface with from C, is not necessarily an ideal tradeoff...).
so, the gain is a type-system where I can use raw pointers, do most
other things one can do with raw pointers, run type-checks on whatever
(most calls are friendly to unmanaged and otherwise invalid pointers),
where adding types is often as simple as coming up with a name for it.
similarly, one can register a few callbacks and add new types of
built-in objects to the language (including executable objects, such as
function-types), ...
one doesn't have to register C functions, because the VM is generally
smart enough to figure out how to automatically glue against C functions.
this also includes accessing structs (and struct members), which can be
accessed fairly easily, provided they are allocated with a type-name,
and have an annotation in the typedef to associate between the type-name
and structure definition (in the future, I may make it so that if the
typedef-name is used as the type-name, the VM will figure it out without
an annotation).
the language can also work with raw pointers and function pointers, but
all this has not been well tested. theoretically, one can just shove a
lambda into a function pointer (say, in a struct or similar) and it
should work, but I don't currently trust this all that well.
it is also possible to export structures and functions to C (so that C
code can "call in" without needing to use API calls).
note: "most of this automatic gluing against C" stuff does require the
use of tools (basically to parse headers and similar, or to spew out C
code and headers WRT exporting), which produce databases and similar
(and have to be kept "up to date" so that struct access works).
sadly, some of these tools are a little slow...
note: C code generation can be skipped if one doesn't really need
transparent C -> script calls (and can live with making API calls, or
writing wrapper functions for said API calls...).
also, the current interface is mostly C only, and has almost no support
for C++ gluing (processing C++ and gluing against the C++ ABIs is
admittedly a bit more complex than plain C functions and structs).
IMO, it seems "reasonable" to use a C-style API for cross-language
interfacing (people *can* live without directly sharing classes and
templates across language barriers until if/when I can face this terror...).
so, it is not necessarily the fastest or most rock-solid piece of
technology around (nor necessarily the cleanest or simplest design), but
in general I am generally optimistic about how things are going with it.
nevermind if people don't like aspects of my language design:
it having a JavaScript/ActionScript style syntax, having goto, C-style
pointers, ifdef, and using a mix of C-style and Java-style APIs, ...
but, hell, not everyone can be happy.
some people can make accusations of "blub", but really, what does it
matter if it does what I want from it?...
or such...
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-12 18:25 +0100 |
| Message-ID | <jpm2p8-k571.ln1@ntp6.tmsw.no> |
| In reply to | #4724 |
BGB wrote:
> On 11/11/2011 1:28 PM, Chris Gray wrote:
>> BGB<cr88192@hotmail.com> writes:
>>
>>> although, FWIW, I was recently testing, and my BGBScript interpreter
>>> is 233x slower than native WRT the test... ("fib(38)" currently takes
>>> about 69s).
>>
>> I can't recall, but I think you said you had a byte code engine?
>>
>
> yes.
>
> it was partially modified more recently though (a matter of days ago) to
> use a variant of threaded code, which is built from the bytecode. this
> was more for flexibility reasons than performance ones though.
>
> the interpreter itself is written mostly in plain C.
>
>
>> I just tried it on my Zed one. With unoptimized engine, the time is a bit
>> under 24s. With "gcc -O3", it is a bit over 13s. Given the extra
>> conditional branches you'll need for dynamic type testing (Zed is
>> statically
>> typed, except for explicit tests), I'd say you are doing pretty good.
>>
>
Native 64-bit C code on my laptop took 0.27 seconds, looking at the
disassembly it looks like you could speed this up by 50-100% with better
asm (function prolog/epilog is important for such a tiny recursive
function).
Anyway, we're talking close to 3 orders of magnitude. :-(
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-12 12:02 -0700 |
| Message-ID | <j9mft7$dl4$1@news.albasani.net> |
| In reply to | #4730 |
On 11/12/2011 10:25 AM, Terje Mathisen wrote:
> BGB wrote:
>> On 11/11/2011 1:28 PM, Chris Gray wrote:
>>> BGB<cr88192@hotmail.com> writes:
>>>
>>>> although, FWIW, I was recently testing, and my BGBScript interpreter
>>>> is 233x slower than native WRT the test... ("fib(38)" currently takes
>>>> about 69s).
>>>
>>> I can't recall, but I think you said you had a byte code engine?
>>>
>>
>> yes.
>>
>> it was partially modified more recently though (a matter of days ago) to
>> use a variant of threaded code, which is built from the bytecode. this
>> was more for flexibility reasons than performance ones though.
>>
>> the interpreter itself is written mostly in plain C.
>>
>>
>>> I just tried it on my Zed one. With unoptimized engine, the time is a
>>> bit
>>> under 24s. With "gcc -O3", it is a bit over 13s. Given the extra
>>> conditional branches you'll need for dynamic type testing (Zed is
>>> statically
>>> typed, except for explicit tests), I'd say you are doing pretty good.
>>>
>>
>
> Native 64-bit C code on my laptop took 0.27 seconds, looking at the
> disassembly it looks like you could speed this up by 50-100% with better
> asm (function prolog/epilog is important for such a tiny recursive
> function).
>
> Anyway, we're talking close to 3 orders of magnitude. :-(
>
this is the major problem with interpreters:
they are simpler, and easier to debug, but they are not generally all
that fast.
writing a native compiler or JIT can give much better performance, but
at the cost that a compiler is much more complex both to write and
debug, and with the added drawback of not being terribly portable (any
code-generation logic has to be ported to every target).
so, an interpreter can be used as a more "portable" version, and a JIT
can be used to run things faster on a narrower subset of the targets
(or, possibly, a narrower subset of functions).
however, having a faster interpreter can still be nice, as then the
performance is not dead-slow in cases where the JIT can't be used (or,
worse yet, one is not "dead in the water" if the JIT is not available,
which is, sadly, the current status of my C compiler).
better would be if the C compiler could itself fall back to an
interpreter if no JIT were available (most likely, this could mean
eventually redirecting the C front-end's output to the BGBScript VM's
lower-end). granted, this will still not solve the "C is slow to
compile" issue (which is mostly due to having to preprocess and parse
all of the header contents).
threaded code is "nice" mostly because it opens up a few more possibilities:
one can invoke more complex logic in the interpreter, and then produce
faster threaded code (unlike with a naive loop-and-switch interpreter,
per-opcode logic need not be a part of the direct execution path);
it is more amendable to "micro-JIT" strategies, where only "bits and
pieces" of the code are JIT'ed, with other parts being left to the
interpreter (basically, it can help reduce the "nasty seam" between the
interpreter and the JIT).
for example:
an ISA such as MSIL/CIL could not be handled efficiently by a
loop-and-switch interpreter (which would essentially have to fake
static-type semantics using dynamic types), but could be more
effectively handled by a threaded-code interpreter.
I had previously devised a new VM design (the "BGBScript2 VM") which
would have attempted to re-unify the bytecode used by BGBScript and my C
compiler. this effort died (too much effort, would take too long to
implement from the ground up), and I have been left with the more
conservative strategy of retrofitting most of the stuff I had imagined
onto my existing interpreter (severely altering its internal
architecture in the process...).
sadly, it is kind of a mess, and its performance is a little weak, but
oh well...
a partial worry though is if all this is on a path to eventual
unmaintainability.
or such...
[toc] | [prev] | [next] | [standalone]
| From | Kalle Olavi Niemitalo <kon@iki.fi> |
|---|---|
| Date | 2011-11-12 22:57 +0200 |
| Subject | cost of prolog/epilog (was: big-little) |
| Message-ID | <874ny93voz.fsf_-_@Niukka.kon.iki.fi> |
| In reply to | #4730 |
Terje Mathisen <"terje.mathisen at tmsw.no"> writes: > Native 64-bit C code on my laptop took 0.27 seconds, looking at the > disassembly it looks like you could speed this up by 50-100% with > better asm (function prolog/epilog is important for such a tiny > recursive function). I tried writing the recursive part of fibonacci in amd64 asm but the result was only 1% faster for fib(45) than what gcc -O2 generated, on Intel Core i3-380UM. I'm no asm optimization expert but I did expect I'd do better. In the following assembly, fib_simple was entirely compiled by GCC, and fib_amd64 includes the hand-written part. Notice how fib_amd64 has no prolog/epilog in the recursion at all, and keeps a running sum in %rax across all recursion levels so that it need not explicitly sum the results. I did not implement correct unwind information for fib_amd64. .file "fibonacci.c" .text .p2align 4,,15 .globl fib_simple .type fib_simple, @function fib_simple: .LFB11: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 movl $1, %eax pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 subq $8, %rsp .cfi_def_cfa_offset 32 cmpq $2, %rdi jle .L2 leaq -2(%rdi), %rbx xorl %ebp, %ebp .p2align 4,,10 .p2align 3 .L3: movq %rbx, %rdi call fib_simple addq %rax, %rbp subq $1, %rbx jne .L3 leaq 1(%rbp), %rax .L2: addq $8, %rsp .cfi_def_cfa_offset 24 popq %rbx .cfi_def_cfa_offset 16 popq %rbp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE11: .size fib_simple, .-fib_simple .p2align 4,,15 .globl fib_amd64 .type fib_amd64, @function fib_amd64: .LFB12: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 xorl %eax, %eax movq %rdi, %rbx #APP # 17 "fibonacci.c" 1 jmp 2f 1: cmpq $2, %rbx jle 3f decq %rbx call 1b decq %rbx call 1b addq $2, %rbx ret 3: incq %rax ret 2: call 1b # 0 "" 2 #NO_APP popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE12: .size fib_amd64, .-fib_amd64 .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "simple: %zd\n" .LC1: .string "amd64: %zd\n" .section .text.startup,"ax",@progbits .p2align 4,,15 .globl main .type main, @function main: .LFB13: .cfi_startproc subq $8, %rsp .cfi_def_cfa_offset 16 cmpl $1, %edi movl $45, %edi je .L11 call fib_amd64 movl $.LC1, %edi movq %rax, %rsi xorl %eax, %eax call printf .L10: xorl %eax, %eax addq $8, %rsp .cfi_remember_state .cfi_def_cfa_offset 8 ret .L11: .cfi_restore_state call fib_simple movl $.LC0, %edi movq %rax, %rsi xorl %eax, %eax call printf jmp .L10 .cfi_endproc .LFE13: .size main, .-main .ident "GCC: (Debian 4.6.1-15) 4.6.1" .section .note.GNU-stack,"",@progbits
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
|---|---|
| Date | 2011-11-12 22:47 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <l563p8-n081.ln1@ntp6.tmsw.no> |
| In reply to | #4734 |
Kalle Olavi Niemitalo wrote: > Terje Mathisen<"terje.mathisen at tmsw.no"> writes: > >> Native 64-bit C code on my laptop took 0.27 seconds, looking at the >> disassembly it looks like you could speed this up by 50-100% with >> better asm (function prolog/epilog is important for such a tiny >> recursive function). > > I tried writing the recursive part of fibonacci in amd64 asm but > the result was only 1% faster for fib(45) than what gcc -O2 > generated, on Intel Core i3-380UM. I'm no asm optimization > expert but I did expect I'd do better. > > In the following assembly, fib_simple was entirely compiled by > GCC, and fib_amd64 includes the hand-written part. Notice how > fib_amd64 has no prolog/epilog in the recursion at all, and keeps > a running sum in %rax across all recursion levels so that it need > not explicitly sum the results. I did not implement correct > unwind information for fib_amd64. gcc did a better job than MSVC! I notice that gcc seem to have automatically converted the second recursive fib_simple() call, which is really tail recursion, into a much faster loop. Your asm code is using the natural dual recursive call layout. Anyway, at this point I would expect that most of the time is actually taken by branch misses, making it hard to beat by a lot even with pure asm. gcc version: > ..L3: > movq %rbx, %rdi > call fib_simple > addq %rax, %rbp > subq $1, %rbx > jne .L3 > leaq 1(%rbp), %rax > ..L2: asm: > cmpq $2, %rbx > jle 3f > decq %rbx > call 1b > decq %rbx > call 1b > addq $2, %rbx > ret I really like the way you've replaced push/pop saving of rbx (i.e. the fib(n) parameter) with an ADD RBX,2 at the end! This is _much_ faster than a pair of memory operations.:-) OTOH, this approach isn't compatible with tail conversion... 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-14 09:45 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <2011Nov14.104535@mips.complang.tuwien.ac.at> |
| In reply to | #4736 |
Terje Mathisen <"terje.mathisen at tmsw.no"> writes:
>I notice that gcc seem to have automatically converted the second
>recursive fib_simple() call, which is really tail recursion, into a much
>faster loop.
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); see
<http://groups.google.com/group/comp.compilers/browse_thread/thread/ecfa5ee1512a8ab6/da010694a1916a37#da010694a1916a37>
for a longer discussion.
- 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-14 12:28 +0100 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <eja7p8-oed1.ln1@ntp6.tmsw.no> |
| In reply to | #4758 |
Anton Ertl wrote:
> Terje Mathisen<"terje.mathisen at tmsw.no"> writes:
>> I notice that gcc seem to have automatically converted the second
>> recursive fib_simple() call, which is really tail recursion, into a much
>> faster loop.
>
> 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); see
> <http://groups.google.com/group/comp.compilers/browse_thread/thread/ecfa5ee1512a8ab6/da010694a1916a37#da010694a1916a37>
> for a longer discussion.
So gcc must effectively generate a version of fib() which has a second
parameter to be added to the result of the first evaluation?
...
OK, I see from the c.c discussion that this is close to what gcc is
doing, except that it might instead be a pattern match on the fib() dual
recursion setup?
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-15 16:48 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <2011Nov15.174834@mips.complang.tuwien.ac.at> |
| In reply to | #4759 |
Terje Mathisen <"terje.mathisen at tmsw.no"> writes: >OK, I see from the c.c discussion that this is close to what gcc is >doing, except that it might instead be a pattern match on the fib() dual >recursion setup? I guess the transformation is a little more general in theory, but in practice the only programs where it will trigger and have a significant effect on performance is the Fibonacci benchmark. Maybe it will also trigger on some tree walking code, but I doubt that that was the real reason for implementing it. - 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 | Stefan Monnier <monnier@iro.umontreal.ca> |
|---|---|
| Date | 2011-11-15 21:35 -0500 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <jwvd3cshk1t.fsf-monnier+comp.arch@gnu.org> |
| In reply to | #4774 |
>> OK, I see from the c.c discussion that this is close to what gcc is
>> doing, except that it might instead be a pattern match on the fib() dual
>> recursion setup?
> I guess the transformation is a little more general in theory, but in
> practice the only programs where it will trigger and have a
> significant effect on performance is the Fibonacci benchmark. Maybe
> it will also trigger on some tree walking code, but I doubt that that
> was the real reason for implementing it.
I'd guess that reducing stack usage is also an important benefit.
Stefan
[toc] | [prev] | [next] | [standalone]
| From | Bakul Shah <usenet@bitblocks.com> |
|---|---|
| Date | 2011-11-16 02:41 -0800 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <4EC39359.8050907@bitblocks.com> |
| In reply to | #4759 |
On 11/14/11 3:28 AM, Terje Mathisen wrote:
> Anton Ertl wrote:
>> Terje Mathisen<"terje.mathisen at tmsw.no"> writes:
>>> I notice that gcc seem to have automatically converted the second
>>> recursive fib_simple() call, which is really tail recursion, into a much
>>> faster loop.
>>
>> 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); see
>> <http://groups.google.com/group/comp.compilers/browse_thread/thread/ecfa5ee1512a8ab6/da010694a1916a37#da010694a1916a37>
>>
>> for a longer discussion.
>
> So gcc must effectively generate a version of fib() which has a second parameter to be added to the
> result of the first evaluation?
> ....
> OK, I see from the c.c discussion that this is close to what gcc is doing, except that it might
> instead be a pattern match on the fib() dual recursion setup?
>
> Terje
>
If compilers can detect "fibonacci style" dual recursion
patterns, may be they can improve an O(exp N) algorithm
to an O(log N) one! Consider the following equality
(easy to derive):
fib(n) == fib(k+1)*fib(n-k) + fib(k)*fib(n-k-1)
This translates to
fib(2k) == fib(k)*(2*fib(k-1)+fib(k)) -- even n
fib(2k+1) == fib(k)^2 + fib(k+1)^2 -- odd n
Scheme code (using a table for small fibs):
(define (fib n)
(case n
((0 1 5) n)
((2 3 4) (- n 1))
(else
(let* ((k (quotient n 2)) (fk (fib k)))
(if (odd? (modulo n 2))
(let ((fk1 (fib (+ k 1))))
(+ (* fk fk) (* fk1 fk1)))
(let ((fk-1 (fib (- k 1))))
(* fk (+ (* 2 fk-1) fk))))))))
In gambit (gci) the crossover point is at about 1000
(compared to a tail recursive tc-fib). (fib 10^6) took
1.3 seconds, while (tc-fib 10^6) took 2 minutes. Of
course, at such large number bignum arithmetic makes
tc-fib grow more as N^2 + GC plays a significant role:
58K GCs vs 545 GCs for fib.
No idea if this is of any practical value but it is
interesting that tail call optimization of fib will
at most give you a linear algorithm! Are there
iteration patterns that can be mapped to such dual
recursion? And BTW, this is parallelizable.
[toc] | [prev] | [next] | [standalone]
| From | nmm1@cam.ac.uk |
|---|---|
| Date | 2011-11-16 18:14 +0000 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja0ui5$7dh$1@gosset.csi.cam.ac.uk> |
| In reply to | #4789 |
In article <4EC39359.8050907@bitblocks.com>, Bakul Shah <usenet@bitblocks.com> wrote: > >If compilers can detect "fibonacci style" dual recursion >patterns, may be they can improve an O(exp N) algorithm >to an O(log N) one! Consider the following equality >(easy to derive): There are a zillion such cases, where a compiler can perform mind-boggling optimisations for certain simple, clear cases; but which turn out to be useless in practice. Regards, Nick Maclaren.
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-16 16:50 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <ja1i9j$516$1@news.albasani.net> |
| In reply to | #4793 |
On 11/16/2011 11:14 AM, nmm1@cam.ac.uk wrote: > In article<4EC39359.8050907@bitblocks.com>, > Bakul Shah<usenet@bitblocks.com> wrote: >> >> If compilers can detect "fibonacci style" dual recursion >> patterns, may be they can improve an O(exp N) algorithm >> to an O(log N) one! Consider the following equality >> (easy to derive): > > There are a zillion such cases, where a compiler can perform > mind-boggling optimisations for certain simple, clear cases; > but which turn out to be useless in practice. > yeah... one can also micro-optimize an interpreter to outperform a traditional compiler for special cases like these, but have it fall on its face for everything else. one could even go as far as to recognize the AST for a particular test, and then emit specialized bytecode (for example, substituting in a not-terribly-slow implementation in its place). not that micro-optimizing things like this is inherently bad, but it is generally better to optimize "common special-cases" than "special special-cases". (a lot of the bytecodes in my VM actually have to do with such "common special-case" optimizations).
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@hotmail.com> |
|---|---|
| Date | 2011-11-14 17:00 -0700 |
| Subject | Re: cost of prolog/epilog |
| Message-ID | <j9sa38$mna$1@news.albasani.net> |
| In reply to | #4758 |
On 11/14/2011 2:45 AM, Anton Ertl wrote:
> Terje Mathisen<"terje.mathisen at tmsw.no"> writes:
>> I notice that gcc seem to have automatically converted the second
>> recursive fib_simple() call, which is really tail recursion, into a much
>> faster loop.
>
> 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); see
> <http://groups.google.com/group/comp.compilers/browse_thread/thread/ecfa5ee1512a8ab6/da010694a1916a37#da010694a1916a37>
> for a longer discussion.
>
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.
granted, using deep recursion like this is not necessarily an ideal (or
realistic) case for a benchmark anyways.
tried writing a function to compare the speed of using selection sort...
there is an approx 112x speed difference (~ 143x without 'int' type
annotations).
here is the sort function (BGBScript):
function selsort(a, n:int)
{
var i:int, j:int, k:int;
for(i=0; i<n; i++)
for(j=i+1; j<n; j++)
if(a[j]<a[i])
{
k=a[i];
a[i]=a[j];
a[j]=k;
}
}
and its C analogue:
BTSV_API void btSelSort(int *a, int n)
{
int i, j, k;
for(i=0; i<n; i++)
for(j=i+1; j<n; j++)
if(a[j]<a[i])
{
k=a[i];
a[i]=a[j];
a[j]=k;
}
}
and, the test function (BGBScript):
function sorttst(x)
{
var arr;
var i;
arr=new int[x];
for(i=0; i<x; i++)
arr[i]=rand();
t0=clock();
printf("%f\n", t0);
selsort(arr, x);
t1=clock();
dt=t1-t0;
printf("%d\n", t0);
printf("%d\n", t1);
printf("%d\n", dt);
}
(the version for testing the C function is nearly identical).
[toc] | [prev] | [next] | [standalone]
Page 6 of 9 — ← Prev page 1 2 3 4 5 [6] 7 8 9 Next page →
Back to top | Article view | comp.arch
csiph-web