Repository navigation
object.union_n() is superlinear on the number of objects to merge #4985
Description
This is conceptually the same problem from #4979.
Suppose we are unioning together topdown.builtinObjectUnionN() will make topdown.mergeWithOverwrite(), implying ast.object.MergeWith(). Though MergeWith appears linear at first glance, the calls are not independent from one another. The first call is merging two objects of MergeWith in the inner loop ends up being:
This occurs in the optimal case where
Empirical Benchmarks
With the object.union_n() builtin:
$ cat slowunion/slowunion.rego
package slowunion
SIZE := 250
NSETS := 250
nums := numbers.range(0, NSETS)
sizes := numbers.range(0, SIZE)
sets[n] = x {
nums[n]
x := {sprintf("%d,%d", [n, i]): true | sizes[i]}
}
combined := object.union_n([s | s := sets[_]])
#combined := {k: true | s := sets[_]; s[k]}
$ time opa eval --profile --format pretty --bundle ./slowunion/ --import "data.slowunion" 'count(data.slowunion.combined)'
63001
+------------------------------+------------+
| METRIC | VALUE |
+------------------------------+------------+
| timer_rego_load_bundles_ns | 533250 |
| timer_rego_module_compile_ns | 708000 |
| timer_rego_module_parse_ns | 210625 |
| timer_rego_query_compile_ns | 46625 |
| timer_rego_query_eval_ns | 3028944250 |
| timer_rego_query_parse_ns | 33875 |
+------------------------------+------------+
+-------------+----------+----------+-----------------------------+
| TIME | NUM EVAL | NUM REDO | LOCATION |
+-------------+----------+----------+-----------------------------+
| 2.88952125s | 4 | 254 | slowunion/slowunion.rego:14 |
| 110.7097ms | 63503 | 126253 | slowunion/slowunion.rego:11 |
| 18.169001ms | 2 | 2 | data.slowunion.combined |
| 154.583µs | 3 | 3 | slowunion/slowunion.rego:6 |
| 114.531µs | 1 | 251 | slowunion/slowunion.rego:10 |
| 91.833µs | 3 | 3 | slowunion/slowunion.rego:7 |
| 4.458µs | 1 | 1 | slowunion/slowunion.rego:4 |
| 2.042µs | 1 | 1 | slowunion/slowunion.rego:3 |
+-------------+----------+----------+-----------------------------+
real 0m3.055s
user 0m4.560s
sys 0m0.153s
With pure Rego:
$ cat slowunion/slowunion.rego
package slowunion
SIZE := 250
NSETS := 250
nums := numbers.range(0, NSETS)
sizes := numbers.range(0, SIZE)
sets[n] = x {
nums[n]
x := {sprintf("%d,%d", [n, i]): true | sizes[i]}
}
#combined := object.union_n([s | s := sets[_]])
combined := {k: true | s := sets[_]; s[k]}
$ time opa eval --profile --format pretty --bundle ./slowunion/ --import "data.slowunion" 'count(data.slowunion.combined)'
63001
+------------------------------+-----------+
| METRIC | VALUE |
+------------------------------+-----------+
| timer_rego_load_bundles_ns | 554167 |
| timer_rego_module_compile_ns | 710166 |
| timer_rego_module_parse_ns | 154792 |
| timer_rego_query_compile_ns | 48458 |
| timer_rego_query_eval_ns | 194535167 |
| timer_rego_query_parse_ns | 32042 |
+------------------------------+-----------+
+--------------+----------+----------+-----------------------------+
| TIME | NUM EVAL | NUM REDO | LOCATION |
+--------------+----------+----------+-----------------------------+
| 111.776641ms | 63503 | 126253 | slowunion/slowunion.rego:11 |
| 48.923215ms | 254 | 63254 | slowunion/slowunion.rego:15 |
| 20.819749ms | 2 | 2 | data.slowunion.combined |
| 160.292µs | 3 | 3 | slowunion/slowunion.rego:6 |
| 106.874µs | 1 | 251 | slowunion/slowunion.rego:10 |
| 93.332µs | 3 | 3 | slowunion/slowunion.rego:7 |
| 4.584µs | 1 | 1 | slowunion/slowunion.rego:4 |
| 2.084µs | 1 | 1 | slowunion/slowunion.rego:3 |
+--------------+----------+----------+-----------------------------+
real 0m0.218s
user 0m0.327s
sys 0m0.024s
System info:
$ uname -a
Darwin styra-macbook.local 21.5.0 Darwin Kernel Version 21.5.0: Tue Apr 26 21:08:37 PDT 2022; root:xnu-8020.121.3~4/RELEASE_ARM64_T6000 arm64
$ system_profiler SPSoftwareDataType SPHardwareDataType
Software:
System Software Overview:
System Version: macOS 12.4 (21F79)
Kernel Version: Darwin 21.5.0
Boot Volume: Macintosh HD
Boot Mode: Normal
Computer Name: styra-macbook
User Name: Charles Daniels (cad)
Secure Virtual Memory: Enabled
System Integrity Protection: Enabled
Time since boot: 5 days 21:41
Hardware:
Hardware Overview:
Model Name: MacBook Pro
Model Identifier: MacBookPro18,3
Chip: Apple M1 Pro
Total Number of Cores: 8 (6 performance and 2 efficiency)
Memory: 32 GB
System Firmware Version: 7459.121.3
OS Loader Version: 7459.121.3
Serial Number (system): REDACTED
Hardware UUID: REDACTED
Provisioning UDID: REDACTED
Activation Lock Status: Disabled
$ opa version
Version: 0.43.0
Build Commit: d75bbdd
Build Timestamp: 2022-07-29T21:15:42Z
Build Hostname: Mac-1659129125033.local
Go Version: go1.18.4
Platform: darwin/arm64
WebAssembly: unavailable
Note that unlike in #4979, this is not an apples-to-apples comparison, because object.union_n() is not expressible in the general case (to my knowledge) using pure Rego. The fact that object.union_n() is slower than the given Rego code is not an "obvious" problem in of itself, it's the fact that the it grows far faster than linearly on the number of objects to merge.
Although the asymptotic analysis is sufficient on it's own to demonstrate this, I have implemented the following ad-hoc benchmark to demonstrate. Note that this needs a version of Bash new enough to support EPOCHREALTIME. Notice that though nsets varies with each run of the benchmark, size is fixed at 250 for all of them. This in the previous asymptotic analysis,
$ cat slowunion/slowunion.rego
package slowunion
nums := numbers.range(0, input.nsets)
sizes := numbers.range(0, input.size)
sets[n] = x {
nums[n]
x := {sprintf("%d,%d", [n, i]): true | sizes[i]}
}
combined := object.union_n([s | s := sets[_]])
#combined := {k: true | s := sets[_]; s[k]}
$ rm out.csv
$ for n in 10 100 200 300 400 500 ; do START=$EPOCHREALTIME ; time opa eval --format pretty --bundle ./slowunion/ --import "data.slowunion" 'count(data.slowunion.combined) with input as {"nsets": '$n', "size": 250}' ; echo "$n,$START,$EPOCHREALTIME" >> out.csv ; done
$ cat out.csv
10,1659994724.161146,1659994724.199003
100,1659994724.199294,1659994724.692205
200,1659994724.692459,1659994726.621330
300,1659994726.621561,1659994731.005600
400,1659994731.005872,1659994738.928419
500,1659994738.928674,1659994751.609016
$ awk 'BEGIN{FS=","} {printf("n=%d, elapsed seconds=%f\n", $1, (1.0 * $3 - 1.0 * $2))}' < out.csv
n=10, elapsed seconds=0.037857
n=100, elapsed seconds=0.492911
n=200, elapsed seconds=1.928871
n=300, elapsed seconds=4.384039
n=400, elapsed seconds=7.922547
n=500, elapsed seconds=12.680342
As we can see, between n=100 and n=500 (factor of 5x increase in input size), the running time has gone from 0.49s to 12.68s, a 25x increase.
Activity
topdown/object: Rework object.union_n to use in-place merge algorithm. (