¿Por qué GNU encuentra tan rápido en comparación con las utilidades de búsqueda de archivos gráficos?

47

Estoy tratando de encontrar un archivo que no existe en mi directorio de inicio y en todos los subdirectorios.

find ~/ -name "bogus"me da esa información después de unos segundos, pero el dolphinadministrador de archivos de KDE necesitó casi 3 minutos para hacer lo mismo. Esto corresponde con mi experiencia previa con GNOMEbeagle .

¿Cómo se las findarregla para hacer lo mismo muy rápido mientras la búsqueda gráfica (que es más intuitiva de usar que los parámetros de la línea de comandos) se queda atrás?

rojo
fuente
No sé qué es "Dolphin", pero ¿quizás también busque dentro de los archivos?
Kusalananda
1
Es un administrador de archivos gráfico de KDE: kde.org/applications/system/dolphin Tiene la capacidad de buscar dentro de los archivos, pero no habilité esa opción durante esta breve prueba.
Rojo
99
¿Buscaste más de una vez en delfines? Podría estar "indexando" la primera vez. Y "encontrar" también es lento. Intente "localizar" si el archivo es anterior a la última vez que se indexó la base de datos para localizar ;-)
Rinzwind
Lo uso con locatemás frecuencia findy es más rápido en una carpeta enorme
phuclv
11
Si bien locatees realmente excelente para encontrar archivos, esto es un poco OT, ya que utiliza un enfoque completamente diferente: findy las herramientas de GUI como Dolphinatraviesan el árbol de archivos a pedido, mientras locateusan una estructura de índice creada previamente.
Michael Schaefers

Respuestas:

68

Mirando específicamente a Dolphin con Baloo, parece buscar los metadatos de cada archivo en su dominio de búsqueda, incluso si está haciendo una simple búsqueda de nombre de archivo. Cuando trazo el file.soproceso, veo llamadas a lstat, getxattry getxattrnuevamente para cada archivo, e incluso para las ..entradas. Estas llamadas al sistema recuperan metadatos sobre el archivo que se almacena en una ubicación diferente del nombre del archivo (el nombre del archivo se almacena en el contenido del directorio, pero los metadatos están en el inodo ). Consultar los metadatos de un archivo varias veces es barato, ya que los datos estarían en el caché del disco, pero puede haber una diferencia significativa entre consultar los metadatos y no consultar los metadatos.

findEs mucho más inteligente. Intenta evitar llamadas innecesarias al sistema. No llamará getxattrporque no busca en función de atributos extendidos. Cuando atraviesa un directorio, es posible que necesite invocar lstatnombres de archivo que no coinciden porque puede ser un subdirectorio para buscar de forma recursiva ( lstates la llamada al sistema que devuelve metadatos de archivo, incluido el tipo de archivo como regular / directorio / enlace simbólico / ...). Sin embargo, findtiene una optimización: sabe cuántos subdirectorios tiene un directorio desde su recuento de enlaces , y deja de llamar lstatuna vez que sabe que ha recorrido todos los subdirectorios. En particular, en un directorio hoja (un directorio sin subdirectorios),findsolo verifica los nombres, no los metadatos. Además, algunos sistemas de archivos mantienen una copia del tipo de archivo en la entrada del directorio para que findni siquiera tenga que llamar lstatsi esa es la única información que necesita.

Si ejecuta findopciones que requieren verificar los metadatos, realizará más lstatllamadas, pero aún no hará una lstatllamada en un archivo si no necesita la información (por ejemplo, porque el archivo está excluido por una condición previa coincidencia en el nombre).

Sospecho que otras herramientas de búsqueda de GUI que reinventan la findrueda son igualmente menos inteligentes que la utilidad de línea de comandos que ha sufrido décadas de optimización. Dolphin, al menos, es lo suficientemente inteligente como para usar la base de datos de localización si busca "en todas partes" (con la limitación que no está clara en la interfaz de usuario de que los resultados pueden estar desactualizados).

Gilles 'SO- deja de ser malvado'
fuente
22
GNU find es tan "inteligente" que pierde algunos archivos en algunos tipos de sistemas de archivos. El error bien conocido en GNU encuentra es que hace la suposición ilegal de que el conteo de enlaces de un directorio es 2 + number of sub-directories.Esto funciona para sistemas de archivos que implementan el error de diseño del sistema de archivos UNIX V7, pero no para todos los sistemas de archivos, ya que este no es un requisito POSIX . Si desea obtener un número de rendimiento útil para GNU make, debe especificar -noleafel orden para que GNU make se comporte correctamente.
schily
12
@schily, GNU findpuede haber tenido ese error hace mucho tiempo, pero dudo que encuentres un caso en el que necesites especificarlo -noleafa mano hoy en día. AFAICT, al menos en Linux getdents()(y readdir ()) le dice qué archivos son archivos de directorio en UDF, ISO-9660, btrfs que no tienen entradas reales .o ..y se findcomporta bien allí. ¿Conoces un caso en el que GNU findmuestra el problema?
Stéphane Chazelas
44
Simplemente use esta imagen genérica podrida de Debian para crear un sistema de archivos Rock Ridge usando "puntos de injerto" y el recuento de enlaces en un directorio es un valor aleatorio. Como Rock Ridge implementa un conteo de enlaces y. / .., GNU find generalmente no encontrará todos los archivos en dicho sistema de archivos.
schily
44
@ StéphaneChazelas: la última vez que verifiqué (para mi tesis de maestría), el error se corrigió afirmando exactamente 2 significaba hoja conocida en lugar de <= 2. Todos los sistemas de archivos que no implementan el contador 2+ devuelven 1 para el recuento de enlaces de directorio. todo está bien. Ahora, si algún día alguien creó un sistema de archivos que hiciera enlaces duros a directorios que no tenían esta propiedad, alguien tendrá un mal día.
Joshua
15
@schily, no pude obtener conteos de enlaces aleatorios con puntos de injerto y RR con genisoimage 1.1.11 en Debian e incluso si edito binariamente la imagen iso para cambiar los conteos de enlaces a valores aleatorios, todavía no veo ninguno problema con GNU find. Y, en cualquier caso, strace -vmuestra que getdents()devuelve correctamente d_type = DT_DIR para directorios, por lo que GNU find no tiene que usar el truco de conteo de enlaces.
Stéphane Chazelas