bugfindutils - Bugs: bug #54860, Less performance of -execdir echo...

 
 

bug #54860: Less performance of -execdir echo {} +

Submitter:  Ahmad ElKomey <ahmad_elkomey>
Submitted:  Wed 17 Oct 2018 10:31:41 PM UTC
   
 
Category:  find Severity:  1 - Wish
Item Group:  None Status:  None
Privacy:  Public Assigned to:  berny
Originator Name:  Open/Closed:  Open
Release:  None Fixed Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 23 Oct 2018 10:18:32 PM UTC, comment #7: 

Ha, it's the directory order which plays into the game!
That means, 'dir-2/another' has been created later than 'dir-2/dir-4':


mkdir -pv dir dir-2 dir-3/dir-{4,5}   \
  && touch dir/{bar,one}.c dir-2/file dir-2/foo.c dir-3/dir-4/file
           dir-3/dir-5/file dir-3/file file \
  && mkdir dir-2/dir-4 dir-2/dir-5 \
  && touch dir-2/another.c \
  && touch dir-2/dir-4/file dir-2/dir-5/file


The underlying system call 'getdents' returns the directory entries of 'dir-2'
un-ordered, i.e., not sorted alphabetically but usually in the order of
creation:


getdents(6, [{d_ino=90672, d_off=1, d_reclen=24, d_name=".", d_type=DT_DIR},
             {d_ino=91825, d_off=2, d_reclen=24, d_name="..", d_type=DT_DIR},
             {d_ino=92462, d_off=3, d_reclen=32, d_name="another.c", d_type=DT_REG},
             {d_ino=90677, d_off=4, d_reclen=32, d_name="dir-5", d_type=DT_DIR},
             {d_ino=90676, d_off=5, d_reclen=32, d_name="dir-4", d_type=DT_DIR},
             {d_ino=91934, d_off=6, d_reclen=32, d_name="foo.c", d_type=DT_REG},
             {d_ino=91933, d_off=7, d_reclen=24, d_name="file", d_type=DT_REG}], 32768) = 200

find will process all entries exactly in that order, and between 'another.c'
and 'foo.c' it processes the subdirectories dir-5 and dir-4.  As it has
changed directory in between (internally), 'foo.c' is processed in its
own -execdir run.

There is also a comment on this in the code:

/* If we changed level, perform any outstanding
 * execdirs.  If we see a sequence of directory entries
 * like this: fffdfffdfff, we could build a command line
 * of 9 files, but this simple-minded implementation
 * builds a command line for only 3 files at a time
 * (since fts descends into the directories).
 */


After all, find works as intended (by the implementation).
I'm therefore marking the severity as 'wishlist'.

Of course, we can continue the discussion, and maybe someone (even me?)
may propose a patch to improve things.

The problem in that is that the whole point about using gnulib's FTS module
is that we don't have to care whether a directory has 2 entries or
4 million; in the latter case (or even larger directories) sorting is not
possible anymore.

Bernhard Voelker <berny>
Group administrator
Tue 23 Oct 2018 11:20:15 AM UTC, comment #6: 

I ran the same command you posted:


find -D search,exec -iname "*c" -execdir echo '{}' + 2>&1 | grep -E 'dir-2|exec'


And I got the following:


consider_visiting (early): './dir-2': fts_info=FTS_D , fts_level= 1, prev_depth=1 fts_path='./dir-2', fts_accpath='dir-2'
consider_visiting (late): './dir-2': fts_info=FTS_D , isdir=1 ignore=0 have_stat=1 have_type=1
consider_visiting (early): './dir-2/foo.c': fts_info=FTS_NSOK, fts_level= 2, prev_depth=1 fts_path='./dir-2/foo.c', fts_accpath='foo.c'
consider_visiting (late): './dir-2/foo.c': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/file': fts_info=FTS_NSOK, fts_level= 2, prev_depth=2 fts_path='./dir-2/file', fts_accpath='file'
consider_visiting (late): './dir-2/file': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-4': fts_info=FTS_D , fts_level= 2, prev_depth=2 fts_path='./dir-2/dir-4', fts_accpath='dir-4'
consider_visiting (late): './dir-2/dir-4': fts_info=FTS_D , isdir=1 ignore=0 have_stat=1 have_type=1
Outstanding execdirs:-execdir multiple 2 args: echo ./foo.c
consider_visiting (early): './dir-2/dir-4/file': fts_info=FTS_NSOK, fts_level= 3, prev_depth=2 fts_path='./dir-2/dir-4/file', fts_accpath='file'
consider_visiting (late): './dir-2/dir-4/file': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-4': fts_info=FTS_DP, fts_level= 2, prev_depth=3 fts_path='./dir-2/dir-4', fts_accpath='dir-4'
consider_visiting (late): './dir-2/dir-4': fts_info=FTS_DP, isdir=1 ignore=1 have_stat=1 have_type=1
consider_visiting (early): './dir-2/another.c': fts_info=FTS_NSOK, fts_level= 2, prev_depth=2 fts_path='./dir-2/another.c', fts_accpath='another.c'
consider_visiting (late): './dir-2/another.c': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-5': fts_info=FTS_D , fts_level= 2, prev_depth=2 fts_path='./dir-2/dir-5', fts_accpath='dir-5'
consider_visiting (late): './dir-2/dir-5': fts_info=FTS_D , isdir=1 ignore=0 have_stat=1 have_type=1
Outstanding execdirs:-execdir multiple 2 args: echo ./another.c
consider_visiting (early): './dir-2/dir-5/file': fts_info=FTS_NSOK, fts_level= 3, prev_depth=2 fts_path='./dir-2/dir-5/file', fts_accpath='file'
consider_visiting (late): './dir-2/dir-5/file': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-5': fts_info=FTS_DP, fts_level= 2, prev_depth=3 fts_path='./dir-2/dir-5', fts_accpath='dir-5'
consider_visiting (late): './dir-2/dir-5': fts_info=FTS_DP, isdir=1 ignore=1 have_stat=1 have_type=1
consider_visiting (early): './dir-2': fts_info=FTS_DP, fts_level= 1, prev_depth=2 fts_path='./dir-2', fts_accpath='dir-2'
consider_visiting (late): './dir-2': fts_info=FTS_DP, isdir=1 ignore=1 have_stat=1 have_type=1
Outstanding execdirs:-execdir multiple 3 args: echo ./bar.c ./one.c


If you sort both outputs (yours and mine), you get the difference as follows:


- marks yours
+ marks mine

- Outstanding execdirs:-execdir multiple 3 args: echo ./foo.c ./another.c
- Outstanding execdirs:-execdir multiple 3 args: echo ./one.c ./bar.c
+ Outstanding execdirs:-execdir multiple 2 args: echo ./another.c
+ Outstanding execdirs:-execdir multiple 2 args: echo ./foo.c
+ Outstanding execdirs:-execdir multiple 3 args: echo ./bar.c ./one.c


Ahmad ElKomey <ahmad_elkomey>
Mon 22 Oct 2018 08:57:27 PM UTC, comment #5: 

Thanks for the tests.
I'm running openSUSE:Tumbleweed, and I'm using ext4.
Maybe the underlying file system returns the information to the
FTS implementation in gnulib in chunks.

With "-execdir CMD '{}' +", you cannot guarantee that only one
process of CMD is spawned ... due to the maximum command line
length, but in such a small directory, the number of processes
should be deterministic, i.e., 1.

Before going on system call level, this is what I get with the
debug options 'exec,search' enabled (this time on a 'tmpfs' in /dev/shm
which obviously doesn't matter):

$ find -D search,exec -iname "*c" -execdir echo '{}' + 2>&1 | grep -E 'dir-2|exec'
consider_visiting (early): './dir-2': fts_info=FTS_D , fts_level= 1, prev_depth=1 fts_path='./dir-2', fts_accpath='dir-2'
consider_visiting (late): './dir-2': fts_info=FTS_D , isdir=1 ignore=0 have_stat=1 have_type=1
consider_visiting (early): './dir-2/foo.c': fts_info=FTS_NSOK, fts_level= 2, prev_depth=1 fts_path='./dir-2/foo.c', fts_accpath='foo.c'
consider_visiting (late): './dir-2/foo.c': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/file': fts_info=FTS_NSOK, fts_level= 2, prev_depth=2 fts_path='./dir-2/file', fts_accpath='file'
consider_visiting (late): './dir-2/file': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/another.c': fts_info=FTS_NSOK, fts_level= 2, prev_depth=2 fts_path='./dir-2/another.c', fts_accpath='another.c'
consider_visiting (late): './dir-2/another.c': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-5': fts_info=FTS_D , fts_level= 2, prev_depth=2 fts_path='./dir-2/dir-5', fts_accpath='dir-5'
consider_visiting (late): './dir-2/dir-5': fts_info=FTS_D , isdir=1 ignore=0 have_stat=1 have_type=1
Outstanding execdirs:-execdir multiple 3 args: echo ./foo.c ./another.c
consider_visiting (early): './dir-2/dir-5/file': fts_info=FTS_NSOK, fts_level= 3, prev_depth=2 fts_path='./dir-2/dir-5/file', fts_accpath='file'
consider_visiting (late): './dir-2/dir-5/file': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-5': fts_info=FTS_DP, fts_level= 2, prev_depth=3 fts_path='./dir-2/dir-5', fts_accpath='dir-5'
consider_visiting (late): './dir-2/dir-5': fts_info=FTS_DP, isdir=1 ignore=1 have_stat=1 have_type=1
consider_visiting (early): './dir-2/dir-4': fts_info=FTS_D , fts_level= 2, prev_depth=2 fts_path='./dir-2/dir-4', fts_accpath='dir-4'
consider_visiting (late): './dir-2/dir-4': fts_info=FTS_D , isdir=1 ignore=0 have_stat=1 have_type=1
consider_visiting (early): './dir-2/dir-4/file': fts_info=FTS_NSOK, fts_level= 3, prev_depth=2 fts_path='./dir-2/dir-4/file', fts_accpath='file'
consider_visiting (late): './dir-2/dir-4/file': fts_info=FTS_NSOK, isdir=0 ignore=0 have_stat=0 have_type=1
consider_visiting (early): './dir-2/dir-4': fts_info=FTS_DP, fts_level= 2, prev_depth=3 fts_path='./dir-2/dir-4', fts_accpath='dir-4'
consider_visiting (late): './dir-2/dir-4': fts_info=FTS_DP, isdir=1 ignore=1 have_stat=1 have_type=1
consider_visiting (early): './dir-2': fts_info=FTS_DP, fts_level= 1, prev_depth=2 fts_path='./dir-2', fts_accpath='dir-2'
consider_visiting (late): './dir-2': fts_info=FTS_DP, isdir=1 ignore=1 have_stat=1 have_type=1
Outstanding execdirs:-execdir multiple 3 args: echo ./one.c ./bar.c

Bernhard Voelker <berny>
Group administrator
Sat 20 Oct 2018 04:44:02 PM UTC, comment #4: 

I tried it on Ubuntu 16.04 LTS with find 4.7.0-git. Also tried it on CentOS 6.5 with find 4.4.2.

Both produced the same result I posted earlier.

Ahmad ElKomey <ahmad_elkomey>
Sat 20 Oct 2018 03:37:03 PM UTC, comment #3: 

I ran the command you posted to build the tree structure, downloaded this (findutils version 4.6.0) and built the applications (./configure && make).

I had the same results as the one posted in my original post.
Am I missing something here?

Ahmad ElKomey <ahmad_elkomey>
Sat 20 Oct 2018 01:15:05 PM UTC, comment #2: 

I'm using "less performance" because, as per the result I get, it is going to the same directory more than once. It should change directory once per directory (as it is with your case).

It's interesting that I have a bit different result than yours. I checked the tree structure you used and it is the same as mine.

I find it strange that I have version find (GNU findutils) 4.7.0-git installed while the latest version here is findutils-4.6.0.tar.gz.
Does this mean I don't have the most recent official version?

Thank you for your time. And please excuse my English. I'm not an English native speaker. I also appreciate your patience; as I am new to the GNU and FOSS world.

Ahmad ElKomey <ahmad_elkomey>
Thu 18 Oct 2018 11:01:38 AM UTC, comment #1: 

First of all, I don't understand why the bug report would be related to
"less performance".  Could you explain, please?

Then, these are the commands to create the tree structure you said:

$ mkdir -pv dir dir-2/dir-4 dir-2/dir-5 dir-3/dir-{4,5} \
  && touch dir/{bar,one}.c dir-2/another.c dir-2/dir-4/file \
       dir-2/dir-5/file dir-2/file dir-2/foo.c dir-3/dir-4/file \
       dir-3/dir-5/file dir-3/file file


This is what I get:

../find/find -iname "*c" -execdir echo '{}' +
./another.c ./foo.c
./one.c ./bar.c


I use latest git:

../find/find --version | sed 1q
find (GNU findutils) 4.6.0.191-0130


That said, I cannot reproduce your result, neither with latest
git version nor with the stable 4.6.0 release.  I don't see any
changes regarding -execdir since 4.6.0, maybe there was a change
in underlying gnulib, but I doubt it.
What is your environment?

Bernhard Voelker <berny>
Group administrator
Wed 17 Oct 2018 10:31:41 PM UTC, original submission:  

I have this directory structure with some trivial files
.
├── dir
│   ├── bar.c
│   └── one.c
├── dir-2
│   ├── another.c
│   ├── dir-4
│   │   └── file
│   ├── dir-5
│   │   └── file
│   ├── file
│   └── foo.c
├── dir-3
│   ├── dir-4
│   │   └── file
│   ├── dir-5
│   │   └── file
│   └── file
└── file

7 directories, 11 files

Running the command:

find -iname "*c" -exec echo '{}' +

returns

./dir-2/foo.c ./dir-2/another.c ./dir/bar.c ./dir/one.c

which is as expected.

But when I run:

find -iname "*c" -execdir echo '{}' +

it returns

./foo.c
./another.c
./bar.c ./one.c


And I was expecting

./foo.c ./another.c
./bar.c ./one.c


I'm using find (GNU findutils) 4.7.0-git

Ahmad ElKomey <ahmad_elkomey>

 

(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 ahmad_elkomey (Submitted the item)
  • -email is unavailable- added by ahmad_elkomey (-execdir performance enhancement)
  • -email is unavailable- added by ahmad_elkomey (-execdir performance enhancement)
  •  

    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.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-10-23 berny Severity3 - Normal 1 - Wish
    2018-10-18 berny Assigned toNone berny
    2018-10-17 ahmad_elkomey Carbon-Copy- Added -email is unavailable-
        Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code