5 ms·
Did you try a (tiny) bloom filter? Doing a quick convolution of the header key and a test against a bloom filter (SIMD? Using builtin CRC ops? 256-bit bloom fil
by Scaevolus 2y ago
Did you try a (tiny) bloom filter? Doing a quick convolution of the header key and a test against a bloom filter (SIMD? Using builtin CRC ops? 256-bit bloom filter size?) might avoid walking the trie altogether in most cases at the cost of a few cycles.
- deleted 2y ago[deleted]
- jgrahamc 2y agoI do not know if the team did that but Bloom filters aren't a panacea: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
- Scaevolus 2y agoYeah, for this problem you'd want a bloom filter that can entirely fit in vector registers during the computation, which should work well for a few hundred items.
- vlovich123 2y agoA bloom filter will have the same weaknesses of needing to do a hash. For static filters like this though where you have the set of strings to check against known up front, something like a binary fuse filter could work really well as it's significantly faster than bloom filters when you don't need online construction (you still need to do a hash of course but the evaluation against std::HashMap is flawed since it uses SipHash instead of modern constructions like xxh3 or gxhash).
- jkaptur 2y agoI think that would require calculating the hash, which was ruled out as too slow.
- pragma_x 2y agoConsidering that each node's filter in their trie implementation is bloom-like already, the solution is awful close. I agree that testing wider swaths of the string at once might be a dramatic accelerator. A more naive approach might also be warranted. Some frequency analysis of hit/miss for trie nodes might allow them to find specific character positions with a higher miss rate than the first one. Testing such special positions first would speed things up. That assumes, of course, that the header data is fairly regular in nature.