Warum findet `. -Typ f` dauert länger als `find .`?

15

Es scheint, als findmüsste geprüft werden, ob ein angegebener Pfad einer Datei oder einem Verzeichnis entspricht, um den Inhalt von Verzeichnissen rekursiv zu durchsuchen.

Hier ist ein wenig Motivation und was ich vor Ort getan habe, um mich davon zu überzeugen, dass es find . -type fwirklich langsamer ist als find .. Ich habe mich noch nicht mit dem GNU-Find-Quellcode beschäftigt.

Daher sichere ich einige der Dateien in meinem $HOME/WorkspaceVerzeichnis und schließe Dateien aus, bei denen es sich entweder um Abhängigkeiten meiner Projekte oder um Versionskontrolldateien handelt.

Also habe ich den folgenden Befehl ausgeführt, der schnell ausgeführt wurde

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

findEine Pipe zu grepeiner schlechten Form mag sein, aber es schien der direkteste Weg zu sein, einen negierten Regex-Filter zu verwenden.

Der folgende Befehl bezieht nur Dateien in die Ausgabe von find ein und hat deutlich länger gedauert.

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

Ich habe Code geschrieben, um die Leistung dieser beiden Befehle zu testen (mit dashund tcsh, um mögliche Effekte der Shell auszuschließen, auch wenn es keine geben sollte). Die tcshErgebnisse wurden weggelassen, da sie im Wesentlichen gleich sind.

Die Ergebnisse, die ich erhalten habe, zeigten eine 10% ige Leistungsstrafe für -type f

Hier ist die Ausgabe des Programms, die die Zeit angibt, die für die Ausführung von 1000 Iterationen verschiedener Befehle benötigt wurde.

% 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

Getestet mit

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

Unter Ubuntu 15.10

Hier ist das Perl-Skript, das ich für das Benchmarking verwendet habe

#!/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
quelle
2
Es scheint, als findmüsste geprüft werden, ob ein angegebener Pfad einer Datei oder einem Verzeichnis entspricht, um den Inhalt von Verzeichnissen rekursiv zu durchsuchen. - Es müsste überprüft werden, ob es sich um ein Verzeichnis handelt. Es müsste nicht überprüft werden, ob es sich um eine Datei handelt. Es gibt noch andere Eintragsarten: Named Pipes, symbolische Links, Blockieren spezieller Geräte, Sockets ... Obwohl bereits geprüft wurde, ob es sich um ein Verzeichnis handelt, bedeutet dies nicht, dass es weiß, ob es sich um eine reguläre Datei handelt.
RealSkeptic
busybox find, angewendet auf zufällige Verzeichnisse mit 4,3k Verzeichnissen und 2,8k Dateien, die gleichzeitig mit -type fund ohne ausgeführt werden. Aber beim ersten Mal hat der Linux-Kernel ihn in den Cache geladen und der erste Fund war langsamer.
1
Meine erste Vermutung war , dass die -type fOption verursacht findanrufen stat()oder fstat()oder was auch immer , um herauszufinden, ob der Dateiname in eine Datei entsprach, ein Verzeichnis, ein symbolischer Link, etc etc. Ich habe ein straceauf ein find . und ein find . -type fund die Spur war fast identisch, unterscheidet sich nur in den write()Aufrufen, die Verzeichnisnamen in ihnen hatten. Also, ich weiß es nicht, aber ich möchte die Antwort wissen.
Bruce Ediger
1
Keine wirkliche Antwort auf Ihre Frage, aber es gibt einen timeeingebauten Befehl, mit dem Sie feststellen können, wie lange die Ausführung eines Befehls dauert. Sie mussten zum Testen nicht unbedingt ein benutzerdefiniertes Skript schreiben.
Elronnd

Antworten:

16

GNU find hat eine Optimierung, die angewendet werden kann, find .aber nicht auf find . -type f: Wenn es bekannt ist, dass keiner der verbleibenden Einträge in einem Verzeichnis Verzeichnisse sind, muss der Dateityp (mit dem statSystemaufruf) nur von einem der Verzeichnisse bestimmt werden Suchkriterien erfordert es. Das Aufrufen statkann messbare Zeit in Anspruch nehmen, da sich die Informationen in der Regel im Inode an einem separaten Speicherort auf der Festplatte und nicht im übergeordneten Verzeichnis befinden.

Woher weiß es das? Weil die Anzahl der Links in einem Verzeichnis angibt, über wie viele Unterverzeichnisse es verfügt. In typischen Unix-Dateisystemen beträgt die Verbindungsanzahl eines Verzeichnisses 2 plus der Anzahl der Verzeichnisse: eines für den Verzeichniseintrag in seinem übergeordneten Verzeichnis, eines für den .Eintrag und eines für den ..Eintrag in jedem Unterverzeichnis.

Die -noleafOption weist Sie findan, diese Optimierung nicht anzuwenden. Dies ist nützlich, wenn findes in einem Dateisystem aufgerufen wird, in dem die Anzahl der Verzeichnisverknüpfungen nicht der Unix-Konvention entspricht.

Gilles 'SO - hör auf böse zu sein'
quelle
Ist das noch relevant? Wenn man sich die findQuelle ansieht, verwendet man heutzutage einfach das fts_open()und fts_read().
RealSkeptic
@RealSkeptic Hat sich dies in den letzten Versionen geändert? Ich habe die Quelle nicht überprüft, aber experimentell optimiert Version 4.4.2 in Debian Stable statAufrufe, wenn sie aufgrund der Anzahl der Verzeichnisverknüpfungen nicht benötigt werden, und die -noleafOption ist im Handbuch dokumentiert.
Gilles 'SO- hör auf böse zu sein'
Es optimiert statsogar in der fts...Version - es übergibt dem fts_openAufruf das entsprechende Flag dafür . Was ich mir aber nicht sicher bin, ist die Überprüfung mit der Anzahl der Links. Stattdessen wird geprüft, ob der zurückgegebene fts-Datensatz eines der "Verzeichnis" -Flags enthält. Es kann sein, dass fts_readselbst die Links überprüft, um dieses Flag zu setzen, dies jedoch findnicht. Sie können sehen, ob sich Ihre Version darauf stützt, ftsindem Sie anrufen find --version.
RealSkeptic
@ Gilles, Wäre es findtheoretisch möglich festzustellen, wann alle Einträge in einem Verzeichnis auch Verzeichnisse sind, und diese Informationen zu verwenden?
Gregory Nisbet
@GregoryNisbet Theoretisch ja, aber der Quellcode (den ich jetzt überprüft habe) macht das nicht, vermutlich, weil es ein viel seltenerer Fall ist.
Gilles 'SO- hör auf böse zu sein'