Pathological performance with O(n) objects

[igorwwwwwwwwwwwwwwwwwwww]

We ran into a pathological case of field lookup recently. A common pattern we follow is something along the lines of:

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:

go-jsonnet/value.go

Lines 618 to 634 in 923f51b

	// extendedObject represents an object created through inheritance (left + right).
	// We represent it as the pair of objects. This results in a tree-like structure.
	// Example:
	// (A + B) + C
	//
	// +
	// / \
	// + C
	// / \
	// A B
	//
	// It is possible to create an arbitrary binary tree.
	// Note however, that because + is associative the only thing that matters
	// is the order of leafs.
	//
	// This represenation allows us to implement "+" in O(1),
	// but requires going through the tree and trying subsequent leafs for field access.

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 --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 extendedObjects down into a simpleObject.

Thanks to @suprememoocow for tracking down the original issue.

[CertainLach]

Object fields are late-bound, thus it is only possible to perform such optimization for object fields, which depend on neither self/super (directly, or through locals), and this requires pretty complicated analysis.

As for your code,

std.foldl(function (acc, o) acc + { [o.key]: o.val }, arr, {})

It can be replaced with

{
  [o.key]: o.val
  for o in arr
}

Which has no such performance problems, and much more readable.

[igorwwwwwwwwwwwwwwwwwwww]

I've managed to construct a minimal example of this pathology:

local ouch(values) =
  std.foldl(
    function(acc, value)
      local lookup = std.get(acc, "a", {});
      acc { ["a"]+: lookup },
    values,
    {}
  );

local values = [null for x in std.range(1, 30)];

ouch(values)

It takes 80 cpu seconds / 40 wall clock seconds:

$ time ./jsonnet ouch.jsonnet

{
   "a": { }
}

./jsonnet ouch.jsonnet  81.81s user 4.70s system 209% cpu 41.382 total

CPU profile captured via JSONNET_CPU_PROFILE:

[igorwwwwwwwwwwwwwwwwwwww]

Thinking a bit more about the extendedObject data structure. There are other purely functional data structures that could be considered which avoid excessive copying, e.g. clojure's PersistentHashMap.

[igorwwwwwwwwwwwwwwwwwwww]

I dug a bit more, preliminary conclusions:

• Most of the time is spent on walking the extendedObject tree during manifestJSON.
• The initially created tree actually looks fine. It's a right-leaning tree, effectively a linked list. We'd expect O(n) lookup and walk of this list.
• The actual problem happens during evaluation, *ast.DesugaredObject with PlusSuper results in the linked list becoming a fully populated tree of depth n. Thus our tree size is now O(n^2).
• I'm not entirely sure yet why this happens, but it feels off.

[igorwwwwwwwwwwwwwwwwwwww]

Here's a graphviz graph I generated of the resulting object structure.

The linked list at the bottom is the initial structure. The fully populated tree at the top is what we end up at the end.

What's curious:

• There are many extendedObject nodes pointing to the same destination.
• At depth 1, both right nodes point to 0x140001d0cf0
• At depth 2, all right and left nodes point to 0x140001d4340
• All of the leaf nodes are in fact the same simpleObject, 0x140001d4340

[igorwwwwwwwwwwwwwwwwwwww]

This optimization works for the minimal reproducer, but unfortunately not for the general case:

diff --git a/thunks.go b/thunks.go
index 1cccadb..d677462 100644
--- a/thunks.go
+++ b/thunks.go
@@ -159,6 +159,10 @@ func (f *plusSuperUnboundField) evaluate(i *interpreter, sb selfBinding, origBin
                return nil, err
        }

+       if left == right {
+               return left, nil
+       }
+
        value, err := builtinPlus(i, left, right)
        if err != nil {
                return nil, err