The 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.
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.
from log join ua_data on log.useragent ~ ua_data.match_exp
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.
You say hard rules can cause A beats B, B beats C, and C beats A. Is it because hard rules itself can have cycles, or because hard rule and scores together causing cycles? What does tie-breaker even mean here, how does it change the ordering?
Let's ignore tie-breaker. Is it the following abstract problem?
Given a partial order A (the hard rules) and a total order B (the scores). Find a total order C that is an linear extension of A and "agrees" with B the most.
I feel if phrase this way, then there is probably some faster greedy approximation of w/e "agrees" you are thinking about, because w/e you are doing here is also just an approximation of w/e true best you are thinking.
The 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.You say hard rules can cause A beats B, B beats C, and C beats A. Is it because hard rules itself can have cycles, or because hard rule and scores together causing cycles? What does tie-breaker even mean here, how does it change the ordering?
Let's ignore tie-breaker. Is it the following abstract problem?
Given a partial order A (the hard rules) and a total order B (the scores). Find a total order C that is an linear extension of A and "agrees" with B the most.
I feel if phrase this way, then there is probably some faster greedy approximation of w/e "agrees" you are thinking about, because w/e you are doing here is also just an approximation of w/e true best you are thinking.