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
Add sort option to find
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. 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, 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." This is not a new idea. It's been in this project's TODO file in the context of updatedb since the year 2000. 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. 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. 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`. 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? 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. Please see the attached patches: [PATCH 1/3] Add find -s (sort) global option [PATCH 2/3] find: Update docs for -s (sort) [PATCH 3/3] find: Add test for sort I'll reply to this email with the patches too, and hopefully one of those options will be readable to you all. Apologies in advance if I and/or GMail mess that up. Thanks for your feedback, Diego [1] https://www.freebsd.org/cgi/man.cgi?query=find&manpath=FreeBSD+3.1-RELEASE [2] https://lists.gnu.org/archive/html/findutils-patches/2014-12/msg5.html [3] https://lists.gnu.org/archive/html/findutils-patches/2015-01/msg3.html From 882a6b0f36ae78252e1a384414a9728e07017ab7 Mon Sep 17 00:00:00 2001 From: Diego Ongaro Date: Tue, 18 Aug 2020 16:51:53 -0700 Subject: [PATCH 2/3] find: Update docs for -s (sort) --- TODO | 12 ++-- doc/find.texi | 24 ++-- find/find.1 | 12 +++- 3 files changed, 35 insertions(+), 13 deletions(-) diff --git a/TODO b/TODO index 6f0a5536..3760b7f4 100644 --- a/TODO +++ b/TODO @@ -5,16 +5,8 @@ * man page for frcode Perhaps a better description in texi pages as well. -* Add option for find to sort output in lexical order for use for updatedb [email protected] (Olivier) made the following suggestion: - -As I was running thru the code looking for the bug I wondered why the updatedb -has to use sort... -why not add an option to find that sorts the output in lexical order? -my point is: -- sort on a big list is costly (here we do locate on big big file system) -- find may (in theory) sort incrementally very easily by sorting only the current -directory entries before recursion +* Make updatedb use find -s (sort) where available, as suggested by [email protected] (Olivier) long ago. * Include example of use of updatedb in documentation. Use something close to the Debian daily cron job. diff --git a/doc/find.texi b/doc/find.texi index ce63ca52..ebc8f8ee 100644 --- a/doc/find.texi +++ b/doc/find.texi @@ -3258,7 +3258,7 @@ discussed in this manual. @section Invoking @code{find} @example -find @r{[-H] [-L] [-P] [-D @var{debugoptions}] [-O@var{level}]} @r{[}@var{file}@dots{}@r{]} @r{[}@var{expression}@r{]} +find @r{[-H] [-L] [-P] [-s] [-D @var{debugoptions}] [-O@var{level}]} @r{[}@var{file}@dots{}@r{]} @r{[}@var{expression}@r{]} @end example @code{find} searches the directory tree rooted at each file name @@ -3266,7 +3266,7 @@ find @r{[-H] [-L] [-P] [-D @var{debugoptions}] [-O@var{level}]} @r{[}@var{file}@ the tree. The command line may begin with the @samp{-H}, @samp{-L}, @samp{-P}, -@samp{-D} and @samp{-O} options. These are followed by a list of +@samp{-s}, @samp{-D} and @samp{-O} options. These are followed by a list of files or directories that should be searched. If no files to search are specified, the current directory (@file{.}) is used. @@ -3330,6 +3330,26 @@ broken), it falls back on using the properties of the symbolic link itself. @ref{Symbolic Links} for a more complete description of how symbolic links are handled. +The @samp{-s} option causes @code{find} to process files within each directory +in sorted order by name, as defined by the current locale. Without this, +@code{find} processes files in unspecified order. + +The exact ordering is determined by the @code{LC_COLLATE} setting in the +curr
