3 ms·
Chromium does this in a bunch of places; the article only links to Safe Browsing using murmur, but the renderer (Blink) generally uses rapidhash and has some of
by Sesse__ 1y ago
Chromium does this in a bunch of places; the article only links to Safe Browsing using murmur, but the renderer (Blink) generally uses rapidhash and has some of these micro-filters which it uses for e.g.:
- querySelector() in certain cases
- Prefiltering hash lookups in CSS buckets
- Rapid reject of elements when looking for certain Aria attributes (for accessibility)
It's surprising that such tiny filters (32 or 64 bits) work at all, but they often do. There are also some larger Bloom filters around.
(I added some of these)
- marginalia_nu 1y agoThey just have a really unintuitive economy where they basically only need to work once or twice to make up for the cost of all the times they don't contribute any benefit.
- Sesse__ 1y agoFor extra fun, you sometimes can make ideal filters with no false positives, if you know your possible elements ahead of time and you don't insert too many of them. (E.g., for 20 elements, you can construct a 12-bit code where there are guaranteed no false positives as long as you insert at most two elements.)