Objective-C uses a hash table cache for all method calls. It's a bit different in that Objective-C deals with collisions by just not handling them: since it's only a cache, collisions will result in going through the slow name lookup path.
But aren't hash tables orders of magnitude slower than dynamic dispatch with jump tables? I'm just interested in PL implementation as a hobby, so correct me if I'm wrong, but this seems horribly inefficient to me.
This is what came to mind when I read this. Far too many professional programmers are unaware of perfect hash functions. A disturbing number are unaware of pathological collision cases.
For a complete set of methods known at compile time, a minimal perfect hash is, well, kinda perfect...
In this case I did actually consider it but forgot to mention it in my post. The slightly more complex constraints of having multiple different tables using the same hash function make searching for the hash function more annoying so I didn’t bother.
I think Self did the same. At those times this was one of the most researched topics, how to efficiently implement a PIC, polymorphic inline cache. Either with a simple ordered list (usually constructed at run-time, a harder problem), such a hash (good for compile-time) or vtables.
According to my compilers class professor there’s a broad literature of optimizing the “giant table with all signatures” approach with heuristics for saving space by rearranging and merging the tables of different classes into the same space or re-using offsets across classes to make tables smaller. But the general problem is NP-complete so can only be solved heuristically.
A SAT solver should actually be able to handle this fairly easily, because in practice, you don't get long complex chains of overlap between the interfaces implemented by common classes. If someone feeds your compiler an adversarial input you can just fall back to the naive implementation.
I've been using a similar but flipped approach in my own interpreted language, creating a hash table for each method and then look for the object type as the key. This allows me to check the parent types if an exact object type is not found. I then nest the tables for multiple dispatch.
I think this is more common that the author assumes, I use hash tables in a similar way in my own project. It quickly suggests itself when you are mapping names within types to different offsets per type.
Mike Ash has a nice series that goes through the disassembly of objc_msgSend: https://www.mikeash.com/pyblog/friday-qa-2017-06-30-dissecti...