15

It seems like find would have to check whether a given path corresponds to a file or directory anyway in order to recursively walk the contents of directories.

Here's some motivation and what I've done locally to convince myself that find . -type f really is slower than find .. I haven't dug into the GNU find source code yet.

So I'm backing up some of the files in my $HOME/Workspace directory, and excluding files that are either dependencies of my projects or version control files.

So I ran the following command which executed quickly

% find Workspace/ | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > ws-files-and-dirs.txt

find piped to grep may be bad form, but it seemed like the most direct way to use a negated regex filter.

The following command includes only files in the output of find and took noticeably longer.

% find Workspace/ -type f | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > ws-files-only.txt

I wrote some code to test the performance of these two commands (with dash and tcsh, just to rule out any effects the shell might have, even though there shouldn't be any). The tcsh results have been omitted because they're essentially the same.

The results I got showed about a 10% performance penalty for -type f

Here's the output of the program showing the amount of time taken to execute 1000 iterations of various commands.

% perl tester.pl
/bin/sh -c find Workspace/ >/dev/null
82.986582

/bin/sh -c find Workspace/ | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null
90.313318

/bin/sh -c find Workspace/ -type f >/dev/null
102.882118

/bin/sh -c find Workspace/ -type f | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null

109.872865

Tested with

% find --version
find (GNU findutils) 4.4.2
Copyright (C) 2007 Free Software Foundation, Inc.

On Ubuntu 15.10

Here's the perl script I used for benchmarking

#!/usr/bin/env perl
use strict;
use warnings;
use Time::HiRes qw[gettimeofday tv_interval];

my $max_iterations = 1000;

my $find_everything_no_grep = <<'EOF';
find Workspace/ >/dev/null
EOF

my $find_everything = <<'EOF';
find Workspace/ | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null
EOF

my $find_just_file_no_grep = <<'EOF';
find Workspace/ -type f >/dev/null
EOF

my $find_just_file = <<'EOF';
find Workspace/ -type f | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null
EOF

my @finds = ($find_everything_no_grep, $find_everything,
    $find_just_file_no_grep, $find_just_file);

sub time_command {
    my @args = @_;
    my $start = [gettimeofday()];
    for my $x (1 .. $max_iterations) {
        system(@args);
    }
    return tv_interval($start);
}

for my $shell (["/bin/sh", '-c']) {
    for my $command (@finds) {
        print "@$shell $command";
        printf "%s\n\n", time_command(@$shell, $command);
    }
}
  • 2
    It seems like find would have to check whether a given path corresponds to a file or directory anyway in order to recursively walk the contents of directories. - it would have to check if it's a directory, it would not have to check whether it is a file. There are other entry types: named pipes, symbolic links, block special devices, sockets... So although it may have done the check already to see if it's a directory, it doesn't mean it knows whether it's a regular file. – RealSkeptic May 1 '16 at 19:38
  • busybox find, applied to random directory with 4,3k dirs and 2,8k files run same time with -type f and without it. But at first time Linux kernel loaded it into cache and very first find was slower. – user140866 May 1 '16 at 23:00
  • 1
    My first guess was that the -type f option caused find to call stat() or fstat() or whatever in order to find out if the file name corresponded to a file, a directory, a symlink, etc etc. I did an strace on a find . and a find . -type f and the trace was almost identical, differing only in the write() calls that had directory names in them. So, I don't know, but I want to know the answer. – Bruce Ediger May 1 '16 at 23:05
  • 1
    Not really an answer to your question, but there's a time builtin command to see how long a command takes to execute, you didn't really need to write a custom script to test. – Elronnd May 2 '16 at 1:49
16

GNU find has an optimization which can be applied to find . but not to find . -type f: if it knows that none of the remaining entries in a directory are directories, then it doesn't bother to determine the file type (with the stat system call) unless one of the search criteria requires it. Calling stat can take measurable time since the information is typically in the inode, in a separate location on the disk, rather than in the containing directory.

How does it know? Because the link count on a directory indicates how many subdirectories it has. On typical Unix filesystems, a directory's link count is 2 plus the number of directories: one for the directory's entry in its parent, one for the . entry, and one for the .. entry in each subdirectory.

The -noleaf option tells find not to apply this optimization. This is useful if find is invoked on some filesystem where directory link counts don't follow the Unix convention.

  • Is this still pertinent? Looking at the find source, it simply uses the fts_open() and fts_read() calls nowadays. – RealSkeptic May 2 '16 at 9:28
  • @RealSkeptic Has this changed in recent versions? I haven't checked the source, but experimentally, version 4.4.2 in Debian stable does optimize stat calls when it doesn't need them due to directory link counts, and the -noleaf option is documented in the manual. – Gilles May 2 '16 at 10:07
  • It optimizes stat even in the fts... version - it passes the appropriate flag for that to the fts_open call. But what I am not sure is still pertinent is the check with the number of links. It checks instead whether the returned fts record has one of the "directory" flags. It may be that fts_read itself checks the links to set that flag, but find doesn't. You can see whether your version relies on fts by calling find --version. – RealSkeptic May 2 '16 at 10:13
  • @Gilles, Would find theoretically be able to determine when all the all of the entries in a directory are directories too and use that information? – Gregory Nisbet May 2 '16 at 17:59
  • @GregoryNisbet In theory yes, but the source code (I've now checked) doesn't do that, presumably because it's a much rarer case. – Gilles May 2 '16 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.