search

dotnet / runtime

.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.
https://docs.microsoft.com/dotnet/core/
MIT License
15.29k stars 4.74k forks source link

[mono] Implement cuckoo filter for attribute retrieval #83974

Open kotlarmilos opened 1 year ago

kotlarmilos commented 1 year ago

Description

This PR tracks progress on implementation of cuckoo filter for attribute retrieval with possibly higher execution speed performance path if attribute doesn't exist, as outlined in https://github.com/dotnet/coreclr/pull/24498.

The runtime has a list of "well known" attributes and their names. During the AOT compilation, if a class or method is annotated with the attribute, a cuckoo filter entry could be created that combines the hash code of the known attribute name and the metadata token of the item as a hash key.

At the runtime, if the AOT image is available, it could first lookup if a particular item has the attribute by computing the hash again and retrieving probability from the filter. If there is a non-zero probability for the attribute, the runtime could perform a slow check (false positives are possible). Otherwise (common case), it is known that the member doesn't have the attribute.

lambdageek commented 1 year ago

Couple of thoughts - we dont' have to do the exact same design as CoreCLR:

  1. I wonder if the cuckoo filter really has to be in the AOT image. For something like CoreLib, we could source-generate an internal managed class that has the entries (and we'd need to tell the IL Linker to keep it). That might be useful when we're on interp or JIT without AOT (ie, common WASM and Android scenarios).
  2. On the other hand, sticking the filter into the AOT image means we'll generate it after trimming, which might be more space-efficient.
  3. I wonder if we need some kind of flag to generate an AOT image that doesn't have any AOTed methods, it just has the cuckoo filter and the cached class info, for example. If we can do that fast, and the resulting output is sufficiently small, maybe we could use it even for Android (and thus avoid the need for # 1)