Efficacité de l'indexation des listes (python 2 vs python 3)

Question

En répondant à une autre question j'ai suggéré d'utiliser timeit pour tester la différence entre l'indexation d'une liste avec des entiers positifs et des entiers négatifs. Voici le code :

import timeit
t=timeit.timeit('mylist[99]',setup='mylist=list(range(100))',number=10000000)
print (t)
t=timeit.timeit('mylist[-1]',setup='mylist=list(range(100))',number=10000000)
print (t)

J'ai exécuté ce code avec python 2.6 :

$ python2.6 test.py
0.587687015533
0.586369991302

Je l'ai ensuite exécuté avec python 3.2 :

$ python3.2 test.py
0.9212150573730469
1.0225799083709717

Puis je me suis gratté la tête, j'ai fait une petite recherche sur Google et j'ai décidé de poster ces observations ici.

Système d'exploitation : OS-X (10.5.8) -- Intel Core2Duo

Cela me semble être une différence assez importante (un facteur de plus de 1,5). Quelqu'un a-t-il une idée de la raison pour laquelle python3 est tellement plus lent, surtout pour une opération aussi courante ?

EDIT

J'ai exécuté le même code sur mon ordinateur de bureau Ubuntu Linux (Intel i7) et obtenu des résultats comparables avec python 2.6 et python 3.2. Il semble qu'il s'agisse d'un problème qui dépend du système d'exploitation (ou du processeur) (d'autres utilisateurs constatent le même comportement sur des machines Linux - voir les commentaires).

EDIT 2

La bannière de démarrage a été demandée dans l'une des réponses, alors voilà :

Python 2.6.4 (r264:75821M, Oct 27 2009, 19:48:32) 
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin

et :

Python 3.2 (r32:88452, Feb 20 2011, 10:19:59) 
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin

UPDATE

Je viens d'installer des versions récentes de python2.7.3 et python3.2.3 à partir de http://www.python.org/download/

Dans les deux cas, j'ai pris le

"Python x.x.3 Mac OS X 32-bit i386/PPC Installer (pour Mac OS X 10.3 jusqu'à 10.6 [2])".

puisque je suis sur OS X 10.5. Voici les nouveaux temps (qui sont raisonnablement cohérents à travers plusieurs essais) :

python 2.7

$python2.7 test.py
0.577006101608
0.590042829514

python 3.2.3

$python3.2 test.py
0.8882801532745361
1.034242868423462

Answer 1

Cela semble être un artefact de certaines constructions de Python 3.2. La meilleure hypothèse à ce stade est que toutes les versions 32 bits d'Intel présentent ce ralentissement, mais aucune version 64 bits. Lisez la suite pour plus de détails.

Vous n'avez pas fait assez de tests pour déterminer quoi que ce soit. En répétant votre test plusieurs fois, j'ai obtenu des valeurs allant de 0,31 à 0,54 pour le même test, ce qui représente une variation énorme.

J'ai donc exécuté votre test avec 10x le numéro, et repeat=10 en utilisant un tas d'installations différentes de Python2 et Python3. En jetant les résultats du haut et du bas, en faisant la moyenne des 8 autres, et en divisant par 10 (pour obtenir un nombre équivalent à vos tests), voici ce que j'ai vu :

 1. 0.52/0.53 Lion 2.6
 2. 0.49/0.50 Lion 2.7
 3. 0.48/0.48 MacPorts 2.7
 4. 0.39/0.49 MacPorts 3.2
 5. 0.39/0.48 HomeBrew 3.2

Donc, il semble que la 3.2 est en fait légèrement plus rapide avec [99] et à peu près à la même vitesse avec [-1] .

Cependant, sur une machine 10.5, j'ai obtenu ces résultats :

 1. 0.98/1.02 MacPorts 2.6
 2. 1.47/1.59 MacPorts 3.2

Sur la machine originale (Lion), j'ai exécuté en mode 32 bits et j'ai obtenu ceci :

 1. 0.50/0.48 Homebrew 2.7
 2. 0.75/0.82 Homebrew 3.2

Il semble donc que ce soit le format 32 bits qui importe, et non Leopard ou Lion, gcc 4.0 ou gcc 4.2 ou clang, les différences de matériel, etc. Il serait utile de tester les constructions 64 bits sous Leopard, avec différents compilateurs, etc., mais malheureusement ma boîte Leopard est un Intel Mini de première génération (avec un CPU Core Solo 32 bits), donc je ne peux pas faire ce test.

Comme preuve circonstancielle supplémentaire, j'ai effectué toute une série d'autres tests rapides sur la boîte Lion, et il semble que 32-bit 3.2 est ~50% plus lent que 2.x, tandis que 64-bit 3.2 est peut-être un peu plus rapide que 2.x. Mais si nous voulons vraiment confirmer cela, quelqu'un doit choisir et exécuter une vraie suite de benchmark.

Quoi qu'il en soit, je pense qu'à ce stade, lors de l'optimisation de la branche 3.x, personne n'a fait beaucoup d'efforts pour construire des Macs i386 32 bits. Ce qui est en fait un choix raisonnable pour eux.

Ou, alternativement, ils n'ont même pas fait beaucoup d'efforts pour le 32-bit i386. Cette possibilité pourrait expliquer pourquoi l'OP a vu 2.x et 3.2 donner des résultats similaires sur une boîte linux, alors qu'Otto Allmendinger a vu 3.2 être aussi plus lent que 2.6 sur une boîte linux. Mais comme aucun d'entre eux n'a mentionné s'ils utilisaient linux 32 bits ou 64 bits, il est difficile de savoir si cela est pertinent.

Il y a encore beaucoup d'autres possibilités que nous n'avons pas écartées, mais celle-ci semble être la meilleure.

Answer 2

Voici un code qui illustre au moins une partie de la réponse :

$ python
Python 2.7.3 (default, Apr 20 2012, 22:44:07) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> t=timeit.timeit('mylist[99]',setup='mylist=list(range(100))',number=50000000)
>>> print (t)
2.55517697334
>>> t=timeit.timeit('mylist[99L]',setup='mylist=list(range(100))',number=50000000)
>>> print (t)
3.89904499054

$ python3
Python 3.2.3 (default, May  3 2012, 15:54:42) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> t=timeit.timeit('mylist[99]',setup='mylist=list(range(100))',number=50000000)
>>> print (t)
3.9906489849090576

python3 n'a pas l'ancien type int.

Answer 3

Python 3 range() est la version Python 2 xrange() . Si vous voulez simuler le programme Python 2 range() dans le code Python 3, vous devez utiliser list(range(num) . Plus le num est, la plus grande différence sera observée avec votre code original.

L'indexation doit être indépendante de ce qui est stocké à l'intérieur de la liste, car celle-ci ne stocke que les références aux objets cibles. Ces références ne sont pas typées et sont toutes du même type. Le type liste est donc une structure de données homogène -- techniquement. L'indexation consiste à transformer la valeur de l'index en adresse de départ + offset. Le calcul de l'offset est très efficace avec tout au plus une soustraction. C'est une opération supplémentaire très bon marché par rapport aux autres opérations.