Disclaimer: Some of the information here may already be obvious or well understood to you. If it is, then thank you for your patience as I use this as an excuse to push out background information that other developers may find useful.
Oh, I think I was a little unclear in what I wrote. What I was trying to say in "a call to enumerateDirectory of this nature" was that if I call enumerateDirectory with a non-minimal attribute set (i.e. include attributes that need more I/O to fetch), then I see that behavior. But you're right in that iterating over a directory with minimal attributes doesn't generally have additional lookupItem calls in my tests.
Again, you have to be careful of the API you're using. The "classic" Unix directory iteration pattern[1] is to read the directory (readdir-> enumerateDirectory) and then retrieve metadata (stat-> lookupItemNamed).
There are two problems with that:
-
At a basic level, it generates a lot of syscalls, each of which nibble away at performance.
-
From the file system side, it throws away some very easy and obvious performance wins.
Expanding on that last point, the vast majority of block file systems all:
-
Store most of a file’s metadata in a single data structure.
-
Organize those records such that the records for objects within the same directory are (often) physically close to each other on disk a significant portion of the time.
-
Use a storage allocation scheme ("allocation block size") which guarantees that data will be read in large enough chunks that many records will invariably be retrieved at once.
Putting all those points into concrete terms, when a file system retrieves the name of any given object, it invariably has a bunch of other information "at hand" (size, dates, etc.), since all of that information was in the same record. Similarly, the blocks it read to retrieve the data about one file are VERY likely to include the data about other files in the same directory, since they were already close to each other on disk.
All of that is an API like "getattrlistbulk()", readdir_r(), and getdirentriesattr() exist— they let the file system return the data for a bunch of files "at once", taking advantage of the fact that the file system often has much of that data already. One interesting detail about that process— the reason getattrlistbulk takes a list of attributes isn’t to optimize the retrieval process on the file system side— as I talked about above, there often isn't anything to "optimize", since all the data is a single record that the file system can't partially retrieve. What it's actually doing there is reducing what it has to RETURN to user space so that it can pack more replies into the same syscall.
With all that background, let me jump back to here:
What I was trying to say in "a call to enumerateDirectory of this nature" was that if I call enumerateDirectory with a non-minimal attribute set (i.e. include attributes that need more I/O to fetch)
The thing to be aware of here is that different APIs will generate different behavior in ways that aren't entirely obvious/predictable. Notably, NSFileManager's URL enumerator does "bulk" enumeration while its older path enumerator ends up calling stat() on every file. I have a forum post here that covers this and includes some performance comparisons.
Switching over to the FSKit side, that's why "enumerateDirectory" has the design it has— you're using FSDirectoryEntryPacker to fill up a buffer which will then be returned to the kernel (once it's full or you run out of entries).
[1] As a side note, while writing this up I noticed that "Building a passthrough file system" not only uses the (slow) readdir/stat pattern, but appears to leak the directory descriptor and has a serious issue with its telldir() usage (r.175523886). Anyone actually implementing a passthrough file system should probably NOT use that implementation as a direct model.
__
Kevin Elliott
DTS Engineer, CoreOS/Hardware
