Improving the performance of Rule Engine

[sridhar]

I was trying to research some of the python based rule engines for the cloud. I then compare it with a similar logic using expanded out if else. Here's the sample code. Am I doing something wrong or missing some optimization here?:

import rule_engine
import time


namelist = ["Luke", "tester"]
vallist = [10,20,30,40,50,60,70,80,90]

rules = [ rule_engine.Rule(f'first_name in {namelist} and val in {vallist}'),  rule_engine.Rule(f'val in {vallist}')]

testdict = [{ 'first_name': 'Luke', 'last_name': 'Skywalker', 'val': 10 },{ 'first_name': 'somename', 'last_name': 'Skywalker', 'val': 20 }]

tmp = [0, 0]
st = time.perf_counter()
for _ in range(0,100000):
    for cond in testdict:
    ¦   for rule in rules:
    ¦   ¦   if(rule.matches(cond)) :
    ¦   ¦   ¦   tmp[1] = tmp[1] + 1
    ¦   ¦   else :
    ¦   ¦   ¦   tmp[0] = tmp[0] + 1
end = time.perf_counter()
re_time = end - st
print(f"Rule engine took {end - st} seconds")


tmp = [0, 0]
st = time.perf_counter()
for _ in range(0,100000):
    for cond in testdict:
    ¦   if ('first_name' in cond and cond['first_name'] in namelist) and ('val' in cond and cond['val'] in vallist):
    ¦   ¦   tmp[1] = tmp[1] + 1
    ¦   elif ('val' in cond and cond['val'] in vallist):
    ¦   ¦   tmp[1] = tmp[1] + 1
    ¦   else:
    ¦   ¦   tmp[0] = tmp[0] + 1
end = time.perf_counter()
if_time = end- st
print(f"If-else took {end - st} seconds")

print(f"If-else faster by {re_time/if_time} times")

The output here is:
Rule engine took 9.247348009143025 seconds
If-else took 0.05902006570249796 seconds
If-else faster by 156.68142519115563 times

[zeroSteiner]

I mean rule engine is going to be slower, there's just no way around that. The only thing I see though is that the python expression has an advantage:

If we look at the following. The left side of the 2 and corresponds to the first rule, while the right side corresponds to the second.

if ('first_name' in cond and cond['first_name'] in namelist) and ('val' in cond and cond['val'] in vallist):

Since you have them in Python, it's evaluated as a single expression. If the left side evaluates to false, then the right side is ignored. Rule engine does the same thing, but you have the rules broken out so both rules are always evaluated. A more fair test would be to combine both rule expressions, and you'll notice a decent performance improvement.

New Output

import rule_engine
import time


namelist = ["Luke", "tester"]
vallist = [10,20,30,40,50,60,70,80,90]

rules = [ rule_engine.Rule(f'first_name in {namelist} and val in {vallist} and val in {vallist}')]

testdict = [{ 'first_name': 'Luke', 'last_name': 'Skywalker', 'val': 10 },{ 'first_name': 'somename', 'last_name': 'Skywalker', 'val': 20 }]

rule = rules[0]
tmp = [0, 0]
st = time.perf_counter()
for _ in range(0,100000):
    for cond in testdict:
        if(rule.matches(cond)) :
            tmp[1] = tmp[1] + 1
        else :
            tmp[0] = tmp[0] + 1
end = time.perf_counter()
re_time = end - st
print(f"Rule engine took {end - st} seconds")


tmp = [0, 0]
st = time.perf_counter()
for _ in range(0,100000):
    for cond in testdict:
        if ('first_name' in cond and cond['first_name'] in namelist) and ('val' in cond and cond['val'] in vallist):
            tmp[1] = tmp[1] + 1
        elif ('val' in cond and cond['val'] in vallist):
            tmp[1] = tmp[1] + 1
        else:
            tmp[0] = tmp[0] + 1
end = time.perf_counter()
if_time = end- st
print(f"If-else took {end - st} seconds")

print(f"If-else faster by {re_time/if_time} times")

New output:

python test.py 
Rule engine took 6.368217186998663 seconds
If-else took 0.05549073699876317 seconds
If-else faster by 114.76180586934004 times

It's not a huge gain but it is something. With all of the calls necessary to evaluate the AST, I'm just not sure you're ever going to see something on-par with Python. Literal expressions in the rule will be reduced automatically after it's parsed but that's about the only optimization that's in place.

[sridhar]

Hi @zeroSteiner ,

The original code has two rules. The second rule has one condition, similar to the two if conditions I have.
The problem I am trying to solve is that, I have multiple rules and a lot of datasets to match against for a cloud application. The requirement is to find the first rule matching a particular dataset. Right now it's NxM solution (where there are N rules and M datapoints). This itself is sort of unusable for higher loads. I was wondering if the naive solution is fast enough for me to not worry about improving the rule matching logic.
I'm wondering why AST evaluation takes that much time. I'll take a look at the source code.

I've used a C implementation of RFC (https://ieeexplore.ieee.org/document/4908500) to achieve good performance for this use case.
Thanks.

[sridhar]

Hi @zeroSteiner,

I wrote an implementation that was pared down to be specific to few rule checks (set matches and equality matches), and only allowed AND in the rule combination. This removed the generality of the library but gave me much needed performance gain. It took .22s for the above test.

Thanks.