Il y avait déjà des articles sur Habré sur les détails d'implémentation du
gestionnaire de mémoire de CPython,
Pandas , j'ai écrit un article sur l'
implémentation du dictionnaire .
Il semblerait que vous pouvez écrire sur un type entier régulier? Cependant, tout n'est pas si simple et le type entier n'est pas si évident.
Si vous vous demandez pourquoi
x * 2 est plus rapide que x << 1 .
Et comment lancer l'astuce suivante:
>>> 42 == 4 True >>> 42 4 >>> 1 + 41 4
Alors vous devriez lire cet article.
Il n'y a pas de types primitifs en python - toutes les variables sont des objets et sont allouées dans la mémoire dynamique. Dans le même temps, les entiers sont représentés par un seul type (nous ne considérons pas
décimal ) - PyLongObject. L'implémentation et les déclarations se trouvent dans les fichiers longobject.h, longintrepr.h et longobject.c.
struct _longobject { PyObject_VAR_HEAD
Dans tout objet dans CPython, il y a deux champs: ob_refcnt - compteur de références à l'objet et ob_type - pointeur vers le type de l'objet; pour les objets qui peuvent changer leur longueur, le champ ob_size est ajouté - la taille allouée actuelle (utilisée peut être inférieure).
Ainsi, un type entier est représenté par un tableau de longueur variable à partir de chiffres séparés, donc python prêt à l'emploi prend en charge l'arithmétique longue, dans la deuxième version du langage il y avait un type distinct d'entiers «ordinaires». Les entiers «longs» ont été créés en utilisant la lettre L ou, si le résultat des opérations a provoqué un débordement par des ordinaires, dans la troisième version il a été décidé de le refuser.
La valeur entière stockée par la structure _longobject est égale à:
En tant que bit, le type non signé 32 bits (uint32_t) sur les systèmes 64 bits et le type court non signé 16 bits sur les systèmes 32 bits sont utilisés.
Les algorithmes utilisés dans l'implémentation imposent des restrictions strictes sur le SHIFT de la formule précédente, en particulier, il doit être divisé par 15, donc maintenant cpython prend en charge deux valeurs: 30 et 15, respectivement, pour les systèmes 64 et 32 bits. Pour les valeurs négatives, ob_size a une valeur négative, zéro est donné par un nombre pour lequel ob_size = 0.
Lors de l'exécution d'opérations arithmétiques, l'interpréteur vérifie la longueur actuelle des opérandes, si les deux se composent d'un seul bit, alors l'arithmétique standard est effectuée.
static PyObject * long_add(PyLongObject *a, PyLongObject *b) { ...
La multiplication a une structure similaire, en plus, l'interpréteur implémente
l'algorithme de Karatsuba et
la quadrature rapide , cependant, ils ne sont pas effectués pour chaque "longue multiplication", mais seulement pour des nombres suffisamment grands, le nombre de chiffres dans lequel sont donnés par deux constantes:
static PyObject * long_mul(PyLongObject *a, PyLongObject *b) { ...
Cependant, les commandes shift n'ont pas de contrôle pour le cas des entiers "courts", elles sont toujours exécutées pour le cas de l'arithmétique longue. Par conséquent, la multiplication par 2 est plus rapide que le décalage. Il est intéressant de noter que la division est plus lente que le décalage à droite, ce qui ne vérifie pas non plus le cas des entiers à un chiffre. Mais la division est plus compliquée: il existe une méthode qui calcule d'abord le quotient, puis le reste, NULL lui est transmis, si vous devez calculer une chose, c'est-à-dire que la méthode doit également vérifier ce cas, tout cela augmente les frais généraux.
La fonction de comparaison n'a pas non plus de cas particulier pour les entiers «courts».
static int long_compare(PyLongObject *a, PyLongObject *b) { Py_ssize_t sign;
Tableaux (listes) de nombres
Lors de la création d'une variable de type entier, l'interpréteur doit allouer une zone suffisante dans la mémoire dynamique, puis définir le compteur de référence (type ssize_t), un pointeur pour taper PyLongObject, la taille actuelle du tableau de bits (également ssize_t) et initialiser le tableau lui-même. Pour les systèmes 64 bits, la taille de structure minimale est: 2 * ssize_t + pointeur + chiffre = 2 * 8 + 8 + 4 = 28 octets. Des problèmes supplémentaires apparaissent lors de la création de listes de nombres: étant donné que les nombres ne sont pas de type primitif et que les listes en python stockent des références à des objets, les objets ne sont pas séquentiellement en mémoire dynamique.
Cette disposition ralentit l'itération sur le tableau: en fait, un accès aléatoire est effectué, ce qui rend impossible de prédire les transitions.
Afin d'éviter une allocation excessive de mémoire dynamique, ce qui ralentit le temps de fonctionnement et contribue à la fragmentation de la mémoire, l'optimisation est implémentée en cpython: lors de la phase de démarrage, un tableau de petits entiers est pré-alloué: de -5 à 256.
#ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257
Par conséquent, la liste des nombres en cpython est représentée en mémoire comme suit:
Il est possible d'accéder à la liste présélectionnée de petits entiers du script, armée de
cet article et du module ctypes standard:
Avertissement: Le code suivant est fourni tel quel, l'auteur n'assume aucune responsabilité et ne peut garantir l'état de l'interprète, ainsi que la santé mentale de vous et de vos collègues, après avoir exécuté ce code.
import ctypes
Honest PyLongObject est stocké dans cette liste, c'est-à-dire qu'ils ont un compteur de référence, par exemple, vous pouvez savoir combien de zéros votre script et l'interpréteur utilisent.
De l'implémentation interne d'entiers, il s'ensuit que l'arithmétique en cpython ne peut pas être rapide, où d'autres langages itèrent séquentiellement sur le tableau, lisant des nombres dans des registres et appelant directement plusieurs instructions de processeur, cpython est balisé dans toute la mémoire, exécutant des méthodes plutôt compliquées. Dans le cas le plus simple des entiers mono-bit, dans lequel il suffirait d'appeler une instruction, l'interpréteur doit comparer les tailles, puis créer un objet en mémoire dynamique, remplir les champs de service, et lui renvoyer un pointeur; de plus, ces actions nécessitent un verrou GIL. Vous comprenez maintenant pourquoi la bibliothèque numpy est née et pourquoi elle est si populaire.
Je voudrais terminer l'article sur le type entier en cpython, soudainement, avec des informations sur le type booléen.
Le fait est que pendant longtemps en python il n'y avait pas de type séparé pour les variables booléennes, toutes les fonctions logiques retournaient 0 et 1. Cependant,
ils ont décidé d'introduire un nouveau type. Dans le même temps, il a été mis en œuvre comme un type enfant à l'ensemble.
PyTypeObject PyBool_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0)
De plus, chacune des valeurs du type booléen est un singleton, une variable booléenne est un pointeur vers une instance de True ou False (None est implémenté de manière similaire).
struct _longobject _Py_FalseStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 0) { 0 } }; struct _longobject _Py_TrueStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 1) { 1 } }; static PyObject * bool_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *x = Py_False; long ok; if (!_PyArg_NoKeywords("bool", kwds)) return NULL; if (!PyArg_UnpackTuple(args, "bool", 0, 1, &x)) return NULL; ok = PyObject_IsTrue(x); if (ok < 0) return NULL; return PyBool_FromLong(ok); } PyObject *PyBool_FromLong(long ok) { PyObject *result; if (ok) result = Py_True; else result = Py_False; Py_INCREF(result); return result; }
PyObject_IsTrue (x) est un mécanisme délicat pour calculer une valeur booléenne, vous pouvez le voir
ici dans la section sur la fonction booléenne ou dans la
documentation .
Un tel héritage conduit à des effets amusants, tels que l'égalité exacte de True et 1, l'incapacité d'avoir True et 1 comme clés dans le dictionnaire et l'ensemble, et l'admissibilité des opérations arithmétiques sur le type booléen:
>>> True == 1 True >>> {True: "true", 1: "one"} {True: 'one'} >>> True * 2 + False / (5 * True) - (True << 3) -6.0 >>> False < -1 False
Le langage python est magnifique pour sa flexibilité et sa lisibilité, cependant, il faut garder à l'esprit que tout cela a un prix, par exemple, sous la forme d'abstractions et de frais généraux superflus, auxquels nous ne pensons ou ne devinons pas souvent. J'espère que cet article vous a permis de dissiper un peu le «brouillard de guerre» sur le code source de l'interprète, peut-être même de vous inciter à l'étudier. Le code de l'interpréteur est très facile à lire, presque comme le code sur python lui-même, et l'étudier vous permettra non seulement d'apprendre comment l'interpréteur est implémenté, mais aussi d'intéressantes solutions algorithmiques et système, ainsi que d'écrire éventuellement du code plus efficace ou de devenir développeur de cpython lui-même.