Chuck Moore on stack size, stack operators and function arguments

[c3d]

(11-08-2024 12:31 PM)John Keith Wrote:  While Moore's views on stack depth are rather extreme, we must realize that a major reason for the "stackrobatics" that we see in RPL programs is speed. Stack operations are faster than algebraic expressions or STO and RCL operations, and the 48 series is not that fast to begin with, so programs tend toward heavy use of the stack. NewRPL and (presumably) DB48X have more efficient variable assignments and shouldn't be as dependent on the stack, so we may see lighter stack usage with these newer systems.

Well, I can comment on this specifically.

RPN calculators typically have the actual values in the stack or in registers. Except in the case of indirect accessing, the cost of accessing a stack register or memory register is roughly the same: you simply load the data from a known location. X, Y, Z or T are known locations or registers, so are R0, R19, etc.

In RPL in general, and DB48x in particular, the stack can contain arbitrary objects. This is achieve by having pointers to objects on the stack, where the objects themselves have some type identifier in their memory representation (a prologue for HP calculators or newRPL, an LEB128-encoded type ID for DB48x). This adds a level of indirection relative to RPN.

This means that the cost of accessing a stack element is constant: you just load a pointer, and you have your object. However, the cost of accessing a named global variable is not constant. You need to lookup the name by scanning the curent directory, and if that fails, the parent directory, and so on. Once you have found the value, you put a pointer to it on the stack, and from there, the cost of operations on that value is the same as for any object (it does not matter if the object is in a global or some temporary). But the lookup of a named global variable is not constant and potentially somewhat expensive. As far as I know, all existing RPL implementations do a simple linear search, so the cost is O(n) where n is the number of variables to search.

RPL also has a notion of local variables. The HP48 implementation uses the prologue 02E6D for local names, but they otherwise have the same structure as a regular name, i.e. they contain a number of characters and then the characters of the name. In other words, on the HP48, local names must must be looked up as well, although presumably on a smaller set of names. They may be a tiny bit faster, but the cost of lookup is still not fixed.

DB48x local names are implemented differently. Instead of storing the names in each local name, they are stored in the program declaring the locals. In other words words, on HP48, «→ A B C « A B × A B + C ÷ »» will store the character sequences for names A and B 3 times, and for C twice, whereas the DB48x implementation stores them only once. The local name references simply index the local variables, i.e. the inner program is really stored as « r0 r1 × r0 r1 + r2 ÷ ». It is only when decompiling the program that r0 is turned back into A. You can see this effect at the moment because the debugger is not smart enough to show the name, so it will show LocalVariable0 instead of A.

The benefit of the DB48x approach is that now local name references are fixed: it's just an index into an array of pointers similar to the stack. This means that on DB48x, local names are significantly faster than local names, and should be used whenever you can.

A similar optimization exists for XLIB objects (library objects). In that case, it's even more important because XLIB objects are loaded from disk, which is expensive. The first time you evaluate an XLIB, it is loaded from disk, compiled, and from there on, the cost of evaluation is the same as a stack object. No lookup is needed.