julia
julia copied to clipboard
Add a hashtable to lookup method roots
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