On 12/23/23 06:20, minforth wrote:
> Krishna Myneni wrote:
>> I do use code inlining. I don't understand what you mean by this being
>> a counter-example. For example, you may need to give interpretation
>> semantics for a word that performs a sequence of words, but the
>> compilation semantics does inline compiling of the sequence.
>
> I am a little surprised that this is a topic of discussion. See also:
> https://ethz.ch/content/dam/ethz/special-interest/infk/ast-dam/documents/Theodoridis-ASPLOS22-Inlining-Paper.pdf
>
> Well, I consider compiling a single xt to be equivalent to compiling a
> function call. Including the function body (apart from reducing function
> call overhead)
> a) eliminates the xt, so it is no longer there for decompilation or
> introspection, and
> b) creates a wider area for further optimisations.
> For example, peephole optimisation can now extend across the boundaries
> of the host code and inlined code, et cetera.

Aren't we saying the same thing? Inlining avoids compiling a function
call by including the function body in the function into which it is
inlined.

I didn't understand why you claimed inlining is a counterexample to
using dual semantics for optimization.

--
KM

Quoting you:
> Krishna Myneni wrote:
> This is my preference -- COMPILE, should simply compile the code needed
> to execute the xt given to it and not do something clever by
> substituting a different xt for it.

Generally spoken, inlining substitutes the original xt with different xts
(the inlined code) or machine code. But okay, just a misunderstanding.

Merry Xmas !! :-)

On 12/23/23 11:17, minforth wrote:
> Quoting you:
>> Krishna Myneni wrote:
>> This is my preference -- COMPILE, should simply compile the code
>> needed to execute the xt given to it and not do something clever by
>> substituting a different xt for it.
>
> Generally spoken, inlining substitutes the original xt with different xts
> (the inlined code) or machine code. But okay, just a misunderstanding.
>
> Merry Xmas !!  :-)

Likewise!

--
Krishna

On 12/22/23 08:14, Anton Ertl wrote:
> Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>> On 12/19/23 10:43, Anton Ertl wrote:
>>> Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>>>> But, I want }} to do the size-specific compilation,
>>>> eventually. To do that properly, I want to go to a dual-xt system and
>>>> avoid explicit STATE-dependence (which has other benefits we've
>>>> discussed in the past).
>>>
>>> Avoiding STATE is a good idea. However, what you have in mind seems
>>> to be an optimization, not something like S". Dual-xt words are good
>>> for stuff like S"; you can use them for optimization, but the
>>> intelligent COMPILE, is better for that.
>>>
>>
>> We had a discussion about this earlier, and I did not like the design of
>> SET-OPTIMIZER changing the behavior of COMPILE, .
>
> If it changes the behaviour of COMPILE, (rather than the
> implementation of that behaviour), that's a mistake in the use of
> SET-OPTIMIZER: Whatever you do, it must not change the behaviour.
>
>> I don't see the
>> drawback of changing the xt for compilation state as a method of
>> optimization. Why add extra complexity with SET-OPTIMIZER when you don't
>> have to?
>
> * It's a separation of concerns: SET-OPTIMIZER is for optimization and
> must not change the behaviour (i.e., if you replace the call to
> SET-OPTIMIZER with DROP, the program should still work), whereas
> SET->COMP (and related words such as INTERPRET/COMPILE:) changes the
> compilation semantics, i.e., the behaviour.
>
> * If you implement [COMPILE], you need to know if a word has
> non-default compilation semantics. If you have the separation of
> concerns above, that is easy: If it does not have the default
> NAME>COMPILE method (DEFAULT-NAME>COMP), it has non-default
> compilation semantics. If you are using this mechanism for a
> purpose that does not change the compilation semantics, you have to
> add a mechanism that tells the compiler about the difference, and
> the user has to provide this information in some way, too (e.g., by
> having INTERPRET/COMPILE: if the resulting word has non-default
> compilation semantics and INTERPRET/OPTIMIZE: if it has).
>
> * There is a difference in performance if an xt is COMPILE,ed; with
> the intelligent COMPILE, the result is as good as going through the
> text interpreter; with INTERPRET/COMPILE:, you get a generic call to
> the xt, while the text interpreter produces better code.
>
> * The COMPILE, methods get the xt that is COMPILE,d (they have the
> same stack effect as COMPILE,), which helps in using the same
> implementation for several xts. E.g., FOLD1-1 is the optimizer of
> 29 words (all with the stack effect ( x -- x ). INTERPRET/COMPILE:
> lacks this flexibility. I guess you could have a way that provides
> the xt or nt of the word for which you are performing the
> compilation semantics; not sure how well that would work.
>
> Finally, my vision for the (far-away) future is that words such as S"
> and TO go away, and with them the need for words such as
> INTERPRET/COMPILE: or (worse) STATE-smart words.
>

I have not had time to respond to this, but will do so in more detail in
a separate thread. This is an important topic, and it will take me a
little while to digest the points you make above, as well as lookup our
previous discussion about SET-OPTIMIZER.

My impression is that, in Gforth, you implement xt for a word as follows:

{ xt-interp, xt-compile [,xt-opt] }

and SET-OPTIMIZER allows you to specify xt-opt. Perhaps some pseudo-code
for INTERPRET will be helpful in understanding how compilation occurs in
Gforth.

--
Krishna

Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>My impression is that, in Gforth, you implement xt for a word as follows:
>
>{ xt-interp, xt-compile [,xt-opt] }
>
>and SET-OPTIMIZER allows you to specify xt-opt.

Actually, Gforth has 8 header methods (method selectors) and 9 setter
words for specifying the method implementation for a method selector
in the current word:

execute ( ... xt -- ... ) set-execute ( code-address -- )
execute ( ... xt -- ... ) set-does> ( xt -- )
compile, ( xt -- ) set-optimizer ( xt -- )
name>interpret ( nt -- xt ) set->int ( xt -- )
name>compile ( nt -- xt1 xt2 ) set->comp ( xt -- )
(to) ( val xt -- ) set-to ( xt -- )
defer@ ( xt1 -- xt2 ) set-defer@ ( xt -- )
name>string ( nt -- c-addr u ) set->string ( xt -- )
name>link ( nt1 -- nt2|0 ) set->link ( xt -- )

In particular, you change the compilation semantics by specifying the
NAME>COMPILE method implementation, which is somewhat different from
providing xt-compsem (your xt-compile). Based on that, we also
provide the convenience words:

set-compsem ( xt -- )
compsem: ( -- ) \ dedicated to Stephen Pelc
intsem: ( -- ) \ special dedication to Stephen Pelc
interpret/compile: ( xt-int xt-comp "name" -- )

Usage examples, all equivalent:

:noname ." compiling" ;
: foo ." interpreting" ; set-compsem

: foo ." interpreting" ; compsem: ." compiling" ;
: foo ." compiling" ; intsem: ." interpreting" ;

: foo-int ." interpreting" ;
: foo-comp ." compiling" ;
' foo-int ' foo-comp interpret/compile: foo

Note that several people (including me) have recommended to define,
for every dual-semantics word like FOO, also FOO-INT and FOO-COMP.

Usage:
9 interpret/compile:
1 set-compsem: (in the definition of COMPSEM:)
1 compsem:
0 intselm:
23 set-optimizer (and there are other, derived words)

Read all about it in:

http://www.euroforth.org/ef19/papers/paysan.pdf

Since then, we have moved nt and xt to point to the body.

You can see the header methods (except the code field) with

..hm ( nt -- )

E.g., for seeing the code generator of "!", you say

``! .hm

Let's compare the header methods of "!", ":", and "TO" and the
constant K-F1:

``! .hm ``: .hm ``to .hm ``k-f1 .hm
opt: peephole-compile, :, :, constant,
to: no-to no-to no-to no-to
extra: $0 $0 $0 $0
>int: noop noop a>int noop
>comp: default-name>comp default-name>comp i/c>comp default-name>comp
>string: named>string named>string named>string named>string
>link: named>link named>link named>link named>link

The "extra:" field is used for SET-DOES>.

>Perhaps some pseudo-code
>for INTERPRET will be helpful in understanding how compilation occurs in
>Gforth.

For dictionary words, what happens is, in essence:

parse-name find-name dup 0= #-13 and throw ( nt )
state @ if
name>compile
else
name>interpret
then
execute

You won't find it in this form in the current text interpreter,
because the text interpreter is now written to cover all kinds of
recognizers.

What may also be interesting to you is what happens then: For words
with default interpretation and compilation semantics (most words),
the NAME>COMPILE implementation is (simplified)

: default-name>comp ( nt -- xt1 xt2 )
name>interpret ['] compile, ;

For an immediate word, the NAME>COMPILE implementation is:

: imm>comp ( nt -- xt1 xt2 )
name>interpret ['] execute ;

Not just optimization, but all code generation happens in the
implementations of COMPILE,. E.g., ":,", "CONSTANT," and
"PEEPHOLE-COMPILE," are (simplified):

: :, ( xt -- ) >body ['] call peephole-compile, , ;

: constant, ( xt -- ) >body @ postpone literal ;

: peephole-compile, ( xt -- )
\ compile xt, appending its code to the current dynamic superinstruction
lits, here swap , compile-prim1 ;

LITS, ensures that any literals on the literal stack are compiled
before the primitive (this is part of the constant folding
implementation), and COMPILE-PRIM1 ( addr -- ) is in the C part of
Gforth; in gforth-fast, it performs stack caching, combines primitives
into superinstructions, and performs native-code generation if these
optimizations are enabled (they are by default), but at the very
least, turns the code-field address (ITC) into a code address (DTC).

Note that in the gforth and gforth-fast engines, "," alone does not
work for compiling a word, because these engines use hybrid
direct/indirect threaded code, which requires primitive-centric code
for colon definitions: In a colon definition, every word is compiled
to a primitive, possibly followed by an immediate argument; e.g., a
colon definition is compiled to the primitive CALL followed by the
address of the called word. See:

@InProceedings{ertl02,
author = {M. Anton Ertl},
title = {Threaded Code Variations and Optimizations (Extended
Version)},
booktitle = {Forth-Tagung 2002},
year = {2002},
address = {Garmisch-Partenkirchen},
url = {http://www.complang.tuwien.ac.at/papers/ertl02.ps.gz},
abstract = {Forth has been traditionally implemented as indirect
threaded code, where the code for non-primitives is
the code-field address of the word. To get the
maximum benefit from combining sequences of
primitives into superinstructions, the code produced
for a non-primitive should be a primitive followed
by a parameter (e.g., \code{lit} \emph{addr} for
variables). This paper takes a look at the steps
from a traditional threaded-code implementation to
superinstructions, and at the size and speed effects
of the various steps.\comment{It also compares these
variants of Gforth to various other Forth
implementations on contemporary machines.} The use
of superinstructions gives speedups of up to a
factor of 2 on large benchmarks on processors with
branch target buffers, but requires more space for
the primitives and the optimization tables, and also
a little more space for the threaded code.}
}

- 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: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

On 12/18/23 18:48, Krishna Myneni wrote:
> On 12/18/23 07:37, Krishna Myneni wrote:
....
> I also introduced the word "*+" in the last commit in kForth-64.
>
> *+ ( a b c -- n )  \ n = a*b + c
>
> Note that *+ is not the same as the sequence "* +", ...
>
> I expect the floating point version, F*+, to be equally, if not more
> useful for improving readability of fp code and increasing efficiency.
>
> F*+ ( F: r1 r2 r3 -- r )  \ r = r1*r2 + r3
>
> F*+ provides a intrinsic scalar linear transformation. I have not yet
> added this word.
>

I need to correct my terminology in the prior statement. It is incorrect
to refer to the word F*+ (and its integer counterpart, *+) as a scalar
"linear transformation." They allow efficient calculation of linear
functions, of the form f(x) = a*x + b.

A "linear transformation" is something else. A function effecting a
linear transformation must have the property f(x=0) = 0, which is most
certainly not true in the general case for F*+ or *+.

--
Krishna

Krishna Myneni wrote:
> I need to correct my terminology in the prior statement. It is incorrect
> to refer to the word F*+ (and its integer counterpart, *+) as a scalar
> "linear transformation." They allow efficient calculation of linear
> functions, of the form f(x) = a*x + b.

> A "linear transformation" is something else. A function effecting a
> linear transformation must have the property f(x=0) = 0, which is most
> certainly not true in the general case for F*+ or *+.

Mathematically correct. FMA or F*+ is used row-wise or column-wise within
many matrix operations e.g. Gaussian elimination.

Unsurprisingly many modern CPUs even support vectorized FMA.

On 12/29/23 02:21, Anton Ertl wrote:
> Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>> My impression is that, in Gforth, you implement xt for a word as follows:
>>
>> { xt-interp, xt-compile [,xt-opt] }
>>
>> and SET-OPTIMIZER allows you to specify xt-opt.
>
> Actually, Gforth has 8 header methods (method selectors) and 9 setter
> words for specifying the method implementation for a method selector
> in the current word:
>
> execute ( ... xt -- ... ) set-execute ( code-address -- )
> execute ( ... xt -- ... ) set-does> ( xt -- )
> compile, ( xt -- ) set-optimizer ( xt -- )
> name>interpret ( nt -- xt ) set->int ( xt -- )
> name>compile ( nt -- xt1 xt2 ) set->comp ( xt -- )
> (to) ( val xt -- ) set-to ( xt -- )
> defer@ ( xt1 -- xt2 ) set-defer@ ( xt -- )
> name>string ( nt -- c-addr u ) set->string ( xt -- )
> name>link ( nt1 -- nt2|0 ) set->link ( xt -- )
>
> In particular, you change the compilation semantics by specifying the
> NAME>COMPILE method implementation, which is somewhat different from
> providing xt-compsem (your xt-compile). Based on that, we also
> provide the convenience words:
>
> set-compsem ( xt -- )
> compsem: ( -- ) \ dedicated to Stephen Pelc
> intsem: ( -- ) \ special dedication to Stephen Pelc
> interpret/compile: ( xt-int xt-comp "name" -- )
>
> Usage examples, all equivalent:
>
> :noname ." compiling" ;
> : foo ." interpreting" ; set-compsem
>
> : foo ." interpreting" ; compsem: ." compiling" ;
> : foo ." compiling" ; intsem: ." interpreting" ;
>
> : foo-int ." interpreting" ;
> : foo-comp ." compiling" ;
> ' foo-int ' foo-comp interpret/compile: foo
>
> Note that several people (including me) have recommended to define,
> for every dual-semantics word like FOO, also FOO-INT and FOO-COMP.
>
> Usage:
> 9 interpret/compile:
> 1 set-compsem: (in the definition of COMPSEM:)
> 1 compsem:
> 0 intselm:
> 23 set-optimizer (and there are other, derived words)
>
> Read all about it in:
>
> http://www.euroforth.org/ef19/papers/paysan.pdf
>
> Since then, we have moved nt and xt to point to the body.
>
> You can see the header methods (except the code field) with
>
> .hm ( nt -- )
>
> E.g., for seeing the code generator of "!", you say
>
> ``! .hm
>
> Let's compare the header methods of "!", ":", and "TO" and the
> constant K-F1:
>
> ``! .hm ``: .hm ``to .hm ``k-f1 .hm
> opt: peephole-compile, :, :, constant,
> to: no-to no-to no-to no-to
> extra: $0 $0 $0 $0
>> int: noop noop a>int noop
>> comp: default-name>comp default-name>comp i/c>comp default-name>comp
>> string: named>string named>string named>string named>string
>> link: named>link named>link named>link named>link
>
> The "extra:" field is used for SET-DOES>.
>
>> Perhaps some pseudo-code
>> for INTERPRET will be helpful in understanding how compilation occurs in
>> Gforth.
>
> For dictionary words, what happens is, in essence:
>
> parse-name find-name dup 0= #-13 and throw ( nt )
> state @ if
> name>compile
> else
> name>interpret
> then
> execute
>
> You won't find it in this form in the current text interpreter,
> because the text interpreter is now written to cover all kinds of
> recognizers.
>
> What may also be interesting to you is what happens then: For words
> with default interpretation and compilation semantics (most words),
> the NAME>COMPILE implementation is (simplified)
>
> : default-name>comp ( nt -- xt1 xt2 )
> name>interpret ['] compile, ;
>
> For an immediate word, the NAME>COMPILE implementation is:
>
> : imm>comp ( nt -- xt1 xt2 )
> name>interpret ['] execute ;
>
> Not just optimization, but all code generation happens in the
> implementations of COMPILE,. E.g., ":,", "CONSTANT," and
> "PEEPHOLE-COMPILE," are (simplified):
>
> : :, ( xt -- ) >body ['] call peephole-compile, , ;
>
> : constant, ( xt -- ) >body @ postpone literal ;
>
> : peephole-compile, ( xt -- )
> \ compile xt, appending its code to the current dynamic superinstruction
> lits, here swap , compile-prim1 ;
>
> LITS, ensures that any literals on the literal stack are compiled
> before the primitive (this is part of the constant folding
> implementation), and COMPILE-PRIM1 ( addr -- ) is in the C part of
> Gforth; in gforth-fast, it performs stack caching, combines primitives
> into superinstructions, and performs native-code generation if these
> optimizations are enabled (they are by default), but at the very
> least, turns the code-field address (ITC) into a code address (DTC).
>
> Note that in the gforth and gforth-fast engines, "," alone does not
> work for compiling a word, because these engines use hybrid
> direct/indirect threaded code, which requires primitive-centric code
> for colon definitions: In a colon definition, every word is compiled
> to a primitive, possibly followed by an immediate argument; e.g., a
> colon definition is compiled to the primitive CALL followed by the
> address of the called word. See:
>
> @InProceedings{ertl02,
> author = {M. Anton Ertl},
> title = {Threaded Code Variations and Optimizations (Extended
> Version)},
> booktitle = {Forth-Tagung 2002},
> year = {2002},
> address = {Garmisch-Partenkirchen},
> url = {http://www.complang.tuwien.ac.at/papers/ertl02.ps.gz},
> abstract = {Forth has been traditionally implemented as indirect
> threaded code, where the code for non-primitives is
> the code-field address of the word. To get the
> maximum benefit from combining sequences of
> primitives into superinstructions, the code produced
> for a non-primitive should be a primitive followed
> by a parameter (e.g., \code{lit} \emph{addr} for
> variables). This paper takes a look at the steps
> from a traditional threaded-code implementation to
> superinstructions, and at the size and speed effects
> of the various steps.\comment{It also compares these
> variants of Gforth to various other Forth
> implementations on contemporary machines.} The use
> of superinstructions gives speedups of up to a
> factor of 2 on large benchmarks on processors with
> branch target buffers, but requires more space for
> the primitives and the optimization tables, and also
> a little more space for the threaded code.}
> }
>
> - anton

Thank you for the details. There is a good deal to absorb here.

--
Krishna

On 3/01/2024 1:11 pm, Krishna Myneni wrote:
> On 12/29/23 02:21, Anton Ertl wrote:
>> Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>>> My impression is that, in Gforth, you implement xt for a word as follows:
>>>
>>> { xt-interp, xt-compile [,xt-opt] }
>>>
>>> and SET-OPTIMIZER allows you to specify xt-opt.
>>
>> Actually, Gforth has 8 header methods (method selectors) and 9 setter
>> words for specifying the method implementation for a method selector
>> in the current word:
>>
>> execute ( ... xt -- ... )      set-execute   ( code-address -- )
>> execute ( ... xt -- ... )      set-does>     ( xt -- )
>> compile, ( xt -- )             set-optimizer ( xt -- )
>> name>interpret ( nt -- xt )    set->int      ( xt -- )
>> name>compile ( nt -- xt1 xt2 ) set->comp     ( xt -- )
>> (to) ( val xt -- )             set-to        ( xt -- )
>> defer@ ( xt1 -- xt2 )          set-defer@    ( xt -- )
>> name>string ( nt -- c-addr u ) set->string   ( xt -- )
>> name>link ( nt1 -- nt2|0 )     set->link     ( xt -- )
>>
>> In particular, you change the compilation semantics by specifying the
>> NAME>COMPILE method implementation, which is somewhat different from
>> providing xt-compsem (your xt-compile).  Based on that, we also
>> provide the convenience words:
>>
>> set-compsem ( xt -- )
>> compsem: ( -- )                  \ dedicated to Stephen Pelc
>> intsem:  ( -- )                  \ special dedication to Stephen Pelc
>> interpret/compile: ( xt-int xt-comp "name" -- )
>>
>> Usage examples, all equivalent:
>>
>> :noname ." compiling" ;
>> : foo ." interpreting" ; set-compsem
>>
>> : foo ." interpreting" ; compsem: ." compiling" ;
>> : foo ." compiling" ;     intsem: ." interpreting" ;
>>
>> : foo-int  ." interpreting" ;
>> : foo-comp ." compiling" ;
>> ' foo-int ' foo-comp interpret/compile: foo
>>
>> Note that several people (including me) have recommended to define,
>> for every dual-semantics word like FOO, also FOO-INT and FOO-COMP.
>>
>> Usage:
>>   9 interpret/compile:
>>   1 set-compsem: (in the definition of COMPSEM:)
>>   1 compsem:
>>   0 intselm:
>> 23 set-optimizer (and there are other, derived words)
>>
>> Read all about it in:
>>
>> http://www.euroforth.org/ef19/papers/paysan.pdf
>>
>> Since then, we have moved nt and xt to point to the body.
>>
>> You can see the header methods (except the code field) with
>>
>> .hm ( nt -- )
>>
>> E.g., for seeing the code generator of "!", you say
>>
>> ``! .hm
>>
>> Let's compare the header methods of "!", ":", and "TO" and the
>> constant K-F1:
>>
>>           ``! .hm           ``: .hm           ``to .hm     ``k-f1 .hm
>> opt:     peephole-compile, :,                :,           constant,
>> to:      no-to             no-to             no-to        no-to
>> extra:   $0                $0                $0           $0
>>> int:    noop              noop              a>int        noop
>>> comp:   default-name>comp default-name>comp i/c>comp     default-name>comp
>>> string: named>string      named>string      named>string named>string
>>> link:   named>link        named>link        named>link   named>link
>>
>> The "extra:" field is used for SET-DOES>.
>>
>>> Perhaps some pseudo-code
>>> for INTERPRET will be helpful in understanding how compilation occurs in
>>> Gforth.
>>
>> For dictionary words, what happens is, in essence:
>>
>> parse-name find-name dup 0= #-13 and throw ( nt )
>> state @ if
>>    name>compile
>> else
>>    name>interpret
>> then
>> execute
>>
>> You won't find it in this form in the current text interpreter,
>> because the text interpreter is now written to cover all kinds of
>> recognizers.
>>
>> What may also be interesting to you is what happens then: For words
>> with default interpretation and compilation semantics (most words),
>> the NAME>COMPILE implementation is (simplified)
>>
>> : default-name>comp ( nt -- xt1 xt2 )
>>    name>interpret ['] compile, ;
>>
>> For an immediate word, the NAME>COMPILE implementation is:
>>
>> : imm>comp ( nt -- xt1 xt2 )
>>    name>interpret ['] execute ;
>>    Not just optimization, but all code generation happens in the
>> implementations of COMPILE,.  E.g., ":,", "CONSTANT," and
>> "PEEPHOLE-COMPILE," are (simplified):
>>
>> : :, ( xt -- ) >body ['] call peephole-compile, , ;
>>
>> : constant, ( xt -- ) >body @ postpone literal ;
>>
>> : peephole-compile, ( xt -- )
>>      \ compile xt, appending its code to the current dynamic superinstruction
>>      lits, here swap , compile-prim1 ;
>>
>> LITS, ensures that any literals on the literal stack are compiled
>> before the primitive (this is part of the constant folding
>> implementation), and COMPILE-PRIM1 ( addr -- ) is in the C part of
>> Gforth; in gforth-fast, it performs stack caching, combines primitives
>> into superinstructions, and performs native-code generation if these
>> optimizations are enabled (they are by default), but at the very
>> least, turns the code-field address (ITC) into a code address (DTC).
>>
>> Note that in the gforth and gforth-fast engines, "," alone does not
>> work for compiling a word, because these engines use hybrid
>> direct/indirect threaded code, which requires primitive-centric code
>> for colon definitions: In a colon definition, every word is compiled
>> to a primitive, possibly followed by an immediate argument; e.g., a
>> colon definition is compiled to the primitive CALL followed by the
>> address of the called word.  See:
>>
>> @InProceedings{ertl02,
>>    author =     {M. Anton Ertl},
>>    title =     {Threaded Code Variations and Optimizations (Extended
>>                    Version)},
>>    booktitle =     {Forth-Tagung 2002},
>>    year =     {2002},
>>    address =     {Garmisch-Partenkirchen},
>>    url =          {http://www.complang.tuwien.ac.at/papers/ertl02.ps.gz},
>>    abstract =     {Forth has been traditionally implemented as indirect
>>                    threaded code, where the code for non-primitives is
>>                    the code-field address of the word. To get the
>>                    maximum benefit from combining sequences of
>>                    primitives into superinstructions, the code produced
>>                    for a non-primitive should be a primitive followed
>>                    by a parameter (e.g., \code{lit} \emph{addr} for
>>                    variables). This paper takes a look at the steps
>>                    from a traditional threaded-code implementation to
>>                    superinstructions, and at the size and speed effects
>>                    of the various steps.\comment{It also compares these
>>                    variants of Gforth to various other Forth
>>                    implementations on contemporary machines.} The use
>>                    of superinstructions gives speedups of up to a
>>                    factor of 2 on large benchmarks on processors with
>>                    branch target buffers, but requires more space for
>>                    the primitives and the optimization tables, and also
>>                    a little more space for the threaded code.}
>> }
>>
>> - anton
>
> Thank you for the details. There is a good deal to absorb here.

Anton Ertl wrote:
> Not just optimization, but all code generation happens in the
> implementations of COMPILE,. E.g., ":,", "CONSTANT," and
> "PEEPHOLE-COMPILE," are (simplified):

> : :, ( xt -- ) >body ['] call peephole-compile, , ;

> : constant, ( xt -- ) >body @ postpone literal ;

> : peephole-compile, ( xt -- )
> compile xt, appending its code to the current dynamic superinstruction
> lits, here swap , compile-prim1 ;

> LITS, ensures that any literals on the literal stack are compiled
> before the primitive (this is part of the constant folding
> implementation), and COMPILE-PRIM1 ( addr -- ) is in the C part of
> Gforth; in gforth-fast, it performs stack caching, combines primitives
> into superinstructions, and performs native-code generation if these
> optimizations are enabled (they are by default), but at the very
> least, turns the code-field address (ITC) into a code address (DTC).

For constant folding, superinstructions and peephole optimisation,
my compiler has a FIFO token queue for delayed compilation.
Optimisations are based on simple pattern recognition of the queue content.
When active, this is fully automatic and does not require complicated
contortions and a bag of special words.

minforth@gmx.net (minforth) writes:
>Anton Ertl wrote:
>> Not just optimization, but all code generation happens in the
>> implementations of COMPILE,. E.g., ":,", "CONSTANT," and
>> "PEEPHOLE-COMPILE," are (simplified):
>
>> : :, ( xt -- ) >body ['] call peephole-compile, , ;
>
>> : constant, ( xt -- ) >body @ postpone literal ;
>
>> : peephole-compile, ( xt -- )
>> \ compile xt, appending its code to the current dynamic superinstruction
>> lits, here swap , compile-prim1 ;
>
>> LITS, ensures that any literals on the literal stack are compiled
>> before the primitive (this is part of the constant folding
>> implementation), and COMPILE-PRIM1 ( addr -- ) is in the C part of
>> Gforth; in gforth-fast, it performs stack caching, combines primitives
>> into superinstructions, and performs native-code generation if these
>> optimizations are enabled (they are by default), but at the very
>> least, turns the code-field address (ITC) into a code address (DTC).
>
>For constant folding, superinstructions and peephole optimisation,
>my compiler has a FIFO token queue for delayed compilation.
>Optimisations are based on simple pattern recognition of the queue content.
>When active, this is fully automatic and does not require complicated
>contortions and a bag of special words.

No words for these optimizations in this compiler? So they are
written in a different language than Forth.

Gforth also has that, and COMPILE-PRIM1 is the interface to it. It
combines primitives into superinstructions, it optimizes stack
cacheing and it optimizes many instruction-pointer updates away. It
does not use a FIFO, but compiles a superblock at a time. It is quite
complicated (contorted?), but it does produce good results. You can
see the results by disabling the optimizations. Here are results on a
Ryzen 5800X.

sieve bubble matrix fib fft
0.037 0.035 0.013 0.031 0.021 gforth-fast
0.058 0.061 0.034 0.054 0.020 gforth-fast --ss-states=0 --ss-number=0 --opt-ip-updates=0

Gforth implements constant folding and some related optimizations,
such as optimizing "2 PICK" to "THIRD" on the Forth level, and that,
of course means that there is "a bag of special words". Matthias Koch
invented this approach. It uses a literal stack, and "LITERAL" pushes
its argument to that stack rather than compiling a literal.
"COMPILE," implementations of many words look at the literal stack and
perform constant folding if all arguments are constant, or sometimes
other optimizations (e.g., of 2 PICK) if some of the arguments are
constant.

This is actually a simple and straightforward optimization, and has
the nice property that most of the optimization code is very local to
the word that is optimized. E.g., the 2 PICK optimization looks as
follows:

:noname ( xt -- )
lits# 1 u>= if
lits> case
0 of postpone dup drop exit endof
1 of postpone over drop exit endof
2 of postpone third drop exit endof
3 of postpone fourth drop exit endof
dup >lits
endcase
then
peephole-compile, ;
optimizes pick

And note that DUP also has a constant-folding optimization, but that's
local to DUP. So if you actually compile

: foo 3 0 pick ;

you get the same code as with

: foo 3 3 ;

because first PICK is optimized to "COMPILE," DUP, and then DUP is
optimized. I doubt that this particular optimization sequence will
ever happen, but there have been other cases where I have been
positively surprised how far this simple optimization got us.

Anyway, back to the "special words". I guess you mean "LITS,". Yes,
there are some places where "LITS," has to be used; these are 4 places
in Gforth, three of them corresponding to code generation boundaries
(BEGIN, the start of a closure, and BASIC-BLOCK-END), and the use in
"PEEPHOLE-COMPILE," just before calling the lower-level compiler
COMPILE-PRIM1 shown above. If you look at it from a higher level
(e.g., at the level of COMPILE,), it's "fully automatic".

- 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: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

On 4/01/2024 10:33 pm, Anton Ertl wrote:
> minforth@gmx.net (minforth) writes:
>> Anton Ertl wrote:
>>> Not just optimization, but all code generation happens in the
>>> implementations of COMPILE,. E.g., ":,", "CONSTANT," and
>>> "PEEPHOLE-COMPILE," are (simplified):
>>
>>> : :, ( xt -- ) >body ['] call peephole-compile, , ;
>>
>>> : constant, ( xt -- ) >body @ postpone literal ;
>>
>>> : peephole-compile, ( xt -- )
>>> \ compile xt, appending its code to the current dynamic superinstruction
>>> lits, here swap , compile-prim1 ;
>>
>>> LITS, ensures that any literals on the literal stack are compiled
>>> before the primitive (this is part of the constant folding
>>> implementation), and COMPILE-PRIM1 ( addr -- ) is in the C part of
>>> Gforth; in gforth-fast, it performs stack caching, combines primitives
>>> into superinstructions, and performs native-code generation if these
>>> optimizations are enabled (they are by default), but at the very
>>> least, turns the code-field address (ITC) into a code address (DTC).
>>
>> For constant folding, superinstructions and peephole optimisation,
>> my compiler has a FIFO token queue for delayed compilation.
>> Optimisations are based on simple pattern recognition of the queue content.
>> When active, this is fully automatic and does not require complicated
>> contortions and a bag of special words.
>
> No words for these optimizations in this compiler? So they are
> written in a different language than Forth.
>
> Gforth also has that, and COMPILE-PRIM1 is the interface to it. It
> combines primitives into superinstructions, it optimizes stack
> cacheing and it optimizes many instruction-pointer updates away. It
> does not use a FIFO, but compiles a superblock at a time. It is quite
> complicated (contorted?), but it does produce good results. You can
> see the results by disabling the optimizations. Here are results on a
> Ryzen 5800X.
>
> sieve bubble matrix fib fft
> 0.037 0.035 0.013 0.031 0.021 gforth-fast
> 0.058 0.061 0.034 0.054 0.020 gforth-fast --ss-states=0 --ss-number=0 --opt-ip-updates=0
>
> Gforth implements constant folding and some related optimizations,
> such as optimizing "2 PICK" to "THIRD" on the Forth level, and that,
> of course means that there is "a bag of special words". Matthias Koch
> invented this approach. It uses a literal stack, and "LITERAL" pushes
> its argument to that stack rather than compiling a literal.
> "COMPILE," implementations of many words look at the literal stack and
> perform constant folding if all arguments are constant, or sometimes
> other optimizations (e.g., of 2 PICK) if some of the arguments are
> constant.
>
> This is actually a simple and straightforward optimization, and has
> the nice property that most of the optimization code is very local to
> the word that is optimized. E.g., the 2 PICK optimization looks as
> follows:
>
> :noname ( xt -- )
> lits# 1 u>= if
> lits> case
> 0 of postpone dup drop exit endof
> 1 of postpone over drop exit endof
> 2 of postpone third drop exit endof
> 3 of postpone fourth drop exit endof
> dup >lits
> endcase
> then
> peephole-compile, ;
> optimizes pick

What this demonstrates is how badly ANS CASE needs optimization.
PICK not so much.

dxf <dxforth@gmail.com> writes:
>On 4/01/2024 10:33 pm, Anton Ertl wrote:
>> :noname ( xt -- )
>> lits# 1 u>= if
>> lits> case
>> 0 of postpone dup drop exit endof
>> 1 of postpone over drop exit endof
>> 2 of postpone third drop exit endof
>> 3 of postpone fourth drop exit endof
>> dup >lits
>> endcase
>> then
>> peephole-compile, ;
>> optimizes pick
>
>What this demonstrates is how badly ANS CASE needs optimization.
>PICK not so much.

What makes you think so?

Sure, this could be rewritten as:

create npicks ' dup , ' over , ' third , ' fourth ,

:noname ( xt -- )
lits# 1 u>= if
lits> dup 4 u< if
cells npicks + @ compile, exit then
>lits then
peephole-compile, ;
optimizes pick

and the result would be slightly faster when it is used, PICK is
compiled not that often, so why optimize it? Especially given that,
if the optimization was really useful, one could just write the latter
code.

Another question in this context is which version is easier to write
correctly and easier to read and understand.

- 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: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

On 5/01/2024 10:27 pm, Anton Ertl wrote:
> dxf <dxforth@gmail.com> writes:
>> On 4/01/2024 10:33 pm, Anton Ertl wrote:
>>> :noname ( xt -- )
>>> lits# 1 u>= if
>>> lits> case
>>> 0 of postpone dup drop exit endof
>>> 1 of postpone over drop exit endof
>>> 2 of postpone third drop exit endof
>>> 3 of postpone fourth drop exit endof
>>> dup >lits
>>> endcase
>>> then
>>> peephole-compile, ;
>>> optimizes pick
>>
>> What this demonstrates is how badly ANS CASE needs optimization.
>> PICK not so much.
>
> What makes you think so?

Is it not obvious to all that ENDOF jumps in the above are compiled but
never used? I'm curious. What is it about ANS-FORTH that users and
implementers alike have become so uncritical?

> Sure, this could be rewritten as:
>
> create npicks ' dup , ' over , ' third , ' fourth ,
>
> :noname ( xt -- )
> lits# 1 u>= if
> lits> dup 4 u< if
> cells npicks + @ compile, exit then
> >lits then
> peephole-compile, ;
> optimizes pick
>
> and the result would be slightly faster when it is used, PICK is
> compiled not that often, so why optimize it? Especially given that,
> if the optimization was really useful, one could just write the latter
> code.

Don't make a computer do what intelligence will do anyway.

> Another question in this context is which version is easier to write
> correctly and easier to read and understand.

When the cases are 0 1 2 3 etc execution tables are easy to write and
overall code is minimal. But such is not often the case.

In article <unaf0p$b7ql$1@dont-email.me>, dxf <dxforth@gmail.com> wrote:
>On 5/01/2024 10:27 pm, Anton Ertl wrote:
>> dxf <dxforth@gmail.com> writes:
>>> On 4/01/2024 10:33 pm, Anton Ertl wrote:
>>>> :noname ( xt -- )
>>>> lits# 1 u>= if
>>>> lits> case
>>>> 0 of postpone dup drop exit endof
>>>> 1 of postpone over drop exit endof
>>>> 2 of postpone third drop exit endof
>>>> 3 of postpone fourth drop exit endof
>>>> dup >lits
>>>> endcase
>>>> then
>>>> peephole-compile, ;
>>>> optimizes pick
>>>
>>> What this demonstrates is how badly ANS CASE needs optimization.
>>> PICK not so much.
>>
>> What makes you think so?
>
>Is it not obvious to all that ENDOF jumps in the above are compiled but
>never used? I'm curious. What is it about ANS-FORTH that users and
>implementers alike have become so uncritical?
>
>> Sure, this could be rewritten as:
>>
>> create npicks ' dup , ' over , ' third , ' fourth ,
>>
>> :noname ( xt -- )
>> lits# 1 u>= if
>> lits> dup 4 u< if
>> cells npicks + @ compile, exit then
>> >lits then
>> peephole-compile, ;
>> optimizes pick
>>
>> and the result would be slightly faster when it is used, PICK is
>> compiled not that often, so why optimize it? Especially given that,
>> if the optimization was really useful, one could just write the latter
>> code.
>
>Don't make a computer do what intelligence will do anyway.
>
>> Another question in this context is which version is easier to write
>> correctly and easier to read and understand.
>
>When the cases are 0 1 2 3 etc execution tables are easy to write and
>overall code is minimal. But such is not often the case.

Optimiser for each word? IMHO this is peephole gone to far.
I prefer an optimisation table.

Adding
"
0 PICK | DUP |
1 PICK | OVER |
2 PICK | ROT DUP >R ROT ROT R> |
"
is easy enough.
Is it worth it?

From my optimiser:

: (MATCH-TABLE) |
\ `` MATCH-TABLE'' points here :
'P EXECUTE | P | \ Execute optimisation
'P + 'P + | 'P 'P + + | \ Associativity optimisation
'P 'P D+ 'P 'P D+ | 'P 'P 'P 'P D+ D+ | \ Associativity optimisation
'P + 'P - | 'P 'P - + |
'P - 'P + | 'P 'P - - |
'P - 'P - | 'P 'P + - |
'P @ 'P ! | NOOP |
'P ! 'P @ | DUP 'P ! |
'P M* DROP 'P M* DROP | 'P 'P M* DROP M* DROP | \ Invalid if last drop removed!
'P OR 'P OR | 'P 'P OR OR |
'P AND 'P AND | 'P 'P AND AND |
'P XOR 'P XOR | 'P 'P XOR XOR |
[ 0 ]L + | NOOP | \ Shortcut evaluations
[ 0 ]L - | NOOP |
[ 0 ]L M* DROP | DROP 0 |
[ 0 ]L OR | NOOP |
[ 0 ]L AND | DROP 0 |
[ 0 ]L XOR | NOOP |
[ 1 ]L M* DROP | NOOP |
[ 1 ]L / | NOOP |
[ -1 ]L M* DROP | NEGATE |
[ -1 ]L / | NEGATE |
[ -1 ]L OR | DROP -1 |
[ -1 ]L AND | NOOP |
[ -1 ]L XOR | INVERT |
'P LSHIFT 'P LSHIFT | 'P 'P + LSHIFT | \ Distributivity optimisation
'P RSHIFT 'P RSHIFT | 'P 'P + RSHIFT |
[ 0 ]L 0BRANCH [ 'P , ] | NOP1 NOP1 BRANCH [ 'P , ] | \ Branch optimisation
'P 0BRANCH [ 'P , ] | NOOP | \ Non-zero, zero is matched by previous
BRANCH [ 0 , ] | NOOP |
0BRANCH [ 0 , ] | DROP |
< 0= | 1+ > |
> 0= | 1- < |
>R R> | NOOP |
R> >R | NOOP |
;

This is on top of generalised folding and before inspecting the
machine code.
The machine code matcher relies heavily on my ciasdis assembler

<! !Q LEA, XO| !!T 0 {L,} ~!!T
!Q LEA, XO| !!T 0 {L,} ~!!T !>
<A QX: !TALLY LEA, XO| 0 L, !TALLY A>
{ bufv L@ $FFFFFF AND bufc OR!U
bufv 3 + L@ bufv 10 + L@ + bufc 3 + L! }
optimisation lealea-pattern

This generates an optimisation object, with a match pattern,
a replace pattern and a replacing xt.
This is definitively ugly. In view of special registers treatment in
the 86 I am at the verge of giving up.
Making a RISCV optimiser is probably a much more fruitful endeavour.

(The optimised version of the original byte sieve benchmark comes
with 10/20 procent of vfx and swiftforth versions, but this is unfair.)

Groetjes Albert

>
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

dxf wrote:

> never used? I'm curious. What is it about ANS-FORTH that users and
> implementers alike have become so uncritical?

"to be prickly in small matters is the nature of a hedgehog"
Nietzsche

dxf <dxforth@gmail.com> writes:
>On 5/01/2024 10:27 pm, Anton Ertl wrote:
>> dxf <dxforth@gmail.com> writes:
>>> On 4/01/2024 10:33 pm, Anton Ertl wrote:
>>>> :noname ( xt -- )
>>>> lits# 1 u>= if
>>>> lits> case
>>>> 0 of postpone dup drop exit endof
>>>> 1 of postpone over drop exit endof
>>>> 2 of postpone third drop exit endof
>>>> 3 of postpone fourth drop exit endof
>>>> dup >lits
>>>> endcase
>>>> then
>>>> peephole-compile, ;
>>>> optimizes pick
>>>
>>> What this demonstrates is how badly ANS CASE needs optimization.
>>> PICK not so much.
>>
>> What makes you think so?
>
>Is it not obvious to all that ENDOF jumps in the above are compiled but
>never used?

No. It depends on the Forth system. This optimization would be
relatively easy to implement (see below), but I never found it
worthwhile.

How to implement it? When performing the compilation semantics of
EXIT, AHEAD or AGAIN, just set a flag DEAD-CODE, and clear that flag
when performing the compilation semantics of THEN or BEGIN, or when
starting a new definition. Let the code-generation words ("COMPILE,",
LITERAL etc.) skip the code generation action when DEAD-CODE is set.

Gforth maintains DEAD-CODE for the automatic scoping of local
variables, but does not skip code generation.

This optimization would also eliminate the final exit in the pattern

begin ... again ;

- 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: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

On 7/01/2024 1:09 am, sjack wrote:
> dxf wrote:
>
>> never used?  I'm curious.  What is it about ANS-FORTH that users and
>> implementers alike have become so uncritical?
>
> "to be prickly in small matters is the nature of a hedgehog"
> Nietzsche

If the tools one uses everyday are a small matter, it begs the question
what is greater.

On 7/01/2024 3:35 am, Anton Ertl wrote:
> dxf <dxforth@gmail.com> writes:
>> On 5/01/2024 10:27 pm, Anton Ertl wrote:
>>> dxf <dxforth@gmail.com> writes:
>>>> On 4/01/2024 10:33 pm, Anton Ertl wrote:
>>>>> :noname ( xt -- )
>>>>> lits# 1 u>= if
>>>>> lits> case
>>>>> 0 of postpone dup drop exit endof
>>>>> 1 of postpone over drop exit endof
>>>>> 2 of postpone third drop exit endof
>>>>> 3 of postpone fourth drop exit endof
>>>>> dup >lits
>>>>> endcase
>>>>> then
>>>>> peephole-compile, ;
>>>>> optimizes pick
>>>>
>>>> What this demonstrates is how badly ANS CASE needs optimization.
>>>> PICK not so much.
>>>
>>> What makes you think so?
>>
>> Is it not obvious to all that ENDOF jumps in the above are compiled but
>> never used?
>
> No. It depends on the Forth system. This optimization would be
> relatively easy to implement (see below), but I never found it
> worthwhile.
>
> How to implement it? When performing the compilation semantics of
> EXIT, AHEAD or AGAIN, just set a flag DEAD-CODE, and clear that flag
> when performing the compilation semantics of THEN or BEGIN, or when
> starting a new definition. Let the code-generation words ("COMPILE,",
> LITERAL etc.) skip the code generation action when DEAD-CODE is set.
>
> Gforth maintains DEAD-CODE for the automatic scoping of local
> variables, but does not skip code generation.
>
> This optimization would also eliminate the final exit in the pattern
>
> begin ... again ;

The source is replete with 'dead code' and is due to the ANS-FORTH spec.
As the spec is unlikely to change, it is left to compiler writers to
make changes in the best interests of users and Forth in general. A
user ought to be able to write:

:noname ( xt -- )
lits# 1 u>= if
lits>
0 of postpone dup drop end
1 of postpone over drop end
2 of postpone third drop end
3 of postpone fourth drop end
>lits
then
peephole-compile, ;
optimizes pick

Everything to gain and nothing to lose - other than workarounds such
as ?OF et al folks have tacked on since ANS.

On 12/13/23 18:38, Krishna Myneni wrote:
> The array and matrix definitions given in the FSL utilities source,
>
> fsl-util.x
> or
> fsl_util.x.
>
> The arrays are quite nice for their flexibility in making arrays out of
> any type of data, and are useful in many instances. However, the source
> definitions are slow on non-optimizing Forth systems.
>
> I believe the design of the arrays and matrices traces back to Julian
> Noble's, "Scientific Forth." A 1-D array is named with a trailing left
> brace "{" while 2-D matrices have a trailing double left brace, "{{".
> This allows a convenient notation
>
> a{ I }     \ resolves to address of array element I
> m{{ J I }} \ resolves to address of matrix element at row J, col I
>
....

For writing code which uses FSL arrays of FLOATS, we can improve the
efficiency significantly by defining ]F@ and ]F! . Recently, I had to
modify my Numerov integrator module in this manner, not primarily for
efficiency, but to be able to pass the address of an arbitrary element
index in an FSL array which is treated as the first element of a sub
array (this can't be done with the usual FSL array indexing method).

See

https://github.com/mynenik/kForth-64/blob/master/forth-src/fsl/extras/numerov.4th

--
KM