TechPulseTechPulse
Back to News
Advertisement
Advertisement

⚡ Community Insights

Discussion Sentiment

50% Positive

Analyzed from 291 words in the discussion.

Trending Topics

#rules#bit#rule#order#hard#bits#useragent#regexes#beats#partial

Discussion (3 Comments)Read Original on HackerNews

gopalv•about 3 hours ago
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

somat•about 2 hours ago
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.
chaoxu•about 4 hours ago
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.