Take for example tcc, which is a very fast c compiler.
They just use a basic chaining hash table: `Node *nodes[16384];`.
Since most translation units have far less than 16384 tokens, most lookups result in a direct hit.
Take for example tcc, which is a very fast c compiler.
They just use a basic chaining hash table: `Node *nodes[16384];`.
Since most translation units have far less than 16384 tokens, most lookups result in a direct hit.
What TCC is actually storing in TokenSym (which you've named "Node" in this context) is four pointers to other information about symbols, a unique ID, and a string.
If we used a compact inline string (like CompactString) we can squeeze all this into 60 bytes unless the string is more than 24 bytes in length such as TCC's own warn_implicit_function_declaration or is_compatible_unqualified_types which would need a heap allocation like they have today, for the string itself.
If we do that we can build a linear probed open addressed hash table and avoid paying for the extra indirection any time the symbol names are 24 bytes or shorter in length, I'd expect this is markedly better.
But it's a lot of work in C, so it isn't a surprise TCC doesn't do it.
General libraries have to handle all kinds cases you might not care about. The most egregious example is assuming every piece of code might be threaded so everything needs to be protected by locks. (I would guess > 75% of dictionaries never remove a key, and simply throw away the whole thing at the end.)
There are probably multiple reasons for this, including historical precedent and the need for misuse resistance in a language’s standard library, but I’d guess that in part this is simply because locks used to be much cheaper, especially before systems with multiple hardware threads became ubiquitous.
I think historically it wasn't clear what role threads would take. If you look at Java they expected application programmers to be using threads haphazardly. Now we know that isn't a good idea.