ugrep indexer
v1.0.0
L'utilitaire ugrep-indexer indexe les fichiers de manière récursive pour accélérer la recherche récursive.
De plus, le contenu des archives et des fichiers compressés est indexé lorsqu'il est spécifié avec une option de ligne de commande. Cela élimine la recherche lorsqu'aucun de leurs contenus ne correspond aux modèles spécifiés.
ugrep est un outil de recherche de fichiers rapide compatible grep qui prend en charge la recherche basée sur un index. La recherche basée sur l'index peut être beaucoup plus rapide sur les systèmes de fichiers lents et lorsque la mise en cache du système de fichiers est inefficace : si le système de fichiers sur un lecteur recherché n'est pas mis en cache dans la RAM, c'est-à-dire s'il est « froid », alors l'indexation accélérera la recherche. Il recherche uniquement les fichiers pouvant correspondre à un modèle d'expression régulière spécifié en utilisant un index du fichier. Cet index permet de vérifier rapidement s'il existe une correspondance potentielle, nous évitons ainsi de rechercher tous les fichiers.
La recherche indexée avec ugrep est sûre et n'ignore jamais les fichiers mis à jour qui peuvent désormais correspondre. Si des fichiers et des répertoires sont ajoutés ou modifiés après l'indexation, la recherche recherchera toujours ces ajouts et modifications apportés au système de fichiers en comparant les horodatages des fichiers et des répertoires à l'horodatage d'indexation.
Lorsque de nombreux fichiers sont ajoutés ou modifiés après l'indexation, nous souhaiterons peut-être les réindexer pour mettre les index à jour. La réindexation est incrémentielle, elle ne prendra donc pas autant de temps que le processus d'indexation initial.
Un exemple typique mais petit de recherche basée sur un index, par exemple sur le référentiel ugrep v3.12.6 placé sur un lecteur séparé :
$ cd drive/ugrep
$ ugrep-indexer -I
12247077 bytes scanned and indexed with 19% noise on average
1317 files indexed in 28 directories
28 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
5605227 bytes indexing storage increase at 4256 bytes/file
La recherche normale sur un système de fichiers froid sans indexation prend 1,02 secondes après le démontage du drive et son nouveau montage pour vider le cache FS afin d'enregistrer l'effet de l'indexation :
$ ugrep -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 1.02 seconds with 8 threads: 1 matching (0.07593%)
Ripgrep 13.0.0 prend plus de temps avec 1,18 secondes pour la même recherche à froid (ripgrep ignore les fichiers binaires par défaut, donc l'option -I n'est pas spécifiée) :
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
En revanche, avec l'indexation, la recherche d'un système de fichiers froid ne prend que 0,0487 seconde avec ugrep, ce qui est 21 fois plus rapide, après avoir démonté drive et remonté pour vider le cache FS afin d'enregistrer l'effet de l'indexation :
$ ugrep --index -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 0.0487 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1316 of 1317 files with non-matching indexes
Il y a toujours une certaine variation dans le temps écoulé, 0,0487 seconde étant le meilleur temps des quatre cycles de recherche qui ont produit une plage de temps de recherche de 0,0487 (accélération 21x) à 0,0983 secondes (accélération 10x).
L'augmentation de la vitesse peut être significativement plus élevée en général par rapport à cette petite démo, en fonction de plusieurs facteurs, de la taille des fichiers indexés, de la vitesse de lecture du système de fichiers et en supposant que la plupart des fichiers sont froids.
L'algorithme d'indexation que j'ai conçu est prouvablement monotone : une précision plus élevée garantit des performances de recherche accrues en réduisant le taux de faux positifs, mais augmente également la surcharge de stockage de l'index. De même, une précision moindre diminue les performances de recherche, mais réduit également la surcharge de stockage de l'index. Par conséquent, j'ai nommé mon indexeur un indexeur monotone .
Si l'espace de stockage de fichiers est limité, nous pouvons alors réduire la surcharge de stockage d'index en spécifiant une précision d'indexation inférieure.
L'indexation de l'exemple ci-dessus avec le niveau 0 (option -0 ) réduit la surcharge de stockage d'indexation de 8,6 fois, de 4 256 octets par fichier à un maigre 490 octets par fichier :
12247077 bytes scanned and indexed with 42% noise on average
1317 files indexed in 28 directories
0 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
646123 bytes indexing storage increase at 490 bytes/file
La recherche indexée est toujours beaucoup plus rapide (12 fois) que la recherche non indexée pour cet exemple, avec 16 fichiers réellement recherchés (15 faux positifs) :
Searched 1317 files in 28 directories in 0.0722 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1301 of 1317 files with non-matching indexes
Les modèles Regex plus complexes que cet exemple peuvent naturellement avoir un taux de faux positifs plus élevé, qui correspond au taux de fichiers considérés comme pouvant correspondre alors qu'ils ne le sont pas. Un taux de faux positifs plus élevé peut réduire les vitesses de recherche lorsque le taux est suffisamment élevé pour avoir un impact.
Le tableau suivant montre comment la précision de l'indexation affecte le stockage de l'indexation et le bruit moyen par fichier indexé. Les colonnes les plus à droite indiquent la vitesse de recherche et le taux de faux positifs pour ugrep --index -I -l 'std::chrono' :
| acc. | stockage d'index (Ko) | bruit moyen | faux positifs | temps de recherche (s) |
|---|---|---|---|---|
-0 | 631 | 42% | 15 | 0,0722 |
-1 | 1276 | 39% | 1 | 0,0506 |
-2 | 1576 | 36% | 0 | 0,0487 |
-3 | 2692 | 31% | 0 | unch |
-4 | 2966 | 28% | 0 | unch |
-5 | 4953 | 23% | 0 | unch |
-6 | 5474 | 19% | 0 | unch |
-7 | 9513 | 15% | 0 | unch |
-8 | 10889 | 11% | 0 | unch |
-9 | 13388 | 7% | 0 | unch |
Si l'expression régulière spécifiée correspond à beaucoup plus de modèles possibles, par exemple avec la recherche ugrep --index -I -l '(todo|TODO)[: ]' , alors nous pouvons observer un taux plus élevé de faux positifs parmi les 1317 fichiers recherchés, ce qui entraîne des temps de recherche légèrement plus longs :
| acc. | faux positifs | temps de recherche (s) |
|---|---|---|
-0 | 189 | 0,292 |
-1 | 69 | 0,122 |
-2 | 43 | 0,103 |
-3 | 19 | 0,101 |
-4 | 16 | 0,097 |
-5 | 2 | 0,096 |
-6 | 1 | unch |
-7 | 0 | unch |
-8 | 0 | unch |
-9 | 0 | unch |
La précision -4 est la valeur par défaut (contre -5 précédemment dans les anciennes versions), ce qui a tendance à très bien fonctionner pour rechercher avec des modèles d'expressions régulières de complexité modeste.
Un mot d'avertissement. Il y a toujours un petit peu de temps système pour vérifier les index. Cela signifie que si tous les fichiers sont déjà mis en cache dans la RAM, parce que les fichiers ont été recherchés ou lus récemment, l'indexation n'accélérera évidemment pas nécessairement la recherche. Dans ce cas, une recherche non indexée pourrait être plus rapide. De plus, une recherche basée sur un index a un temps de démarrage plus long. Ce temps de démarrage augmente lorsque des classes de caractères Unicode et des caractères génériques sont utilisés et doivent être convertis en tables de hachage.
Pour résumer, la recherche basée sur l'index est plus efficace lors de la recherche d'un grand nombre de fichiers froids et lorsque les modèles d'expression régulière ne correspondent pas trop, c'est-à-dire que nous voulons limiter l'utilisation de répétitions illimitées * et + et limiter l'utilisation de classes de caractères Unicode lorsque possible. Cela réduit le temps de démarrage de l'ugrep et limite le taux de correspondances de modèles faussement positifs (voir également les questions et réponses ci-dessous).
Indexez de manière récursive et incrémentielle tous les fichiers non binaires affichant la progression :
ugrep-indexer -I -v
Indexez de manière récursive et incrémentielle tous les fichiers non binaires, y compris les fichiers non binaires stockés dans des archives et dans des fichiers compressés, en affichant la progression :
ugrep-indexer -z -I -v
Indexez incrémentalement tous les fichiers non binaires, y compris les archives et les fichiers compressés, affichez la progression, suivez les liens symboliques vers les fichiers (mais pas vers les répertoires), mais n'indexez pas les fichiers et répertoires correspondant aux globs dans .gitignore :
ugrep-indexer -z -I -v -S -X
Forcez la réindexation de tous les fichiers non binaires, y compris les archives et les fichiers compressés, suivez les liens symboliques vers les fichiers (mais pas vers les répertoires), mais n'indexez pas les fichiers et répertoires correspondant aux globs dans .gitignore :
ugrep-indexer -f -z -I -v -S -X
Idem, mais réduisez au minimum le stockage des fichiers d'index en diminuant la précision de l'indexation de 5 (par défaut) à 0 :
ugrep-indexer -f -0 -z -I -v -S -X
Augmentez les performances de recherche en augmentant la précision de l'indexation de 5 (par défaut) à 7 au prix de fichiers d'index plus volumineux :
ugrep-indexer -f7zIvSX
Supprimez de manière récursive tous les fichiers d'index ._UG#_Store masqués pour restaurer l'arborescence des répertoires en mode non indexé :
ugrep-indexer -d
Configurez et compilez avec :
./build.sh
Si vous le souhaitez mais pas obligatoire, installez avec :
sudo make install
Ajoutez une option pour créer un fichier d'index, par exemple spécifié explicitement à ugrep. Cela pourrait encore améliorer la vitesse de recherche indexée si le fichier d'index se trouve sur un système de fichiers rapide. Sinon, ne vous attendez pas à une grande amélioration ni même à un éventuel ralentissement, puisqu'un seul fichier d'index ne peut pas être recherché simultanément et que davantage d'entrées d'index seront vérifiées alors qu'en fait les répertoires sont ignorés (en sautant également leurs index). Les expériences le diront. Un inconvénient majeur de cette approche est que la recherche basée sur l'index avec ugrep --index n'est plus sûre : les fichiers nouveaux et modifiés qui ne sont pas encore indexés ne seront pas recherchés.
Chaque filtre N-gram Bloom possède son propre « niveau de bits » dans la table de hachage pour éviter les conflits de hachage. Par exemple, 2 grammes ne partagent aucun bit avec 3 grammes. Cela garantit que nous n’aurons jamais de faux positifs avec des caractères faussement correspondants qui ne font en réalité pas partie du modèle. Cependant, l'espace binaire d'un gramme (caractère unique) est petit (au maximum 256 bits). Par conséquent, nous gaspillons certains bits lorsque les tables de hachage sont plus grandes. Une approche possible pour réduire les déchets consiste à combiner 1 gramme avec 2 grammes pour partager le même espace binaire. C'est facile à faire si l'on considère qu'un 1 gramme est égal à un 2 grammes avec le deuxième caractère défini sur (NUL). Nous pouvons réduire le taux de faux positifs avec un deuxième hachage de 2 grammes basé sur une méthode de hachage différente. Ou nous pouvons étendre les « niveaux de bits » de 8 à 9 pour stocker 9 grammes. Cela augmentera la précision de l'indexation pour les modèles plus longs (9 ou plus) sans frais supplémentaires. D'un autre côté, ce changement peut provoquer davantage de faux positifs lorsque des caractères faussement correspondants ne font pas partie du modèle ; on perd l'avantage d'une précision parfaite au gramme près.
L'indexation ajoute un fichier d'index caché ._UG#_Store à chaque répertoire indexé. Les fichiers indexés sont analysés (jamais modifiés !) par ugrep-indexer pour générer des fichiers d'index.
La taille des fichiers d'index dépend de la précision spécifiée, -0 étant la plus faible (petits fichiers d'index) et -9 la plus élevée (grands fichiers d'index). La précision par défaut est -4 . Voir la question suivante pour plus de détails sur l'impact de la précision sur la taille de l'indexation par rapport à la vitesse de recherche.
L'indexation ne suit jamais les liens symboliques vers des répertoires , car les répertoires liés symboliquement peuvent être situés n'importe où dans un système de fichiers ou dans un autre système de fichiers, où nous ne souhaitons pas ajouter de fichiers d'index. Vous pouvez toujours indexer des liens symboliques vers des fichiers avec l'option ugrep-indexer -S .
L'option -v ( --verbose ) affiche la progression de l'indexation et le "bruit" de chaque fichier indexé. Le bruit est une mesure de l'entropie ou du caractère aléatoire de l'entrée. Un niveau de bruit plus élevé signifie que l'indexation était moins précise dans la représentation du contenu d'un fichier. Par exemple, un fichier volumineux contenant des données aléatoires est difficile à indexer avec précision et aura un niveau de bruit élevé.
La complexité de l'indexation est linéaire dans la taille d'un fichier donné à indexer. En pratique, ce n'est pas un processus rapide, ni une recherche aussi rapide, et peut prendre un certain temps pour effectuer une indexation complète sur une grande arborescence de répertoires. Une fois l'indexation terminée, ugrep-indexer affiche les résultats de l'indexation. La taille totale des index ajoutés et le bruit d'indexation moyen sont également signalés.
L'analyse d'un fichier à indexer génère une table de hachage d'indexation de 64 Ko. Ensuite, l'indexeur ugrep divise la table par deux avec une compression binaire en utilisant le bitwise - et tant que la précision cible n'est pas dépassée. La réduction de moitié est rendue possible par le fait que la table code les hachages pour 8 fenêtres à des décalages depuis le début du modèle, correspondant aux 8 bits par cellule de la table de hachage d'index. La combinaison des deux moitiés du tableau peut faire passer certains bits de un à zéro, ce qui peut provoquer une correspondance faussement positive. Cela prouve la monotonie de l'indexeur. Une valeur de hachage de zéro bit indique une correspondance possible.
L'ugrep-indexer détecte les "fichiers binaires", qui peuvent être ignorés et non indexés avec l'option ugrep-indexer -I ( --ignore-binary ). Ceci est utile lors d'une recherche avec l'option ugrep -I ( --ignore-binary ) pour ignorer les fichiers binaires, ce qui est un scénario typique.
L'indexeur ugrep obéit aux exclusions de fichiers .gitignore lorsqu'il est spécifié avec l'option -X ( --ignore-files ). Les fichiers et répertoires ignorés ne seront pas indexés pour économiser de l'espace sur le système de fichiers. Cela fonctionne bien lors de la recherche de fichiers avec l'option ugrep --ignore-files .
L'indexation peut être interrompue, par exemple avec CTRL-C, ce qui n'entraînera pas de perte de capacité de recherche avec ugrep, mais laissera la structure des répertoires seulement partiellement indexée.
L'option -c vérifie les index pour les références obsolètes et les fichiers et répertoires non indexés.
Les index sont supprimés avec l'option ugrep-indexer -d .
L'indexeur ugrep a été largement testé en comparant les résultats de recherche ugrep --index aux résultats de recherche ugrep "lents" non indexés sur des milliers de fichiers avec des milliers de modèles de recherche aléatoires.
La recherche indexée fonctionne avec toutes les options ugrep sauf avec l'option -v ( --invert-match ), --filter , -P ( --perl-regexp ) et -Z ( --fuzzy ). L'option -c ( --count ) avec --index définit automatiquement --min-count=1 pour ignorer tous les fichiers avec zéro correspondance.
Si des fichiers ou des répertoires ont été mis à jour, ajoutés ou supprimés après l'indexation, alors ugrep --index recherchera toujours ces fichiers et répertoires lorsqu'ils sont présents sur le chemin de recherche récursif. Vous pouvez réexécuter ugrep-indexer pour mettre à jour progressivement tous les index.
Les modèles regex sont convertis en interne par ugrep avec l'option --index en une forme de tables de hachage jusqu'aux 16 premiers octets des modèles regex spécifiés, éventuellement plus courts afin de réduire le temps de construction lorsque les modèles regex sont complexes. Par conséquent, les 8 à 16 premiers caractères d'un modèle d'expression régulière à rechercher sont les plus critiques et ne doivent pas trop correspondre pour limiter les correspondances dites faussement positives qui peuvent ralentir la recherche.
Dans ugrep, un modèle regex est converti en DFA. Un automate fini de hachage d'indexation (HFA) est construit au-dessus du DFA pour représenter de manière compacte les tables de hachage sous forme de transitions d'état avec des bords étiquetés. Ce HFA comprend jusqu'à huit couches, chacune décalée d'un octet pour représenter la fenêtre suivante de 8 octets sur le motif. Chaque couche HFA code les hachages d'index pour cette partie du modèle. La fonction de hachage d'index choisie est « additive », ce qui signifie que l'octet suivant est ajouté lorsqu'il est haché avec le hachage précédent. Ceci est très important car cela réduit considérablement les frais généraux de construction de HFA. Nous pouvons désormais coder les transitions HFA étiquetées vers des états sous la forme de plusieurs arêtes avec des plages de valeurs de hachage de 16 bits au lieu d'un ensemble d'arêtes uniques, chacune avec une valeur de hachage individuelle. À cette fin, j'utilise ma bibliothèque de plages ouvertes reflex::ORanges<T> dérivée de std::set<T> .
Une fonction très simple de chaîne unique maybe_match() avec la fonction de hachage d'index prime 61 est donnée ci-dessous pour démontrer la recherche basée sur l'index d'une seule chaîne :
// prime 61 hashing
uint16_t indexhash(uint16_t h, uint8_t b, size_t size)
{
return ((h << 6) - h - h - h + b) & (size - 1);
}
// return possible match of string given array of hashes of size <= 64K (power of two)
bool maybe_match(const char *string, uint8_t *hashes, size_t size)
{
size_t len = strlen(string); // practically we can and should limit len to e.g. 15 or 16
for (const char *window = string; len > 0; ++window, --len)
{
uint16_t h = window[0] & (size - 1);
if (hashes[h] & 0x01)
return false
size_t k, n = len < 8 ? len : 8;
for (k = 1; k < n; ++k)
{
h = indexhash(h, window[k], size);
if (hashes[h] & (1 << k))
return false;
}
}
return true;
}
Le hachage prime 61 a été choisi parmi de nombreuses autres fonctions de hachage possibles en utilisant une configuration expérimentale réaliste. Une fonction de hachage candidate a été testée en recherchant de manière répétée un mot tiré au hasard dans un fichier Wikipédia de 100 Mo. Le mot a été muté avec une, deux ou trois lettres aléatoires. Cette mutation est vérifiée pour s'assurer qu'elle ne correspond pas à un mot valide dans le fichier Wikipédia. Ensuite, le taux de faux positifs a été enregistré chaque fois qu’un mot muté correspond au fichier. Une fonction de hachage avec un taux de faux positifs minimal devrait être globalement un bon candidat.
En utilisant une fenêtre de 8 (ou plus courte selon la longueur du motif), le taux de faux positifs est inférieur à celui des filtres Bloom standard. Plus précisément, les fonctions de hachage N² sont utilisées à la place de N dans un filtre Bloom. Pour les modèles plus courts, N est souvent trop petit pour limiter les faux positifs. Par conséquent, N² est plus efficace. Il rejette également tout modèle d'une correspondance dont un caractère n'importe où dans les 8 premiers octets du modèle n'apparaît en réalité nulle part dans un fichier indexé, alors qu'un filtre Bloom standard pourrait avoir une correspondance faussement positive. De plus, l'adressage des bits utilisé pour indexer la table de hachage permet une compression efficace de la table.
L'indexation est une forme de compression avec perte. Plus la précision de l'indexation est élevée, plus les performances de recherche ugrep doivent être rapides en ignorant davantage de fichiers qui ne correspondent pas. Une plus grande précision réduit le bruit (moins de perte). Un niveau de bruit élevé amène parfois ugrep à rechercher des fichiers indexés qui ne correspondent pas. Nous appelons cela des « correspondances faussement positives ». Une plus grande précision nécessite des fichiers d'index plus volumineux. Normalement, nous nous attendons à un stockage d’indexation de 4 Ko ou moins par fichier en moyenne. Le minimum est de 128 octets de stockage d'index par fichier, à l'exclusion du nom de fichier et d'un en-tête d'index de 4 octets. Le maximum est de 64 Ko de stockage par fichier pour les très gros fichiers bruyants.
Lors de la recherche de fichiers indexés avec ugrep --index --stats , l'option --stats affiche les statistiques de recherche une fois la recherche basée sur l'indexation terminée. Lorsque de nombreux fichiers ne sont pas ignorés de la recherche en raison du bruit d'indexation (c'est-à-dire des faux positifs), une plus grande précision contribue à augmenter l'efficacité de l'indexation, ce qui peut accélérer la recherche.
Les fichiers UTF-16 et UTF-32 sont également indexés. L'indexeur les traite comme UTF-8 après les avoir convertis en interne en UTF-8 en index.
L'espace disque est économisé en archivant (zip/tar/pax/cpio) et en compressant les fichiers. D'un autre côté, la recherche d'archives et de fichiers compressés est beaucoup plus lente que la recherche de fichiers normaux. L'indexation des archives et des fichiers compressés avec ugrep-indexer -z -I et leur recherche avec ugrep -z -I --index PATTERN accélère la recherche, c'est-à-dire lorsque les archives et les fichiers compressés sont ignorés. D'un autre côté, les besoins en matière de stockage sur disque augmenteront avec l'ajout d'entrées de fichiers d'index pour les archives et les fichiers compressés. Notez que lorsque les archives et les fichiers compressés contiennent des binaires, l'option -I ignore ces binaires.
La surcharge de démarrage de ugrep --index pour construire des tables de hachage d'indexation dépend des modèles d'expression régulière. Si un modèle d'expression régulière est très "permissif", c'est-à-dire correspond à un grand nombre de modèles possibles, alors le temps de démarrage de ugrep --index augmente considérablement pour calculer les tables de hachage. Cela peut se produire lorsque de grandes classes de caractères Unicode et des caractères génériques sont utilisés, en particulier avec les répétitions * et + illimitées. Pour savoir comment le temps de démarrage augmente, utilisez l'option ugrep --index -r PATTERN /dev/null --stats=vm pour rechercher /dev/null avec votre PATTERN.
Les fichiers d'index doivent être très denses en contenu informatif et c'est le cas de ce nouvel algorithme d'indexation pour ugrep que j'ai conçu et implémenté. Plus un fichier d'index est dense, plus il représente avec précision les données du fichier d'origine. Cela rend difficile, voire impossible, la compression des fichiers d'index. C’est également un bon indicateur de l’efficacité pratique d’un fichier d’index.
