5 ms·
Shenanigans With Hash Tables
- caf 7y agoAccording 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.
- nwellnhof 7y agoSeems like the same idea as in this paper: Efficient Implementation of Java Interfaces: Invokeinterface Considered Harmless (2001) https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.7133 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21....
- jasoneckert 7y agoI'm quite experienced in shenanigans. Doing them with hash tables, however, definitely peaks my interest.
- radiowave 7y agoPlease allow me to bring your whimsical humour back down to earth with some tedious pedantry: "piques", not "peaks".
- nutjob2 7y agoI 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.
- layoutIfNeeded 7y agoI recommend reading up on minimal perfect hashing: http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html
- chaboud 7y agoThis 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...
- trishume 7y agoIn 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.
- pcwalton 7y agoObjective-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. Mike Ash has a nice series that goes through the disassembly of objc_msgSend: https://www.mikeash.com/pyblog/friday-qa-2017-06-30-dissecting-objc_msgsend-on-arm64.html https://www.mikeash.com/pyblog/friday-qa-2017-06-30-dissecti...
- perishabledave 7y agoMike Ash’s posts are gold. I wish there were more in depth technical posts like those on HN or Lobsters.
- saagarjha 7y ago> Objective-C uses a hash table cache for all method calls. Nit: method calls to objects that are not nil, since the latter causes objc_msgSend to bail out before the hash table is consulted.
- jonathanstrange 7y agoBut 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.
- deleted 7y ago[deleted]
- rurban 7y agoI 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.
- raja_mukherji 7y agoI'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.