Thanks for the details about it. They may well get applied....the in-place merge. It is a good idea!
If this means that the binary search should start in the middle of the part of the large list that remains (that which lies to the left of the current insertion point), that certainly makes sense.the binary search could start at the element located in the position n/(m+1) from the end of the larger list, not at the median.
That's a good point but the current design relies on the address of each local variable being known at load-time, and never changing throughout the life of the script (i.e. variables are never destroyed, only set to NULL contents). I'm not saying this is a good design, but rather than spending a week to redesign the whole thing, I think I'll try to patch it up. That's where save-and-restore comes in: I think it offers superior performance when there are no other instances of a function on the call stack (which is probably 90% of the time). As a trade-off, it requires more memory because local variables are all static in duration.There is no need for backup and restore the values of dynamic variables if the process ID is prefixed to their names (they get created at the first reference and purged form the table some time after the process terminates).
They don't terminate in different order. When a thread interrupts another, the interrupted thread stays suspended until the current thread finishes. In this sense, it's the same as recursion because interrupted threads are always resumed in reverse order (newest to oldest) and threads never run simultaneously in a true multithreaded sense.if subroutines are started asynchronously by external events (timer, interrupts), and terminate in different order, is a call stack still the right data structure to manage the processes?
Of the first five you posted I liked the above the best because it just comes out recommends djb2 as a great compromise between speed and distribution.Here are some references:
...
http://www.cs.yorku.ca/~oz/hash.html
In summary (from what I know now), a balanced tree is probably the best overall approach, but the need to periodically rebalance it is an example of conceptual complexity which makes it seem harder to implement (probably due to inexperience).
Hash tables seem very good too, though perhaps a little wasteful in memory if every script would require a new 256 KB table (perhaps the table could grow instead: starting at 6400 entries and growing to 64K/640K entries when the number of script variables goes beyond some certain limit, say 4000/40000). But anyway, hashing might be abandoned for now because the need to "backup" local variables would require each function to have its own hash table, which seems wasteful of memory. Individual hash tables seem necessary because backing up one block of local variables among a huge/central hash table seems like it would be very poor in performance, requiring a complete traversal of the entire table unless a separate, unsorted array of pointers-to-vars were maintained solely for backup purposes (which is probably less wasteful than separate hash tables).
So unless you see some way to salvage either of the above approaches to be workable under my constraints (and you're probably well tired of this topic by now ), that leaves the binary search idea with your wonderful lazy-sort enhancement, which will hopefully improve its performance scalability by an order of magnitude or more.
Finally, although I'd welcome further advice if you care to give it, you've already done so much that I don't want to ask for more. I might contact you via e-mail with specific questions in the future, but I'll try to keep them to a minimum.
Thanks for everything.