Chuck Moore on stack size, stack operators and function arguments

[c3d]

(11-09-2024 01:20 PM)John Keith Wrote:  Thanks, that was very informative, and leads me to another question: Would it be possible to encode global names with a hash table, binary tree or similar data structure with O(log2(n)) access time?

There is already a binary search for keywords, although I added that relatively recently (when I added the ability for the help to show the various spellings, which implied that while displaying the help, I needed to do a few keyword lookups as well). For keywords, where there are a little over 1000 keywords at the moment, this gave me roughly a 2 to 3x improvements (from memory). This was after reducing the number of theoretical lookups from ~500 (1000/2 on average) down to ~10 (log2(1000)).

So why not a 50x improvement? That's because the binary search is a bit more complicated and probably not as cache efficient as a linear search. I'm not sure how smart prefetching is on such a small chip, but jumping at random in memory has to be less efficient than moving forward regularly.

So this means that the chances we get a real benefit for a number of global variables that, on a typical calculator, is in the order of a dozen at most, seems pretty low. In number of iterations, you'd get let's say from 32 down to 5, but then each of the iteration would cost you 15 times more if the keyword lookup is any indication, and since 5x15 is much higher than 32, you would lose.

Quote:And going further, would it be practical to add a set or dictionary data type to RPL?

That data type actually exists, it's called the directory. The functionality to use that as a true dictionary is not fully exposed yet, but it's in plan. At the moment, you need to enter the directory by evaluating it, use « Value Key Store » to associate Value to Key, use « Key Recall » to get the value for Key, use just Key to evaluate the value associated to the key, and so on.

While you might think that a directory only contains name/value pairs, it's really key/value pair internally. At the moment, the ability to use non-name keys in directories is somewhat limited, but it's already exposed in DB48x as follows:

- Some special names that are really keywords are allowed, e.g. 'EQ', 'PPAR' or 'ΣDat' or 'CST'. Two primary benefits are that these special names use only one or two bytes in the directory, and then they display according to user preferences, i.e. 'EQ' or 'eq' or 'Equation', 'CST' or 'CustomMenu' depending on RPL style.

- The `NumberedVariables` flag allows you to use numbers as names, mostly to facilitate the porting of code written for keystroke calculators. So with that flag set, you can replace "3 STO00" with "3 0 STO".

- The user-mode key assignments are stored in a variable called 'Keymap' that is actually a directory with numbered entries, the index being the native keycode. So if you run something like « 'abs' 24.2 AssignKey », on a DM42 you will be able to enter the KeyMap directory, and you will see a 104 entry that is the native keycode for shifted D, and if you recall that 104 you will see the 'abs' assigned to that key.

In the future, I expect a number of additional features that will let you use directories on the stack, and not just directories in global variables. Stay tuned.

Quote:Also I thank you for your work on this inspiring project. I was sad when Claudio discontinued work on NewRPL

Is this official, or just an observation that he stopped working on it?

Quote: and DB48X gives me new hope. I am also hoping for Swiss Micros or others to make a hardware platform with a keyboard more suitable for an RPL calculator. In the mean time an Android emulator would be nice.

I heard that a few times. I actually tried building one, but for now it needs more work.

Quote:BTW, I assume that in the quoted text you meant "global names are significantly faster than local names".

Yes but the opposite, it's local names that are faster, because it's just a pointer load using some local variable index.