>>> import timeit
>>>
>>> timeit.timeit("{i * (2**61 - 2) for i in range(10000)}", number=1)
0.00266260898206383
>>> timeit.timeit("{i * (2**61 - 1) for i in range(10000)}", number=1)
0.7670511459582485
Soiler !
Commençons par comprendre ce qui est écrit dans le code. Celui-ci commence par
importer le module timeit qui permet de mesurer le temps d'évaluation d'une
expression Python. Puis nous mesurons justement le temps d'évaluation de deux
expressions, les deux étants très similaire à un chiffre près.
Regardons cette première expression : {i * (2**61 - 2) for i in range(10000)}.
Il s'agit d'une set comprehension, c'est à dire un raccourcis syntaxique pour
créer un set[^1] (un ensemble au sens mathématique : sans doublons et sans
relation d'ordre). Étant donné que c'est un raccourcis, on peut l'exprimer sous
sa forme "déroulée", l'expression est strictement équivalente au code suivant :
result = set() # Création d'un set vide
for i in range(10000):
result.add(i * (2**61 - 2))On créé donc un set contenant les 10000 premiers nombres multiples de 2**61 -2.
Dans la deuxième expression, c'est quasiment la même chose qui est faite, à ceci
prêt que ce sont les multiples de 2**61 - 1 que l'on ajoute, et la création du
set est manifestement ici significativement plus longue (presque 300 fois plus
long). La question est donc de savoir pourquoi les multiples de ce nombre là
prennent autant de temps à être ajoutées à un set.
Regardons comment l'ajout à un
set
se fait en Python :
A set object is an unordered collection of distinct
hashable objects.
En interne, Python sauvegarde en fait les hash de chaque élément du set (on
dit aussi "l'empreinte" de l'élément, en français, bien que le terme "hash"
soit beaucoup plus souvent utilisé). Un hash est une suite de bit relativement
courte (souvent de la taille d'un entier) qui sert d'identifiant unique pour la
valeur d'un élément. Contrairement à id() en revanche, on souhaite que deux
objets différents mais égaux aient le même hash. Contrairement à id()
encore, on ne garanti l'unicité des hash qu'au sein d'un même set ou d'un
même dictionnaire (c'est à dire que deux valeurs égales peuvent avoir un hash
différent si elles se trouvent dans deux set différents, le but d'un hash
n'étant que de différentier les éléments au sein d'un set).
Pour ajouter un élément à un set il faut donc commencer par calculer son
hash. Beaucoup de méthodes sont possibles, mais une bonne fonction de hash
doit être rapide et ne pas créer de "collision". Une "collision" est le nom que
l'on donne à deux valeurs différentes qui auraient le même hash. La plupart
des fonctions de hash existantes commencent par faire un calcul rapide sur la
valeur hashée pour en déterminer un premier hash possible, puis vérifie si
ce hash n'a pas déjà été attribué à une autre valeur. Si c'est le cas, la
fonction calcule alors une nouvelle valeur en utilisant une stratégie
différente, afin d'éviter de générer une collision.
C'est un peu comme ça que fonctionne la méthode choisie par l'interpréteur de
référence, regardons de plus prêt (plus précisemment cette
fonction) :
/* Here x is a quantity in the range [0, _PyHASH_MODULUS); we
want to compute x * 2**PyLong_SHIFT + v->ob_digit[i] modulo
_PyHASH_MODULUS.
[…]
*/La fonction de hash de CPython utilise quelques optimisations compliquée, mais
le commentaire nous permet de comprendre que le hash d'une valeur est le
résultat d'un calcul modulo _PyHASH_MODULUS. C'est intéressant car cela
signifie que si le calcul est un multiple de _PyHASH_MODULUS, alors le hash
vaudra 0. Si nous hashons donc plusieurs fois à la suite des valeurs différentes
mais multiples de _PyHASH_MODULUS, cette fonction renverra 0 à chaque fois et
forcera l'appelant à trouver une stratégie alternative pour éviter la collision.
Cela semble être ce qui se passe mais cherchons la valeur exacte de ce
_PyHASH_MODULUS. C'est dans ce
fichier que
nous trouvons sa définition :
#if SIZEOF_VOID_P >= 8
# define _PyHASH_BITS 61
#else
# define _PyHASH_BITS 31
#endif
#define _PyHASH_MODULUS (((size_t)1 << _PyHASH_BITS) - 1)
_PyHASH_MODULUS vaut donc (1 << _PyHASH_BITS) - 1. _PyHASH_BITS vaut 61
sur les architectures 64 bits et 31 sur les architectures 32 bits. Les
ordinateurs récents (comme celui utilisé pour le sujet de l'énigme) ont une
architecture 64 bits, on peut donc remplacer _PyHASH_BITS par sa valeur dans
l'expression de _PyHASH_MODULUS, qui devient donc (1 << 61) - 1. L'opérateur
<< en C effectue un "shift" : on prend la représentation binaire de l'opérande
de gauche et on la décale d'autant de cases sur la gauche qu'indiqué dans
l'opérande de droite, donc 1 << 61 signifie "1 décalé de 61 bits sur la
gauche". On a vu en architecture que décaler un nombre d'un bit sur la gauche
revenait à le multiplier par deux, donc un shift de 61 sur la gauche revient à
multiplier 61 fois par deux, ce qui signifie que 1 << 61 vaut 261.
On y est : _PyHASH_MODULUS, la valeur du modulo utilisé pour calculer le hash
d'un objet dans CPython, est 261-1, or tous les nombres que l'on
ajoute au set dans la deuxième expression de l'énigme sont de la forme i * (2**61 - 1), c'est à dire des multiples de 261-1. Cela signifie que
quand la fonction set.add() calcule le hash d'un élément que l'on ajoute au
set, la fonction de hash de CPython lui renvoie 0 à chaque fois, la
forçant à trouver une stratégie alternative de calcul de hash pour chaque
élément, ce qui prend énormément de temps.
[1]: https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset et
https://docs.python.org/3/tutorial/datastructures.html#sets
@Dettorer I see two "Égnime 5"