Evaluation performance

[hsluoyz]

Hi. Thanks again for making this great library!

One of my clients ask about the performance at: https://github.com/casbin/casbin/issues/45#issuecomment-343703409. My software is an access control library that uses govaluate to make authorization decisions. And I thought the performance bottleneck may be in the expression evaluation. Is there any way to upgrade the performance? Like adding a cache? Thanks!

[Knetic]

Thanks! And thanks for using the library!

I looked through the issue you linked, and this comment is correct; caching is probably a good move. Parsing an expression is the most expensive operation this library does (even though it's still pretty fast). This library doesn't attempt to cache parsed expressions for later, because different users need it for different purposes, and a cache isn't always desirable.

While I'm not familiar with the usage patterns of your library, I think you might benefit by using an LRU cache. - something like this. This would automatically keep the most-used expressions in memory, while lesser-used ones would eventually be removed from memory. It would increase your memory footprint a bit, but not by much - and the savings in compute would probably be worth it. I'm recommending this because I assume there are policies that are commonly evaluated for many requests.

However, in the RBAC (large) case mentioned in your benchmarks, you might benefit from disabling govaluate's type checking. This doesn't do anything to help the parsing time, but evaluation will be a bit faster - however, it means that invalid combinations of parameters will cause panics, rather than errors. This may be acceptable to you, but i'd recommend adding the line expression.ChecksTypes = false on this line and see how much it helps your benchmarks.

[hsluoyz]

I have implemented a version with the LRU here: https://github.com/casbin/casbin/tree/with-lru to cache the expressions. But unfortunately, it does not improve the performance.

And I also tried your disabling govaluate's type checking way, it doesn't improve performance either:(

Then I found the bottleneck may be in Casbin's rule matching, aka the result, err := expression.Evaluate(parameters) call. This call will run once for every policy rule. And when the number of rules is increased from 1000 to 10000, the enforcement overhead then multiplies by 10x. So is there a way to make expression.Evaluate(parameters) faster? In fact, I also need to find a way to not match so many rules for an Enforcer.Enforce() call. But it's kind of hard based on how Casbin works.

[Knetic]

Added some findings in the casbin issue.