4 ms·

Sometimes a very basic fixed size chaining hash tables is actually the best you can do. Take for example tcc, which is a very fast c compiler. They just use a

Sometimes a very basic fixed size chaining hash tables is actually the best you can do. 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.

mananaysiempre 4y ago
TCC has the advantage of being a batch process, so it can insert things using open addressing without ever considering how it intends to delete them, then just drop the whole thing on the floor at the end. Of course, if you are also a batch process, you absolutely should do that too.
- citizen_friend 4y ago
  This is an advantage of C style programming. If you understand the problem and tailor a solution you can utilize simplifying assumptions which make the code easier and faster. 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.)
  - KerrAvon 4y ago
    Locks require enough of a performance hit on enough architectures that it’s better to document the dictionary as _not_ being threadsafe and require external synchronization. You’ll frequently need external locking anyway to enforce atomicity with changes to other related data structures
    - mananaysiempre 4y ago
      And yet most stdio implementations on systems capable of multithreading add locking around every operation (with the notable exception of Microsoft’s single-threaded C runtime when it still existed, as well as a handful of distinct *_unlocked functions on Unix that were added specifically to mitigate this problem). 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.
      - citizen_friend 4y ago
        I would include malloc in that list of regrets (or at least not having a lock free alternative). 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.
tialaramex 4y ago
Is that the best TCC could have done here? It's easy to write this in C, which is one obvious reason for TCC to do it, but it's not at all clear this is the best way. 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.
_0w8t 4y ago
This may result in poor CPU cache access pattern. For tasks that are often human-bound like source files or UI data structures using a sorted array can be a good option.

mananaysiempre 4y ago

TCC has the advantage of being a batch process, so it can insert things using open addressing without ever considering how it intends to delete them, then just drop the whole thing on the floor at the end. Of course, if you are also a batch process, you absolutely should do that too.

citizen_friend 4y ago
This is an advantage of C style programming. If you understand the problem and tailor a solution you can utilize simplifying assumptions which make the code easier and faster. 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.)
- KerrAvon 4y ago
  Locks require enough of a performance hit on enough architectures that it’s better to document the dictionary as _not_ being threadsafe and require external synchronization. You’ll frequently need external locking anyway to enforce atomicity with changes to other related data structures
  - mananaysiempre 4y ago
    And yet most stdio implementations on systems capable of multithreading add locking around every operation (with the notable exception of Microsoft’s single-threaded C runtime when it still existed, as well as a handful of distinct *_unlocked functions on Unix that were added specifically to mitigate this problem). 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.
    - citizen_friend 4y ago
      I would include malloc in that list of regrets (or at least not having a lock free alternative). 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.

tialaramex 4y ago

Is that the best TCC could have done here? It's easy to write this in C, which is one obvious reason for TCC to do it, but it's not at all clear this is the best way. 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.

_0w8t 4y ago

This may result in poor CPU cache access pattern. For tasks that are often human-bound like source files or UI data structures using a sorted array can be a good option.