Use non-string symbols internally?

[dcodeIO]

For a while now I've been thinking about switching the string names we have internally with something that is faster to look up in a hash map. Pretty sure that other compilers do this for various reasons, but after looking through it I have my doubts that it will speed-up compilation significantly, justifying such an extensive change. For instance, currently we are looking up names in code by doing a Map#has (each time hashing the string), but if we'd use non-string symbols, we'd have to do that hash lookup when parsing to make a non-string symbol of a string anyway, leading to about the same overhead. Also, my first reflex was to utilize JS symbols for this, which has the drawback that the compiler would have to build a map of all the internal symbols on load, potentially degrading start-up time, while strings are just static data.

Pinning this here for future reference, or if someone has an idea or experience with actual benefits.

[willemneal]

I think that it's fine to create a symbols abstraction that has a parsing input and lookup table. This way we can start with the current hashing. But since we have the same idea of building the map first, we could swap out later for the more efficient solution. In the future, I see the compiler as more of a server that will cache all of the things it needs to. So in the case of lookup tables, their initial overhead becomes worth it. But personally, I too doubt that the work at the current stage is worth it. Features are more important than performance. (not to say that the performance aspects of the features shouldn't be part of considered.

[MaxGraey]

Instead simple hashtable may be better use LRU cache which allow O(1) lookup and O(1) insert/delete

[MaxGraey]

Also will be interesting try to adopt qp-tries (faster than crit-bit tries) or double-array-trie for symbolic table. @jedisct1 I know you have Rust's implementation of qp-trie what do you think?

[jedisct1]

qp-tries are GREAT!

But them being fast requires the compiled code to be friendly to cache prefetch. It works pretty well in C and Rust, but I don't know how an AS version would perform. There's one way to know :)

[dcodeIO]

Closing this issue as part of 2020 vacuum because it is not absolutely crucial at this point in time. My expectation is that there will be new opportunities once compiling the compiler to WebAssembly becomes the default, like internalizing strings.