As I've already mentioned in another post (https://forum.nim-lang.org/t/5421), I've been working on an interpreter.
For keeping symbols, my Call Stack was implemented as a sequence(stack) of [string,Value] Table's.
Every time we entered in a new context (see: function block) a new [string,Value] symbol table was added with: Stack.add(newTable[string, Value]()) and every time we exited a context, the corresponding symbol table was popped from the stack by discard Stack.pop(). Also, there were getSymbol and setSymbol routines in order to get/set a specific (string,Value) pair at the top-most context in the stack.
The thing is I decided to experiment with the second option (a sequence of sequences) and the results, in intensive benchmarks, can be up to 3X faster(!). This time I'm just adding an empty seq, when creating a new "context", by Stack.add(@[]) and popping it as usual. I've also added my own hasKey method to accomodate this new data structure.
The question is: HOW is this possible?! Shouldn't hash tables be faster than my some sequences of tuples, where I'm just performing simple linear searches? Any ideas/tweaks to further improve the performance?
if a hash is useful depends on the problem. Hashes are good when you have a big dictionary which does not change (much). If you have only some elements in the dictionary, then the costs for calculating the hash values might be higher than the costs for some compares. And don't forget the costs for building the hash like you did!
But if you care about performance than I would think you should use another design. For me it sounds strange to build the symbol lookup according to the call-stack. I would make my lookup table for each scope once (at parse/compile) and than just pass a ref to that scope at runtime
Hmm... Admittedly this sounds like a nice (and obvious) idea. I'll try it and - unless I'm missing sth design/implementation-wise - it should be work much better. Let's see...
Thanks!