Improve readDir performance

[roberth]

Is your feature request related to a problem? Please describe.

builtins.readDir currently performs stat calls for each directory entry. This is bad enough that @aakropotkin works around readDir with a generated file. A fast readDir may allow Nixpkgs to replace all-packages.nix over time; a project that the Nixpkgs Architecture Team is researching.

Describe the solution you'd like

Implementation 1, posix compatible:
Fill the attrset with thunks that call pathType #3096

Implementation 2, linux optimized:
Use getdents or getdents64

Describe alternatives you've considered

Avoid readDir on large directories, generate a list of files. The readDir function is not crucial for the architecture team proposal.

Additional context

nixpkgs-architecture/simple-package-paths#17 (comment)

[edolstra]

I'm a bit skeptical about auto-called-packages. It inherently makes any Nix evaluation take time linear in the size of Nixpkgs, rather than the number of packages used by the derivation you're building. A full traversal would be deadly on non-SSD drives (and even on SSD it takes >2 seconds on a cold cache), but maybe we don't need to care about that anymore. IIRC that was one of the reasons why the previous attempt at auto-called packages was reverted (NixOS/nixpkgs/ece61b7cc803d374e81b1094bd9c1f6d5a9ca5d0).

Having said that, readDirectory is supposed to avoid stat calls by returning a type hint (which may be DT_UNKNOWN depending on the filesystem/OS).

[roberth]

It inherently makes any Nix evaluation take time linear in the size of Nixpkgs

Technically this is already the case, but with a small constant factor.
We won't be scanning recursively, but if performance suffers, we will use a generated list in a file instead.

Having said that, readDirectory is supposed to avoid stat calls by returning a type hint (which may be DT_UNKNOWN depending on the filesystem/OS).

It seems that we've overlooked this. "Implementation 2" seems to be already implemented then. The .type thunk optimization could still be implemented.

[Ericson2314]

Yeah it is already linear time today. And even if Nixpkgs continues to not use it, it should still be better if we can make it better. Finally, if we ever do #4090 we can simply stat paths (or the lazy trees equivalent) when attributes are accessed, fully lazy again!

Basically, lazy vs eager (and thus O(size of attrset) vs O(min(number of accesses, size of attrset))) and read dir vs all-packages.nix should be orthogonal.

[nixos-discourse]

This issue has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2022-11-21-nixpkgs-architecture-team-meeting-18/23393/1

[edolstra]

Other than the size of all-packages.nix, how is it linear? Doing nix-build -A hello will only read the Nix files for hello and its dependencies. It's not doing a traversal of the entire Nixpkgs tree.

[Ericson2314]

The nixpkgs record (of thunks) is still constructed, which is linear in respect to the top level namespace. Reading all the dir entries and creating thunks is also linear with respect to the top level namespace.

It's not doing a traversal of the entire Nixpkgs tree.

And neither is this! We don't need to care what is inside each directory, that work is deferred in a thunk.

[nixos-discourse]

This issue has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2022-12-05-nixpkgs-architecture-team-meeting-20/23740/1

[Ericson2314]

#7447 does the first part of this.

[Ericson2314]

https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/unix/sysv/linux/readdir64.c;h=7952da5c27555e44f3970629f8cfd39cb42425f3;hb=HEAD#l42 shows that glibc
and https://git.musl-libc.org/cgit/musl/tree/src/dirent/readdir.c shows that musl already does chunking internally so I don't think the second part is necessary on Linux.

We didn't get into empirical benchmarking that much today, but @gropotkin did say things seemed plenty fast on Linux in general, and the problem might be macOS only. We'll do more exploring over this I suppose next time.

[nixos-discourse]

This issue has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2022-12-12-nixpkgs-architecture-team-meeting-21/23967/1

[roberth]

I agree that (2) is not needed. I'm pretty sure my intent with the reference to the syscall documentation was just to show that it's possible to get the info efficiently. When readdir exposes that for us, that's the best way to use getdents. Actually skipping libc would be almost pointless and certainly not productive for us.