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:  3 - Normal
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)
   

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 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.

     

     

     

     

    No changes have been made to this item

    Back to the top

    Powered by Savane 3.11