Comment grep fonctionne-t-il si vite?

Question

Je suis vraiment épaté par les fonctionnalités de GREP dans un shell. Avant, j’utilisais la méthode de sous-chaîne en java, mais maintenant, j’utilise GREP pour cela et il s’exécute en quelques secondes. Il est incroyablement plus rapide que le code java que j’écrivais. (selon mon expérience, je pourrais me tromper cependant)

Cela étant dit, je n'ai pas été en mesure de comprendre comment cela se passe? il n'y a pas non plus beaucoup de disponible sur le web.

Est-ce que quelqu'un peut m'aider avec ça?

Answer 1

En supposant que votre question concerne GNU grep précisément. Voici une note de l'auteur, Mike Haertel:

GNU grep est rapide, parce qu'il ÉVITE de REGARDER À TOUS les OCTETS d'ENTRÉE.

GNU grep est rapide car il s'EXÉCUTE TRÈS PEU d'INSTRUCTIONS POUR CHAQUE D'OCTETS qu'il ne regarder.

GNU grep utilise la célèbre Boyer-Moore algorithme, qui regarde en premier pour la dernière lettre de la chaîne cible, et utilise une table de recherche pour dire à quel point il peut sauter dans l'entrée lorsqu'il trouve un non-correspondance des caractères.

GNU grep également déroule la boucle interne de Boyer-Moore, et met en place les Boyer-Moore delta entrées de la table de telle manière qu'il n'a pas besoin d' faire le test de sortie de boucle à chaque déroulé étape. Le résultat de ceci est qui, à la limite, GNU grep moyennes de moins de 3 instructions x86 exécutée pour chaque entrée octet elle ressemble vraiment à (et il saute beaucoup octets entièrement).

GNU grep utilise raw Unix système d'entrée des appels et évite la copie de données après l'avoir lu. En outre, GNU grep ÉVITE la RUPTURE de L'ENTRÉE EN Les LIGNES. La recherche de retours à la ligne permettrait de ralentir grep par un facteur de plusieurs fois, parce que trouver les retours à la ligne, il faudrait regarder chaque octet!

Donc, au lieu d'utiliser orienté ligne d'entrée, GNU grep lit les données brutes en un grand tampon, les recherches de la mémoire tampon à l'aide de Boyer-Moore, et seulement quand il trouve une correspondance t-il aller chercher le cadre des retours à la ligne (Certaines options en ligne de commande comme -n désactiver cette optimisation.)

Cette réponse est un sous-ensemble des informations prises à partir d' ici.

Answer 2

Pour ajouter à Steve excellente réponse.

Il peut ne pas être connu de tous, mais la commande grep est presque toujours plus rapide lorsque grepping pour une plus longue motif de chaîne que de courte durée, car, en plus de modèle, de Boyer-Moore pouvez sauter en avant dans une foulée plus longue à atteindre, même mieux sublinéaire vitesses:

Exemple:

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

La forme longue est de 35% plus rapide!

Comment venir? Boyer-Moore consructs un skip-avant le tableau de la structure de la chaîne, et chaque fois qu'il y a une incompatibilité, il choisit le plus long saut possible (depuis le dernier char de première) avant de comparer un seul char, à l'entrée de l'omble chevalier dans le saut de la table.

Voici une vidéo expliquant Boyer Moore

Une autre idée fausse commune (pour GNU grep) est qu' fgrep plus rapide que de l' grep. f en fgrep ne pas défendre "rapide", ça signifie "fixe" (voir la page de man), et puisque les deux sont le même programme, et les deux utilisent Boyer-Moore, il n'y a pas de différence de vitesse entre eux lors de la recherche pour les chaînes de caractères sans regexp de caractères spéciaux. La seule raison pour laquelle j'utilise fgrep , c'est quand il y a une regexp un caractère spécial (comme ., []ou *) je ne veux pas être interprétés comme tels. Et même alors, le plus portable/forme standard de l' grep -F qui est privilégiée fgrep.