[perf] cache nix.searchSystem #1546

savil · 2023-10-09T23:22:58Z

Summary

From observing times for adding and removing packages, I notice that a lot of time is spent in syncPackagesToProfile and most of that is from nix.Search, which is a fairly slow operation. However, from observing the results, it seems that these should be constant.

For example, here are some search results keyed by the queries:
https://gist.github.com/savil/584c4d9bd6c468aaa8c289265287a23a
Correct me if wrong: all these seem to be constants that won't change, because the queries we run have the nixpkgs-commit-hash in them.

The general nix search command seems to be slower since the query it accepts is an installable regex, which can match a large number of concrete queries. Furthermore, it needs to accept queries likenixpkgs#vim and figure out which nixpkgs commit hash this would resolve to. In our case, our queries are much more specific being of the form nixpkgs/<commit>#attribute

How was it tested?

This effect is more pronounced for packages that are not using store-paths. This will affect all users who are still on nix < 2.17, which is a fairly large percentage for now.

I have a devbox global of about 43 packages. For the times below, I ran devbox global add vim (where vim is already in my /nix/store), and did export DEVBOX_FEATURE_REMOVE_NIXPKGS=0

BEFORE:
syncPackagesToProfile takes about 1 min 30+ seconds

AFTER:
syncPackagesToProfile takes 500ms

savil · 2023-10-09T23:23:10Z

Current dependencies on/for this PR:

main
- PR [perf] cache nix.searchSystem #1546 👈

This comment was auto-generated by Graphite.

internal/nix/search.go

mikeland73 · 2023-10-11T04:37:19Z

internal/devpkg/package.go

@@ -284,8 +284,25 @@ func (p *Package) NormalizedPackageAttributePath() (string, error) {
 	return p.normalizedPackageAttributePathCache, nil
 }

+// search attempts to find the package in the local nixpkgs. It may be an expensive
+// call, if it is has not been cached.
+func (p *Package) search(query string) (map[string]*nix.Info, error) {


This API is really weird. Having the package as a receiver and also requiring a query. I would suggest a different API, but I'm not sure we need this function at all. See comments below

I don't follow why its that's weird?

We use the receiver's properties to determine how to execute the search.

The query is needed to do the search.

Maybe it can be renamed to searchNixPackageLocally or something more specific.

It's weird because you are searching for the query (which is determined by the package), but tangentially using the package information to determine how the search will happen as well.

It's a bit like

mysql := devpkg.New("mysql") mysql.Search("mysql")

Search should not have a receiver OR should not have a query param.

I'm not sure renaming it addresses the concern.

An alternative:

func (p *Package) lookupNixInfo() (map[string]*nix.Info, error) { var query string if p.IsDevboxPackage() { if p.isVersioned() { entry, err := p.lockfile.Resolve(p.Raw) if err != nil { return "", err } query = entry.Resolved } else { query = p.lockfile.LegacyNixpkgsPath(p.String()) } } else { query = p.String() } return nix.Search(query) }

I still don't understand the concern. Your analogy is not accurate.

I'll just inline it.

We can't use a function like yours above because we need the query later in normalizePackageAttributePath

internal/devpkg/package.go

mikeland73 · 2023-10-11T04:38:44Z

internal/devpkg/package.go

+		return nix.SearchNixpkgsAttribute(query)
+	}
+
+	// fallback to the slow but generalized nix.Search
+	return nix.Search(query)


Why the distinction between devbox packages and flakes? Can't you cache the flakes as well?

I'm being conservative in this PR. I'll see if it makes sense for flakes...

We cannot use nix.Search caching for flakes, local flakes at least. For now, I'd lean towards being conservative and just support queries of the form nixpkgs/commit#attribute

To illustrate the problem, consider the examples/flakes/php. This has a package "path:my-php-flake#php"

The query for this package is of the form: <absolute path on laptop>/devbox/examples/flakes/php/my-php-flake#php

Originally, that flake exported:

php = pkgs.php.withExtensions ({ enabled, all }: enabled ++ (with all; [ ds ]));

and the infos returned from nix.Search is map[packages.x86_64-darwin.php:php-with-extensions-8.1.19]

However, inside the package's flake.nix, I can make this edit:

php = pkgs.cowsay;

and now the infos is map[packages.x86_64-darwin.php:cowsay-3.7.0] for the same query.

mikeland73 · 2023-10-11T04:39:38Z

internal/nix/search.go

-	if strings.HasPrefix(url, "runx:") {
-		// TODO implement runx search
-		return map[string]*Info{}, nil
-	}


Yeah, this is wrong, but I'm not sure we should fix it in this PR?

mikeland73 · 2023-10-11T04:42:33Z

internal/nix/search.go

+// queries of the form `nixpkgs/<commit-hash>#attribute`, we can know for sure that
+// once `nix search` returns a valid result, it will always be the very same result.
+// Hence we can cache it locally and answer future queries fast, by not calling `nix search`.
+func SearchNixpkgsAttribute(query string) (map[string]*Info, error) {


Why not just CachedSearch

For the reasons explained in the comment.

I wanted to keep it specific to search queries I have high confidence should always resolve to the very same result. The nix search api accepts installable regex queries which this doesn't. Hence I chose a very specific name to indicate what scenarios this works with.

see my comment above about flake-reference queries not being suitable to be cached.

Could we throw in a regex to verify that the input query is ^github:NixOS/nixpkgs/[0-9a-f]{40}#? Just to make sure we don't end up caching a ref like github:NixOS/nixpkgs/nixpkgs-unstable#go_1_19.

good call, done

internal/nix/search.go

gcurtis · 2023-10-11T13:52:57Z

I had a few ideas I wanted to throw out there in case they help with the performance:

Do we use nix search just to determine if a flakeref valid? If so, would running nix eval --raw nixpkgs#one nixpkgs#two ... once with all the packages speed things up?
Are we evaluating the flakerefs in pure mode? That would let Nix leverage its own cache.
Nix 2.18 has a new built-in for parsing flake refs. Not sure if that would help at all here.

mikeland73 · 2023-10-11T16:52:25Z

@savil I just realized the reason this is super slow for you it's because it's downloading nixpkgs. We are searching for the "resolved" packages. Previously nixpkgs always existed because you could not install the package otherwise. But now that we allow installing packages without nixpkgs, this function will needlessly download nixpkgs.

I still think caching is a good idea, but now I think how we do profile comparisons for packages with store path is broken. We should not be running search on a reference that includes nixpkgs if we don't intend on installing the package using nixpkgs

Just to give you an example, if our lockfile includes store paths, then simply comparing the store path on the nix profile and the store path in the lockfile is sufficient.

@gcurtis, for more context:

we use search to find a normalized way to compare packages in devbox.json with packages in the nix profile.

Nix has a set of rules of how it determines the default output. To avoid re-implementing those rules we rely on search. If two flake references with outputs are searched we can compare the results and that way we know we are using same rules as nix.

For example:

github:F1bonacc1/process-compose#process-compose
github:F1bonacc1/process-compose

Are both the same.

Similarly, nixpkgs can be referred to using github, nixpkgs or as a devbox package. This function allows us to compare all of these correctly.

Using eval could work, but in practice can be slower (~600ms) than search. I think the solution is:

We need to ensure we never download nixpkgs for a package that was installed via store path
Add caching to avoid slowish calls to nix search

savil · 2023-10-11T17:05:59Z

@savil I just realized the reason this is super slow for you it's because it's downloading nixpkgs. We are searching for the "resolved" packages. Previously nixpkgs always existed because you could not install the package otherwise. But now that we allow installing packages without nixpkgs, this function will needlessly download nixpkgs.

I still think caching is a good idea, but now I think how we do profile comparisons for packages with store path is broken. We should not be running search on a reference that includes nixpkgs if we don't intend on installing the package using nixpkgs

Just to give you an example, if our lockfile includes store paths, then simply comparing the store path on the nix profile and the store path in the lockfile is sufficient.

Ah, no, this is not accurate. In my testing, I had disabled remove-nixpkgs, removed .devbox, and installed all packages in the devbox.json. All timings are after doing that setup and then doing devbox add.

For remove-nixpkgs, @ipince and I added various higher-level functions (like NixProfileItem.Matches) so packages with store-paths don't call this function. Otherwise, you'd be witnessing "Downloading nixpkgs" a lot more!

gcurtis · 2023-10-11T18:28:30Z

Directly-installed packages slowing things down makes sense. Even if it's not downloading a new nixpkgs commit, just evaluating the package for the first time can take a while.

Taking a step back, why are we comparing packages in the profile to the ones in devbox.json? I'm a little unsure about adding caching, because that's what Nix is supposed to do. We should just have the devbox-generated flake refer to the packages and save them to a file.

Here's a small example of a flake that could be generated to track Devbox dependencies:

{
  description = "A Devbox environment";

  outputs = { self, nixpkgs }: {
    packages.aarch64-darwin.default = derivation {
      name = "devbox-env";
      system = "aarch64-darwin";
      builder = "/bin/bash";
      args = let
        script = builtins.toFile "builder.sh" ''
          echo "$hello
          $go" > $out
        '';
        in [ "${script}" ];

      # Note the packages don't need to be nixpkgs attributes. They could also
      # be direct store paths or `fetchClosure` calls.
      hello = nixpkgs.legacyPackages.aarch64-darwin.hello;
      go = nixpkgs.legacyPackages.aarch64-darwin.go;
    };
  };
}

If you run nix path-info it spits out all the references:

// $ nix path-info --json | jq
[
  {
    "deriver": "/nix/store/kpl2nb2b3xwkyw0ma4d4qnxvsz3zllgh-devbox-env.drv",
    "narHash": "sha256-KzYFyXkgG8kWpdHNABX/zu6qchMP7TWylosl8/zirOk=",
    "narSize": 224,
    "path": "/nix/store/c9046f6p7dg0v248cvrfhlqbj5bsy544-devbox-env",
    "references": [
      "/nix/store/c4n3i1nfhvcim30s4ij502cw84yl4vdn-hello-2.12.1",
      "/nix/store/dpnvxm37r1z9vk77mdc3h68b95kxvsji-go-1.20.8"
    ],
    "registrationTime": 1697048631,
    "ultimate": true,
    "valid": true
  }
]

savil

@mikeland73 switched to using filecache. I've left the API as nix.SearchNixpkgsAttribute

This is a specialized api for queries of the form nixpkgs/<commit>#attribute
I want it distinct from nix.Search which is the more general API that supports all queries (nixpkgs/<commit>#attribute, all other flake references, etc.)
open to alternate names, but not to having "cache" in it since that doesn't tell users when to use it, and users shouldn't need to worry about it being cached or not.

@gcurtis I hear your concerns. However, I'm a bit reluctant to change the machinery of how we're currently implementing all of with devpkg and nix-profile. That would be a more invasive change.

To your concerns:

I'm a little unsure about adding caching, because that's what Nix is supposed to do.

nix search is a very general API. This makes it hard for nix to internally optimize it. In our case, we are adding caching for a strict subset of it that we know is always guaranteed to return the same result: nixpkgs/<commit>#attribute. We can do this because we know our app's specific query patterns and can exploit it. Seems reasonable to me.

We should just have the devbox-generated flake refer to the packages and save them to a file.

The problem with this is that we can't query it while incrementally adding or removing packages quickly (EDIT: actually, I have low confidence in what I said, perhaps there's a way. My bigger concern is limiting scope for now)

savil · 2023-10-25T22:27:25Z

ping

gcurtis · 2023-10-26T15:26:05Z

internal/nix/search.go

+// cacheKey sanitizes the search query to be a valid unix filename.
+// This cache key is used as the filename to store the cache value, and having a
+// representation of the query is important for debuggability.
+func cacheKey(input string) string {


Do we handle collisions for queries that have sanitized characters? Using the infamous emacsPackages.@ package as an example, the input would get cached under the key emacsPackages.. Does that mean devbox add emacsPackages. would install that package if it was in the cache?

Ooh good catch. I added that @ to the "replace disallowed chars with underscores"

I tried searching the other non-alphanumeric-characters on my standard American keyboard, and no packages showed up so I think its okay (practically speaking).

Theoretically speaking this scheme is not collision-resistant since two packages with foo-<disallowed-char-number-one> and foo-<disallowed-char-number-two> would have a collision in the sanitized name. Same for the name-length-truncation we do.

gcurtis · 2023-10-26T15:31:34Z

internal/nix/search.go

+// queries of the form `nixpkgs/<commit-hash>#attribute`, we can know for sure that
+// once `nix search` returns a valid result, it will always be the very same result.
+// Hence we can cache it locally and answer future queries fast, by not calling `nix search`.
+func SearchNixpkgsAttribute(query string) (map[string]*Info, error) {


Could we throw in a regex to verify that the input query is ^github:NixOS/nixpkgs/[0-9a-f]{40}#? Just to make sure we don't end up caching a ref like github:NixOS/nixpkgs/nixpkgs-unstable#go_1_19.

… the name

mikeland73

Looks great! no blocking comments.

internal/nix/search.go

mikeland73 · 2023-10-26T23:22:12Z

internal/nix/search.go

+}
+
+// read as: filecache.NeedsUpdate(err)
+// TODO savil: this should be implemented in the filecache package


mikeland73 · 2023-10-26T23:25:35Z

internal/nix/search.go

+
+// read as: filecache.NeedsUpdate(err)
+// TODO savil: this should be implemented in the filecache package
+func filecacheNeedsUpdate(err error) bool {


fwiw I would just name this isNotFoundOrExpired

Maybe in filecache, using new errors.Join we can return an error that is both NotFound and also something like CacheMiss

so return errors.Join(NotFound, CacheMiss)

and then here we just check if it is CacheMiss

yeah, that sgtm

named it as: filecacheIsCacheMiss

mikeland73 · 2023-10-26T23:29:22Z

internal/devpkg/package.go

+	// nix.Search will guarantee that the package exists for the current system.
+	var infos map[string]*nix.Info
+	var err error
+	if p.IsDevboxPackage() && !p.IsRunX() {


Nice! this feels really understandable to me.

savil force-pushed the savil/cache-nix-search branch 2 times, most recently from 378c267 to a0d9a8f Compare October 9, 2023 23:36

savil requested review from mikeland73, LucilleH and gcurtis October 9, 2023 23:39

savil force-pushed the savil/cache-nix-search branch from a0d9a8f to d5cdee7 Compare October 9, 2023 23:40

savil marked this pull request as ready for review October 9, 2023 23:41

savil commented Oct 10, 2023

View reviewed changes

internal/nix/search.go Outdated Show resolved Hide resolved

savil marked this pull request as draft October 10, 2023 13:04

savil mentioned this pull request Oct 10, 2023

[perf] in syncPackagesToProfile, only removeExtraItemsFromProfile is mode is not install #1541

Merged

savil force-pushed the savil/cache-nix-search branch from d5cdee7 to 7e75d9f Compare October 10, 2023 18:51

savil marked this pull request as ready for review October 10, 2023 18:52

savil removed the request for review from LucilleH October 10, 2023 20:51

mikeland73 requested changes Oct 11, 2023

View reviewed changes

savil force-pushed the savil/cache-nix-search branch 2 times, most recently from c0bc050 to 81a06d1 Compare October 24, 2023 13:00

savil requested a review from mikeland73 October 24, 2023 13:03

savil commented Oct 24, 2023

View reviewed changes

gcurtis approved these changes Oct 26, 2023

View reviewed changes

savil added 5 commits October 26, 2023 13:47

[perf] cache nix.searchSystem

503f884

move out of nix.Search, and rename to SearchNixpkgsAttribute

54d95ad

lint fix

b2fb532

use filecache

e393a99

requested fixes: allowableQuery regex, and sanitize queries with @ in…

0dbfe03

… the name

savil force-pushed the savil/cache-nix-search branch from 81a06d1 to 0dbfe03 Compare October 26, 2023 21:25

mikeland73 approved these changes Oct 26, 2023

View reviewed changes

requested changes

314d249

savil merged commit 00ee8fb into main Oct 27, 2023

savil deleted the savil/cache-nix-search branch October 27, 2023 00:52

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[perf] cache nix.searchSystem #1546

[perf] cache nix.searchSystem #1546

savil commented Oct 9, 2023 •

edited

Loading

savil commented Oct 9, 2023

mikeland73 Oct 11, 2023

savil Oct 11, 2023

mikeland73 Oct 11, 2023

savil Oct 24, 2023 •

edited

Loading

mikeland73 Oct 11, 2023

savil Oct 11, 2023

savil Oct 24, 2023

mikeland73 Oct 11, 2023

mikeland73 Oct 11, 2023

savil Oct 11, 2023

savil Oct 24, 2023

gcurtis Oct 26, 2023

savil Oct 26, 2023

gcurtis commented Oct 11, 2023

mikeland73 commented Oct 11, 2023

savil commented Oct 11, 2023

gcurtis commented Oct 11, 2023

savil left a comment •

edited

Loading

savil commented Oct 25, 2023

gcurtis Oct 26, 2023

savil Oct 26, 2023

gcurtis Oct 26, 2023

mikeland73 left a comment

mikeland73 Oct 26, 2023

mikeland73 Oct 26, 2023

savil Oct 27, 2023

savil Oct 27, 2023

mikeland73 Oct 26, 2023

[perf] cache nix.searchSystem #1546

[perf] cache nix.searchSystem #1546

Conversation

savil commented Oct 9, 2023 • edited Loading

Summary

How was it tested?

savil commented Oct 9, 2023

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

savil Oct 24, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

gcurtis commented Oct 11, 2023

mikeland73 commented Oct 11, 2023

savil commented Oct 11, 2023

gcurtis commented Oct 11, 2023

savil left a comment • edited Loading

Choose a reason for hiding this comment

savil commented Oct 25, 2023

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mikeland73 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

savil commented Oct 9, 2023 •

edited

Loading

savil Oct 24, 2023 •

edited

Loading

savil left a comment •

edited

Loading