On another thread, Mike B writes

The idea came from David Wheeler's 6502 page and also here.

Garth has gently suggested that the split stack might not be very good.There are two 48-byte regions of zero page called 'stackl' and 'stackh', with 'tos' being stored in a separate 2-bytes contiguous region of zero page. The X register is the stack pointer Here are DUP and DROP

FIG DUP = [23] = 2 + 2 + 4 + 4 + 4 + 4 + 3
FIG DROP = [7] = 2 + 2 + 3

The normal ones (with bytes together) is:

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Another way to do it would be splitting the stack without a separate 16-bit TOS. As with FIG, words like @ or ! require a copy of tos before using (ZP),Y addressing

I can't say that I've analyzed every permutation, but when it comes to the good old NMOS 6502, I think that perhaps it would be best to concentrate on which words get executed the most often and optimize them as best you can.

Dr. Brad dropped an interesting little tidbit here:


I'll forgive him for listing twelve words in the top ten, and also mention that NEXT can be a big cycle hog, depending on implementation and host architecture (free for STC, significantly less free for others, but to varying degrees). I think that Pettil is a strong performer in the NMOS 6502 crowd because of its streamlined NEXT, not because of its split stack and separate TOS, but I am most certainly not a expert in that area, so I'll just leave it at a thought. It's a shame that NIP isn't on that list, though, because Pettil crushes the competition for that word.

A parting thought would be to spend some serious time and energy on coding an optimal ENTER and EXIT (unless we're talking STC, in which case they're just JSR and RTS).

Mike B.

Oops. I don't know how I miscounted that.

On STC Forths that don't do inline expansion, the function of NEXT (chaining from one machine language primitive to another) is performed by RTS/JSR, so it's not free. On CPUs that can do a single-instruction NEXT, STC can actually be slower.

_________________
Because there are never enough Forth implementations: http://www.camelforth.com

VARIABLE is third? really? I'm also surprised CONSTANT makes this list

The key phrase is "some benchmark Forth programs." Koopman tested a fractal landscape generation program, Conway's game of Life, a floating-point package written in high-level Forth, and the Forth compiler itself. VARIABLE was used almost as much as CALL and EXIT in the Life program. In the Forth compiler, VARIABLE didn't make the top twelve. The results I quoted were the average across all four test programs.

_________________
Because there are never enough Forth implementations: http://www.camelforth.com

Now it's my turn to say "oops". I have read your Moving Forth series enough times to know better, but maybe I'm due for another round.

I have really become enamored with DTC ... it seems to have the right "feel" in the simple work that I've been doing so far. I am not nearly advanced enough to tackle the subjects of optimizing compilers and other more modern techniques, but I wouldn't mind peeking at a few links, if you have any available.

Thanks,

Mike B.

So, here's a frightening thought: Using KimKlone-like techniques, it should be possible to maintain and manipulate the "effective" program counter outside of the CPU, basically using a microcode rom to indicate, based on sync and latched opcode, which bytes need to be fetched from the instruction stream, completely ignoring the address provided by the CPU. Taken branches involve an extra instruction before sync, so even that can be dealt with. Next, use a 16-bit data bus and a MUX for memory access by the CPU. Add another 16-bit pointer for use as a Forth instruction pointer. Allow the microcode to kick off a 16-bit aligned read to load into the instruction pointer in a single cycle. Finally, use instruction substitution or similar to set up a two-cycle instruction that will load the externalized CPU instruction pointer from the memory pointed to by the Forth instruction pointer, also forcing a pre- or post-increment.

It's not quite a one-cycle NEXT, as it takes two cycles, but it should still be a win over RTS/JSR. Requires DTC, though. ITC would be three cycles with this sort of scheme.

(edit: swapped DTC and ITC in the context of cycle counts.)

Had I been aware of the concept of a split stack at the time, I would definitely have incorporated it into my forth. However, it would be low on my list of priorities to do now. Since adding or removing numbers from the stack involves only one DEX or INX instead of two (saving 2 clock cycles each time) there is a saving to be had but not enough to justify the effort of getting it to work right in an existing forth.

Having a separate TOS is useful in processors like the x86 where you can dedicate a register solely for that purpose - especially if you can reverse the roles of the data and return stack pointers so that refilling the TOS becomes a simple POP operation.

On a 6502 there is not so much of an advantage. Even the fact that the TOS would be a pointer in its own right is only a marginal advantage. There is definitely an advantage when performing the @ operation but not for the corresponding ! operation because like most forth primitives, the TOS has to be refilled each time the word is executed.

In spite of the "research" listed above, I believe that after NEXT, the words that need the most time saved would be DUP and DROP. The DUP operation would be speeded up (very) slightly with a separate TOS but the DROP operation would be slowed down significantly as shown in the OP. In an STC forth, the difference would be even greater because without a separate TOS, DROP could be coded in-line as INX (or INX INX) with no JSR/RTS overhead.

I like all of your points, especially this one. It is a huge advantage in my custom hobby processor design, because I have just enough registers to dedicate the accumulator to TOS, I have auto-increment and auto-decrement, the accumulator can be used as a pointer without penalty, and pushes to the R stack can be combined with a post-load to the same register with no code space penalty. Now I just need to get the dang thing working ...

Mike B.

Alas, I don't. Many years ago my friend Charles Curley wrote a book on Forth for the 68000 -- never published; I reviewed a draft -- which had a chapter on some optimization techniques (inline expansion, if I recall correctly). Other than that, what I've learned I have picked up from hints dropped in various conference papers. I know there has been some very good work done on optimizing Forth compilers, but it tends to be proprietary.

_________________
Because there are never enough Forth implementations: http://www.camelforth.com

Yes, but if you're going to do that, why not just design a Forth CPU?

_________________
Because there are never enough Forth implementations: http://www.camelforth.com

Because then it would be off-topic for 6502.org?

I can't wait to see how it turns out ... I hope that you name it the 6502.Borg!!

Locutus B.