alt Hacker NewsThe rule partial order problem seems to be very similar to how Rule engines are optimized for ACL rule application.
> Once per candidate, we precompute a bitmask, an integer whose bits flag which rules that candidate is eligible for. For a pair, the bitwise AND of their two masks is exactly the set of rules both are eligible for, and we check only those.
Once I see a bit-mask loop, the next item I pick up is a Karnaugh Map[1] as a way of looking at the rules.
If one side is generally immutable to automatically reorder the generators of the bits (i.e can I turn a 192 bit expression into a 64 bit followed by a 128 bit - if so which bits are important).
The C++ template hacks over this looks a bit like a fastdiv from Lemire.
The specific one where I spent 2+ months optimizing this was the UserAgent matcher with regexes - an extension replacement for the get_browser() in PHP where the goal was to split up the regexes and build a KV Map for it, so that you can run 40+ small regexes instead of looping through 400.
[1] - https://en.wikipedia.org/wiki/Karnaugh_map#Don't_cares
With regards to the user agent matching it reminds me of the time I loaded the full useragent database(the same data php get_browser() uses) into postgres and landed my first 3+ hour query.
It was intractable to indexing (gin can almost do it. using like instead of ~ but gin only works on pure prefix or suffix matches) so I moved on to better things.