6502.org

Someone trapped me in the forth rabbit hole via this article (reader beware: https://ratfactor.com/forth/the_program ... tself.html )

This ended up with me writing a 16-bit 6502-based port of jonesforth. It's super slow (I recently discovered TaliForth is about 3x faster) but has been a great learning experience, and led to some interesting profiling visualization. Work in progress is at https://github.com/patricksurry/forth-6502

One of the main sources of slowness comes from too much overhead in 16-bit pointer manipulation.
For example I think I went too general in using 16-bit data and return stack pointers where a single page each would
likely be enough. What do people typically use for stack size in 16bit forth?

A question that's been bugging me: since the 65(C)02 only has indirect addressing indexed by y, is there any reasonably efficient way to copy between two offsets of the same indirect address? i.e. something which would be similar to followed by but obviously that's not legal. all of I can think of is copying the indirect address value into some self modifying code that uses direct indexing but that seems pretty icky.

Nice - thanks!

In my BASIC interpreter, in which I'm targeting the NMOS 6502, I'm making use of three tricks to handle this sort of problem:

1: You can set up two zero-page pointers with the required offset between them. A single Y post-index value can then be used with both.

2: You can set X to zero, and use increments of a zero-page address for counting instead of incrementing X (the status flags are set the same way). You can then use pre-indexed indirect as if it were straight indirect. This would be one of the first things to optimise when specialising for 65C02, though.

3: If you use an index register to track the top of a stack with a fixed base, you can perform stack-relative accesses by altering the base address. This works for zero-page as well as absolute indexing, because zero-page indexing wraps within zero page, thus you can specify twos-complement negative base addresses. Both FORTH and my BASIC interpreter use a zero-page operand stack, which can be manipulated conveniently in this way.

ya I think restricting my stacks to a single page each is probably the next thing to do, so I can use an index register as a stack pointer without having to indirect via a 16-bit stack pointer

I did this in VTL02 to open and close gaps of 128 bytes or less in the program text area while inserting and deleting lines. My obsession with trimming every byte of fat from VTLC02 has gradually shrunk it down to 952 bytes (VTL02C is about 1020), prompting me to consider investing a few bytes here and there to improve performance. An improved PRNG (from Arlet) and a smarter line editor that only moves the tail of the program text once while replacing existing lines are near the top of the to-do list. I also want to see about back porting the CMOS code back to NMOS, since my recent improvements haven't all been about CMOS instructions and addressing modes. CMOS instructions can still be a deal breaker for some hobbyists, and I don't want to exclude anyone (not even the ceramic package guys with no ROR) if I can help it.

A single page for both may well suffice, with one growing down from the top and the other growing up from the bottom. >R and R> will, for example, then never overflow.

Note that if you are using X-indexed absolute addressing for the data stack / return stack, you can split into parallel byte stacks to save one X increment / decrement, eg:

PLUS:
LDA TL,X
CLC
ADC TL+1,X
STA TL+1,X
LDA TH,X
CLC
ADC TH+1,X
STA TH+1,X
INX
JMP NEXT

A net four bytes extra memory usage because you have two utility vectors in the zero page plus the stack somewhere in general memory rather than the stack in the zero page is a negligible memory penalty. And a two cycle faster DROP, typically the most frequently executed primitive, pays off some the net clock penalty that exists for memory access op execution overall.

And for memory access primitive execution speed, there are trade-offs, since you get to use (ZP) and (ZP),Y to fetch and store, which are both normally one cycle faster than (ZP,X)*, and which reduces the 16bit access penalty, since "INC D,X : BNE + : INC D+1,X : + ..." costs 8 clocks (more on crossing a page boundary)*, as opposed to 2 for "LDY #1" or "INY", and for fetches beyond C@,"TAY" to postpone the store of the first fetched byte because you are still using the vector sitting on the stack costs another two. So the 14 cycles to move a memory vector is not normally a net 14 cycle cost, it's more like a net 0-2 cycles on 16bit memory ops. For 8bit memory ops, it will be a bigger net cost, but OTOH, for the double memory ops, it's probably a net gain:

TWOFETCH: ; 2@
LDA TL,X ; costs clocks
STA W ; costs clocks
LDA TH,X ; costs clocks
STA W+1 ; costs clocks
DEX
LDA (W) ; saves 1 clock*
STA TL,X
LDY #1 ; saves clocks on T,X/T+1,X increment
LDA (W),Y ; saves 1 clock*
STA TH,X
INY ; saves clocks on T,X/T+1,X increment
LDA (W),Y ; saves 1 clock*
STA TL+1,X ; saves clocks on preserving (T,X)
INY ; saves clocks on T,X/T+1,X increment
LDA (W),Y ; saves one clock*
STA TH+1,X
JMP NEXT

__________________
{* Note: if the (W),Y crosses a page boundary, because the low byte of the base address is $FD to $FF, there is no clock saving in the post-indexed versus pre-indexed address mode, but on the other hand, the "INC T,X : BNE + : INC T+1,X" skips the branch once at a cost of 4 clock cycles, so it just juggles around where the clock cycles are saved.}

First of all, congratulations. As a member of the "oops.. I fell into a rabbit hole" club myself, I think the journey is the most rewarding part. TaliForth2 has a data stack depth of 33 16-bit cells (66 bytes) that lives in zero page, making it super easy/fast to address with (ZP,X)-based addressing that Garth describes. X always holds the top of the stack (which gets lower in value as you add things to the stack, eg. the stack grows upside down in zero page) so the TOS (Top Of Stack) 16-bit cell is always at 0,X and 1,X and the (NOS) Next On Stack is at 2,X and 3,X. Here's the code for DUP to see how it works (Tali2 is an STC forth): The underflow_1 routine makes sure there is at least 1 item on the stack.
The two DEX instructions make room on the data stack (which grows upside down, so we decrement X to make room on the "top" of the stack). Then the bytes are copied into the new location. Because we've already grown the stack, the value to be copied is at 2,X and 3,X.

I've written Forth for reading FAT32-formatted compact flash cards and generally don't use more than 1/4 of the data stack. Tali's data stack depth is technically adjustable, but one of Scot's original design goals was to leave half of zero page free for the user's use.

The return stack uses the 65C02 hardware return stack in page 1 ($0100-01FF), and I doubt I've used more than a quarter of that as well.

Is it possible to do a slight tweak to check underflow with a branch?

So you have 66 slots, from the bottom of the stack area to the top of the stack area, for a stack growing down:
BOSA: [#66L][#66H][#65L][#65H]...[#2L][#2H] TOSA: [#1L][#1H]

Now, AFTER the "DEX : DEX", the X should be indexing #2 or lower. So if you have underflow, it will be indexing #1 or somewhere above the stack. So if X is indexed relative to "DS", which is the top slot, then after X decrements, if it is not a negative value, it has an underflow. So:
Then in the case that you don't underflow, the underflow test costs 2 cycles, rather than 11 cycles for the call and return and whatever it costs to do the test itself.

Yes, but...

Tali "natively" compiles short words (eg. it will copy the assembly for the word into the word you are defining) and it has an option to strip the underflow check when doing so. There are variables you can set to control the max size of a word that will be natively compiled and also whether to strip the underflow checking. The JSR is always exactly 3 bytes on words that have underflow checking, so it's easy to strip off, and the size and speed penalty can be eliminated if you opt to strip the underflow checking while compiling. I usually leave the underflow checking on while developing new words, but will turn it off if I need the extra speed (I haven't really run into a situation where I have been concerned about the memory usage, as Forth is generally quite compact for a given functionality).

I do like your method though, from a general speed perspective, and it would probably be worth doing if Tali didn't have the ability/option to strip off the underflow check when native compiling.

Aha, that makes more sense if it can be avoided ... though I'd still be sorely tempted to trade off the size against the speed of pre-checking, with DS set to the first address above the stack, of "CPX #0 : BMI + : JMP UNDERFLOW : + ..." and strip off those seven bytes if natively compiled.

I'm used to eForth / Camel Forth style overflow and underflow checking at return to the outer interpreter -- indeed, the xForth for the Commander X16 which I partly finished a year or two ago was largely a port of CamelForth.

I've written many Forth programs, and a single page data stack coupled with a single page return stack is plenty. In fact, half of page zero data stack is usually more than enough. When that isn't enough I usually have a bug or bad design.

I'd strongly agree with that for a 16bit Forth. 64 cells on the stack should be plenty, unless an implementation has floating point words and is keeping floating points values on the data stack ... and if you have floating point words, a separate floating point stack is so handy that the answer is "don't keep floating points on your data stack".