Pourquoi les tuples prennent-ils moins de place en mémoire que les listes?

Un tuple prend moins d’espace mémoire en Python:

 >>> a = (1,2,3) >>> a.__sizeof__() 48 

alors que la list s prend plus d’espace mémoire:

 >>> b = [1,2,3] >>> b.__sizeof__() 64 

Que se passe-t-il en interne sur la gestion de la mémoire Python?

Je suppose que vous utilisez CPython et 64 bits (j’ai obtenu les mêmes résultats sur mon CPython 2.7 64 bits). Il pourrait y avoir des différences dans d’autres implémentations Python ou si vous avez un Python 32 bits.

Indépendamment de l’implémentation, les list sont de taille variable alors que les tuple sont de taille fixe.

Les tuple s peuvent donc stocker les éléments directement dans la structure, les listes, en revanche, nécessitent une couche d’indirection (qui stocke un pointeur sur les éléments). Cette couche d’indirection est un pointeur sur les systèmes 64 bits 64 bits, donc 8 octets.

Mais il y a une autre chose que la list fait: ils sur-atsortingbuent. Sinon, list.append serait une opération O(n) toujours – pour le rendre amorti O(1) (beaucoup plus rapide !!!) il est sur-alloué. Mais maintenant, il doit garder une trace de la taille allouée et de la taille remplie (les tuple n’ont besoin que de stocker une taille, car les tailles allouées et remplies sont toujours identiques). Cela signifie que chaque liste doit stocker une autre “taille” qui, sur les systèmes 64 bits, est un entier 64 bits, à nouveau 8 octets.

Les list donc besoin d’au moins 16 octets de mémoire de plus que les tuple . Pourquoi ai-je dit “au moins”? En raison de la surallocation. Une surallocation signifie qu’il alloue plus d’espace que nécessaire. Cependant, le montant de la surallocation dépend de “comment” créer la liste et de l’historique des ajouts / suppressions:

 >>> l = [1,2,3] >>> l.__sizeof__() 64 >>> l.append(4) # sortingggers re-allocation (with over-allocation), because the original list is full >>> l.__sizeof__() 96 >>> l = [] >>> l.__sizeof__() 40 >>> l.append(1) # re-allocation with over-allocation >>> l.__sizeof__() 72 >>> l.append(2) # no re-alloc >>> l.append(3) # no re-alloc >>> l.__sizeof__() 72 >>> l.append(4) # still has room, so no over-allocation needed (yet) >>> l.__sizeof__() 72 

Images

J’ai décidé de créer des images pour accompagner l’explication ci-dessus. Peut-être que ceux-ci sont utiles

Voici comment (schématiquement) il est stocké en mémoire dans votre exemple. J’ai mis en évidence les différences avec les cycles rouges (à main levée):

entrer la description de l'image ici

C’est en fait juste une approximation, car les objects int sont aussi des objects Python et CPython réutilise même les petits entiers. Une représentation probablement plus précise (mais pas aussi lisible) des objects en mémoire serait:

entrer la description de l'image ici

Liens utiles:

  • tuple struct dans le repository CPython pour Python 2.7
  • struct struct dans le repository CPython pour Python 2.7
  • int struct dans le repository CPython pour Python 2.7

Notez que __sizeof__ ne __sizeof__ pas vraiment la taille “correcte”! Il ne renvoie que la taille des valeurs stockées. Cependant, lorsque vous utilisez sys.getsizeof le résultat est différent:

 >>> import sys >>> l = [1,2,3] >>> t = (1, 2, 3) >>> sys.getsizeof(l) 88 >>> sys.getsizeof(t) 72 

Il y a 24 octets “supplémentaires”. Celles-ci sont réelles , c’est la surcharge du garbage collector qui n’est pas prise en compte dans la méthode __sizeof__ . C’est parce que vous n’êtes généralement pas supposé utiliser les méthodes magiques directement – utilisez les fonctions qui savent les gérer, dans ce cas: sys.getsizeof (qui ajoute réellement la surcharge GC à la valeur renvoyée par __sizeof__ ).

Je vais plonger plus profondément dans la base de code CPython pour voir comment les tailles sont réellement calculées. Dans votre exemple spécifique , aucune surallocation n’a été effectuée. Je ne vais donc pas y revenir .

Je vais utiliser les valeurs 64 bits ici, comme vous.


La taille de la list s est calculée à partir de la fonction suivante, list_sizeof :

 static PyObject * list_sizeof(PyListObject *self) { Py_ssize_t res; res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*); return PyInt_FromSsize_t(res); } 

Ici, Py_TYPE(self) est une macro qui récupère le ob_type d’ ob_type de self (renvoyant PyList_Type ) tandis que _PyObject_SIZE est une autre macro qui récupère tp_basicsize de ce type. tp_basicsize est calculé en tant que sizeof(PyListObject)PyListObject est la structure de l’instance.

La structure PyListObject comporte trois champs:

 PyObject_VAR_HEAD # 24 bytes PyObject **ob_item; # 8 bytes Py_ssize_t allocated; # 8 bytes 

ceux-ci ont des commentaires (que j’ai coupé) expliquant ce qu’ils sont, suivez le lien ci-dessus pour les lire. PyObject_VAR_HEAD développe en trois champs de 8 octets ( ob_refcount , ob_type et ob_size ), soit une consortingbution de 24 octets.

Donc pour l’instant res est:

 sizeof(PyListObject) + self->allocated * sizeof(void*) 

ou:

 40 + self->allocated * sizeof(void*) 

Si l’instance de liste comporte des éléments alloués. la deuxième partie calcule leur consortingbution. self->allocated , comme son nom l’indique, contient le nombre d’éléments alloués.

Sans aucun élément, la taille des listes est calculée comme suit:

 >>> [].__sizeof__() 40 

c’est-à-dire la taille de la structure de l’instance.


tuple objects tuple ne définissent pas de fonction tuple_sizeof . Au lieu de cela, ils utilisent object_sizeof pour calculer leur taille:

 static PyObject * object_sizeof(PyObject *self, PyObject *args) { Py_ssize_t res, isize; res = 0; isize = self->ob_type->tp_itemsize; if (isize > 0) res = Py_SIZE(self) * isize; res += self->ob_type->tp_basicsize; return PyInt_FromSsize_t(res); } 

Ceci, comme pour les list s, récupère le tp_basicsize et, si l’object a un tp_itemsize zéro (ce qui signifie qu’il a des instances de longueur variable), il multiplie le nombre d’éléments dans le tuple (via Py_SIZE ) avec tp_itemsize .

tp_basicsize utilise à nouveau sizeof(PyTupleObject) où la structure PyTupleObject contient :

 PyObject_VAR_HEAD # 24 bytes PyObject *ob_item[1]; # 8 bytes 

Donc, sans aucun élément (c’est-à-dire que Py_SIZE renvoie 0 ), la taille des tuples vides est égale à sizeof(PyTupleObject) :

 >>> ().__sizeof__() 24 

hein? Eh bien, voici une singularité à laquelle je n’ai pas trouvé d’explication, le tp_basicsize des tuple s est en fait calculé comme suit:

 sizeof(PyTupleObject) - sizeof(PyObject *) 

pourquoi 8 octets supplémentaires ont été supprimés de tp_basicsize est quelque chose que je n’ai pas pu découvrir. (Voir le commentaire de MSeifert pour une explication possible)


Mais, fondamentalement, c’est la différence dans votre exemple spécifique . list conservent également un certain nombre d’éléments alloués, ce qui aide à déterminer à quel moment il faut les surallouer à nouveau.

Maintenant, lorsque des éléments supplémentaires sont ajoutés, les listes effectuent effectivement cette surallocation afin d’atteindre les ajouts O (1). Cela se traduit par de plus grandes tailles que MSeifert couvre bien dans sa réponse.

Réponse MSeifert couvre largement; pour restr simple, vous pouvez penser à:

tuple est immuable. Une fois défini, vous ne pouvez pas le changer. Vous savez donc à l’avance combien de mémoire vous devez allouer pour cet object.

list est mutable. Vous pouvez append ou supprimer des éléments vers ou depuis celui-ci. Il doit en connaître la taille (pour les impl. Internes). Il redimensionne au besoin.

Il n’y a pas de repas gratuits – ces fonctionnalités ont un coût. D’où la surcharge en mémoire pour les listes.

La taille du tuple est préfixée, ce qui signifie qu’à l’initialisation du tuple, l’interprète alloue suffisamment d’espace pour les données contenues, et c’est la fin de celle-ci, c’est immuable allocation de mémoire, pour éviter d’allouer de l’espace chaque fois que vous ajoutez ou modifiez la liste (allouez suffisamment d’espace pour contenir les données modifiées et y copiez les données), il alloue de l’espace supplémentaire pour les futures ajouts, modifications, etc. résume.