separate stacks

Slava Pestov <slava@jedit.org> writes Re: separate stacks

> On Aug 2, 8:03 am, m...@iae.nl (Marcel Hendrix) wrote:
>> FORTH> variable d ok
>> FORTH> d H. $00558E50 ok
>> FORTH> : foo { a b c } a b + c * a xor c and d ! ; ok
>> FORTH> : test 1 2 3 foo d @ . ; ok
>> FORTH> see test
>> Flags: ANSI
>> $00559300 : test
>> $00559308 mov $00558E50 dword-offset, 0 d#
>> $00559312 push $00558E50 dword-offset
>> $00559318 jmp .+8 ( $00482068 ) offset NEAR
>>
>> ( foo completely optimized away as its result can be pre-computed to be 0= )

> Can you explain why it is easier to perform constant folding on locals
> compared to stack code?

Your quote is out of context.

| Elizabeth D Rather <erather@forth.com> writes Re: separate stacks

|| In the implementations I'm familiar with, locals are implemented on the
|| Return Stack, and objects do not have a separate stack. I know some
|| people have experimented with separate loop stacks and other things, but
|| IMO they don't offer sufficient advantages to justify the added code
|| complexity.

| For simple implementations it doesn't matter, but locals on a separate
| stack are easier to optimize; e.g.

I meant that when locals are on a separate stack, they are easier to optimize
than when intermingled with other items on the return stack.

> Can iForth prove that the following word always outputs 4?

> : foo ( a -- b ) dup 0 < if dup xor 3 + else drop 3 then 1 + ;

No, the iForth32/64 'optimizer' as such does not optimize at that
level, it only tries to generate efficient code, without ever scanning
ahead. It will never remove a branch (but it will turn conditional branches
into unconditional ones if possible.) To optimize the above you would need
language level optimization (e.g SwiftForth or eForth64).

I don't find a single appearance of 'dup xor' in my database of Forth
programs. I assume you have found that this can happen as a result of
intermediate optimizations. Care to tell us what/where that is?

-marcel

Marcel Hendrix wrote:
> Slava Pestov <slava@jedit.org> writes Re: separate stacks
....
> | Elizabeth D Rather <erather@forth.com> writes Re: separate stacks
>
> || In the implementations I'm familiar with, locals are implemented on the
> || Return Stack, and objects do not have a separate stack. I know some
> || people have experimented with separate loop stacks and other things, but
> || IMO they don't offer sufficient advantages to justify the added code
> || complexity.
>
> | For simple implementations it doesn't matter, but locals on a separate
> | stack are easier to optimize; e.g.
>
> I meant that when locals are on a separate stack, they are easier to optimize
> than when intermingled with other items on the return stack.

The implementations I was referring to set up a stack frame for the
locals on the return stack. Things aren't really "intermingled".

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

Hi

> I don't find a single appearance of 'dup xor' in my database of Forth
> programs. I assume you have found that this can happen as a result of
> intermediate optimizations. Care to tell us what/where that is?
>
> -marcel

: 0 dup xor ; ( fast zero constant when high lit penalty)

cheers
jacko

On 2 Aug, 15:48, Elizabeth D Rather <erat...@forth.com> wrote:
> jacko wrote:
> > Fist was the program stack which instructions were poped from one by
> > one, then a data stack seemed a useful idea, then return addresses
> > were clogging the data stack, and so processors implemented subrotine
> > calls, and the return stack arrived, the data stack got lost a while
> > in the expansion of the register file, but came back with java. Then a
> > split float stack came for the number crunchers, and an object stack
> > with stacks on. IIRC.
>
> I'm not sure what's your frame of reference here. *Are you talking about
> the history of computing in general, or Forth? *I'm not sure I've ever
> encountered a "program stack", and float stacks precede Java, I think.

My personal introductions to stack sage, the register file thing was
precedded by stack frames and differing ones at that C and PASCAL.
Thats when forth got interesting. Java has a seperate data stack,
although when they came back in java is not in cronological sequence.
Just my experience.

cheers.
jacko

> Cheers,
> Elizabeth
>
> --
> ==================================================
> Elizabeth D. Rather * (US & Canada) * 800-55-FORTH
> FORTH Inc. * * * * * * * * * * * * +1 310.999.6784
> 5959 West Century Blvd. Suite 700
> Los Angeles, CA 90045http://www.forth.com
>
> "Forth-based products and Services for real-time
> applications since 1973."
> ==================================================

p.s.

: 0 DUP DUP XOR ; ( I know you know I mean't this)

jacko wrote:
> Hi
>
>> I don't find a single appearance of 'dup xor' in my database of Forth
>> programs. I assume you have found that this can happen as a result of
>> intermediate optimizations. Care to tell us what/where that is?
>>
>> -marcel
>
> : 0 dup xor ; ( fast zero constant when high lit penalty)

Have you tried it?

: 0 ( n -- 0 ) DUP XOR ; \ Nasty!

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On 4 Aug, 16:27, Jerry Avins <j...@ieee.org> wrote:
> jacko wrote:
> > Hi
>
> >> I don't find a single appearance of 'dup xor' in my database of Forth
> >> programs. I assume you have found that this can happen as a result of
> >> intermediate optimizations. Care to tell us what/where that is?
>
> >> -marcel
>
> > : 0 dup xor ; ( fast zero constant when high lit penalty)
>
> Have you tried it?
>
> : 0 ( n -- 0 ) DUP XOR ; \ *Nasty!
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Yes hence the correction in new post. For some applications,
compressing the LIT val cell pairs into a single xt could be the
necessary way of workng. To this end i suggest a data base of standard
LIT constructor words using only a single xt.

net_saving = num_of_LIT_replacements - code_of_words_for_xts

of particular inteset would be often used constants.

cheers
jacko

On 4 Aug, 17:28, Thomas Pornin <por...@bolet.org> wrote:
> According to jacko *<jackokr...@gmail.com>:
>
> > : 0 dup xor ; ( fast zero constant when high lit penalty)
>
> It is:
>
> : 0 dup dup xor ;
>
> except that this does not work when the stack is empty (or rather, it
> duplicates a value from outer space, which may be harmless on some
> architectures, and devastating on others).

True a memory protection fault occurs on certain architectures. On
other achitectuesits fine, especially the tiny ones.

> As for the "fast" and "penalty": usually, the penalty associated
> with literal constants is a space problem. When the compiler encounters
> a "0", it compiles a two-cells sequence, one pointing to a special
> word (often internally dubbed "DOLIT"), then another cell containing
> the actual value (the zero). By replacing this with an actual
> exectuable word called "0", one gains one cell per call site, at
> the expense of actually calling a function which has to perform the
> job of pushing the zero.

Yep.

> One way to view this is that you are un-inlining a word. Numerical
> constants are translated by the compiler into code sequences which
> are inserted directly into the caller code. This is as if there was
> a word named "0" except that the compiler does not let it live as
> a stand-alone word. Forth allows you to redefine "0" to be a
> non-inlined word, with:
>
> : 0 (zblurk) ;
>
> where "(zblurk)" is a code sequence which actually does the job of
> pushing a zero on the data stack. When you use such an alternate
> definition, you get the space-bonus: every call site (where the
> source code contains a "0") now uses a single cell. What remains
> now is to find a zblurk sequence which is fast: it needs not be
> really small, since it occurs only once in memory, but it should
> be

as fast as possible

> since it is invoked several times (which is the reason why
> you bothered to factor it out in the first place). Now what is
> the fastest way to push a zero on the data stack ? Basically, this
> is precisely what the compiler usually does with a "0". The
> two-cell constant that the Forth compiler inserts is probably
> better than a "dup dup xor", because otherwise the compiler would
> insert a "dup dup xor". Hence this yields the following:

If your compiler is optimized for speed. If you need space
optimization, this is not the compilers job (yet) this is your job as
a factorization expert.

> : 0 0 ;
>
> which I claim is better in all aspects than your "dup dup xor" (and, in
> particular, it works with an empty stack as well).

"And I'll Just flood a custom product with unnecessary transistors,
'cos even though it runs twenty times to fast for me to make sense of
the output, I just need a bigger memory." - said the engineer to the
accountant.

> Although, really, if the space taken by the compilation of "0" is really
> an issue, then the Forth compiler itself should provide a special
> "DOLIT0" primitive, compiling to a single cell. Hey, isn't it precisely
> what FALSE does on any decent Forth implementation ?
>

Ya, but whats the definition of false?

: FALSE 0 ;

You cycle saving monkey. ;-)

cheers
jacko

hi

just for the record my definition of LIT is

LIT = RI FA RO BA SE

in http://nibz.googlecode.com instructions, so using the : 0 0 ; model
is slower!!

As for stacks, seperate float will be NO. Float words, MAYBE, and
seperate object stack, SEPARATE ABSTRACTION COMPILER.

cheers.
jacko

p.s. maybe i should have put in LIT optimization thread, xpressions of
limits under which word works.

On 4 Aug, 18:07, jacko <jackokr...@gmail.com> wrote:
> hi
>
> just for the record my definition of LIT is
>
> LIT = RI FA RO BA SE
>
> inhttp://nibz.googlecode.cominstructions, so using the : 0 0 ; model
> is slower!!
>
> As for stacks, seperate float will be NO. Float words, MAYBE, and
> seperate object stack, SEPARATE ABSTRACTION COMPILER.

Yes even the return stack will hold objects, and return to multiple
word threads. Or have other sensible defaults!

> cheers.
> jacko
>
> p.s. maybe i should have put in LIT optimization thread, xpressions of
> limits under which word works.

Hi

<snip>

> Yes even the return stack will hold objects, and return to multiple
> word threads. Or have other sensible defaults!

<snip>

Linked lists representation of stacks would be most useful here, so
that all common elements remained common, and any stack op could be
performed in a thread space, while keeping common things.

NIP would do SWAP DROP

DROP would follow chain one down, but SWAP would have to drop two and
replace them in oposite order, and then join into the common elements,
this would leave the un swapped set still accessable from any thread
which had not done a swap also.

I believe this to be a powerful concept, getting arround memory
fragmentation issues. A parallel gc would not be too hard. (mark
referers in loop, until refered base not grow). Although reference
counting may be a prefered slower option.

cheers.
jacko