So you want the context save/restore to be fast, lookups to be fast, sharing of the outer scopes... it doesn't seem like you can have it all.
Using flat hash tables and cloning them and throwing them away every time is right out.
Conversation
Fine-grained persistent structures are good at sharing and save/restore, but are full of allocations, indirections, and cache inefficiency.
Coarse-grained ones seem like they'd degrade to being the same as a flat structure, because there aren't *that* many local variables.
2
1
So a flat hash table where you individually delete the new variables when exiting the scope seems like the least-bad option, but it leaves me with the nagging sense that something better must be Out There.
2
1
1
What I *really* want to do is push local variables onto a stack and then pop off an entire scope at a time, but then lookups ???
2
2
I like the idea from twitter.com/typeswitch/sta of associating each variable with an index/ID and then using arrays/vecs for everything (shades of ECS), and you can do scope-popping for those, but you still need to do the initial var->ID association somehow.
This Tweet is unavailable.
2
1
[I'm also not sure that that's /necessarily/ superior to storing a var->{struct-of-all-associated-things} mapping directly; most likely that depends on the actual usage patterns in the compiler.]
2
1
Let me know if you find a solution! I want it for Pikelet. Atm I do names->debruijn indices using the slow lookup, fast push/pop method in my elaborator. I do need persistent data structures for variable environments though :(
1
2
For NBE?
1
Hmm. IIRC `im` uses something like 64 elements per node. How much sharing do you actually get this way? (I.e., how many variables are there typically?)
1
was just like, 'ehhhh don't have to think about this right now' haha
1