Re: readdir vs. getdirentriesattr

2019-04-29 Thread Thomas Tempelmann
Doing more performance tests for directory traversal I ran into a
performance issue with [NSURL contentsOfDirectoryAtURL:]:

See this typical code for scanning a directory:

  NSArray *contentURLs = [fileMgr contentsOfDirectoryAtURL:parentURL
includingPropertiesForKeys:nil options:0 error:nil];

  for (NSURL *url in contentURLs) {

id value;

[url getResourceValue: forKey:NSURLVolumeIdentifierKey error:nil];


I would have expected the call for fetching NSURLVolumeIdentifierKey to be
rather fast because the upper file system layer should know which volume
this belong to because it has to know which FS driver it has to pass the
calls to. I.e., asking for the volume ID should be much faster than
fetching actual directory data such as the file size, for instance.

However, it turns out that this is just as slow as getting actual data from
the lower levels.

Could it be that the call is not optimized for returning this information
as earlier as possible but that it passes the call down to the lowest level
regardless of need?

I mention this because it degrades the performance of a recursive directory
scan significantly in my tests (on both APFS and HFS) - by more than 30%!
The only thing even slower would be to call stat() instead (for getting the
st_dev value).

Is this worth having looked at? If so, should I report this via bugreporter
(though, when I'm then asked to provide a system profiler report then, it's
not going anywhere)?

Thomas
 ___
Do not post admin requests to the list. They will be ignored.
Filesystem-dev mailing list  (Filesystem-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/filesystem-dev/archive%40mail-archive.com

This email sent to arch...@mail-archive.com


Re: readdir vs. getdirentriesattr

2019-04-29 Thread Jim Luther
In contentsOfDirectoryAtURL, instead of "includingPropertiesForKeys:nil", use 
"includingPropertiesForKeys:@[NSURLVolumeIdentifierKey]" (and add whatever 
other property keys you know you'll need). The whole purpose of the 
includingPropertiesForKeys argument is so the enumerator code can pre-fetch the 
properties you need as efficiently as possible. The enumeration will be a bit 
slower, but the entire operation of enumerating and getting the properties from 
the URLs returned will be faster.

Also, use -[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] 
instead of 
-[contentsOfDirectoryAtURL:includingPropertiesForKeys:options:error:] unless 
you really need an NSArray of NSURLs. If your code is just processing all of 
the URLs and has no need to keep them after processing, there's no reason to 
add them to an array (which takes time and adds to peak memory pressure).

-[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] also 
supports recursive enumeration (which stops at device boundaries -- you'll see 
mount points but not their contents) so you don't have to do that yourself.

- Jim

> On Apr 29, 2019, at 8:01 AM, Thomas Tempelmann  wrote:
> 
> Doing more performance tests for directory traversal I ran into a performance 
> issue with [NSURL contentsOfDirectoryAtURL:]:
> 
> See this typical code for scanning a directory:
> 
>   NSArray *contentURLs = [fileMgr contentsOfDirectoryAtURL:parentURL 
> includingPropertiesForKeys:nil options:0 error:nil];
>   for (NSURL *url in contentURLs) {
> id value;
> [url getResourceValue: forKey:NSURLVolumeIdentifierKey error:nil];
> 
> I would have expected the call for fetching NSURLVolumeIdentifierKey to be 
> rather fast because the upper file system layer should know which volume this 
> belong to because it has to know which FS driver it has to pass the calls to. 
> I.e., asking for the volume ID should be much faster than fetching actual 
> directory data such as the file size, for instance.
> 
> However, it turns out that this is just as slow as getting actual data from 
> the lower levels.
> 
> Could it be that the call is not optimized for returning this information as 
> earlier as possible but that it passes the call down to the lowest level 
> regardless of need?
> 
> I mention this because it degrades the performance of a recursive directory 
> scan significantly in my tests (on both APFS and HFS) - by more than 30%! The 
> only thing even slower would be to call stat() instead (for getting the 
> st_dev value).
> 
> Is this worth having looked at? If so, should I report this via bugreporter 
> (though, when I'm then asked to provide a system profiler report then, it's 
> not going anywhere)?
> 
> Thomas
> 
> ___
> Do not post admin requests to the list. They will be ignored.
> Filesystem-dev mailing list  (Filesystem-dev@lists.apple.com)
> Help/Unsubscribe/Update your Subscription:
> https://lists.apple.com/mailman/options/filesystem-dev/luther.j%40apple.com
> 
> This email sent to luthe...@apple.com

 ___
Do not post admin requests to the list. They will be ignored.
Filesystem-dev mailing list  (Filesystem-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/filesystem-dev/archive%40mail-archive.com

This email sent to arch...@mail-archive.com


Re: readdir vs. getdirentriesattr

2019-04-29 Thread Thomas Tempelmann
Jim,

In contentsOfDirectoryAtURL, instead of "includingPropertiesForKeys:nil",
> use "includingPropertiesForKeys:@[NSURLVolumeIdentifierKey]" (and add
> whatever other property keys you know you'll need). The whole purpose of
> the includingPropertiesForKeys argument is so the enumerator code can
> pre-fetch the properties you need as efficiently as possible. The
> enumeration will be a bit slower, but the entire operation of enumerating
> and getting the properties from the URLs returned will be faster.
>

I know. That's the theory, but my benchmarking says it makes no difference
in that case. And that's quite logical because the pre-caching is meant for
data that has to come from the lowest level, i.e. where the catalog data is
fetched - it makes sense to combine multiple property requests into one,
just like the getdirentriesattr is meant to used like. However, as I
explained the volume ID is not stored in the catalog but at a higher level,
and therefore pre-fetching this at the lowest level makes no difference, at
requires no catalog access, right?

My performance tests always runs twice in fast succession, so that in the
second run, due to caching, all data's ready and does not incur random
delays that would give imprecise measurements. Sure, this does not give me
the worst case, but it gives me the best case results at least. And these
best case results say: Scanning "/System" on my Mac without getting the
Volume ID takes less than 3s, but with (with and without pre-fetching)
getting it takes over 6s. That's TWICE as much time. With smaller dir tree
the difference is less, possibly because then there's other caches helping.

I assume that when I re-run the scan, after having released all NSURLs from
the previous scan (even by restarting the test app), the framework creates,
fresh, NSURL objects, right? It's not that there is only one
NSURL instance on the entire system per volume item, shared between all
processes, or is there? The only caching, once I release an NSURL, is at
the volume block cache level, isn't it?

Also, use
> -[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] instead
> of -[contentsOfDirectoryAtURL:includingPropertiesForKeys:options:error:]
> unless you really need an NSArray of NSURLs. If your code is just
> processing all of the URLs and has no need to keep them after processing,
> there's no reason to add them to an array (which takes time and adds to
> peak memory pressure).
>

Thanks, that makes sense.

-[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] also
> supports recursive enumeration (which stops at device boundaries -- you'll
> see mount points but not their contents) so you don't have to do that
> yourself.
>

Is that based on fts_read? Because I found that this is much faster on
local volumes (not on network vols, though) than all other ways I've tried.
And it brings along the st_dev value without time penalty, unlike
contentsOfDirectoryAtURL.

Regardless, I'll give that a try.

-- 
Thomas Tempelmann, http://apps.tempel.org/
Follow me on Twitter: https://twitter.com/tempelorg
Read my programming blog: http://blog.tempel.org/
 ___
Do not post admin requests to the list. They will be ignored.
Filesystem-dev mailing list  (Filesystem-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/filesystem-dev/archive%40mail-archive.com

This email sent to arch...@mail-archive.com


Re: readdir vs. getdirentriesattr

2019-04-29 Thread Thomas Tempelmann
Quick update:


> -[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] also
>> supports recursive enumeration (which stops at device boundaries -- you'll
>> see mount points but not their contents) so you don't have to do that
>> yourself.
>>
>
This is indeed faster than most of the other options, but, if only looking
for file names, not as fast as fts_read. When also looking at file sizes,
it's the fastest, though. Here are run times for "best case" in an APFS
volume ("/System" folder). These times come out quite similarly on repeated
runs.

*Target: /System, format: apfs*

*--- contentsOfDirectoryAtURL ---*

*3.35s, scanned: 336991, found: 520, size: 0*

*4.31s, scanned: 336991, found: 520, size: 9184548546*

*--- getattrlistbulk() ---*

*3.45s, scanned: 336991, found: 520, size: 0*

*3.50s, scanned: 336991, found: 520, size: 9184548546*

*--- readdir() ---*

*3.05s, scanned: 336991, found: 520, size: 0*

*8.04s, scanned: 336991, found: 520, size: 9184548546*

*--- fts ---*

*2.32s, scanned: 336991, found: 520, size: 0*

*2.40s, scanned: 336991, found: 520, size: 9184548546*

*--- enumeratorAtURL ---*

*1.97s, scanned: 336991, found: 520, size: 0*

*2.52s, scanned: 336991, found: 520, size: 9184548546*

The first of each test type looks for names only (and it extracts them from
the URL, not by getting it as a resource value like the code in
https://developer.apple.com/documentation/foundation/nsfilemanager/1409571-enumeratoraturl
suggests.
The second test also fetches the file size.

Note that on network volumes, readdir may be faster than the others,
though. Also depends on the server (Linux based NAS vs. macOS).

Thomas
 ___
Do not post admin requests to the list. They will be ignored.
Filesystem-dev mailing list  (Filesystem-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/filesystem-dev/archive%40mail-archive.com

This email sent to arch...@mail-archive.com


Re: readdir vs. getdirentriesattr

2019-04-29 Thread Jim Luther


> On Apr 29, 2019, at 1:19 PM, Thomas Tempelmann  wrote:
> 
> Jim,
> 
> In contentsOfDirectoryAtURL, instead of "includingPropertiesForKeys:nil", use 
> "includingPropertiesForKeys:@[NSURLVolumeIdentifierKey]" (and add whatever 
> other property keys you know you'll need). The whole purpose of the 
> includingPropertiesForKeys argument is so the enumerator code can pre-fetch 
> the properties you need as efficiently as possible. The enumeration will be a 
> bit slower, but the entire operation of enumerating and getting the 
> properties from the URLs returned will be faster.
> 
> I know. That's the theory, but my benchmarking says it makes no difference in 
> that case. And that's quite logical because the pre-caching is meant for data 
> that has to come from the lowest level, i.e. where the catalog data is 
> fetched - it makes sense to combine multiple property requests into one, just 
> like the getdirentriesattr is meant to used like. However, as I explained the 
> volume ID is not stored in the catalog but at a higher level, and therefore 
> pre-fetching this at the lowest level makes no difference, at requires no 
> catalog access, right?

The volume ID is at a higher layer, but the enumeration code attempts to 
retrieve the value less than once per URL returned. That said, if the directory 
hierarchy has few items per directory, the number of times it is retrieved will 
be higher. You can write a bug report and I'll look to see if there are ways to 
improve the performance.

In the meantime, there's something you could do to improve the performance 
(even if our code changes). You can get the volumeIdentifier for the directory 
you start enumerating from. It will be the same for the entire enumeration 
except when directories are seen on other file systems (today, that's volume 
mount points and mount triggers). Like this:

NSURL *directoryURL = [NSURL 
fileURLWithPath:@"/System/Applications/Utilities/" isDirectory:YES];
// get the volume identifier for most of the enumeration
id mainVolumeIdentifier;
[directoryURL getResourceValue: 
forKey:NSURLVolumeIdentifierKey error:nil];
NSDirectoryEnumerator *directoryEnumerator = 
[NSFileManager.defaultManager enumeratorAtURL:directoryURL 
includingPropertiesForKeys:nil options:0 errorHandler:nil];
for (NSURL *url in directoryEnumerator) {
NSNumber *isVolume;
NSNumber *isMountTrigger;
if ( ([url getResourceValue: forKey:NSURLIsVolumeKey 
error:nil] && isVolume.boolValue)
|| ([url getResourceValue: 
forKey:NSURLIsMountTriggerKey error:nil] && isMountTrigger.boolValue) ) {
// get the volume identifier for the volume or mount 
trigger
id otherVolumeIdentifier ;
[directoryURL getResourceValue: 
forKey:NSURLVolumeIdentifierKey error:nil];
}
}

> My performance tests always runs twice in fast succession, so that in the 
> second run, due to caching, all data's ready and does not incur random delays 
> that would give imprecise measurements. Sure, this does not give me the worst 
> case, but it gives me the best case results at least. And these best case 
> results say: Scanning "/System" on my Mac without getting the Volume ID takes 
> less than 3s, but with (with and without pre-fetching) getting it takes over 
> 6s. That's TWICE as much time. With smaller dir tree the difference is less, 
> possibly because then there's other caches helping.
> 
> I assume that when I re-run the scan, after having released all NSURLs from 
> the previous scan (even by restarting the test app), the framework creates, 
> fresh, NSURL objects, right? It's not that there is only one NSURL instance 
> on the entire system per volume item, shared between all processes, or is 
> there? The only caching, once I release an NSURL, is at the volume block 
> cache level, isn't it?
> 
> Also, use -[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] 
> instead of 
> -[contentsOfDirectoryAtURL:includingPropertiesForKeys:options:error:] unless 
> you really need an NSArray of NSURLs. If your code is just processing all of 
> the URLs and has no need to keep them after processing, there's no reason to 
> add them to an array (which takes time and adds to peak memory pressure).
> 
> Thanks, that makes sense.
> 
> -[enumeratorAtURL:includingPropertiesForKeys:options:errorHandler:] also 
> supports recursive enumeration (which stops at device boundaries -- you'll 
> see mount points but not their contents) so you don't have to do that 
> yourself.
> 
> Is that based on fts_read? Because I found that this is much faster on local 
> volumes (not on network vols, though) than all other ways I've tried. And it 
> brings along the st_dev value without time penalty, unlike 
> contentsOfDirectoryAtURL.

It used to be based on heavily modified fts(3). I rewrote it for Mojave 

Re: readdir vs. getdirentriesattr

2019-04-29 Thread Thomas Tempelmann
> The volume ID is at a higher layer, but the enumeration code attempts to
> retrieve the value less than once per URL returned. That said, if the
> directory hierarchy has few items per directory, the number of times it is
> retrieved will be higher. You can write a bug report and I'll look to see
> if there are ways to improve the performance.
>

As I just wrote, going with your proposed enumeratorAtURL: method takes
care of that already. I may still write a report, and will let you know if
I do.

Though I still haven't gotten to see if I can speed up recursive search by
using multiple threads for each directory read. If that helps, then I
cannot use enumeratorAtURL for that but would have to revert to classic
recursion, and which point the volumeID checking comes into play again
(but, with only checking it whenever I enter a dir, it'll be less of an
impact).


> In the meantime, there's something you could do to improve the performance
> (even if our code changes). You can get the volumeIdentifier for the
> directory you start enumerating from. It will be the same for the entire
> enumeration except when directories are seen on other file systems (today,
> that's volume mount points and mount triggers). Like this:
>

I already do that in my actual working code. I was just showing this more
inefficient way of ALWAYS getting the value in order to demonstrate its
performance impact.

It used to be based on heavily modified fts(3). I rewrote it for Mojave to
> improve the memory footprint. It uses getattrlistbulk()for everything
> except when ti sees a mount point, and then it calls getattrlist on the
> mount point path to get the attributes from the other file system's root
> directory.
>

Glad to see you're still on top of it.

Thomas
 ___
Do not post admin requests to the list. They will be ignored.
Filesystem-dev mailing list  (Filesystem-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/filesystem-dev/archive%40mail-archive.com

This email sent to arch...@mail-archive.com