Prebuilding a {Selector, IMP} Static Hash Table and baking it into executable

[hmelder]

Apple figured out that precomputing a {Selector, IMP} static hash table significantly improves dispatch time and the memory footprint. This cache is stored inside the DYLD shared cache and includes the pairs for all system libraries.
The procedure is outline in https://opensource.apple.com/source/dyld/dyld-851.27/IMPCaches.md.

There is no DYLD shared cache on Linux or Windows, but why not store it in an ELF section? This can either be one section per object file (i.e. libgnustep-base.so and myApplication has one) or we bake it into the main application which is more of a special case.

What do you think about precomputing the dtable @davidchisnall?

CC: @triplef

[davidchisnall]

We don’t use a hash table, we use a radix tree. It would be interesting to try a hash table approach, but that would be a first step before trying to add a prebuilt hash table.

[hmelder]

So I guess profiling the memory footprint of the sparse array in a large application after warm up, IMP look up times, and number of cache misses would be the first step, before changing the underlying data structure of the dtable, right?

[davidchisnall]

Yes, if you can get some good data. Anecdotally, the radix tree does as well as Apple’s fast path when the caches are warm and much worse when the caches are cold.