Chuck Moore on stack size, stack operators and function arguments

[Thomas Okken]

(11-09-2024 01:20 PM)John Keith Wrote:  Would it be possible to encode global names with a hash table, binary tree or similar data structure with O(log2(n)) access time?

I asked myself the same question when I implemented variable lookup in Free42, and I decided that the added complexity, and the added computational overhead for maintaining these data structures when variables are added or deleted, wouldn't be worth it. I didn't do any empirical tests to confirm this intuition, but rather, I based it on the observation that typically, the number of variables is not that great, so the linear search isn't that expensive.

Also, since the search starts with the most recently created variables, its real-world efficiency is a lot closer to O(1) than O(n), at least assuming the current directory isn't full of old junk that never gets cleaned up.

(11-09-2024 01:20 PM)John Keith Wrote:  BTW, I assume that in the quoted text you meant "global names are significantly faster than local names".

This depends on the implementation, but typically, local variables are searched before global ones. In Free42 and Plus42 specifically, the current function's local variables are guaranteed to be searched before anything else, so they will be found very quickly. I imagine RPL is pretty similar under the hood.