3

In an answer over on Stack Overflow, I provided a code sample to perform some small task referenced in the question. The original question had to do with the fastest-performing technique (so performance criteria are in play, here).

Another commenter/answerer suggested that making a POSIX-defined system API call (in this case, readdir) was not as fast as making a direct system call into the kernel (syscall(SYS_getdents,...)) and the claimed performance difference is in the 25% range. (I didn't implement and re-benchmark; I believe that the performance could in fact be better.)

My question is about the performance characteristics of the proposed syscall-based solution and why they might be faster. I can think of a few reasons why performance might be better:

  1. POSIX readdir is inherently more complicated than syscall(SYS_getdents,...)/getdents()
  2. readdir (which presumably calls syscall(SYS_getdents,...) simply adds the overhead of indirection
  3. readdir only returns one record (per kernel-call) versus syscall(SYS_getdents,...)/getdents()` which returns (presumably) more than one record per kernel-call

I can't imagine that #1 above is true. readdir and getdents are so similar that the implementation of readdir in glibc simply can't have many more "true" system calls than a direct-invocation of syscall(SYS_getdents,...)/getdents() would invoke.

I can't imagine that #2 is true, either, since calling readdir likely wraps getdents and also syscall(SYS_getdents,...) likely calls getdents as well (the proposed answer specifically uses syscall(SYS_getdents,...) instead of calling getdents directly. It's possible that everything within glibc on Linux boils down to syscall(syscallid, args) in which case #2 probably is true.

The last possibility seems to me to be the best explanation: fewer calls into the kernel simply results in faster performance.

Is there any specific explanation for why a "direct kernel call" would be measurably faster than calling a POSIX-defined function?

  • 2
    POSIX does not specify any system calls, it specifies APIs – fpmurphy Jan 10 '18 at 2:14
  • @fpmurphy1 Pardon me for misspeaking. I meant POSIX-defined APIs not system calls, of course. – Christopher Schultz Jan 10 '18 at 21:08
1

Functions like readdir() and friends are implemented in libc, which is a shared library. As with all shared libraries, that adds some redirection in order to be able to resolve the memory address of the function inside the shared library.

The first time any particular library call is performed, the dynamic linker needs to look up the address of the library call inside a hash table. This involves at least one (but possibly more) string comparisons, a comparatively expensive method. The found address is then saved in the PLT (procedure linkage table), so that the next time the function is called, the overhead of finding the function is reduced to three instructions (on the x86 architecture, fewer than that on some other architectures). This is why compiling something as a shared object (rather than a static object) has some overhead. For more information on shared library overhead and how shared libraries work on Linux, see Ulrich Drepper's detailed technical explanation on the subject.

The syscall() function itself is also implemented in libc, so it too has that redirection. However, since you would only use that function (and no other), the dynamic linker has less work to do. In addition, the implementation of a particular function such as readdir would have to convert the return values and do error checking etc upon exiting the syscall() function, which is some extra overhead. A program that runs syscall() directly would work with the direct return values of the system call and would not need that conversion (it would still need to do the error checking, which would complicate the function significantly).

The downside of running syscall() directly is that you move to an API that is less portable. The syscall() manpage explains some architecture-specific constraints that libc deals with for you; if you use syscall() directly, your function might work on the architecture you're dealing with, but would fail on, say, an arm machine.

In general, I would recommend against using the syscall() API directly, for the very same reason that I would recommend against writing the code in assembly language directly. Yes, that might end up being faster in the end, but the maintenance burden becomes (much) higher. Some things you could do instead:

  • Don't care about performance. Systems keep getting cheaper, and in many cases "adding another system so things go faster" is cheaper than "paying a programmer's hourly rates to improve performance".
  • Compile the software against static libraries rather than using shared libraries, for the few small things where performance is critical (i.e., gcc -static)
  • Use a profiler to see where things are going slow, and focus on those things, rather than worrying about how to do a system call.
  • Thank you for your detailed response. I agree that direct system calls should be avoided and portability (and, perhaps more importantly, readability) is a more important factor than performance in general. In my question, I was specifically curious about the performance implications of using syscall directly as opposed to a POSIX-defined API which ultimately probably makes the same underlying system call. Could you clarify in your answer whether you think that "translation overhead" or "less frequent kernel calls" is likely to make the greater performance difference, here? – Christopher Schultz Jan 10 '18 at 21:06
  • He's saying that there is a one-time cost in the glibc version of the call due to the overhead of dynamic linking. There is no reduction in the number of system calls in the usual case of calling a function that always just calls the underlying system call. In some cases, calling the "POSIX" calls (really just library calls) may have a huge reduction: something like getc will only make an occasional kernel call to read many characters and then cache the result in-process, so most calls don't go the kernel at all. – BeeOnRope Feb 21 '18 at 19:29
  • Wouter - interesting point about the PLT, but you might point out this is a one-time cost: if the cost of any given system call is important, you are likely calling it many times (or else it wouldn't be important) and the PLT cost goes to zero (in a relative sense). In my benchmarks, using syscall(...) is slower than calling the library wrapper (by about 4 cycles, generally), probably because syscall is a generic varargs method and has to shuffle all the arguments around to make them line up with the syscall interface, while the wrapper functions have less of an issue. – BeeOnRope Feb 21 '18 at 19:32
  • @BeeOnRope I actually did point that out ;-) but my main point was "don't worry about performance in a generic sense, worry about the output of your profiler". I stand by that, as your point shows, too. – Wouter Verhelst Feb 26 '18 at 17:11
  • Directory scans on Linux take from start at about 5µs for an empty directory. The PLT overhead (<1ns) or even the function call overhead (1-2ns) of readdir there is a drop in the bucket. Completely negligible. – PSkocik Jul 14 at 0:00
3

Factors like PLT indirection or syscall()'s variadic-ness (registers have to be saved to memory) should play little role given that getdents is one of the most expensive calls in Linux.

Fully reading an empty directory on my machine costs about 5µs, a 100-item directory 37µs, a 1000-item directory 340µs and a 10,000-item directory 3.79ms.

What fdopendir+readdir does on top of getdents is it adds a buffer allocation/deallocation (0.1µs) and a stat check that the supplied fd is of the directory variety (0.4µs). readdir then makes one cheap call per directory entry (moves a position in the buffer and possibly refills).

So there is something like a one-time overhead of 0.5µs, which is 10% of the directory scanning time for empty directories, but only 1% for 100-item directories and negligibly little for larger ones. This overhead is 5 times less (only the allocation/deallocation cost) if you you don't need fdopen. (you only need fdopen if you can't diropen directly and therefore must go through a separately obtained (e.g., openat'ted) filedescriptor).

So if you use a custom one-time allocated buffer along with getdents, you can save 2-10% on the scanning cost of empty directories and negligibly little on the bigger ones.

As for the readdir calls, the cost of PLT indirection on modern hardware is typically less than a 1ns, function call overhead is about 1-2ns. Given that the directory scanning times are in the order of microseconds, you'd need to make at least 1000 readdir calls for these factors to translate into a single µs, but then the scanning cost is 340µs and the accrued 1 extra µs is like 0.3% of that -- negligible effect. Inlining these readdir (thus eliminating the call overhead and the PLT overhead) would only serve to expand the code, but it wouldn't much improve performance as getdents is very much the bottleneck there.

(readdir_r is more expensive because of additional locking, but you shouldn't need readdir_r because plain readdir calls are typically thread-safe unless you have multiple threads calling them on the same directory stream. POSIX might not be explicit about this yet, but I believe this guarantee should be getting standardized soon given that glibc went as far as to deprecate readdir_r.)

  • 1
    Thanks for this analysis. Others may disagree, but it demonstrates to me that direct syscalls are not worth the reduction in portability for the of use-case presented in the original question: the whole point of the "as fast as possible" requirement is due to the fact that reading huge directories takes a long time. Reading an empty directory is practically instantaneous therefore the "huge" performance hit for using opendir is irrelevant. – Christopher Schultz Jul 15 at 14:19
0

Is there any specific explanation for why a "direct kernel call" would be measurably faster

I think the notorious case where this actually matters, is if your filesystem does not do sufficient readahead, given the size of your directory, and the per-request latency of your disk device. I.e. this may be higher on busy disks (long request queues), or disks accessed over a network.

http://be-n.com/spw/you-can-list-a-million-files-in-a-directory-but-not-with-ls.html

For most purposes, the amount of buffering used by glibc does not cause any problem. Pointing to this extreme as justification for bypassing the usual buffering code, may lead to calls of "premature optimization" or similar annoyance :-).

https://github.com/BurntSushi/walkdir/issues/108


If you're not too tired of reading Linus going off on one, he had some comments about filesystem directory readahead. They might or might not be revealing.

https://lore.kernel.org/lkml/20061229171654.e6e1b1c7.akpm@osdl.org/T/#u

ext4_readdir() has not been changed to satisfy Linus' rant. I don't see his desired approach used in readdir() of other filesystems either. I think XFS uses the (physically indexed) buffer cache for directories as well [at least this means it cannot not benefit from the core readahead implementation, if the directory is fragmented]. bcachefs does not use the page cache for readdir() at all; it uses its own cache for btrees. I might be missing something in btrfs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.