pkg/list: Sort is too slow

[vikstrous2]

What version of CUE are you using (cue version)?

$ cue version v0.3.0-beta.4 linux/amd64

Does this issue reproduce with the latest release?

yes

What did you do?

Baseline:
root.cue

package kube

import "list"

_a: [{name: 1}, {name: 3}, {name: 4}, {name: 5}, {name: 6}, {name: 7}, {name: 8}, {name: 9}, {name: 0}]
_b: [_a, _a, _a, _a, _a, _a, _a, _a, _a, _a]
_c: [_b, _b, _b, _b, _b, _b, _b, _b, _b, _b]
_d: [_c, _c, _c, _c, _c, _c, _c, _c, _c, _c]

out: list.FlattenN(_d, 4)

Run:

$ time cue eval root.cue | wc -l
0.34user 0.01system 0:00.20elapsed 172%CPU (0avgtext+0avgdata 68940maxresident)k
0inputs+0outputs (0major+1293minor)pagefaults 0swaps
18001

Replace the last line with this list.Sort command to see the performance impact of using list.Sort in this config:

out: list.Sort(list.FlattenN(_d, 4), {x: {}, y: {}, less: x.name< y.name})

Run:

$ time cue eval root.cue | wc -l
6.03user 0.07system 0:02.87elapsed 212%CPU (0avgtext+0avgdata 72392maxresident)k
0inputs+0outputs (0major+2495minor)pagefaults 0swaps
18001

What did you expect to see?

10x slow down

What did you see instead?

negligible performance difference

[mpvl]

Is this something you found in practice or just when playing around? We are aware of slowness in various places, but we tend to prioritize actual use cases.

[vikstrous2]

The use case is outputting a predictable yaml output when generating kubernetes configs so that we can diff the produced changes on PRs. It turned out that a few simple sorts are actually not enough for this anyway, so I'm using this yq command to clean the output of cue and make it git diffable: yq -s -S --yaml-output '.| sort_by(.metadata.name) | sort_by(.kind) | .[] | (.spec.template.spec.containers |select(.!=null) | .[].env |select(.!=null)) |= sort_by(.name) | (.spec.template.spec.containers |select(.!=null) | .[].volumeMounts |select(.!=null)) |= sort_by(.name) | (.spec.template.spec.volumes |select(.!=null)) |= sort_by(.name)'

[mpvl]

Would it be useful to have a semantic diff? There is an internal diff package in the CUE, but we could expose it as a package and or command. If the latter, you could comment on Issue #8 on how you think this would best look like.

[vikstrous2]

I'll comment on #8 because that's closer to my use case.

[cueckoo]

This issue has been migrated to cue-lang/cue#745.

For more details about CUE's migration to a new home, please see cue-lang/cue#1078.