Re: Difficulty with Brad Rodriguez' screenful

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	Re: Difficulty with Brad Rodriguez' screenful
Date	2013-03-30 16:40 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2013Mar30.174002@mips.complang.tuwien.ac.at> (permalink)
References	(5 earlier) <ki8ihj$8af$1@online.de> <2013Mar19.160603@mips.complang.tuwien.ac.at> <kial83$tmm$1@online.de> <2013Mar20.130344@mips.complang.tuwien.ac.at> <kicso8$jga$1@online.de>

Show all headers | View raw

Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>> 1) In our work on RAFTS (also later stack caching work) we found that
>> straight-line code is usually very short in Forth, so allocating stack
>> items to registers (or, as you call it, an analytical compiler) was
>> not as effective as we had imagined; more than half of the
>> instructions were still stack overhead, because that overhead was
>> incurred at control flow boundaries; and the main source of control
>> flow boundaries were calls and returns.  So inlining is probably an
>> important optimization that can reduce the number of executed
>> instructions by a significant factor and probably provide a good
>> speedup.
>
>Yes.  Fully agreed.  Just inline *with knowledge what happens on the return 
>stack*.  This isn't compilcated.  You have to keep track of three stacks 
>(data, locals, floats), keep track of the fourth, as well.  Done.
[...]
>> Even
>> if we assume a heroic compiler like you do, it cannot inline words
>> that contain deferred words, EXECUTE, or methods;
>
>It still can.  It only needs to fill in the return stack with data when it 
>calls EXECUTE and DEFER.

Ok, that can be done.  But you lose much of the benefit of inlining:
With your language feature, you have to treat every original return
address as control-flow boundary and have to reach the canonical stack
state there, unless you can prove that the address is never returned
to, which you cannot prove for words that call EXECUTE or DEFERred
words directly or indirectly.  Now EXITs are every 6-8 primitives
dynamically, so your feature might seriously limit the benefit of an
analytical compiler.

In addition, you replace every call with an rpush and every EXIT with
an rpop unless you can prove that that's not needed.

Also, it's not as simple as just adding another stack, because the
return addresses you push are influenced by inlining (and other
transformations); that requires quite a bit of work, not just one
index more in an array.  Yes, words with internal EXIT also need that
if they are inlined.  But if a compiler writer does not do that work
(yet), your feature excludes all words from inlining that call EXECUTE
or deferred words directly or indirectly.

>However, as far as I know, the only return stack 
>trickery that usually crosses an EXECUTE/DEFER boundary is that of THROW.

If your language feature is "return-address manipulation like in the
systems before inlining and tail-call optimization", that does not
help the compiler.  It still has to implement your language feature.

If your feature is something else, how do you justify it?  And if
somebody happens to replace a regular word with a DEFERred word in a
piece of code that uses return-address manipulation, it would be
pretty nasty if that code stopped working.

> And when you need 
>an early termination from a higher order function, you can just do the RDROP 
>EXIT trick, and the compiler can convert that into a straight-forward jump.

So you suggest crossing an EXECUTE with RDROP EXIT?

>> 2) My impression is that there are not that many programs that use
>> return-address manipulation.  You use it, and Michael Gassananko, but
>> it seems to me that hardly anybody else does.  This is one of the
>> features I was thinking about when we started Gforth, and formulated
>> the "it should be a model" goal and it could be used in regular Gforth
>> in all the 20 years, and yet I have never used it (except when
>> implementin CATCH and THROW).
>
>Come on Anton, now compare that to you insisting on COMPILE,'s semantics.  

I have used it and you have used it, and probably Michael Gassananko,
too.  And probably others.

Also look at the cost side.  A correct COMPILE, costs little, whereas
your feature requires complicating inlining compilers and reduces the
benefit of inlining and an analytic compiler.

>Nobody uses what you want, except you yourself, and it's non-standard.

Read the standard!  BTW, you found the DEFERS definition that uses it
yourself, and it was not written by me.

>> I outlined how a heroic compiler could optimize CATCH and THROW in an
>> answer to Andrew Haley.
>
>As long as we keep CATCHing signals, we can't.

Sure we can.  Take a look at the example again.  Hint: Signals don't
throw a REGEXP-BALL.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Difficulty with Brad Rodriguez' screenful stephenXXX@mpeforth.com (Stephen Pelc) - 2013-03-18 12:40 +0000
  Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-18 17:23 +0100
    Re: Difficulty with Brad Rodriguez' screenful stephenXXX@mpeforth.com (Stephen Pelc) - 2013-03-18 17:35 +0000
      Re: Difficulty with Brad Rodriguez' screenful Brad Eckert <hwfwguy@gmail.com> - 2013-03-18 11:02 -0700
      Re: Difficulty with Brad Rodriguez' screenful "WJ" <w_a_x_man@yahoo.com> - 2013-03-19 03:25 +0000
    Re: Difficulty with Brad Rodriguez' screenful albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-03-18 19:35 +0000
  Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-03-18 18:17 +0000
    Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-19 03:29 +0100
      Re: Difficulty with Brad Rodriguez' screenful Paul Rubin <no.email@nospam.invalid> - 2013-03-19 00:06 -0700
        Re: Difficulty with Brad Rodriguez' screenful Paul Rubin <no.email@nospam.invalid> - 2013-03-19 00:11 -0700
          Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-19 16:16 +0100
      Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-03-19 15:06 +0000
        Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-19 22:27 +0100
          Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-20 03:49 -0500
            Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-03-20 11:09 +0000
              Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-20 10:25 -0500
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-20 18:08 +0100
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-20 13:04 -0500
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-20 20:12 +0100
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-21 04:39 -0500
                Re: Difficulty with Brad Rodriguez' screenful albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-03-20 19:22 +0000
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-03-30 17:35 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-03-31 08:51 -0500
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-02 15:50 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-02 16:16 -0500
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-03 11:57 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-03 10:25 -0500
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-03 16:45 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-03 15:12 -0500
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-04 15:29 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-05 09:11 -0500
              Re: Difficulty with Brad Rodriguez' screenful Alex McDonald <blog@rivadpm.com> - 2013-03-20 10:27 -0700
          Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-03-20 12:03 +0000
            Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-03-20 18:47 +0100
              Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-03-30 16:40 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-01 02:12 +0200
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-01 16:58 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-02 04:20 +0200
                Re: Difficulty with Brad Rodriguez' screenful "Elizabeth D. Rather" <erather@forth.com> - 2013-04-01 16:39 -1000
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-02 14:15 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-02 21:12 +0200
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-04 13:58 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-02 04:17 -0500
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-02 15:35 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-02 16:36 -0500
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-03 04:10 +0200
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-03 04:03 -0500
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-03 21:14 +0200
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-03 16:13 +0000
                Re: Difficulty with Brad Rodriguez' screenful Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-04-03 11:54 -0500
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-03 22:24 +0200
                Re: Difficulty with Brad Rodriguez' screenful stephenXXX@mpeforth.com (Stephen Pelc) - 2013-04-04 11:53 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-04 18:13 +0200
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-04 15:53 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-04 22:11 +0200
                Re: Difficulty with Brad Rodriguez' screenful Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-04-04 21:35 +0100
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-04 23:06 +0200
                Re: Difficulty with Brad Rodriguez' screenful stephenXXX@mpeforth.com (Stephen Pelc) - 2013-04-05 10:57 +0000
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-05 14:47 +0000
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-05 14:28 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-06 03:35 +0200
                Re: Difficulty with Brad Rodriguez' screenful "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-04-08 23:50 -0400
                Re: Difficulty with Brad Rodriguez' screenful "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-04-08 23:49 -0400
                Re: Difficulty with Brad Rodriguez' screenful m.a.m.hendrix@tue.nl - 2013-04-05 02:49 -0700
                Re: Difficulty with Brad Rodriguez' screenful anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-04-05 14:55 +0000
                Re: Difficulty with Brad Rodriguez' screenful Bernd Paysan <bernd.paysan@gmx.de> - 2013-04-05 22:05 +0200

csiph-web