Pourquoi la soustraction est-elle plus rapide que l'addition en Python ?

Question

J'optimisais un code Python et j'ai tenté l'expérience suivante :

import time

start = time.clock()
x = 0
for i in range(10000000):
    x += 1
end = time.clock()

print '+=',end-start

start = time.clock()
x = 0
for i in range(10000000):
    x -= -1
end = time.clock()

print '-=',end-start

La deuxième boucle est plus rapide de manière fiable, d'un poil à 10%, selon le système sur lequel je l'exécute. J'ai essayé de varier l'ordre des boucles, le nombre d'exécutions, etc. et cela semble toujours fonctionner.

Étranger,

for i in range(10000000, 0, -1):

(c'est-à-dire exécuter la boucle à l'envers) est plus rapide que

for i in range(10000000):

même lorsque le contenu des boucles est identique.

Qu'est-ce qui se passe, et y a-t-il une leçon de programmation plus générale à en tirer ?

Answer 1

Je peux reproduire ce phénomène sur mon Q6600 (Python 2.6.2) en augmentant la plage à 100000000 :

('+=', 11.370000000000001)
('-=', 10.769999999999998)

Tout d'abord, quelques observations :

• Cela représente 5 % pour une opération triviale. C'est significatif.
• La vitesse des opcodes natifs d'addition et de soustraction n'est pas pertinente. Elle est dans le bruit de fond, complètement éclipsée par l'évaluation du bytecode. Il s'agit d'une ou deux instructions natives sur des milliers.
• Le bytecode génère exactement le même nombre d'instructions ; la seule différence est la suivante INPLACE_ADD vs. INPLACE_SUBTRACT et +1 contre -1.

En regardant la source Python, je peux faire une supposition. Ceci est géré dans ceval.c, dans PyEval_EvalFrameEx . INPLACE_ADD a un bloc de code supplémentaire significatif, pour gérer la concaténation des chaînes de caractères. Ce bloc n'existe pas dans INPLACE_SUBTRACT puisque vous ne pouvez pas soustraire des chaînes de caractères. Cela signifie que INPLACE_ADD contient plus de code natif. Selon la façon dont le code est généré par le compilateur, ce code supplémentaire peut être en ligne avec le reste du code INPLACE_ADD, ce qui signifie que les additions peuvent toucher le cache d'instructions plus durement que les soustractions. Ce site pourrait provoquer des accès supplémentaires au cache L2, ce qui pourrait entraîner une différence de performances significative.

Cela dépend fortement du système utilisé (les différents processeurs ont des quantités de cache et des architectures de cache différentes), du compilateur utilisé, y compris la version particulière et les options de compilation (différents compilateurs décideront différemment quels bits de code sont sur le chemin critique, ce qui détermine comment le code d'assemblage est regroupé), etc.

En outre, la différence est inversée dans Python 3.0.1 (+ : 15.66, - : 16.71) ; il ne fait aucun doute que cette fonction critique a beaucoup changé.

Answer 2

$ python -m timeit -s "x=0" "x+=1"
10000000 loops, best of 3: 0.151 usec per loop
$ python -m timeit -s "x=0" "x-=-1"
10000000 loops, best of 3: 0.154 usec per loop

On dirait que vous avez biais de mesure

Answer 3

Je pense que la "leçon générale de programmation" est que c'est realmente Il est difficile de prévoir, uniquement en regardant le code source, quelle séquence d'instructions sera la plus rapide. Les programmeurs de tous niveaux se laissent souvent prendre au piège de ce type d'optimisation "intuitive". Ce que vous pensez savoir n'est pas forcément vrai.

Il n'y a simplement aucun substitut à la réalité mesure la performance de votre programme. Félicitations pour cette démarche ; répondre pourquoi nécessite sans aucun doute de se plonger dans l'implémentation de Python, dans ce cas.

Avec les langages compilés par octet tels que Java, Python et .NET, il ne suffit même pas de mesurer les performances sur une seule machine. Les différences entre les versions des machines virtuelles, les implémentations de la traduction du code natif, les optimisations spécifiques au processeur, etc. rendront ce type de question de plus en plus difficile à résoudre.

Answer 4

"La deuxième boucle est plus rapide de manière fiable..."

C'est votre explication, là. Réorganisez votre script pour que le test de soustraction soit chronométré en premier, puis l'addition, et soudain l'addition redevient l'opération la plus rapide :

-= 3.05
+= 2.84

Il est évident que quelque chose se passe dans la seconde moitié du script qui le rend plus rapide. Mon devinez est que le premier appel à range() est plus lent car python doit allouer suffisamment de mémoire pour une liste aussi longue, mais il est capable de réutiliser cette mémoire pour le deuxième appel à range() :

import time
start = time.clock()
x = range(10000000)
end = time.clock()
del x
print 'first range()',end-start
start = time.clock()
x = range(10000000)
end = time.clock()
print 'second range()',end-start

Quelques exécutions de ce script montrent que le temps supplémentaire nécessaire pour la première range() est à l'origine de la quasi-totalité de la différence de temps entre "+=" et "-=" observée ci-dessus :

first range() 0.4
second range() 0.23

Answer 5

Il est toujours bon, lorsque vous posez une question, de préciser la plate-forme et la version de Python que vous utilisez. Parfois, cela n'a pas d'importance. Ceci n'est PAS une de ces fois :

1. time.clock() n'est approprié que sous Windows. Jetez votre propre code de mesure et utilisez -m timeit comme le démontre la réponse de pixelbeat.

2. Python 2.X range() construit une liste. Si vous utilisez Python 2.x, remplacez range con xrange et voir ce qui se passe.

3. Python 3.X int est l'outil de Python2.X long .