Pathological performance with O(n) objects
- Dominant language
- Go
- Stars
- 1.8k
- Forks
- 263
- PR merge metrics
- No merged PRs in 30d
Description
We ran into a pathological case of field lookup recently. A common pattern we follow is something along the lines of:
```jsonnet
std.foldl(function (o, acc) { return acc + { [o.key]: o.val } }, arr, {})
```
We run into an issue here because internally this effectively creates a linked list:
https://github.com/google/go-jsonnet/blob/923f51b8e3ba3fd49dd8b9e859e1c0304f7cdbd4/value.go#L618-L634
Now, O(1) object lookups become O(n). If we do this in a loop, O(n) can become O(n^2) or worse. We can re-flatten the resulting `extendedObject` into a `simpleObject` by using object comprehensions:
```
flattened = { [k]: obj[k] for k in std.objectFields(obj) }
```
I'm not sure if there are additional bugs contributing to this behaviour (e.g., why do the caches not absorb this). But ultimately it does raise the question if optimizing for O(n) object merging is the right move. It heavily penalizes reads.
Would it make sense to instead spend more cycles during the object merging? The hacky patch I've attached eliminates the performance issues we faced.
```diff
diff --git a/builtins.go b/builtins.go
index 251ca40..7b13205 100644
--- a/builtins.go
+++ b/builtins.go
@@ -60,6 +60,27 @@ func builtinPlus(i *interpreter, x, y value) (value, error) {
case *valueObject:
switch right := y.(type) {
case *valueObject:
+ if left, ok := left.uncached.(*simpleObject); ok {
+ if right, ok2 := right.uncached.(*simpleObject); ok2 {
+ frame := make(bindingFrame)
+ for k, v := range left.upValues {
+ frame[k] = v
+ }
+ for k, v := range right.upValues {
+ frame[k] = v
+ }
+
+ fields := make(simpleObjectFieldMap)
+ for k, v := range left.fields {
+ fields[k] = v
+ }
+ for k, v := range right.fields {
+ fields[k] = v
+ }
+
+ return makeValueSimpleObject(frame, fields, append(left.asserts, right.asserts...), append(left.locals, right.locals...)), nil
+ }
+ }
return makeValueExtendedObject(left, right), nil
default:
return nil, i.typeErrorSpecific(y, &valueObject{})
```
A hybrid approach could also be possible. Perhaps we can establish some sort of depth threshold at which we compact `extendedObject`s down into a `simpleObject`.
Thanks to @suprememoocow for tracking down the original issue.
Contributor guide
Assessment
This issue has not been assessed yet.