cmd/cue: unnecessary scan of every directory when loading any package

[Bryant-Cockcroft-IBM]

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

$ cue version
cue version v0.9.0-alpha.5

go version go1.21.0
      -buildmode exe
       -compiler gc
     CGO_ENABLED 1
          GOARCH ppc64le
            GOOS linux
         GOPPC64 power8
cue.lang.version v0.9.0

Does this issue reproduce with the latest stable release?

No, only on pre-release. Also happens with CUE_EXPERIMENT=modules on earlier v0.9.0 alpha versions. Does not reproduce with the new modules disabled.

What did you do?

cue eval --out json example.com/pkg/foo

I have a large project where cue is only a small component. So the cue module root contains many directories and sub-directories un-related to the cue module. But these directories are separate from the foo package above, so I'd expect them to not effect this evaluation.

What did you expect to see?

I expected similar evaluation time to doing cue eval --out json test.cue Where test.cue just imports the exact same foo package. Which takes less than 1 second in this case.

I expect cue commandline to only look a the foo directory and directories leading to the module root, and nothing else, as described in the package instances https://cuelang.org/docs/concept/modules-packages-instances/#instances

What did you see instead?

The command-line version recursively walks every directory starting at the module root looking for cue.mod. Since my project has 100s if not 1000s of directories in total, this now takes ~14 seconds. (note: it does find one in the actual root, but does not stop until it's searched every directory)

used strace -f -t -e trace=file cue eval --out json example.com/pkg/foo to determine this behavior.

I'm unable to share my actual data, but I can probably create reproducer if necessary.

[mvdan]

Thanks for the report. I can reproduce in our repository as well:

$ go install ./cmd/cue && CUE_EXPERIMENT=modules=0 strace -f -t -e trace=file cue fmt ./internal/ci |& grep 'cue\.mod"' | wc -l
8
$ go install ./cmd/cue && strace -f -t -e trace=file cue fmt ./internal/ci |& grep 'cue\.mod"' | wc -l
360

Note how the same command without the experiment tries to stat eight cue.mod directories (althoug that is already somewhat wasteful), and the new experiment default statst as many as 360 cue.mod directories - most of which are missing.

[mvdan]

I also don't think this is limited to cue.mod files; when the new modules mode is enabled, we also open (and read and parse) pretty much every CUE file in the entire module, even when they aren't related to a package pattern like ./internal/ci:

$ go install ./cmd/cue && CUE_EXPERIMENT=modules=0 strace -f -t -e trace=file cue fmt ./internal/ci |& wc -l
51
$ go install ./cmd/cue && strace -f -t -e trace=file cue fmt ./internal/ci |& wc -l
924

So I think this is a larger problem with the new cue/load and not just about statting cue.mod files to find module boundaries.

[mvdan]

I believe https://review.gerrithub.io/c/cue-lang/cue/+/1194921 should fix the issue with cue.mod directories; @Bryant-Cockcroft-IBM let me know how this affects your cue eval times.

[mvdan]

The number of syscalls across our repo is nearly halved, from about 920 to 540:

$ go install ./cmd/cue && strace -f -t -e trace=file cue fmt ./internal/ci |& wc -l
543

Most of the remaining syscalls relate to us walking the entire module directory tree to list all package imports in CUE files upfront, which is technically not necessary in most cases.

[Bryant-Cockcroft-IBM]

I do see that about half the elapsed time with that change, but still significantly slower than CUE_EXPERIMENT=modules=0.

0.61s CUE_EXPERIMENT=modules=0
14.07s v0.9.0-alpha.5
7.76s Your change

Most of the remaining syscalls relate to us walking the entire module directory tree

I'm not sure if this is a general problem, or if we're just doing something weird here with our directory structure. But we have a ton of directories that are unrelated to cue that look as if they're in the module.

Taking some guesses at the strace with your change. About 11s total (some overhead from strace itself). 9s of that is spent searching our unrelated directories. When it switches to actually looking at the imports for the files it found, that only takes 1-2s.

For the record, if we decide my use-case is too odd, I think I can workaround this by specifying the files directly instead of the package (because with the choices we made, restructuring might not be an option)

[mvdan]

Thanks @Bryant-Cockcroft-IBM for your update, that halving of wall time makes sense to me - if you have a repository with many directories that don't contain CUE files, the new modules mode used to do two syscalls per directory (one to read its contents, another to check if cue.mod exists inside), and now we do one syscall per directory after my partial fix.

Traversing the entire CUE module directory tree is something that has to happen in some form for commands like cue mod tidy or cue vet ./..., as those need to find all CUE packages. However, for any command involving just one package like cue eval ./some/package, there is a regression with the new CUE_EXPERIMENT=modules default where we still find all CUE packages upfront, even though it's not actually needed.

@rogpeppe is looking into a fix for this for the upcoming release, as we are treating this as a significant enough regression - it will affect any CUE user with a large enough directory structure. It just won't be a trivial fix so it might take us a couple of days to have something ready.

[Bryant-Cockcroft-IBM]

Thanks that all sounds good to me!

[rogpeppe]

In order to fix this issue, we need to evaluate exactly the packages
that are specified on the command line and no more. That's
straightforward when the root packages are listed explicitly, because
we can then trace out their dependencies. But it's a harder job when
there are patterns involved.

Package pattern matching

The cue command supports package patterns of the form xxx...yyy. The
... matches any sequence of characters in a package import path.

In order to do a complete job, we would need to list an arbitrary
number of repositories from the registry, but OCI registries do not in
general support repository enumeration.

Instead of enumerating all possible match candidates, we can use the
build graph itself as the source of possible candidates. This is what
Go does.

However, that approach introduces a potential feedback loop: because
the build graph is limited to modules that contain packages that are
actually used by the main module, the build graph can change if there
are patterns that match packages outside of that set, which can in
turn affect the set of matched packages.

A way forward

The above consideration implies a rather deep change to the code and
is a bigger change than we'd like to introduce at this late stage in
the v0.9.0 release cycle.

Instead, we propose that for now all patterns must be rooted inside
the main module only. That is, either a pattern of the form
./xxx...yyy for some xxx and yyy or of the form
$module/xxx...yyy where $module is the name of the main module.
All other pattern matches would be rejected.

This leaves us open to applying the proper fix at a later date, and
hopefully covers the by-far-most-common use cases.

Possible regression

Note that this approach seems to imply a regression in existing supported behavior.
If a set of packages is present in cue.mod/{gen,usr,pkg} one might think that
we could use a pattern to package packages in those directories.
However, this turns out not to be the case. This functionality was never
actually implemented. The following testscript fails currently with modules disabled
and failed on previous versions too, so the above proposal should not result in
an actual regression.

external-package-patterns.txtar

exec cue vet foo.example/...
-- cue.mod/module.cue --

module: "github.com/foo/bar"

language: {

version: "v0.9.0"

}

-- cue.mod/pkg/foo.example/x/x.cue --

package x
x: int

-- p.cue --

package m
import "foo.example/x"
z: x.x & 123

[mvdan]

@Bryant-Cockcroft-IBM we are done with our first round of fixes for this performance regression. The original number of syscalls for loading a single package (and its few dependencies) in our repo ballooned by about 6x with the experiment as of May 20th, as I explained above:

$ go install ./cmd/cue && CUE_EXPERIMENT=modules=0 strace -f -t -e trace=file cue eval ./internal/ci/repo |& grep '/home/mvdan/src' | wc -l
81
$ go install ./cmd/cue && strace -f -t -e trace=file cue eval ./internal/ci/repo |& grep '/home/mvdan/src' | wc -l
517

With all the changes above, we are now down to a modest ~35% increase in syscalls:

$ go install ./cmd/cue && strace -f -t -e trace=file cue eval ./internal/ci/repo |& grep '/home/mvdan/src' | wc -l
112

This is still not perfect by any means, and we will continue to make improvements to the loading code to be less wasteful, but I think we're most of the way there in terms of fixing the performance regression.

Could you please try the latest master and let me know what the performance is like for your repository?

[Bryant-Cockcroft-IBM]

Yes, it looks so much better! I'm now seeing a net performance increase from v0.8 too!

2.86s v0.8.0
0.61s CUE_EXPERIMENT=modules=0 v0.9.0-alpha.5
14.07s v0.9.0-alpha.5
7.76s Your change (from May 18th)
0.92s latest master on May 30th

[mvdan]

Oh, excellent :) There were some other speed-ups for cmd/cue along the way. It looks like CUE_EXPERIMENT=modules is still giving you a minor slow-down, similar to what I showed above, but overall we're still in net benefit territory from the last stable release, and the performance still seems reasonable :)