julia icon indicating copy to clipboard operation
julia copied to clipboard

Add a hashtable to lookup method roots

Open BioTurboNick opened this issue 8 months ago • 18 comments

This PR implements a hash table for looking up method roots. Compression of methods with many roots should be sped up, removing a barrier to adding additional roots (such as to address #41099, #50082).

Currently, each time a root is added, all previous roots have to be checked, leading to O(n^2) runtime. ~The hash table adds minimal memory overhead for each method (as a hidden field) to convert this step to O(n). The table is implemented with the existing htable_t type, using jl_object_id as the hash function and jl_egal as the equality function.~ Implemented with an IdDict as a field of the temporary jl_ircode_state struct generated during compression.

Some notes:

  • Sysimage (sys.so) size before: 129.7 MB; after: 130.9 MB
  • Compilation of Base + Stdlibs ~10% faster (n = 2, YMMV)
  • Should look into smallintset/IdSet, after planned updates

BioTurboNick avatar Nov 08 '23 05:11 BioTurboNick