google / google/go-jsonnet

Pathological performance with O(n) objects

Open
#785 6 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.