Dlaczego „znajduje. -typ f zajmuje więcej czasu niż „znajdź”?

15

Wygląda na to, findże musiałbym sprawdzić, czy dana ścieżka i tak odpowiada plikowi lub katalogowi, aby rekursywnie przechodzić przez zawartość katalogów.

Oto motywacja i to, co zrobiłem lokalnie, aby przekonać siebie, że find . -type fnaprawdę jest wolniejsze niż find .. Nie zagłębiłem się jeszcze w kod źródłowy GNU find.

Tworzę więc kopie zapasowe niektórych plików w moim $HOME/Workspacekatalogu i wykluczam pliki, które są albo zależnościami moich projektów, albo plikami kontroli wersji.

Uruchomiłem więc następujące polecenie, które wykonałem szybko

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

findprzesyłane strumieniowo do grepmoże być złej postaci, ale wydawało się, że jest to najbardziej bezpośredni sposób na użycie zanegowanego filtra regex.

Następujące polecenie zawiera tylko pliki w wyjściu find i zajęło zauważalnie więcej czasu.

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

Napisałem trochę kodu, aby przetestować działanie tych dwóch poleceń (z dashi tcsh, aby wykluczyć jakiekolwiek efekty, jakie może mieć powłoka, nawet jeśli nie powinno być żadnych). Te tcshwyniki zostały pominięte, ponieważ są w zasadzie takie same.

Wyniki, które uzyskałem, pokazały około 10% kary za wydajność -type f

Oto wynik programu pokazujący czas potrzebny do wykonania 1000 iteracji różnych poleceń.

% 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

Testowane z

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

Na Ubuntu 15.10

Oto skrypt perla, którego użyłem do testów porównawczych

#!/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);
    }
}
Gregory Nisbet
źródło
2
Wygląda na to, findże musiałbym sprawdzić, czy dana ścieżka i tak odpowiada plikowi lub katalogowi, aby rekursywnie przechodzić przez zawartość katalogów. - musiałby sprawdzić, czy jest to katalog, nie musiałby sprawdzić, czy jest to plik. Istnieją inne typy wpisów: nazwane potoki, dowiązania symboliczne, blokuj urządzenia specjalne, gniazda ... Więc chociaż mógł już sprawdzić, czy jest to katalog, nie znaczy to, że wie, czy jest to zwykły plik.
RealSkeptic
funkcja busybox find, stosowana do losowego katalogu z katalogami 4,3k i plikami 2,8k działającymi jednocześnie z nim -type fi bez niego. Ale po raz pierwszy jądro Linuksa załadowało go do pamięci podręcznej i pierwsze wyszukiwanie było wolniejsze.
1
Najpierw zgadywałem, że -type fopcja spowodowała findwywołanie stat()lub fstat()cokolwiek innego, aby dowiedzieć się, czy nazwa pliku odpowiada plikowi, katalogowi, dowiązaniu symbolicznemu itp. Zrobiłem stracena A find . i A, find . -type fa ślad był prawie identyczny, różni się tylko write()połączeniami, które zawierają nazwy katalogów. Nie wiem, ale chcę znać odpowiedź.
Bruce Ediger,
1
Naprawdę nie jest to odpowiedź na twoje pytanie, ale jest timewbudowane polecenie, aby zobaczyć, jak długo trwa wykonanie polecenia, tak naprawdę nie trzeba pisać niestandardowego skryptu, aby przetestować.
Elronnd

Odpowiedzi:

16

GNU find ma optymalizację, którą można zastosować, find .ale nie do find . -type f: jeśli wie, że żaden z pozostałych wpisów w katalogu nie jest katalogiem, to nie zadaje sobie trudu, aby określić typ pliku (za pomocą statwywołania systemowego), chyba że jeden z kryteria wyszukiwania tego wymagają. Wywołanie statmoże zająć mierzalny czas, ponieważ informacje zwykle znajdują się w i-węzle, w oddzielnym miejscu na dysku, a nie w zawierającym go katalogu.

Skąd to wie? Ponieważ liczba linków w katalogu wskazuje, ile ma podkatalogów. W typowych systemach plików Unix liczba linków do katalogu wynosi 2 plus liczba katalogów: jeden dla pozycji katalogu w jego rodzicu, jeden dla .pozycji i jeden dla ..pozycji w każdym podkatalogu.

Ta -noleafopcja mówi, findaby nie stosować tej optymalizacji. Jest to przydatne, jeśli findjest wywoływane w niektórych systemach plików, w których liczba linków do katalogów nie jest zgodna z konwencją uniksową.

Gilles „SO- przestań być zły”
źródło
Czy to nadal ma znaczenie? Patrząc na findźródło, po prostu używa obecnie połączeń fts_open()i fts_read().
RealSkeptic
@RealSkeptic Czy to się zmieniło w ostatnich wersjach? Nie sprawdziłem źródła, ale eksperymentalnie wersja 4.4.2 w stabilnej wersji Debiana optymalizuje statpołączenia, gdy nie są one potrzebne ze względu na liczbę linków do katalogów, a -noleafopcja jest udokumentowana w instrukcji.
Gilles „SO- przestań być zły”
Optymalizuje statnawet w fts...wersji - przekazuje odpowiednią flagę do fts_openpołączenia. Ale nie jestem pewien, czy nadal dotyczy to liczby linków. Zamiast tego sprawdza, czy zwrócony rekord fts ma jedną z flag „katalogu”. Być może fts_readsam sprawdza łącza, aby ustawić tę flagę, ale findnie robi tego. Możesz sprawdzić, czy Twoja wersja polega na ftstelefonowaniu find --version.
RealSkeptic
@Gilles, Czy findteoretycznie byłby w stanie ustalić, kiedy wszystkie wszystkie wpisy w katalogu są również katalogami i wykorzystać te informacje?
Gregory Nisbet
@GregoryNisbet Teoretycznie tak, ale kod źródłowy (już sprawdziłem) tego nie robi, prawdopodobnie dlatego, że jest to znacznie rzadszy przypadek.
Gilles „SO- przestań być zły”