Pourquoi le coreutils est-il plus lent que Python?

20

J'ai écrit le script suivant pour tester la vitesse de la fonctionnalité de tri de Python:

from sys import stdin, stdout
lines = list(stdin)
lines.sort()
stdout.writelines(lines)

J'ai ensuite comparé cela à la sortcommande coreutils sur un fichier contenant 10 millions de lignes:

$ time python sort.py <numbers.txt >s1.txt
real    0m16.707s
user    0m16.288s
sys     0m0.420s

$ time sort <numbers.txt >s2.txt 
real    0m45.141s
user    2m28.304s
sys     0m0.380s

La commande intégrée a utilisé les quatre processeurs (Python n'en a utilisé qu'un) mais a pris environ 3 fois plus de temps à s'exécuter! Ce qui donne?

J'utilise Ubuntu 12.04.5 (32 bits), Python 2.7.3 et sort8.13

augurar
la source
@goldilocks Oui, regardez l'utilisateur en temps réel.
augurar
Huh - tu as raison. Apparemment, il a été parallélisé dans coreutils 8.6.
goldilocks
Pouvez-vous utiliser --buffer-sizepour spécifier l' sortutilisation de toute la mémoire physique disponible et voir si cela aide?
iruvar
@ 1_CR Essayé avec 1 Go de tampon, aucun changement significatif dans le timing. Il n'en utilisait qu'environ 0,6 Go, donc augmenter la taille de la mémoire tampon ne serait pas utile.
augurar

Réponses:

22

Le commentaire d'Izkata a révélé la réponse: des comparaisons locales spécifiques. La sortcommande utilise les paramètres régionaux indiqués par l'environnement, tandis que Python utilise par défaut une comparaison de l'ordre des octets. La comparaison de chaînes UTF-8 est plus difficile que la comparaison de chaînes d'octets.

$ time (LC_ALL=C sort <numbers.txt >s2.txt)
real    0m5.485s
user    0m14.028s
sys     0m0.404s

Et ça.

augurar
la source
Et comment se comparent-ils pour les cordes UTF-8?
Gilles 'SO- arrête d'être méchant'
@Gilles Modification du script Python à utiliser locale.strxfrmpour trier, le script a pris ~ 32 secondes, encore plus vite que sortmais beaucoup moins.
augurar
3
Python 2.7.3 fait une comparaison d'octets, mais Python3 ferait une comparaison de mots unicode. Python3.3 est environ deux fois plus lent que Python2.7 pour ce "test". La surcharge de compression des octets bruts dans la représentation Unicode est encore plus élevée que celle des objets de compression déjà importants que Python 2.7.3 doit faire.
Anthon
2
J'ai trouvé le même ralentissement avec cut, et d'autres aussi. Sur plusieurs machines , j'ai maintenant export LC_ALL=Cdans .bashrc. Mais attention: cela casse essentiellement wc(sauf wc -l), pour ne citer qu'un exemple. Les "mauvais octets" ne comptent pas du tout ...
Walter Tross
1
Ce problème de performances se produit également avec grep: vous pouvez obtenir une amélioration substantielle des performances lors de la réception de fichiers volumineux en désactivant UTF-8, en particulier lors de l'exécutiongrep -i
Adrian Pronk
7

Il s'agit plus d'une analyse supplémentaire que d'une réponse réelle, mais elle semble varier en fonction des données triées. Tout d'abord, une lecture de base:

$ printf "%s\n" {1..1000000} > numbers.txt

$ time python sort.py <numbers.txt >s1.txt
real    0m0.521s
user    0m0.216s
sys     0m0.100s

$ time sort <numbers.txt >s2.txt
real    0m3.708s
user    0m4.908s
sys     0m0.156s

OK, python est beaucoup plus rapide. Cependant, vous pouvez rendre les coreutils sortplus rapides en lui disant de trier numériquement:

$ time sort <numbers.txt >s2.txt 
real    0m3.743s
user    0m4.964s
sys     0m0.148s

$ time sort -n <numbers.txt >s2.txt 
real    0m0.733s
user    0m0.836s
sys     0m0.100s

C'est beaucoup plus rapide mais python gagne toujours par une large marge. Maintenant, réessayons mais avec une liste non triée de numéros 1M:

$ sort -R numbers.txt > randomized.txt

$ time sort -n <randomized.txt >s2.txt 
real    0m1.493s
user    0m1.920s
sys     0m0.116s

$ time python sort.py <randomized.txt >s1.txt
real    0m2.652s
user    0m1.988s
sys     0m0.064s

Le coreutils sort -nest plus rapide pour les données numériques non triées (bien que vous puissiez modifier le cmpparamètre du tri python pour le rendre plus rapide). Coreutils sortest encore beaucoup plus lent sans le -ndrapeau. Alors, qu'en est-il des caractères aléatoires, pas des nombres purs?

$ tr -dc 'A-Za-z0-9' </dev/urandom | head -c1000000 | 
    sed 's/./&\n/g' > random.txt

$ time sort  <random.txt >s2.txt 
real    0m2.487s
user    0m3.480s
sys     0m0.128s

$ time python sort.py  <random.txt >s2.txt 
real    0m1.314s
user    0m0.744s
sys     0m0.068s

Python bat toujours coreutils mais avec une marge beaucoup plus petite que ce que vous montrez dans votre question. Étonnamment, il est encore plus rapide lorsque l'on regarde des données alphabétiques pures:

$ tr -dc 'A-Za-z' </dev/urandom | head -c1000000 |
    sed 's/./&\n/g' > letters.txt

$ time sort   <letters.txt >s2.txt 
real    0m2.561s
user    0m3.684s
sys     0m0.100s

$ time python sort.py <letters.txt >s1.txt
real    0m1.297s
user    0m0.744s
sys     0m0.064s

Il est également important de noter que les deux ne produisent pas la même sortie triée:

$ echo -e "A\nB\na\nb\n-" | sort -n
-
a
A
b
B

$ echo -e "A\nB\na\nb\n-" | python sort.py 
-
A
B
a
b

Curieusement, l' --buffer-sizeoption ne semblait pas faire beaucoup (ou aucune) différence dans mes tests. En conclusion, probablement en raison des différents algorithmes mentionnés dans la réponse de goldilock, le python sortsemble être plus rapide dans la plupart des cas, mais GNU numérique lesort bat sur les nombres non triés 1 .


L'OP a probablement trouvé la cause première, mais pour être complet, voici une comparaison finale:

$ time LC_ALL=C sort   <letters.txt >s2.txt 
real    0m0.280s
user    0m0.512s
sys     0m0.084s


$ time LC_ALL=C python sort.py   <letters.txt >s2.txt 
real    0m0.493s
user    0m0.448s
sys     0m0.044s

1 Quelqu'un avec plus de python-fu que je devrais essayer de tester l'ajustement list.sort()pour voir la même vitesse peut être obtenu en spécifiant la méthode de tri.

terdon
la source
5
Le tri Python présente un avantage supplémentaire en termes de vitesse, basé sur votre dernier échantillon: l'ordre numérique ASCII. sortsemble faire un peu de travail supplémentaire pour les comparaisons majuscules / minuscules.
Izkata
@Izkata C'est tout! Voir ma réponse ci-dessous.
augurar
1
En fait, python a un peu de surcharge en créant ses chaînes internes à partir de l' stdinentrée brute . Conversion ceux des numéros ( lines = map(int, list(stdin))) et arrière ( stdout.writelines(map(str,lines))) rend plus lent aller tout le tri, jusqu'à de 0.234s réel 0.720s sur ma machine.
Anthon
6

Les deux implémentations sont en C, donc des règles du jeu équitables. Coreutils utilise sort apparemment l' algorithme de fusion . Mergesort effectue un nombre fixe de comparaisons qui augmente logarithmiquement à la taille d'entrée, c'est-à-dire grand O (n log n).

Le tri de Python utilise un tri hybride de fusion / insertion unique, timsort , qui effectuera un nombre variable de comparaisons avec le meilleur des cas O (n) - vraisemblablement, sur une liste déjà triée - mais est généralement logarithmique (logiquement, vous ne peut pas être meilleur que logarithmique pour le cas général lors du tri).

Étant donné deux types logarithmiques différents, l'un pourrait avoir un avantage sur l'autre sur un ensemble de données particulier. Un tri de fusion traditionnel ne varie pas, il fonctionnera donc de la même manière quelles que soient les données, mais par exemple, le tri rapide (également logarithmique), qui varie, fonctionnera mieux sur certaines données mais pire sur d'autres.

Un facteur de trois (ou plus de 3, car il sortest parallélisé) est assez important, ce qui me fait me demander s'il n'y a pas de contingence ici, comme le passage sortau disque (l' -Toption semble impliquer que c'est le cas). Cependant, votre faible temps système vs utilisateur implique que ce n'est pas le problème.

boucle d'or
la source
Bon point que les deux implémentations sont écrites en C. Je suis sûr que si j'implémentais un algorithme de tri en Python, ce serait beaucoup, beaucoup plus lent.
augurar
Soit dit en passant, le fichier se compose de valeurs flottantes générées de manière aléatoire entre 0 et 1, il ne devrait donc pas y avoir trop de structure à exploiter.
augurar