What's the most efficient representation of lexically scoped local contexts for a compiler in C/C++/Rust?
Like, you enter a scope, add some variables, and, upon leaving, restore the state from before it was entered, all the while supporting lookups of variables at any depth.
Conversation
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.
1
1
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
Just added glued values too, inspired by work done by and in smalltt and sixty: github.com/pikelet-lang/p
1
2
Yeah I saw 😅 I'm kinda watching way too many repositories...
1
Replying to
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
good question - haven't really stress-tested it
1
Show replies