Quadratic runtime complexity for adding constraint templates

[open-policy-agent]

Quadratic runtime complexity for adding constraint templates

[tsandall]

I've filed an issue against OPA to improve support for incremental load scenarios. In the meantime, it would be good if the constraint framework could support a bulk load API (e.g., AddTemplates in addition to AddTemplate on the client).

EDIT: One other thing to mention. When I updated to use OPA master with the new parser implementation (which is in v0.19.0-rc1), the load time for the first template went from ~45ms to ~10ms.

[maxsmythe]

@tsandall

The increasing incremental cost is likely due to a larger bulk of Rego needing to be recompiled. Given that constraint templates are meant to be non-interacting, is there any way to eliminate the incremental cost by preserving the work of previous compiles? Maybe caching the artifacts somewhere to improve the cold start as well?

[maxsmythe]

An option for non-referential templates would be to have a separate interpreter per-template.

[tsandall]

@maxsmythe improving the compiler to support incremental updates is possible but would require some work. In short, some of the stages implement checks and rewriting or build data structures that are local to the module/rules in the module whereas others do these things globally (recursion check is one example). The first step would be to categorize the stages in the compiler so we know which ones require global information or perform global updates and which do not. For the global changes that affect data structures, we probably have to update the data structures to support add/remove operations (if they don't already.) In the short term, we should probably benchmark the compile operation and see where the time is spent. If you run opa eval -d x.rego 'data' --instrument you'll get back timers for each of the stages.

[maxsmythe]

Any way to get that debug information from the OPA API?

[tsandall]

Yes, the rego.Instrument option enables it: https://github.com/open-policy-agent/opa/blob/master/rego/rego.go#L785

[willbeason]

Resolved with #202