Por que o GNU Find é tão rápido em comparação com os utilitários gráficos de busca de arquivos?

47

Estou tentando encontrar um arquivo que não existe no meu diretório pessoal e em todos os subdiretórios.

find ~/ -name "bogus"fornece essas informações após alguns segundos, mas o gerenciador de dolphinarquivos do KDE precisou de quase 3 minutos para fazer o mesmo. Isso corresponde à minha experiência anterior com o GNOMEbeagle .

Como findconsegue fazer o mesmo muito rápido enquanto a pesquisa gráfica (que é mais intuitiva de usar do que os parâmetros da linha de comando) fica para trás?

Vermelho
fonte
Não sei o que é "Dolphin", mas talvez ele também procure dentro de arquivos?
Kusalananda
11
É um gerenciador de arquivos gráficos do KDE: kde.org/applications/system/dolphin Ele tem capacidade de pesquisar arquivos internos, mas não habilitei essa opção durante este breve teste.
Vermelho
9
Você pesquisou mais de uma vez no golfinho? Pode estar "indexando" pela 1ª vez. E "encontrar" também é lento. Tente "localizar" se o arquivo é mais velha do que a última vez que o banco de dados para localizar estava indexada ;-)
Rinzwind
Eu uso locatemais frequentemente do que finde é mais rápido em uma pasta enorme
phuclv
11
Embora locateseja realmente ótimo para encontrar arquivos, isso é um pouco obsoleto, porque usa uma abordagem completamente diferente: finde ferramentas da GUI Dolphinestão percorrendo a árvore de arquivos sob demanda, enquanto locateusam uma estrutura de índice criada anteriormente.
Michael Schaefers

Respostas:

68

Olhando especificamente para o Dolphin com o Baloo, parece procurar os metadados de cada arquivo em seu domínio de pesquisa, mesmo se você estiver fazendo uma pesquisa simples de nome de arquivo. Quando eu rastrear o file.soprocesso, eu vejo as chamadas para lstat, getxattre getxattrmais uma vez para cada arquivo, e até mesmo para ..entradas. Essas chamadas do sistema recuperam metadados sobre o arquivo armazenado em um local diferente do nome do arquivo (o nome do arquivo é armazenado no conteúdo do diretório, mas os metadados estão no inode ). Consultar os metadados de um arquivo várias vezes é barato, pois os dados estariam no cache do disco, mas pode haver uma diferença significativa entre consultar os metadados e não os metadados.

findé muito mais inteligente. Ele tenta evitar chamadas desnecessárias ao sistema. Ele não liga getxattrporque não pesquisa com base em atributos estendidos. Ao percorrer um diretório, pode ser necessário chamar lstatnomes de arquivos não correspondentes, porque esse pode ser um subdiretório para pesquisar recursivamente ( lstaté a chamada do sistema que retorna os metadados do arquivo, incluindo o tipo de arquivo como regular / directory / symlink /…). No entanto, findpossui uma otimização: ele sabe quantos subdiretórios um diretório possui a partir de sua contagem de links e para de chamar lstatquando sabe que percorreu todos os subdiretórios. Em particular, em um diretório folha (um diretório sem subdiretórios),findapenas verifica os nomes, não os metadados. Além disso, alguns sistemas de arquivos mantêm uma cópia do tipo de arquivo na entrada do diretório, para que findnem precise ligar lstatse essa é a única informação necessária.

Se você executar findcom opções que exigem a verificação dos metadados, ele fará mais lstatchamadas, mas ainda não fará uma lstatchamada em um arquivo se não precisar das informações (por exemplo, porque o arquivo foi excluído por uma condição anterior). correspondente no nome).

Suspeito que outras ferramentas de pesquisa da GUI que reinventem a findroda sejam igualmente menos inteligentes que o utilitário de linha de comando que passou por décadas de otimização. O Dolphin, pelo menos, é inteligente o suficiente para usar o banco de dados de localização se você pesquisar "em todos os lugares" (com a limitação que não está clara na interface do usuário de que os resultados podem estar desatualizados).

Gilles 'SO- parar de ser mau'
fonte
22
O GNU find é tão "inteligente" que perde alguns arquivos em alguns tipos de sistema de arquivos. O bug bem conhecido na descoberta do GNU é que ele supõe ilegalmente que a contagem de links de um diretório seja. 2 + number of sub-directories.Isso funciona para sistemas de arquivos que implementam o bug de design do sistema de arquivos UNIX V7, mas não para todos os sistemas de arquivos, pois esse não é um requisito do POSIX. . Se você deseja obter um número de desempenho útil para o GNU make, é necessário especificar -noleafpara que o GNU make se comporte corretamente.
schily
12
@schily, o GNU findpode ter esse bug há muito tempo, mas duvido que você encontre um caso em que precise especificar -noleafmanualmente hoje em dia. AFAICT, pelo menos no Linux getdents()(e readdir ()) informa quais arquivos são arquivos de diretório em UDF, ISO-9660, btrfs que não possuem entradas reais .ou se comportam bem lá. Você conhece um caso em que o GNU apresenta o problema? ..findfind
Stéphane Chazelas
4
Apenas use esta imagem podre da debian para criar um sistema de arquivos Rock Ridge usando "graft-points" e a contagem de links em um diretório é um valor aleatório. Como o Rock Ridge implementa uma contagem de links e. / .., o GNU find geralmente não encontrará todos os arquivos nesse sistema de arquivos.
schily
4
@ StéphaneChazelas: Na última vez em que verifiquei (para a tese de mestrado), o bug foi corrigido afirmando exatamente 2 folhas conhecidas, em vez de <= 2. Os sistemas de arquivos que não implementam o contador 2+ retornam 1 para a contagem de links do diretório, portanto tudo otimo. Agora, se algum dia alguém criou um sistema de arquivos com links físicos para diretórios que não tinham essa propriedade, alguém terá um dia ruim.
Joshua
15
@ schch, eu não era capaz de obter contagens aleatórias de links com pontos de enxerto e RR com genisoimage 1.1.11 no Debian e mesmo se eu editar binário a imagem iso para alterar as contagens de links para valores aleatórios, ainda não vejo nenhuma problema com o GNU find. E, de qualquer forma, strace -vmostra que getdents()retorna corretamente d_type = DT_DIR para diretórios, para que o GNU find não precise usar o truque de contagem de links.
Stéphane Chazelas