Slow exportReferencesGraph

[roberth]

This computeFSClosure call is very inefficient, because

• it is called for each .drv in the closure (e.g. over 4000 times in my case)

• it recomputes the whole closure, because the second parameter is only written to. computeFSClosure/computeClosure should probably not assume that the closure property holds for this res set; that seems risky

It seems to lead to O(n²) cost.

Perhaps these paths could be gathered up in a set, and then run computeFSClosure on that set?

It is very tempting to just set includeOutputs = true, and be done with it, but that would silently ignore missing outputs, which could lead to a build impurity if not checked.

To reproduce with Nixpkgs,

nix-build -A nixosTests.nixos-rebuild-target-host

I'll open an issue.

Originally posted in 2897286

[roberth]

I glossed over .second and return in

nix/src/libutil/closure.hh

Line 39 in 55fe4ee

if (!state->res.insert(current).second) return;

It does read from the result set that way, so it's slow for a different reason.

When interrupting the daemon with gdb, it's always querying path info for prepareStructuredAttrs, anecdotally (like 8 tries).

Perhaps it could be sped up by

• only querying the references in computeFSClosure
• reducing the closure size with an implementation of A function rebuildDependencyClosure that produces an efficient closure for offline rebuilds nixpkgs#180529
  • this implementation must not use exportReferencesGraph