Slow arithmetic operations in hot path

[anderseknert]

Or dealing with numbers in general. While it's admittedly not a case one likely will be bothered by in what could be considered normal policy evaluation, Rego is everywhere these days, and its use cases sometimes unorthodox. One such case would be Regal, where we traverse large abstract syntax trees (using the walk built-in function) in order to find bugs and inefficiencies in Rego code. Doing so means we'll sometimes traverse hundreds of thousands of nodes, and in most cases we only look closer at a node if the last element of the path is of interest. To do so, we do a simple lookup of the last element:

path[count(path) - 1]

When benchmarking Regal on some huge policy libraries, this seemingly simple operation accounted for roughly 20% of the total evaluation time.

I believe this is caused by the frequent creation of big floats for the count, the operands (ie. new(big.Float).SetString(string(n))) and of course the subtraction itself (new(big.Float).Sub(a, b)).

Creating 600'000 big floats for the constant number 1 seems excessive, and I believe we could be more efficient by e.g. caching the most common numbers (like any up to 256 or whatnot), or even recognize the "last element construct" and optimize for that. But there might be better optimizations to improve the efficiency of working with numbers across the board. The numbers.range function comes to mind here too, as it performs poorly when creating a large amount of numbers. Again, this is not a common use case, but if we can improve the uncommon ones, perhaps they'll be more common one day :)

For now we've solved this with a custom regal.last built-in, which has the benefit of knowing it's job is a last element lookup, and the result is a 20% reduction of eval time:

path[count(path) - 1]

1669 files linted. 4779 violations found in 1664 files.
regal lint assets  55.83s user 3.51s system 602% cpu 9.850 total

regal.last

1669 files linted. 4779 violations found in 1664 files.
regal lint assets  36.86s user 2.27s system 517% cpu 7.559 total

While this works well, we'd ideally deal with this better in OPA proper.

[srenatus]

Thanks for the write-up!

Something like

var prebuiltInts  [256]big.Float

func init() {
	for i := range prebuiltInts {
		prebuiltInts[i] = ...
	}
}

in the right place, paired with the right code that'll return one of these if the number we're parsing is lower than 256, should do the trick for many cases, I think.

[anderseknert]

Looks straightforward to me! I suppose for simple arithmetic of low-range numbers, like 22 - 1, we wouldn't really need to work with big floats at all? But perhaps it'd add too much clutter trying to account for when it's appropriate and when it isn't.

[srenatus]

Might be reasonable to measure along the way. If one trick has a significant-enough impact, we could leave it at that. But in general, yeah, small numbers should just stay small 😄

[srenatus]

https://gist.github.com/srenatus/5361bfa8c4044aad97fa62af27d5bbcb
Maybe something along those lines?