[romka2]

That's a cool algorithm.

The improvements in the article look pretty small between different versions because CPU time is dominated by system calls that are out of my control. If you look at userspace CPU only, the speedup between v1 and v5 is 15x. In other words, the final version uses 15 times less CPU time in userspace. It also uses less CPU in the kernel, but the improvement there isn’t as dramatic (just the openat vs open optimization).

If some clever sorting optimization could yield infinite speedup and would optimize away all loop counters and pointer arithmetics, the overall performance of ListDir v5 would only increase by 3%. v5 is basically all kernel code, there is almost nothing left to optimize algorithm-wise.