Por que 'encontrar. tipo f 'demora mais que' encontrar '?

Question

Parece que find teria que verificar se um determinado caminho corresponde a um arquivo ou diretório de qualquer maneira para percorrer recursivamente o conteúdo dos diretórios.

Aqui estão algumas motivações e o que eu fiz localmente para me convencer de que find . -type f é realmente mais lento que find . . Eu ainda não pesquisei o código fonte do GNU find.

Por isso, estou fazendo backup de alguns arquivos no diretório $HOME/Workspace e excluindo arquivos que são dependências de meus projetos ou arquivos de controle de versão.

Então eu corri o seguinte comando que executou rapidamente

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

find canalizado para grep pode estar em má forma, mas parecia ser a maneira mais direta de usar um filtro regex negado.

O seguinte comando inclui apenas arquivos na saída do find e demorou muito mais tempo.

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

Eu escrevi algum código para testar o desempenho desses dois comandos (com dash e tcsh , apenas para excluir quaisquer efeitos que o shell possa ter, mesmo que não haja nenhum). Os resultados tcsh foram omitidos porque são essencialmente os mesmos.

Os resultados que obtive mostraram uma penalidade de desempenho de 10% por -type f

Aqui está a saída do programa que mostra o tempo gasto para executar 1000 iterações de vários comandos.

% 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

Testado com

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

No Ubuntu 15.10

Aqui está o script perl que eu usei para 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);
    }
}

    

Answer 1

O GNU find tem uma otimização que pode ser aplicada a find . , mas não a find . -type f : se souber que nenhuma das entradas restantes em um diretório são diretórios, não se preocupe em determinar o tipo de arquivo ( com a chamada de sistema stat ), a menos que um dos critérios de pesquisa exija. Chamar stat pode levar um tempo mensurável, já que as informações geralmente estão no inode, em um local separado no disco, em vez de no diretório contido.

Como isso é sabido? Porque a contagem de links em um diretório indica quantos subdiretórios ele possui. Em sistemas de arquivos Unix típicos, a contagem de links de um diretório é 2 mais o número de diretórios: um para a entrada do diretório em seu pai, um para a entrada . e um para a entrada .. em cada subdiretório.

A opção -noleaf informa find para não aplicar essa otimização. Isso é útil se find for invocado em algum sistema de arquivos no qual as contagens de links de diretório não seguem a convenção Unix.