Re: Add sort option to find
All of the discussion of efficiency is useful, but after writing my assessment, I have the feeling that in practice, efficiency is not that important. In general, one is unlikely to have find generate a list of over a million files, and with modern computers, usually such a list can be sorted in RAM. I think the significant advantage is one someone else mentioned: find -s sorts the output lines by the name of the file that generated them, even when the file name is not the initial portion of the output line. Another advantage is that find -s does not produce anomalous orders if file names contain characters that sort before '/' in the collating sequence. In locale 'C', these characters are < '/': !"#$%&'()*+,-. Of those, I commonly use 3 in file names. So "find | sort" would produce: a/b a/b# a/b-x a/b.c a/b/d a/by whereas "find -s" would produce more natural grouping: a/b a/b/c a/b# a/b-x a/b.c a/by Dale
Re: Add sort option to find
On Wed, Sep 2, 2020 at 7:22 PM Dale R. Worley wrote: > > Bernhard Voelker writes: > >> As I wrote in the info page, "the -s option is more efficient than piping > >> large amounts of output of find into the sort command, [...] > > > > Why exactly is that more efficient? Which resources are saved by that? > > CPU, RAM (*), time, ...? > > "find -s" requires find to store, at any one time, the sorted entries of > all of the directories on the path above the current directory. But > "find | sort" requires the entire output of find to be stored until find > completes. In a sort-of-typical-asymptotic way the second is > exponentially larger than the first. If you made a tree of directories > containing two entries, 20 layers deep, there would be a million entries > to be sorted, but find -s would only need to keep track of 40 at any one > time. Thanks for the thorough and thoughtful feedback, Berny, and for your useful example, Dale. I meant algorithmic efficiency in my original claim, but I see how my wording was ambiguous. Intuitively, sorting names in each directory has two algorithmic wins: (1) each file must be compared with only its siblings instead of the entire directory tree, and (2) only names are compared instead of full paths. Berny's shell script example is exactly the worst-case scenario. If you put all your files in one directory, `find -s` will invoke `qsort()` only once, so that's O(N log N), just like `find | sort`. Dale's example was a much better scenario for `find -s`. In general, consider the best case of a perfectly balanced K-ary tree consisting of N total files and directories. `find -s` needs O(K logK) comparisons per directory, and there are (N - 1) / k directories. It might be cheating, but if we assume K is constant, that comes out to O(N) comparisons total. So in this best case filesystem layout, sorting each directory instead of sorting the output is a significant algorithmic win. Most real users don't have the patience to perfectly balance their filesystems. I ran some stats on my own machine to get a better sense of one real user's branching factor. Here are some basic counts: files dirs both root 252,668 22,973275,641 home 669,986 116,673786,659 both 922,654 139,646 1,062,300 And for each of the directories, how many entries they have: root home mean 12.96 6.78 std 99.47 76.36 min0.00 0.00 25%1.00 1.00 50%2.00 2.00 75%6.00 5.00 90% 18.00 11.00 99% 175.28 69.00 99.9%994.00404.00 99.99% 3060.29 1825.95 max 9184.00 21561.00 For those of you following along, this seems to be a cheap and decent approximation of the average branching factor of a directory tree: echo $(find | wc -l) / $(find -type d | wc -l) | bc -l I only have 18 directories with more than 2,000 entries. My largest is my Firefox profile (21,561 entries). The next is /var/lib/dpkg/info (9,184 entries). So based on just my own filesystem, maybe something in the ballpark of N=1M and K=10 is a reasonable guess for real world users. I think that's encouraging. I also counted the actual number of calls to the compare() function with `find -s`. It varies a little from run to run, but here's an example: comparisons total files comparisons/files root1,466,827 275,641 5.32 home3,342,447 786,659 4.25 both4,809,3471,062,300 4.53 That, too, is encouraging: we only need about 5 string comparisons per file to sort my entire filesystem, and I wouldn't expect that number to grow much for larger filesystems. Here's the equivalent table for `find | sort`: comparisons total files comparisons/files root4,049,248 275,641 14.69 home 11,254,537 786,659 14.30 both 15,349,9171,062,300 14.45 It needs many more comparisons even at this scale, and I'd expect it to scale more poorly with larger filesystems. I also looked at path lengths vs name lengths. All these numbers are averages: len(path) len(name) len(path)-len(name) len(name)/len(path) root 54.39 16.0838.31 0.30 home 99.32 17.8681.46 0.18 So we might see significant wins just by comparing names instead of paths, especially when doing more expensive Unicode comparisons. I think that summarizes why we might expect `find -s` to be algorithmically faster than `find | sort` for typical users, and that's probably enough for tonight. I'll follow up soon with another little patch and some benchmark results to demonstrate how this plays out in practice. Spoiler: FTS_DEFER_STAT makes a big difference when using a compare function. -Diego
Re: Add sort option to find
Bernhard Voelker writes: >> As I wrote in the info page, "the -s option is more efficient than piping >> large amounts of output of find into the sort command, [...] > > Why exactly is that more efficient? Which resources are saved by that? > CPU, RAM (*), time, ...? "find -s" requires find to store, at any one time, the sorted entries of all of the directories on the path above the current directory. But "find | sort" requires the entire output of find to be stored until find completes. In a sort-of-typical-asymptotic way the second is exponentially larger than the first. If you made a tree of directories containing two entries, 20 layers deep, there would be a million entries to be sorted, but find -s would only need to keep track of 40 at any one time. Dale
Re: Add sort option to find
On 2020-08-19 02:48, Diego Ongaro wrote:
> Hi,
>
> Long time user, first time GNU contributor (I think). I'm submitting patches
> to add a sort option to find. It will cause find to sort files by name within
> each directory before processing them.
Thanks for the patch.
This is the kind of material which is perfect as a start for a discussion
on a concrete matter.
FWIW:
If we decide to incorporate this patch, then this is a non-trivial change
which requires to undergo the copyright assignment process to GNU.
> As I wrote in the info page, "the -s option is more efficient than piping
> large amounts of output of find into the sort command, [...]
Why exactly is that more efficient? Which resources are saved by that?
CPU, RAM (*), time, ...?
(*) see tests below.
> [...] and it produces output
> incrementally rather than buffering it all. It's also more convenient when
> the output of a find command isn't line-oriented or the lines don't start
> with the filenames."
Indeed, it is a convenience option for the user.
> This is not a new idea. It's been in this project's TODO file in the context
> of updatedb since the year 2000.
If something stays in a TODO for such a long time, then it's worth
re-considering
again whether the feature is worthwhile nowadays or not.
I don't see why using the specialized 'sort' in 'updatedb' would be wrong.
> FreeBSD has included the -s flag in its man
> page for find since FreeBSD 3.1 [1], which was released in 1999. Mac OS X
> picked it up from FreeBSD.
Ha, that is a good argument: existing implementations:
- FreeBSD:
https://www.freebsd.org/cgi/man.cgi?find(1)
- NetBSD:
https://netbsd.gw.com/cgi-bin/man-cgi?find++NetBSD-current
- OSX (not sure if this is the "official" source):
https://ss64.com/osx/find.html
Some systems where 'find' does not have -s:
- OpenBSD does not have -s:
https://man.openbsd.org/find.1
- Solaris 10:
https://docs.oracle.com/cd/E26505_01/html/816-5165/find-1.html
- Solaris 11.4:
https://docs.oracle.com/cd/E88353_01/html/E37839/find-1.html
> Sorting has also been proposed previously on this mailing list. Phil Miller
> submitted a patch in 2014 that used `-sort` as a predicate [2][3]. After some
> discussion about sorting directories by inode, Phil's proposal appears to
> have fallen through.
As far as I remember, there have been several kind of requirements for sorting.
Mainly, there have been discussions about sorting the output. This is a
completely
different matter than having a sorted order of processing in each directory.
> My proposal uses `-s` as a global option instead of Phil's `-sort` predicate.
> The advantages of `-s` are (a) compatibility with BSD and Mac OS X and
> (b) allowing users to easily create a shell alias for `find -s`.
According to the manuals of the existing implementations, the behavior in
the patch seems to be identical, and therefore seemingly giving compatibility.
> One thing I didn't do is update the `oldfind` command to respect `-s`. It
> looked like that would require a non-trivial change. Is `oldfind` still used?
'oldfind' only exists as ancient reference implementation.
It is not installed anymore, but only used in the tests.
> Another thing is I didn't do is update the `updatedb.sh` script to take
> advantage of `find -s`. I wanted to see if this change would be accepted
> first. I also wasn't sure if testing for `find -s` should happen at
> build-time (like `sort -z`) or at run-time.
Fine, one step after the other.
> Please see the attached patches:
>
> [PATCH 1/3] Add find -s (sort) global option
[Patch discussed inline here.]
> diff --git a/find/ftsfind.c b/find/ftsfind.c
> index 783148c5..aa27666c 100644
> --- a/find/ftsfind.c
> +++ b/find/ftsfind.c
> @@ -34,6 +34,7 @@
> #include
> #include
> #include
> +#include
> #include
> #include
>
> @@ -514,6 +515,10 @@ consider_visiting (FTS *p, FTSENT *ent)
> }
> }
>
> +static int compare(FTSENT const **a, FTSENT const **b) {
> + assert ((*a)->fts_parent == (*b)->fts_parent);
> + return strcoll((*a)->fts_name, (*b)->fts_name);
> +}
strcoll may fail in some locales, see `man 3p strcoll`:
RETURN VALUE
[...]
On error, strcoll() may set errno, but no return value is reserved
to indicate an error.
and
ERRORS
These functions may fail if:
EINVAL The s1 or s2 arguments contain characters outside the domain of
the collating sequence.
I would assume this could easily be triggered with some strange file names.
So that would have to be handled, e.g. by a fallback to 'strcmp'.
Anyway, the code has to ensure that 'errno' does not clobber later/other
processing.
> @@ -547,7 +552,7 @@ find (char *arg)
>if (options.stay_on_filesystem)
> ftsoptions |= FTS_XDEV;
>
> - p = fts_open (arglist, ftsoptions, NULL);
> + p = fts_open (arglist, ftsoptions, options.sort ? compare : NULL);
It is nice that it uses existing functionality in gnulib's FTS implementation.
OTOH this effectively defea
Re: Add sort option to find
On Tue, Aug 18, 2020 at 7:11 PM Dale R. Worley wrote:
>
> How does sorting interact with localization? By default, I'd expect
> find -s to sort a directory the same way that ls does.
It's using strcoll internally, so it respects LC_COLLATE. With my home
directory of about 690K files, I get the same order as `/bin/ls -A` for both
LC_ALL=C and LC_ALL=en_us.UTF-8. Here's the imperfect script I used to test
that:
myfind -s ~ > find.txt
myls() {
/bin/ls -A "$1" | while read file; do
echo "$1/$file"
if [ ! -h "$1/$file" ] && [ -d "$1/$file" ]; then
myls "$1/$file"
fi
done
}
(echo ~; myls ~) > ls.txt
diff find.txt ls.txt
-Diego
Re: Add sort option to find
Very interesting! I can see that making sorting a global option makes a lot of sense. How does sorting interact with localization? By default, I'd expect find -s to sort a directory the same way that ls does. Dale
