bugfindutils - Bugs: bug #58197, "find" fails to optimize...

 
 

bug #58197: "find" fails to optimize "-path /usr/foo -o -path /usr/bar" to "-regex '/usr/\(foo\|bar\)'"

Submitter:  None
Submitted:  Fri 17 Apr 2020 04:26:34 PM UTC
   
 
Category:  find Severity:  1 - Wish
Item Group:  None Status:  None
Privacy:  Public Assigned to:  None
Originator Name:  Askar Safin Originator Email:  -email is unavailable-
Open/Closed:  Open Release:  4.7.0
Fixed Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Fri 21 Jul 2023 10:57:55 AM UTC, comment #5: 

regex-opt only works for fixed strings. If you have further Emacs-specific ideas you can reply to https://debbugs.gnu.org/cgi/bugreport.cgi?bug=64735 let's try to keep this thread for strategies that would work for any find user.

 Spencer Baugh <sbaugh>
Fri 21 Jul 2023 07:02:18 AM UTC, comment #4: 

I think for rgrep the most obvious improvement is to use the existing Emacs LISP function regex-opt on the list of extensions to generate a more efficient find command-line.

 James Youngman <jay>
Group administrator
Wed 19 Jul 2023 08:52:01 PM UTC, comment #3: 

One use case is GNU Emacs which heavily uses find, for example in M-x rgrep.  Emacs often constructs find commands which look like this by default:

find -H . \( -path \*/SCCS/\* -o -path \*/RCS/\* -o -path \*/CVS/\* -o -path \*/MCVS/\* -o -path \*/.src/\* -o -path \*/.svn/\* -o -path \*/.git/\* -o -path \*/.hg/\* -o -path \*/.bzr/\* -o -path \*/_MTN/\* -o -path \*/_darcs/\* -o -path \*/\{arch\}/\* -o -path \*/.\#\* -o -path \*.o -o -path \*\~ -o -path \*.bin -o -path \*.lbin -o -path \*.so -o -path \*.a -o -path \*.ln -o -path \*.blg -o -path \*.bbl -o -path \*.elc -o -path \*.lof -o -path \*.glo -o -path \*.idx -o -path \*.lot -o -path \*.fmt -o -path \*.tfm -o -path \*.class -o -path \*.fas -o -path \*.lib -o -path \*.mem -o -path \*.x86f -o -path \*.sparcf -o -path \*.dfsl -o -path \*.pfsl -o -path \*.d64fsl -o -path \*.p64fsl -o -path \*.lx64fsl -o -path \*.lx32fsl -o -path \*.dx64fsl -o -path \*.dx32fsl -o -path \*.fx64fsl -o -path \*.fx32fsl -o -path \*.sx64fsl -o -path \*.sx32fsl -o -path \*.wx64fsl -o -path \*.wx32fsl -o -path \*.fasl -o -path \*.ufsl -o -path \*.fsl -o -path \*.dxl -o -path \*.lo -o -path \*.la -o -path \*.gmo -o -path \*.mo -o -path \*.toc -o -path \*.aux -o -path \*.cp -o -path \*.fn -o -path \*.ky -o -path \*.pg -o -path \*.tp -o -path \*.vr -o -path \*.cps -o -path \*.fns -o -path \*.kys -o -path \*.pgs -o -path \*.tps -o -path \*.vrs -o -path \*.pyc -o -path \*.pyo \) -prune -o  -type f  -print0

That is, it lists a bunch of file extensions to ignore (from grep-find-ignored-files) and passes them to find.

Because find does not optimize this, the list of file extensions completely dominates the cost of the find execution; on my system, running a find over a particularly common directory, going from the full set of ignores to just one takes the find execution time from:

real 0m7.807s
user 0m7.505s
sys 0m0.359s

to:

real 0m0.491s
user 0m0.221s
sys 0m0.293s

Could you reconsider optimizing this case?

If not, how should Emacs be invoking find instead?  Should we optimize this into a single regex before passing it to find?  That is a bit worse user experience, because we provide the ability to edit the find invocation, but it may be worth it for speed improvements.

Spencer Baugh <sbaugh>
Wed 18 May 2022 06:27:35 AM UTC, comment #2: 

The main point about the optimizer in find(1) is to avoid
costly activities when cheap ones can already rule out that
the current item has to be processed further.
Costly activities are e.g. extra stat() calls.
Cheap activities are evaluating conditions in CPU like -name;
i.e., no further OS call is required.

Therefore "-path ... -o -path ..." is considered about as
expensive as "-regex ...|..." when comparing the things requiring
an extra stat() which is by magnitudes slower than -path
processing in memory.

Although -path appears more times in the expression tree
(or be it other more expensive conditions like -size which
really need an extra stat()), once `find` has the information
for an item, that will be used for the evaluation of the next
condition.  E.g. "-size -1000c -size -999c" will only lead to
one stat() invocation.

Re. the below 2 examples: I've also run both commands here,
and already after a couple of runs of each they are almost at
the same time ... here even the -regex takes 1.22s while the one
with 2x -path needs 1.16s.
Therefore, changing this would be over-optimization just compli-
cating the code further.

BTW: the optimizer in `find` is already too tricky and doesn't
consider some side effects of doing things earlier than specified
by the user on the command line.
It was already discussed to remove at least parts of the optimiser
(arm-swapping) and to adhere the left-to-right rule of POSIX again.

 Bernhard Voelker <berny>
Group administrator
Wed 18 May 2022 02:46:09 AM UTC, comment #1: 

$find ... -regex ".. | .."
$find ... -path.. -o -path ..
they are not the same in the expression tree.

$find -D tree ...
As we can see from the result of this command, -regex on a leaf alone, two -path on two leaves. While searching for files, every leaf will be applied, so I think it is reasonable to spend more time...that's just my opinion

 Shuiqing Zhou <zhoushuiqing>
Fri 17 Apr 2020 04:26:34 PM UTC, original submission:  

I often search my home directory using command similar to this:

find -O3 -L /home/user '(' -path ... -o -path ... -o -name ... -o -name ... -o lots-of-other-paths-i-want-to-skip.......... ')' -prune -o -print | xargs grep ...

So performance of this command is very important for me. Today I discovered this: if I replace pattern "-path ... -o -path ..." with single "-regex" option, that "find" command starts to work faster. Here is minimal reproducer on my system:

user@comp:~$ time -p find -O3 -L /usr '(' -path /usr/foo -o -path /usr/bar ')' -prune -o -print > /dev/null
find: File system loop detected; ‘/usr/bin/X11’ is part of the same file system loop as ‘/usr/bin’.
find: File system loop detected; ‘/usr/lib/llvm-11/build/Debug+Asserts’ is part of the same file system loop as ‘/usr/lib/llvm-11’.
find: File system loop detected; ‘/usr/lib/llvm-11/build/Release’ is part of the same file system loop as ‘/usr/lib/llvm-11’.
find: ‘/usr/lib/ssl/private’: Permission denied
find: ‘/usr/lib/chromium/extensions’: Permission denied
real 1,47
user 0,64
sys 0,82
user@comp:~$ time -p find -O3 -L /usr -regextype grep '(' -regex '/usr/\(bar\|foo\)' ')' -prune -o -print > /dev/null
find: File system loop detected; ‘/usr/bin/X11’ is part of the same file system loop as ‘/usr/bin’.
find: File system loop detected; ‘/usr/lib/llvm-11/build/Debug+Asserts’ is part of the same file system loop as ‘/usr/lib/llvm-11’.
find: File system loop detected; ‘/usr/lib/llvm-11/build/Release’ is part of the same file system loop as ‘/usr/lib/llvm-11’.
find: ‘/usr/lib/ssl/private’: Permission denied
find: ‘/usr/lib/chromium/extensions’: Permission denied
real 1,36
user 0,51
sys 0,84

I don't have dirs /usr/bar and /usr/foo on my system, but still I see substantial speed improvement.

I run both commands on already warm caches, i. e. I already run full find command just before time measurement. I have SSD disks with ext4.

So, "find -O3" is unable to optimize multiple -path options to single -regex option. And this is bad. I don't want to manually replace -path options in my commands, I want "find" to optimize everything.

Steps to reproduce: above
What I see: "1,47" is more than "1,36"
What I expected to see: first command should be as fast as second one

I use Debian Stretch. find --version:

find (GNU findutils) 4.7.0-git
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Eric B. Decker, James Youngman, and Kevin Dalley.
Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS(FTS_CWDFD) CBO(level=2)

 Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jay (Posted a comment)
  • -email is unavailable- added by sbaugh (Posted a comment)
  • -email is unavailable- added by berny (Posted a comment)
  • -email is unavailable- added by zhoushuiqing (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)

    •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2024-05-19 jay Severity3 - Normal 1 - Wish

    Back to the top

    Copyright © 2024 Free Software Foundation, Inc.
    Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
    The Levitating, Meditating, Flute-playing Gnu logo is a GNU GPL'ed image provided by the Nevrax Design Team.
    Page source code

    Powered by Savane 3.13-72d9.
    Corresponding source code