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

Groups > comp.lang.forth > #27317 > unrolled thread

What about code blocks (not Forth blocks)?

Back to article view | Back to comp.lang.forth

Contents

  What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-17 23:56 -0800
    Re: What about code blocks (not Forth blocks)? mhx@iae.nl - 2013-12-18 01:14 -0800
      Re: What about code blocks (not Forth blocks)? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-12-18 01:34 -0800
      Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 02:33 -0800
        Re: What about code blocks (not Forth blocks)? Coos Haak <chforth@hccnet.nl> - 2013-12-18 14:36 +0100
          Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 06:24 -0800
            Re: What about code blocks (not Forth blocks)? Coos Haak <chforth@hccnet.nl> - 2013-12-19 02:54 +0100
              Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 22:12 -0800
        Re: What about code blocks (not Forth blocks)? mhx@iae.nl - 2013-12-18 05:43 -0800
    Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-18 11:21 +0000
      Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 04:31 -0800
        Re: What about code blocks (not Forth blocks)? Ilya Tarasov <ilya74.tarasov@gmail.com> - 2013-12-18 04:49 -0800
          Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 05:12 -0800
    Re: What about code blocks (not Forth blocks)? "Elizabeth D. Rather" <erather@forth.com> - 2013-12-18 08:26 -1000
      Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-18 11:03 -0800
        Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 11:21 -0800
      Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 11:19 -0800
        Re: What about code blocks (not Forth blocks)? "Elizabeth D. Rather" <erather@forth.com> - 2013-12-18 10:08 -1000
          Re: What about code blocks (not Forth blocks)? Bernd Paysan <bernd.paysan@gmx.de> - 2013-12-18 21:58 +0100
            Re: What about code blocks (not Forth blocks)? "Ed" <invalid@invalid.com> - 2013-12-19 14:15 +1100
              Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-19 13:32 +0000
                Re: What about code blocks (not Forth blocks)? "Ed" <invalid@invalid.com> - 2013-12-20 21:07 +1100
                  Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-20 12:35 +0000
                    Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-20 13:02 +0000
                    Re: What about code blocks (not Forth blocks)? "Ed" <invalid@invalid.com> - 2013-12-22 14:19 +1100
                      Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-22 10:15 +0000
                        Re: What about code blocks (not Forth blocks)? "Ed" <invalid@invalid.com> - 2013-12-24 12:30 +1100
                          Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-24 16:48 +0000
                            Re: What about code blocks (not Forth blocks)? "Ed" <invalid@invalid.com> - 2013-12-28 11:08 +1100
                              Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-28 11:40 +0000
                          Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-26 18:03 +0000
                            Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-26 10:34 -0800
                              Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-27 15:53 +0000
                                Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-28 17:26 +0000
                                  Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-28 17:53 +0000
                                    Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-28 18:21 +0000
                                      Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-29 14:49 +0000
                                        Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-29 20:45 +0000
                                          Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-30 17:08 +0000
                                            Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-30 20:00 +0000
                                  Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-28 18:04 +0000
                                    Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-28 18:47 +0000
                                      Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-28 19:12 +0000
                            Re: What about code blocks (not Forth blocks)? "Ed" <invalid@invalid.com> - 2013-12-28 11:09 +1100
                              Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-28 13:45 +0000
            Re: What about code blocks (not Forth blocks)? Elizabeth D Rather <erather@forth.com> - 2013-12-18 19:04 -1000
              Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-19 09:25 +0000
              Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-19 05:00 -0800
          Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-18 23:41 -0800
          Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-19 01:00 -0800
          Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-19 02:47 -0800
            Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-19 11:23 +0000
              Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-19 03:52 -0800
    Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-19 15:58 +0000
      Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-19 10:05 -0800
        Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-19 20:07 +0000
          Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-19 12:33 -0800
            Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-19 20:33 +0000
              Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-19 20:52 +0000
              Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-19 18:52 -0800
            Re: What about code blocks (not Forth blocks)? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-12-28 12:52 -0600
              Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-28 11:47 -0800
                Re: What about code blocks (not Forth blocks)? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-12-29 07:39 -0600
                  Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-29 08:11 -0800
              Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-29 15:25 +0000
                Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-29 08:15 -0800
                  Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-29 16:03 +0000
                    Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-29 20:54 +0000
                      Re: What about code blocks (not Forth blocks)? mhx@iae.nl - 2013-12-29 13:38 -0800
                      Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-30 17:04 +0000
                        Re: What about code blocks (not Forth blocks)? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-12-30 20:05 +0000
                          Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2013-12-30 16:49 -0800
                          Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-01-02 17:27 +0000
                Re: What about code blocks (not Forth blocks)? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-12-29 16:40 -0600
                  Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-30 16:51 +0000
                    Re: What about code blocks (not Forth blocks)? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-12-30 11:15 -0600
                      Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-30 17:37 +0000
                        Re: What about code blocks (not Forth blocks)? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-12-30 12:07 -0600
          Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-20 13:50 +0000
        Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2013-12-19 21:49 -0800
          Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2013-12-20 08:56 +0000
            Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-04-03 19:13 -0700
          Re: What about code blocks (not Forth blocks)? "WJ" <w_a_x_man@yahoo.com> - 2014-03-11 05:35 +0000
            Re: What about code blocks (not Forth blocks)? Bernd Paysan <bernd.paysan@gmx.de> - 2014-03-11 12:59 +0100
              Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-03-11 23:44 -0700
                Re: What about code blocks (not Forth blocks)? Julian Fondren <ayrnieu@gmail.com> - 2014-03-12 11:48 -0700
                  Re: What about code blocks (not Forth blocks)? Bernd Paysan <bernd.paysan@gmx.de> - 2014-03-12 20:21 +0100
                    Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-03-12 23:35 -0700
                      Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2014-03-14 14:25 +0000
                        Re: What about code blocks (not Forth blocks)? Bernd Paysan <bernd.paysan@gmx.de> - 2014-03-14 16:36 +0100
                          Re: What about code blocks (not Forth blocks)? mhx@iae.nl - 2014-03-14 11:27 -0700
                          Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-03-16 17:38 -0700
                            Re: What about code blocks (not Forth blocks)? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-03-17 03:35 -0400
                          Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2014-03-17 20:36 -0700
                            Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-18 13:13 +0000
                              Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-03-18 14:28 +0000
                              Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2014-03-18 10:10 -0700
                              Re: What about code blocks (not Forth blocks)? Paul Rubin <no.email@nospam.invalid> - 2014-03-25 12:54 -0700
                                Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-03-25 23:09 -0700
                                Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-26 13:49 +0000
                                  Re: What about code blocks (not Forth blocks)? Bernd Paysan <bernd.paysan@gmx.de> - 2014-03-26 22:07 +0100
                            Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-03-20 22:11 -0700
                          Re: What about code blocks (not Forth blocks)? hughaguilar96@yahoo.com - 2014-03-28 22:18 -0700
                            Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2014-03-29 10:57 +0000
                    Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-13 16:42 +0000
            Re: What about code blocks (not Forth blocks)? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-03-11 12:51 +0000
              Re: What about code blocks (not Forth blocks)? "Alex McDonald" <blog@rivadpm.com> - 2014-03-11 14:54 +0000
      Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-19 21:36 -0800
        Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-20 16:56 +0000
      Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-19 23:24 -0800
        Re: What about code blocks (not Forth blocks)? mhx@iae.nl - 2013-12-20 02:05 -0800
        Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-20 12:41 +0000
          Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-20 17:46 +0000
            Re: What about code blocks (not Forth blocks)? Alexander Skobelev <al.skobelev@gmail.com> - 2013-12-21 08:11 -0800
              Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-23 10:07 +0000
                Re: What about code blocks (not Forth blocks)? Bernd Paysan <bernd.paysan@gmx.de> - 2013-12-23 19:31 +0100
                  Re: What about code blocks (not Forth blocks)? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-26 17:45 +0000

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6  Next page →

#27491

Paul Rubin <no.email@nospam.invalid> wrote:
> "Alex McDonald" <blog@rivadpm.com> writes:
>> : [:  postpone ahead  here ; immediate
> 
> Hmm, does that mean the quotation is compiled inline with the rest of
> the function, and branched around during execution?  I guess that's
> simple enough, though it adds a little overhead.

On 32-bit x86 native code, it may even be the fastest way to do it: a
CALL insn pushes the start address of the quotation onto the system
stack.  If the system stack is the data stack, you're done; if not,
you have to do a push.

Andrew.

[toc] | [prev] | [next] | [standalone]

#27493

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>> Hmm, does that mean the quotation is compiled inline with the rest of
>> the function, and branched around during execution?
> On 32-bit x86 native code, it may even be the fastest way to do it: a
> CALL insn pushes the start address of the quotation onto the system
> stack.  If the system stack is the data stack, you're done; if not,
> you have to do a push.

Presumably you'd also do that if the quotation weren't inlined.  I was
thinking mostly about the branch required in the outer definition, that
would be avoided by lifting the quotation out instead of inlining it.

[toc] | [prev] | [next] | [standalone]

#27502

Paul Rubin <no.email@nospam.invalid> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>> Hmm, does that mean the quotation is compiled inline with the rest of
>>> the function, and branched around during execution?
>>
>> On 32-bit x86 native code, it may even be the fastest way to do it:
>> a CALL insn pushes the start address of the quotation onto the
>> system stack.  If the system stack is the data stack, you're done;
>> if not, you have to do a push.
> 
> Presumably you'd also do that if the quotation weren't inlined. 

How?

> I was thinking mostly about the branch required in the outer
> definition, that would be avoided by lifting the quotation out
> instead of inlining it.

The CALL in the outer definition both pushes the address of the
quotation and jumps around it.

Andrew.

[toc] | [prev] | [next] | [standalone]

#27507

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>> a CALL insn pushes the start address of the quotation onto the
>>> system stack.
>> Presumably you'd also do that if the quotation weren't inlined. 
> How?

Oh, I see what you mean now.  Clever.  But, I don't see how the obvious
approach of treating
  : foo  BLAH BLAH [: 3 XYZ :] BAR ;
as equivalent to
  : TEMP 3 XYZ ;
  : foo BLAH BLAH ['] TEMP BAR ;
can be slower.  It replaces the CALL with pushing a literal.

[toc] | [prev] | [next] | [standalone]

#27506

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Paul Rubin <no.email@nospam.invalid> wrote:
>> "Alex McDonald" <blog@rivadpm.com> writes:
>>> : [:  postpone ahead  here ; immediate
>> 
>> Hmm, does that mean the quotation is compiled inline with the rest of
>> the function, and branched around during execution?  I guess that's
>> simple enough, though it adds a little overhead.
>
>On 32-bit x86 native code, it may even be the fastest way to do it: a
>CALL insn pushes the start address of the quotation onto the system
>stack.  If the system stack is the data stack, you're done; if not,
>you have to do a push.

That may be a relatively short way to do it (but doing a PUSH imm32,
or MOV reg32, imm32 is just as short), but it is everything but fast.
It poisons the CPU-internal return stack (not the Forth return stack)
with spurious return addresses, so the return branch prediction will
fail (resulting in a misprediction penalty of around 10 cycles on
current CPUs) whenever returning from a word that contains a quotation
and all words that call such words, directly or indirectly.  In
contrast, the branch around the quotation will be perfectly predicted
(it's an unconditional absolute branch, after all) and therefore quite
cheap.

Putting the code for the quotation elsewhere would remove the
branch-around overhead (both size and space), and is perfectly
standard.  However, the overhead is small enough and the frequency of
quotations is also small enough that other things probably deserve
more attention than optimizing this.

By contrast, code should be put in a different place than writable
data.  The overheads caused by failing to do that are often huge.
While the system implementors are at it, they might consider adding
multiple code spaces to deal with quotations without introducing extra
branches.

- 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/

[toc] | [prev] | [next] | [standalone]

#27508

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> While the system implementors are at it, they might consider adding
> multiple code spaces to deal with quotations without introducing extra
> branches.

If quotations can be nested, it sounds like the extra code spaces (if
they are static) just kick the problem down the road slightly.

[toc] | [prev] | [next] | [standalone]

#27509

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> While the system implementors are at it, they might consider adding
>> multiple code spaces to deal with quotations without introducing extra
>> branches.
>
>If quotations can be nested, it sounds like the extra code spaces (if
>they are static) just kick the problem down the road slightly.

Sure.  So the implementor has the option of having a fixed number of
code spaces, and falling back to branching around if the nesting of
quotations becomes too deep, or just opening up another code space
when one is needed, without needing a fallback.  My guess is that
these options are of similar complexity, but the latter is more
elegant.

Another way to avoid the branching-around is to have multi-stage
compilation, which is natural when inlining.  So when going from
source to the intermediate representation, you branch around
quotations, then when you generate native code, you eliminate many
unconditional branches, in particular those around quotations.  The
code for the quotations is produced when the quotation is finally
EXECUTEd, and because there is only one EXECUTE starting at any time,
there is no need to deal with two code generation streams at a time.

- 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/

[toc] | [prev] | [next] | [standalone]

#27512

On 29/12/2013 16:03, Anton Ertl wrote:
> Paul Rubin <no.email@nospam.invalid> writes:
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> While the system implementors are at it, they might consider adding
>>> multiple code spaces to deal with quotations without introducing extra
>>> branches.
>>
>> If quotations can be nested, it sounds like the extra code spaces (if
>> they are static) just kick the problem down the road slightly.
>
> Sure.  So the implementor has the option of having a fixed number of
> code spaces, and falling back to branching around if the nesting of
> quotations becomes too deep, or just opening up another code space
> when one is needed, without needing a fallback.  My guess is that
> these options are of similar complexity, but the latter is more
> elegant.
>
> Another way to avoid the branching-around is to have multi-stage
> compilation, which is natural when inlining.  So when going from
> source to the intermediate representation, you branch around
> quotations, then when you generate native code, you eliminate many
> unconditional branches, in particular those around quotations.  The
> code for the quotations is produced when the quotation is finally
> EXECUTEd, and because there is only one EXECUTE starting at any time,
> there is no need to deal with two code generation streams at a time.
>

In my system the approach is a bit different. It compiles to an 
intermediate representation and when it reaches a quotation, the 
compilation of the current definition is suspended, the quotation 
compiled, when ;] is reached code is generated for the quotation. 
Compilation of the enclosing definition is resumed and code generated 
for that when the closing ; is reached. It doesn't need any 
unconditional jumps or separate code spaces. Given this nesting 
quotations is easy.


-- 
Gerry

[toc] | [prev] | [next] | [standalone]

#27513

On Sunday, December 29, 2013 9:54:42 PM UTC+1, Gerry wrote:
> On 29/12/2013 16:03, Anton Ertl wrote:
> 
> In my system the approach is a bit different. It compiles to an 
> intermediate representation and when it reaches a quotation, the 
> compilation of the current definition is suspended, the quotation 
> compiled, when ;] is reached code is generated for the quotation. 
> Compilation of the enclosing definition is resumed and code generated 
> for that when the closing ; is reached. It doesn't need any 
> unconditional jumps or separate code spaces. Given this nesting 
> quotations is easy.

This doesn't give easy access to the enclosing definition's locals?

[ In iForth we use embedded definitions (a factor of quotations) 
  for the parallel extensions (PAR and ENDPAR, STARTP and ENDP).
  New release pending Januari 2014. ]

-marcel

[toc] | [prev] | [next] | [standalone]

#27533

Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes:
>On 29/12/2013 16:03, Anton Ertl wrote:
>> Another way to avoid the branching-around is to have multi-stage
>> compilation, which is natural when inlining.  So when going from
>> source to the intermediate representation, you branch around
>> quotations, then when you generate native code, you eliminate many
>> unconditional branches, in particular those around quotations.  The
>> code for the quotations is produced when the quotation is finally
>> EXECUTEd, and because there is only one EXECUTE starting at any time,
>> there is no need to deal with two code generation streams at a time.
>>
>
>In my system the approach is a bit different. It compiles to an 
>intermediate representation and when it reaches a quotation, the 
>compilation of the current definition is suspended, the quotation 
>compiled, when ;] is reached code is generated for the quotation. 
>Compilation of the enclosing definition is resumed and code generated 
>for that when the closing ; is reached. It doesn't need any 
>unconditional jumps or separate code spaces. Given this nesting 
>quotations is easy.

So you generate code on ";" instead of (in my description) on EXECUTE.

- 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/

[toc] | [prev] | [next] | [standalone]

#27551

On 30/12/2013 17:04, Anton Ertl wrote:
> Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes:
>> On 29/12/2013 16:03, Anton Ertl wrote:
>>> Another way to avoid the branching-around is to have multi-stage
>>> compilation, which is natural when inlining.  So when going from
>>> source to the intermediate representation, you branch around
>>> quotations, then when you generate native code, you eliminate many
>>> unconditional branches, in particular those around quotations.  The
>>> code for the quotations is produced when the quotation is finally
>>> EXECUTEd, and because there is only one EXECUTE starting at any time,
>>> there is no need to deal with two code generation streams at a time.
>>>
>>
>> In my system the approach is a bit different. It compiles to an
>> intermediate representation and when it reaches a quotation, the
>> compilation of the current definition is suspended, the quotation
>> compiled, when ;] is reached code is generated for the quotation.
>> Compilation of the enclosing definition is resumed and code generated
>> for that when the closing ; is reached. It doesn't need any
>> unconditional jumps or separate code spaces. Given this nesting
>> quotations is easy.
>
> So you generate code on ";" instead of (in my description) on EXECUTE.
>

Yes, it seemed sensible to compile a whole definition into intermediate 
form, then optimise & code generate. Is that a problem?


-- 
Gerry

[toc] | [prev] | [next] | [standalone]

#27555

Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes:
> Yes, it seemed sensible to compile a whole definition into
> intermediate form, then optimise & code generate. Is that a problem?

When I first asked about generating quotation code, I was thinking in
terms of traditional threaded-code Forths with very simple compilers.  I
wondered if there was some clever but simple way to lift the quotations
out of colon definitions to avoid having to branch around them.  The
answer was "branch" and I can understand, that is perfectly workable and
Forth-like.  Obviously with a fancier compiler, a later optimization
pass can rearrange the code to get rid of the branches.

[toc] | [prev] | [next] | [standalone]

#27593

Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes:
>On 30/12/2013 17:04, Anton Ertl wrote:
>> So you generate code on ";" instead of (in my description) on EXECUTE.
>>
>
>Yes, it seemed sensible to compile a whole definition into intermediate 
>form, then optimise & code generate. Is that a problem?

No, just an observation about what the difference is.

- 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/

[toc] | [prev] | [next] | [standalone]

#27514

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Paul Rubin <no.email@nospam.invalid> wrote:
>>> "Alex McDonald" <blog@rivadpm.com> writes:
>>>> : [:  postpone ahead  here ; immediate
>>> 
>>> Hmm, does that mean the quotation is compiled inline with the rest of
>>> the function, and branched around during execution?  I guess that's
>>> simple enough, though it adds a little overhead.
>>
>>On 32-bit x86 native code, it may even be the fastest way to do it: a
>>CALL insn pushes the start address of the quotation onto the system
>>stack.  If the system stack is the data stack, you're done; if not,
>>you have to do a push.
> 
> That may be a relatively short way to do it (but doing a PUSH imm32,
> or MOV reg32, imm32 is just as short), but it is everything but
> fast.  It poisons the CPU-internal return stack (not the Forth
> return stack) with spurious return addresses, so the return branch
> prediction will fail (resulting in a misprediction penalty of around
> 10 cycles on current CPUs) whenever returning from a word that
> contains a quotation and all words that call such words, directly or
> indirectly.  In contrast, the branch around the quotation will be
> perfectly predicted (it's an unconditional absolute branch, after
> all) and therefore quite cheap.

But you still have to get the address of the quotation somehow.  I'm
assuming position-independent code here; for non-PIC a push of a
literal would do.  I suppose that a CALL to a stub that pushes the
return address again then returns, followed by a branch, would play
more nicely with return address prediction.

> Putting the code for the quotation elsewhere would remove the
> branch-around overhead (both size and space), and is perfectly
> standard.  However, the overhead is small enough and the frequency of
> quotations is also small enough that other things probably deserve
> more attention than optimizing this.

Quite.

Andrew.

[toc] | [prev] | [next] | [standalone]

#27532

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>On 32-bit x86 native code, it may even be the fastest way to do it: a
>>>CALL insn pushes the start address of the quotation onto the system
>>>stack.  If the system stack is the data stack, you're done; if not,
>>>you have to do a push.
>> 
>> That may be a relatively short way to do it (but doing a PUSH imm32,
>> or MOV reg32, imm32 is just as short), but it is everything but
>> fast.  It poisons the CPU-internal return stack (not the Forth
>> return stack) with spurious return addresses, so the return branch
>> prediction will fail (resulting in a misprediction penalty of around
>> 10 cycles on current CPUs) whenever returning from a word that
>> contains a quotation and all words that call such words, directly or
>> indirectly.  In contrast, the branch around the quotation will be
>> perfectly predicted (it's an unconditional absolute branch, after
>> all) and therefore quite cheap.
>
>But you still have to get the address of the quotation somehow.

Yes, use a MOV reg32, imm32 or (if your compiler does not do register
allocation and uses ESP as data stack pointer) PUSH imm32.

>I'm
>assuming position-independent code here;

Why?  Hamstringing your compiler for no reason is not really a good
foundation for a serious argument.

> I suppose that a CALL to a stub that pushes the
>return address again then returns, followed by a branch, would play
>more nicely with return address prediction.

Yes, but that's certainly neither the fastest nor the smallest way to
do it.

- 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/

[toc] | [prev] | [next] | [standalone]

#27534

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>>On 32-bit x86 native code, it may even be the fastest way to do it: a
>>>>CALL insn pushes the start address of the quotation onto the system
>>>>stack.  If the system stack is the data stack, you're done; if not,
>>>>you have to do a push.
>>> 
>>> That may be a relatively short way to do it (but doing a PUSH imm32,
>>> or MOV reg32, imm32 is just as short), but it is everything but
>>> fast.  It poisons the CPU-internal return stack (not the Forth
>>> return stack) with spurious return addresses, so the return branch
>>> prediction will fail (resulting in a misprediction penalty of around
>>> 10 cycles on current CPUs) whenever returning from a word that
>>> contains a quotation and all words that call such words, directly or
>>> indirectly.  In contrast, the branch around the quotation will be
>>> perfectly predicted (it's an unconditional absolute branch, after
>>> all) and therefore quite cheap.
>>
>>But you still have to get the address of the quotation somehow.
> 
> Yes, use a MOV reg32, imm32 or (if your compiler does not do register
> allocation and uses ESP as data stack pointer) PUSH imm32.
> 
>>I'm assuming position-independent code here;
> 
> Why?  Hamstringing your compiler for no reason is not really a good
> foundation for a serious argument.

It's what libraries conventionally use, and SwiftForth, for which I
did my trial implementation of quotations, is PIC.  I don't think that
PIC is necessarily a bad choice, but it's not great on 32-bit x86.

>>I suppose that a CALL to a stub that pushes the return address again
>>then returns, followed by a branch, would play more nicely with
>>return address prediction.
> 
> Yes, but that's certainly neither the fastest nor the smallest way to
> do it.

I haven't measured, but I suspect it may be for PIC.

Andrew.

[toc] | [prev] | [next] | [standalone]

#27539

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>>I'm assuming position-independent code here;
>> 
>> Why?  Hamstringing your compiler for no reason is not really a good
>> foundation for a serious argument.
>
>It's what libraries conventionally use,

Forth libraries conventionally are position-independent by coming as
source code.

> and SwiftForth, for which I
>did my trial implementation of quotations, is PIC.

Why does SwiftForth use PIC?  AFAIK They have not even managed to
separate code from writable data (which might be a reason to move code
around), so why use PIC?  It cannot be for SAVESYSTEM, because the
image is not PIC anyway, because addresses are absolute (unlike in
early Win32Forth versions) and can be stored in the image.

- 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/

[toc] | [prev] | [next] | [standalone]

#27543

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>>>I'm assuming position-independent code here;
>>> 
>>> Why?  Hamstringing your compiler for no reason is not really a good
>>> foundation for a serious argument.
>>
>>It's what libraries conventionally use,
> 
> Forth libraries conventionally are position-independent by coming as
> source code.

:-)

>> and SwiftForth, for which I did my trial implementation of
>>quotations, is PIC.
> 
> Why does SwiftForth use PIC?

I don't know.  I can think of several reasons, but can see no reason
to speculate.

Andrew.

[toc] | [prev] | [next] | [standalone]

#27383

on 19/12/2013 20:07:52, "Alex McDonald" wrote:
> on 19/12/2013 18:05:19, Paul Rubin wrote:
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> The current development version of Gforth supports quotations.
>>
>> Oh interesting. Can you say how the implementation works? The obvious
>> way to do it is rather messy compared with a traditional colon
>> compiler that just linearly lays down code into the dictionary,
>> occasionally patching a branch target. Quotations would seem to
>> require a fair amount of copying and bookkeeping. It's doable but
>> seems kind of un-Forthlike, which might be causing discomfort from
>> some quarters.
>>
> 
> The fundamentals are simple.
> 
>: [:  postpone ahead
> here ; immediate
>: ;]  postpone exit
> postpone then
> postpone literal ; immediate
> 
> That only works for a Forth that lays code & data down in the same
> space, 

Actually, I was wrong; it should work for any Forth -- but the HERE
interferes with the control stack for AHEAD THEN in the code shown. The
principal is fine, but correct implementation probably requires carnal
knowledge.

[toc] | [prev] | [next] | [standalone]

#27371

On Thursday, December 19, 2013 11:05:16 AM UTC-7, Paul Rubin wrote:
> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> > The current development version of Gforth supports quotations. 
> 
> Oh interesting.  Can you say how the implementation works?  The obvious
> way to do it is rather messy compared with a traditional colon compiler
> that just linearly lays down code into the dictionary, occasionally
> patching a branch target.  Quotations would seem to require a fair
> amount of copying and bookkeeping.  It's doable but seems kind of
> un-Forthlike, which might be causing discomfort from some quarters.

Apparently you are not on the Forth-200x mailing list? There is some history here.

Bernd Payson wrote some syntactic sugar for :NONAME which allows an unnamed definition to be defined inside of a colon word (yes, the colon word does just branch over it, which adds unneeded run-time overhead).

I said that, to be useful, the quotation needs to have access to the creator function's local variables. The idea is that you have a word (like EACH in my novice package) that traverses a data-structure. It is given the xt of a quotation, and it EXECUTEs this xt for every node in the data-structure, giving the quotation that node's address as a parameter. The quotation needs to have access to the creator function's local variables so that it can communicate back information that it obtains from the data-structure nodes. 

Bernd Payson kicked me off the Forth-200x mailing list for saying this. He wants to continue to pretend that his syntactic-sugar for :NONAME is a "quotation." Elizabeth Rather and various other people support him in doing this because they don't understand the concept at all. I think that Payson does understand that quotations need to have access to the creator function's local variables, but he just doesn't know how to implement it. Anton Ertl most likely also understands the concept, but doesn't know how to implement it either, so he is playing dumb by pretending that Payson's ridiculous implementation is meaningful in some way.

So, to hell with Forth-200x! I am writing my own language which will provide quotations that have access to the creator function's local variables. This will be one of the major advantages of my language over Forth-200x.

Also, btw, the OP's original question wasn't about quotations anyway. He wanted blocks of code. I implemented this in MFX which was written in UR/Forth. I had a word LOCAL (I would call it TEMPORARY nowadays). This word would tag the last definition as being temporary. I also had a word END-MODULE that would traverse the dictionary and smudge all of the definitions that had been tagged as temporary. Typically, END-MODULE would be used at the end of each include-file. This got rid of a lot of namespace pollution. In UR/Forth, I had to resort to assembly language to accomplish this. There were some extra bits available in the name field flag byte, and I used one of them for my "temporary" bit. I'll have this feature in my language too --- it is trivial to implement --- but it is worthwhile, especially in large programs (some of the programs I wrote at Testra were huge). 

[toc] | [prev] | [next] | [standalone]

Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6  Next page →

Back to top | Article view | comp.lang.forth

csiph-web