Como a ordem dos argumentos influencia a velocidade de encontrar

Question

Como a ordem dos argumentos em uma chamada find afeta a velocidade dos resultados?

Compare por exemplo (A)

find -name dir -type d

e (B)

find -type d -name dir

Ou qualquer outra combinação de argumentos (por exemplo, usando -or ou -and ). Espero que find seja inteligente de alguma forma.

Eu tentei coletar algumas estatísticas executando A e B com time e 5 repetições. No entanto com

 11.86, 7.23, 5.25, 5.87, 7.16

para A e para B:

9.73, 6.56, 8.69, 7.14, 6.35

isso não é realmente conclusivo, com valores médios em torno de 7.5s para ambos e uma variância bastante alta.

Então, para repetir minha pergunta, a ordem dos argumentos é importante usando find ?

    

Answer 1

O que é caro, é fazer chamadas do sistema nos arquivos (para as chamadas do sistema e para a E / S).

As coisas como -type , -mtime requerem uma chamada de sistema lstat(2) no arquivo. -name , -path , -regex não (embora, é claro, ele tenha feito chamadas do sistema para os diretórios que eles contêm para ler seu conteúdo).

Geralmente, find faz um lstat() de qualquer maneira (porque precisa saber se um arquivo é um diretório ou não descer nele, a menos que essa informação seja fornecida no readdir() ), mas há casos em que pode fazer sem isto. Por exemplo, se o número de links de um diretório for menor que 3, em alguns sistemas de arquivos, find saberá que ele não tem subdiretórios e que algumas implementações find otimizarão ao não fazer lstat s nele.

-xtype fará com que stat(2) , -printf ... , -ls possa causar stat() , lstat() , readlink() , -lname a lstat() e readlink() .

É por isso que você pode colocar o -name / -path / -regex ... primeiro. Se eles puderem descartar um arquivo, eles poderão evitar um ou mais syscalls.

Agora, um -regex pode ser mais caro que um -name , mas não tenho certeza se você conseguiria muito trocando-os.

Observe também que algumas implementações de find como o GNU find reordenam as verificações por padrão quando possível. Veja:

info find 'Optimisation Options'

em um sistema GNU ( lá no gnu.org para a versão mais recente do GNU findutils ).

Normalmente, se você fez seus testes em um sistema GNU, os dois comandos farão a mesma coisa porque find teria movido o -name para a frente de qualquer maneira.

Portanto, para que -type d -name ... vs -name ... -type d faça a diferença, você precisa de uma implementação de find que não otimize reordenando esses predicados e que faça alguma otimização por não fazer um lstat() em cada arquivo.

Onde haverá uma diferença (enorme), independentemente da implementação estar em:

find . -name 'x*' -exec test -d {} \; -print

vs:

find . -exec test -d {} \; -name 'x*' -print

find não pode reordenar o -exec , pois isso pode introduzir diferenças funcionais ( find não pode saber se o comando que é executado é apenas para testes ou faz outra coisa).

E é claro que -exec ... {} \; é várias ordens de magnitude mais caro do que qualquer outro predicado, pois significa "bifurcar" um processo e executar um comando nele (e executar muitas chamadas do sistema) e aguardar pelo código de saída.

$ time find /usr/lib -exec test -d {} \; -name z\* -print > /dev/null
1.03s user 12.52s system 21% cpu 1:03.43 total
$ time find /usr/lib -name z\* -exec test -d {} \;  -print > /dev/null
0.09s user 0.14s system 62% cpu 0.367 total

(o primeiro chama test para cada arquivo em /usr/lib (56685), o segundo apenas nos arquivos cujo nome começa com z (147)).

Observe que -exec test -d {} \; não é o mesmo que -type d . É o equivalente portátil do -xtype d específico do GNU.