lsr: ls with io_uring

Summary

As an excercise in syscall golf, I wrote an implementation of ls(1) which uses my IO library, ourio to perform as much of the IO as possible. What I ended up with is something that is faster than any version or alternative to ls I tested, and also performs an order of magnitude fewer syscalls. I’m calling it lsr. Let’s start with the benchmarks, then we’ll see how we got there.Data gathered with hyperfine on a directory of n plain files.Programn=10n=100n=1,000n=10,000lsr -al372.6 µs634.3 µs2.7 ms22.1 msls -al1.4 ms1.7 ms4.7 ms38.0 mseza -al2.9 ms3.3 ms6.6 ms40.2 mslsd -al2.1 ms3.5 ms17.0 ms153.4 msuutils ls -al2.9 ms3.6 ms11.3 ms89.6 msData gathered with strace -c on a directory of n plain files. (Lower is better)Programn=10n=100n=1,000n=10,000lsr -al2028105848ls -al4056753,37730,396eza -al3194111,32010,364lsd -al5081,40810,423100,512uutils ls -al4459866,39710,005Let’s start with how lsr works. To list directory contents, we basically have 3 stages to the program:Parse argsGather dataPrint dataAll of the IO involved happens in the second step. Wherever possible, lsr utilizes io_uring to pull in the data it needs. To get to that point, it means that we open the target directory with io_uring, if we need local time, user data, or group data, we open (and read) those files with io_uring. We do all stat calls via io_uring, and as needed we do the equivalent of an lstat via io_uring. In practice, this means that the number of syscalls we have should be drastically smaller than equivalent programs because we are able to batch the stat syscall. The results clearly show this…lsr has at least an order of magnitude fewer syscalls than it’s closest equivalent, being uutils ls.We also use the zig stdlib StackFallbackAllocator. This let’s lsr allocate memory it needs up front, but fallback to a different allocator when it’s exhausted the fixed allocation. We allocate 1MB up front, which is more than enough for typical usage. This further reduces syscalls by reducing mmap usage.A...