Mon programme python s'exécute plus rapidement que ma version java du même programme. Ce qui donne?
mise à Jour: 2009-05-29
Merci pour toutes les suggestions et conseils. j'ai utilisé vos suggestions pour faire exécuter mon code de production 2,5 fois plus vite en moyenne que mon meilleur résultat il y a quelques jours. a la fin j'ai pu faire du code java le plus rapide.
Leçons:
mon exemple de code ci-dessous montre l'insertion des ints primitifs mais le code de production stocke en fait des chaînes (ma mauvaise). Lorsque J'ai corrigé que le temps d'exécution python est passé de 2,8 secondes à 9,6. Donc dès le départ, le java était en fait plus rapide pour stocker des objets.
Mais il ne s'arrête pas là. J'avais été l'exécution du programme java comme suit:
java-xmx1024m SpeedTest
mais si vous définissez la taille initiale du tas comme suit vous obtenez une énorme amélioration:
java -Xms1024m -Xmx1024m SpeedTest
Ce simple changement a réduit le temps d'exécution de plus de 50%. Donc le résultat final pour mon SpeedTest est python 9.6 secondes. Java 6,5 secondes.
Question Originale:
j'avais le code python suivant:
import time
import sys
def main(args):
iterations = 10000000
counts = set()
startTime = time.time();
for i in range(0, iterations):
counts.add(i)
totalTime = time.time() - startTime
print 'total time =',totalTime
print len(counts)
if __name__ == "__main__":
main(sys.argv)
et il s'est exécuté en environ 3,3 secondes sur ma machine mais je voulais le rendre plus rapide et j'ai donc décidé de le programmer en java. J'ai supposé que parce que java est compilé et est généralement considéré comme étant plus rapide que python, je verrais quelques gros gains.
Voici la java code:
import java.util.*;
class SpeedTest
{
public static void main(String[] args)
{
long startTime;
long totalTime;
int iterations = 10000000;
HashSet counts = new HashSet((2*iterations), 0.75f);
startTime = System.currentTimeMillis();
for(int i=0; i<iterations; i++)
{
counts.add(i);
}
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(counts.size());
}
}
Donc ce code java fait la même chose que le code python. Mais il s'est exécuté en 8,3 secondes au lieu de 3,3.
j'ai extrait cet exemple simple d'un exemple réel pour simplifier les choses. L'élément essentiel est que j'ai (ensemble ou hashSet) qui se termine avec beaucoup de membres comme dans l'exemple.
Voici mes questions:
Pourquoi mon implémentation python est plus rapide que mon java la mise en œuvre?
y a-t-il une meilleure structure de données à utiliser que le hashSet (java) pour tenir une collection unique?
Qu'est-ce qui rendrait l'implémentation python plus rapide?
Qu'est-ce qui accélérerait l'implémentation java?
mise à jour:
Merci à tous ceux qui ont contribué jusqu'à présent. Permettez-moi d'ajouter quelques détails.
je n'ai pas repris mon code de production parce qu'il est assez complexe. Et générerait beaucoup de distraction. Le cas que je présente ci-dessus est le plus simplifié possible. Par là, je veux dire que l'appel Java put semble être beaucoup plus lent que l'add () du jeu python.
l'implémentation java du code de production est également environ 2.5 - 3 fois plus lente que la version python -- tout comme la précédente.
Je ne me soucie pas de l'échauffement de la vm ou de la mise en service. Je veux juste comparer le code de mon heure de départ à mon heure totale. S'il vous plaît, ne vous souciez pas d'autres choses.
j'ai initialisé le hashset avec plus qu'assez de seaux pour qu'il n'ait jamais à ressasser. (Je saurai toujours à l'avance combien d'éléments la collection contiendra.) Je suppose que l'on pourrait argumenter que j'aurais dû l'initialiser aux itérations/0.75. Mais si vous l'essayez, vous verrez que le temps d'exécution n'est pas significativement affectée.
j'ai mis Xmx1024m pour ceux c'était curieux (ma machine a 4 Go de ram).
j'utilise la version java: Java (TM) SE Runtime Environment (build 1.6.0_13-b03).
dans la version de production de je stocke une chaîne (2-15 caractères) dans le hashSet donc je ne peux pas utiliser de primitives, bien que ce soit un cas intéressant.
j'ai lancé le code plusieurs fois. Je suis convaincu que le code python est entre 2,5 et 3 fois plus rapide que le code java.
20 réponses
vous ne testez pas vraiment Java contre Python, vous testez java.util.HashSet
en utilisant des entiers autoboxés par rapport à la manipulation des ensembles natifs et des entiers de Python.
apparemment, le côté Python dans ce microbenchmark particulier est en effet plus rapide.
j'ai essayé de remplacer le HashSet par TIntHashSet
GNU trove et atteint un facteur d'accélération entre 3 et 4, amenant Java légèrement en avance sur Python.
La vraie question est de savoir si votre code d'exemple est vraiment comme représentant de votre code d'application comme vous le pensez. Avez-vous lancé un profileur et déterminé que la plupart du temps CPU est passé à mettre un grand nombre d'ints dans un HashSet? Si non, l'exemple n'est pas pertinent. Même si la seule différence est que votre code de production stocke d'autres objets que des ints, leur création et le calcul de leur hashcode pourrait facilement dominer l'insertion set (et détruire totalement L'avantage de Python dans la manipulation des ints spécialement), ce qui rend toute cette question inutile.
je soupçonne que Python utilise la valeur entière elle-même comme son hachage et l'implémentation basée sur le hashtable de set utilise cette valeur directement. À partir des commentaires dans le source:
Ce n'est pas forcément mauvais! Au contraire, dans un tableau de taille 2**i, en tenant les bits d'ordre bas comme l'index de table initial est extrêmement rapide, et là il n'y a aucune collision pour les dicts indexés par une gamme contiguë de ints. La même chose est approximativement vraie lorsque les clés sont des chaînes "consécutives". Donc, ce donne un comportement plus qu'aléatoire dans les cas courants, et c'est très souhaitable.
ce microbenchmark est en quelque sorte un meilleur cas pour Python car il résulte en exactement zéro collisions de hachage. Alors que, si Javas HashSet ressasse les touches, il doit effectuer le travail supplémentaire et son comportement est bien pire avec les collisions.
si vous stockez la plage(itérations) dans une variable temporaire et faites un random.shuffle sur elle, avant la boucle, la durée d'exécution est plus de 2 fois plus lente, même si la création de shuffle et de liste se fait en dehors de la boucle.
une autre explication possible est que les sets en Python sont implémentés nativement en code C, tandis que les Hashsets en Java sont implémentés en Java lui-même. Ainsi, les sets en Python devraient être par nature beaucoup plus rapides.
d'après mon expérience, les programmes python tournent plus vite que les programmes java, malgré le fait que java est un langage un peu "inférieur". Incidemment, les deux langues sont compilées en code octet (c'est ce que ces .les fichiers pyc Sont -- vous pouvez les voir comme un peu comme .les fichiers de classe). Les deux langues sont des bytes-code interprétés sur une machine de pile virtuelle.
vous vous attendriez à ce que python soit plus lent à des choses comme, par exemple,a.b
. En java, que a.b
se résoudre en déréférence. Python, d'autre part, une ou plusieurs table de hachage recherches: vérifier l'étendue locale, vérifier la portée de module, vérifiez portée mondiale, vérifiez les builtins.
En résumé, il n'y a pas de réponse simple. Je ne m'attendrais pas à ce que l'une ou l'autre langue soit plus rapide pour tous les codes exemple.
Correction: plusieurs personnes ont fait remarquer que java n'est plus si mauvais pour la création d'objets. Donc, dans votre exemple, c'est autre chose. Peut-être que c'est l'autoboxing qui est cher, peut-être que l'algorithme de hachage par défaut de python est meilleur dans ce cas. Dans mon expérience pratique, quand je réécrit le code java en python, je vois toujours une augmentation des performances, mais cela pourrait être dû autant au langage qu'à la réécriture en général conduit à des performances amélioration.
j'aimerais dissiper quelques mythes que j'ai vus dans les réponses:
Java est compilé, oui, au bytecode mais finalement au code natif dans la plupart des environnements d'exécution. Les gens qui disent que C est intrinsèquement plus rapide ne racontent pas toute l'histoire, je pourrais faire un cas que les langues compilées par byte sont intrinsèquement plus rapides parce que le compilateur JIT peut faire des optimisations spécifiques à la machine qui ne sont pas disponibles pour les compilateurs à l'avance.
Un certain nombre de choses qui pourraient faire l' les différences sont les suivantes:
- les tables et les ensembles de hachage de Python sont les objets les plus fortement optimisés en Python, et la fonction de hachage de Python est conçue pour retourner des résultats similaires pour des entrées similaires: hachage d'un entier retourne simplement l'entier, garantissant que vous ne verrez jamais une collision dans une table de hachage d'entiers consécutifs en Python.
- un effet secondaire de ce qui précède est que le code Python aura une haute localisation de référence alors que vous accéderez à la table de hachage dans la séquence.
- Java fait un peu de boxe fantaisie et de déboxage des entiers quand vous les ajoutez aux collections. Du côté bonus, cela rend l'arithmétique beaucoup plus rapide en Java que Python (aussi longtemps que vous restez à l'écart de bignums) mais du côté négatif, cela signifie plus d'allocations que vous êtes habitué.
Edit: un TreeSet peut être plus rapide dans le cas d'une utilisation réelle, selon les patrons d'allocation. Mes commentaires ci-dessous traite uniquement de ce scénario simplifié. Cependant, je ne crois pas que ça ferait une différence très significative. La vraie question qui se pose ailleurs.
plusieurs personnes ici ont recommandé de remplacer le HashSet par un arbre. Cela ressemble à un conseil très étrange pour moi, puisqu'il n'y a aucun moyen qu'une structure de données avec o(log n) Temps d'insertion soit plus rapide alors une structure O (1) qui préalloque assez de seaux pour stocker tous les éléments.
Voici un code de test:
import java.util.*;
class SpeedTest
{
public static void main(String[] args)
{
long startTime;
long totalTime;
int iterations = 10000000;
Set counts;
System.out.println("HashSet:");
counts = new HashSet((2*iterations), 0.75f);
startTime = System.currentTimeMillis();
for(int i=0; i<iterations; i++) {
counts.add(i);
}
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(counts.size());
counts.clear();
System.out.println("TreeSet:");
counts = new TreeSet();
startTime = System.currentTimeMillis();
for(int i=0; i<iterations; i++) {
counts.add(i);
}
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(counts.size());
}
}
Et voici le résultat sur ma machine:
$ java -Xmx1024M SpeedTest
HashSet:
TOTAL TIME = 4.436
10000000
TreeSet:
TOTAL TIME = 8.163
10000000
plusieurs personnes ont également fait valoir que la boxe n'est pas un problème de performance et que la création d'objets est peu coûteuse. Bien qu'il soit vrai que la création d'un objet est rapide, elle n'est certainement pas aussi rapide que primitives:
import java.util.*;
class SpeedTest2
{
public static void main(String[] args)
{
long startTime;
long totalTime;
int iterations = 10000000;
System.out.println("primitives:");
startTime = System.currentTimeMillis();
int[] primitive = new int[iterations];
for (int i = 0; i < iterations; i++) {
primitive[i] = i;
}
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println("primitives:");
startTime = System.currentTimeMillis();
Integer[] boxed = new Integer[iterations];
for (int i = 0; i < iterations; i++) {
boxed[i] = i;
}
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
}
}
Résultat:
$ java -Xmx1024M SpeedTest2
primitives:
TOTAL TIME = 0.058
primitives:
TOTAL TIME = 1.402
de plus, la création d'un grand nombre d'objets entraîne des frais généraux supplémentaires du ramasseur d'ordures. Cela devient important lorsque vous commencez à garder des dizaines de millions d'objets vivants en mémoire.
j'ai trouver des repères pour être dénuée de sens. Je ne résous pas les problèmes qui ressemblent à l'affaire test. Il n'est pas très intéressant.
je préférerais voir une solution pour une solution d'algèbre linéaire significative en utilisant NumPy et JAMA. Peut-être que je vais essayer et faire un rapport avec les résultats.
Je ne suis pas trop familier avec python, mais je sais HashSet
ne peut pas contenir de primitives, quand vous dites counts.add(i)
i
il se autoboxed dans un new Integer(i)
appel. C'est sûrement ton problème.
si pour une raison quelconque vous aviez vraiment besoin d'un' ensemble 'd'entiers entre 0 et un grand n, c'est probablement mieux déclaré comme un'ensemble booléen [] = nouveau booléen[n]'. Ensuite, vous pourriez passer par le tableau et marquer les éléments qui sont dans le jeu comme 'true' sans encourir le au-dessus de création de n Objets Integer wrapper. Si vous voulez aller plus loin vous pouvez utiliser un byte[] de taille n/8 et utiliser les bits individuels directement. Ou peut-être BigInteger.
EDIT
arrêtez de voter ma réponse. Son tort.
EDIT
Non, vraiment, c'est mal. J'obtiens des performances comparables si je fais ce que la question suggère, peupler l'ensemble avec n entiers. si je remplace le contenu de la boucle for avec ceci:
Integer[] ints = new Integer[N];
for (int i = 0; i < N; ++i) {
ints[i] = i;
}
alors ça ne prend que 2 secondes. Si vous ne stockez pas L'entier du tout alors il faut moins de 200 millis. Forcer l'allocation de 10000000 objets entiers prend du temps, mais il semble que la plupart du temps est passé à l'intérieur de l'opération HashSet put.
d'Abord si c'est un programme que vous allez seulement à courir une fois, il faut un supplément de quelques secondes?
Deuxièmement, ce ne sont que des microbenchmarks. Les Microbenchmarks sont inutiles pour comparer les performances.
le démarrage a un certain nombre de problèmes.
le Java runtime est beaucoup plus grand que Python donc prend plus de temps à charger à partir du disque et prend plus de mémoire qui peut être important si vous échangez.
Si vous n'avez pas défini -Xms
il se peut que vous utilisiez le GC uniquement pour redimensionner le tas. Autant avoir le tas correctement dimensionné au début.
il est vrai que Java commence par interpréter puis compile. Environ 1 500 itérations pour Sun client [C1] Hotspot et 10 000 pour server [C2]. Serveur Hotspot vous donnera de meilleures performances éventuellement, mais prendre plus de mémoire. Nous pouvons voir le client Hotspot utiliser le serveur pour le code très fréquemment exécuté pour le meilleur des deux mondes. Toutefois, il ne s'agit généralement pas d'une question de secondes.
plus important encore, vous pouvez créer deux objets par itération. Pour la plupart du code, vous ne créeriez pas ces petits objets pour une telle proportion de l'exécution. TreeSet peut être mieux sur le nombre d'objets score, avec 6u14 et harmonie obtenir encore mieux.
Python peut éventuellement gagner en stockant de petits objets entiers dans des références au lieu d'avoir réellement un objet. Il s'agit sans aucun doute d'une bonne optimisation.
Un problème avec beaucoup de références est que vous mélangez beaucoup de code dans une méthode. Tu n'écrirais pas un code auquel tu tenais comme ça, n'est-ce pas? Alors pourquoi essayez-vous de tester les performances, ce qui est différent du code que vous aimeriez exécuter rapidement?
meilleure structure de données: quelque chose comme BitSet
semble logique (même si cela a ynchronisation, qui peut ou peut ne pas l'impact performance.)
Vous devez l'exécuter plusieurs fois afin d'obtenir une réelle idée de "comment rapide" chaque pistes. Le temps de démarrage de JVM [pour une personne] s'ajoute au temps d'exécution unique de la version Java.
vous créez aussi un HashSet avec une grande capacité initiale, ce qui signifie que le HashMap de soutien sera créé avec autant de slots disponibles, contrairement au Python où vous créez un jeu de base. Difficile de dire si cela entraverait cependant, comme quand votre HashSet grandit il devra réattribuer le stocké objet.
Utilisez-vous l'option-server avec le jvm? On ne peut pas tester la performance sans ça. (Vous devez également réchauffer la jvm avant de faire le test.)
en outre, vous voudrez probablement utiliser TreeSet<Integer>
. HashSet sera plus lent à long terme.
et quelle jvm utilisez-vous? La dernière je l'espère.
EDIT
quand je dis utiliser TreeSet, je veux dire en général, pas pour ce benchmark. TreeSet s'occupe de la question réelle de non even le hachage des objets. Si vous obtenez trop d'objets dans la même corbeille dans un HashSet, vous exécuterez environ O(n).
si vous voulez vraiment stocker des types primitifs dans un ensemble, et faire beaucoup de travail dessus, lancez votre propre ensemble en Java. Les classes génériques ne sont pas assez rapides pour l'informatique scientifique.
comme les mentions de fourmis Aasma, Python contourne le hachage et utilise l'entier directement. Java crée un objet entier (l'autoboxing), puis le jette dans un objet (dans votre implémentation). Cet objet doit aussi être hachuré pour être utilisé dans un jeu de hachage.
pour une comparaison amusante, essayez ceci:
Java
import java.util.HashSet;
class SpeedTest
{
public static class Element {
private int m_i;
public Element(int i) {
m_i = i;
}
}
public static void main(String[] args)
{
long startTime;
long totalTime;
int iterations = 1000000;
HashSet<Element> counts = new HashSet<Element>((int)(2*iterations), 0.75f);
startTime = System.currentTimeMillis();
for(int i=0; i<iterations; ++i)
{
counts.add(new Element(i));
}
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(counts.size());
}
}
Résultats:
$java SpeedTest
TOTAL TIME = 3.028
1000000
$java -Xmx1G -Xms1G SpeedTest
TOTAL TIME = 0.578
1000000
Python
#!/usr/bin/python
import time
import sys
class Element(object):
def __init__(self, i):
self.num = i
def main(args):
iterations = 1000000
counts = set()
startTime = time.time();
for i in range(0, iterations):
counts.add(Element(i))
totalTime = time.time() - startTime
print 'total time =',totalTime
print len(counts)
if __name__ == "__main__":
main(sys.argv)
Résultats:
$./speedtest.py
total time = 20.6943161488
1000000
comment ça pour "python est plus rapide que java"?
avec combien de mémoire avez-vous commencé le JVM? Il dépend? Quand j'exécute le JVM avec votre programme avec 1 Gig de RAM:
$ java -Xmx1024M -Xms1024M -classpath . SpeedTest
TOTAL TIME = 5.682
10000000
$ python speedtest.py
total time = 4.48310899734
10000000
si j'exécute le JVM avec moins de mémoire, cela prend plus de temps ... considérablement plus longue:
$ java -Xmx768M -Xms768M -classpath . SpeedTest
TOTAL TIME = 6.706
10000000
$ java -Xmx600M -Xms600M -classpath . SpeedTest
TOTAL TIME = 14.086
10000000
je pense que le HashSet
est le goulot d'étranglement des performances dans ce cas particulier. Si je remplace le HashSet
avec un LinkedList
, le programme est beaucoup plus rapide.
enfin -- notez que les programmes Java sont initialement interprétés et seules les méthodes qui sont appelés plusieurs fois sont compilés. Ainsi, vous comparez probablement Python à l'interpréteur de Java, pas au compilateur.
Juste un coup de poignard dans le noir ici, mais quelques optimisations que Python est Java n'est probablement pas:
- l'appel range () en Python crée tous les objets 10000000 à la fois, en code C optimisé. Java doit créer un objet entier à chaque itération, ce qui peut être plus lent.
- en Python, les ints sont immuables, donc vous pouvez simplement stocker une référence à un "42" global, par exemple, plutôt que d'allouer une fente pour l'objet. Je ne suis pas sûr comment Java boxed Comparer des objets entiers.
- de nombreux algorithmes et structures de données Python intégrés sont plutôt fortement optimisés pour des cas spéciaux. Par exemple, la fonction de hachage pour les entiers est tout simplement la fonction identité. Si Java utilise une fonction de hachage plus "intelligente", cela pourrait ralentir les choses un peu. Si la plupart de votre temps est consacré au code de structure de données, Je ne serais pas surpris du tout de voir Python battre Java étant donné la quantité d'efforts qui ont été consacrés au cours des années mise au point manuelle de L'implémentation Python C.
quelques changements pour Python plus rapide.
#!/usr/bin/python
import time
import sys
import psyco #<<<<
psyco.full()
class Element(object):
__slots__=["num"] #<<<<
def __init__(self, i):
self.num = i
def main(args):
iterations = 1000000
counts = set()
startTime = time.time();
for i in xrange(0, iterations):
counts.add(Element(i))
totalTime = time.time() - startTime
print 'total time =',totalTime
print len(counts)
if __name__ == "__main__":
main(sys.argv)
Avant
(env)~$ python speedTest.py
total time = 8.82906794548
1000000
Après
(env)~$ python speedTest.py
total time = 2.44039201736
1000000
maintenant une bonne vieille tricherie et ...
#!/usr/bin/python
import time
import sys
import psyco
psyco.full()
class Element(object):
__slots__=["num"]
def __init__(self, i):
self.num = i
def main(args):
iterations = 1000000
counts = set()
elements = [Element(i) for i in range(0, iterations)]
startTime = time.time();
for e in elements:
counts.add(e)
totalTime = time.time() - startTime
print 'total time =',totalTime
print len(counts)
if __name__ == "__main__":
main(sys.argv)
(env)~$ python speedTest.py
total time = 0.526521921158
1000000
je suis d'accord avec Gandalf sur le temps de démarrage. En outre, vous attribuez un énorme HashSet qui n'est pas du tout similaire à votre code python. J'imagine que si vous mettez ça sous un profileur, une bonne partie du temps serait passé là-bas. Aussi, l'insertion de nouveaux éléments est vraiment lente avec cette taille. Je regarderais TreeSet comme suggéré.
Le plus gros problème est probablement que ce que le code donné mesures mur -- ce que votre montre à des mesures -- mais ce qui doit être mesuré afin de comparer le code d'exécution est temps de traitement -- le temps que le cpu passe à exécuter ce code particulier et non d'autres tâches.
vous pouvez rendre le Java microbenchamrk beaucoup plus rapide, par ajout juste un petit extra.
HashSet counts = new HashSet((2*iterations), 0.75f);
devient
HashSet counts = new HashSet((2*iterations), 0.75f) {
@Override public boolean add(Object element) { return false; }
};
Simple, plus rapide et obtient le même résultat.
vous pourriez vouloir voir si vous pouvez "amorcer" le compilateur JIT dans la compilation de la section de code qui vous intéresse, en l'exécutant peut-être comme une fonction une fois à l'avance et en dormant brièvement après les mots. Cela pourrait permettre à la JVM de compiler la fonction en code natif.
eh Bien, si vous allez régler le programme Java, vous pouvez ainsi régler le programme en Python.
>>> import timeit
>>> timeit.Timer('x = set()\nfor i in range(10000000):\n x.add(i)').repeat(3, 1)
[2.1174559593200684, 2.0019571781158447, 1.9973630905151367]
>>> timeit.Timer('x = set()\nfor i in xrange(10000000):\n x.add(i)').repeat(3, 1)
[1.8742368221282959, 1.8714439868927002, 1.869229793548584]
>>> timeit.Timer('x = set(xrange(10000000))').repeat(3, 1)
[0.74582195281982422, 0.73061800003051758, 0.73396801948547363]
Juste à l'aide de xrange
rend environ 8% plus rapide sur ma machine. Et l'expression set(xrange(10000000))
construit exactement le même jeu, mais 2,5 x plus rapide (de 1.87 secondes à 0.74).
j'aime comment le réglage d'un programme Python le rend plus court. :) Mais Java peut faire la même chose. Comme tout le monde le sait, si vous voulez un ensemble dense de petits entiers en Java, vous ne utiliser une table de hachage. Vous utilisez un java.util.BitSet
!
BitSet bits = new BitSet(iterations);
startTime = System.currentTimeMillis();
bits.set(0, iterations, true);
totalTime = System.currentTimeMillis() - startTime;
System.out.println("TOTAL TIME = "+( totalTime/1000f) );
System.out.println(bits.cardinality());
Qui devrait être assez rapide. Malheureusement je n'ai pas le temps de le tester dès maintenant.