Pourquoi les tuples prennent moins d'espace en mémoire que les listes?

A tupleprend moins d'espace mémoire en Python:

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

alors que lists 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 avec 64 bits (j'ai obtenu les mêmes résultats sur mon CPython 2.7 64 bits). Il peut 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, lists sont de taille variable tandis que tuples sont de taille fixe.

Pour que tuples puisse stocker les éléments directement à l'intérieur de la structure, les listes par contre ont besoin d'une couche d'indirection (elle stocke un pointeur vers les éléments). Cette couche d'indirection est un pointeur, sur les systèmes 64 bits soit 64 bits, donc 8 octets.

Mais il y a une autre chose à listfaire: ils surallouent. Dans le cas contraire list.appendserait une O(n)opération toujours - pour le rendre amorti O(1)(beaucoup plus rapide !!!) il sur-Alloue. Mais maintenant, il doit garder une trace de la taille allouée et de la taille remplie (il tuplesuffit de stocker une taille, car la taille allouée et la taille remplie sont toujours identiques). Cela signifie que chaque liste doit stocker une autre "taille" qui sur les systèmes 64 bits est un entier de 64 bits, encore une fois 8 octets.

Donc, il listfaut au moins 16 octets de mémoire de plus que tuples. Pourquoi ai-je dit «au moins»? En raison de la surallocation. La surallocation signifie qu'elle alloue plus d'espace que nécessaire. Cependant, le montant de la surallocation dépend de la «façon» dont vous créez la liste et de l'historique des ajouts / suppressions:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers 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 quelques images pour accompagner l'explication ci-dessus. Peut-être que ceux-ci sont utiles

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

Ce n'est en fait qu'une approximation car les intobjets sont également des objets Python et CPython réutilise même de petits entiers, donc une représentation probablement plus précise (bien que pas aussi lisible) des objets en mémoire serait:

Liens utiles:

• tuple struct dans le référentiel CPython pour Python 2.7
• list struct dans le référentiel CPython pour Python 2.7
• int struct dans le référentiel CPython pour Python 2.7

Notez que __sizeof__cela ne renvoie pas vraiment la taille "correcte"! Il ne renvoie que la taille des valeurs stockées. Cependant lorsque vous utilisez sys.getsizeofle 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". Ce sont réels , c'est la surcharge du ramasse-miettes qui n'est pas prise en compte dans la __sizeof__méthode. C'est parce que vous n'êtes généralement pas censé utiliser directement les méthodes magiques - utilisez les fonctions qui savent comment les gérer, dans ce cas: sys.getsizeof(qui ajoute en fait la surcharge GC à la valeur renvoyée __sizeof__).

Je vais plonger plus profondément dans la base de code CPython afin que nous puissions voir comment les tailles sont réellement calculées. Dans votre exemple spécifique , aucune sur-allocation n'a été effectuée, je ne vais donc pas en parler .

Je vais utiliser des valeurs 64 bits ici, comme vous l'êtes.

La taille de lists 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);
}

Voici Py_TYPE(self)une macro qui saisit le ob_typede self(retour PyList_Type) tandis _PyObject_SIZEqu'une autre macro qui saisit tp_basicsizede ce type. tp_basicsizeest calculé comme sizeof(PyListObject)où se PyListObjecttrouve la structure d'instance.

La PyListObjectstructure 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és) expliquant ce qu'ils sont, suivez le lien ci-dessus pour les lire. PyObject_VAR_HEADse développe en trois champs de 8 octets ( ob_refcount, ob_typeet ob_size) donc une 24contribution d'octets.

Donc pour l'instant resc'est:

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

ou:

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

Si l'instance de liste a des éléments alloués. la deuxième partie calcule leur contribution. 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 d'instance.

tupleles objets ne définissent pas une tuple_sizeoffonction. Au lieu de cela, ils utilisent object_sizeofpour 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 lists, saisit le tp_basicsizeet, si l'objet a un non-zéro tp_itemsize(ce qui signifie qu'il a des instances de longueur variable), il multiplie le nombre d'éléments dans le tuple (qu'il obtient via Py_SIZE) avec tp_itemsize.

tp_basicsizeutilise à nouveau sizeof(PyTupleObject)où la PyTupleObjectstructure contient :

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

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

>>> ().__sizeof__()
24

hein? Eh bien, voici une bizarrerie pour laquelle je n'ai pas trouvé d'explication, le tp_basicsizede tuples est en fait calculé comme suit:

sizeof(PyTupleObject) - sizeof(PyObject *)

pourquoi un 8octet supplémentaire est supprimé tp_basicsizeest quelque chose que je n'ai pas pu découvrir. (Voir le commentaire de MSeifert pour une explication possible)

Mais, c'est fondamentalement la différence dans votre exemple spécifique . lists conservent également un certain nombre d'éléments alloués, ce qui permet de déterminer le moment de surallouer à nouveau.

Désormais, lorsque des éléments supplémentaires sont ajoutés, les listes effectuent effectivement cette surallocation afin d'obtenir des appendices O (1). Cela se traduit par des tailles plus grandes car MSeifert couvre bien sa réponse.

La réponse de MSeifert le couvre largement; pour faire simple, vous pouvez penser à:

tupleest immuable. Une fois défini, vous ne pouvez pas le modifier. Vous savez donc à l'avance la quantité de mémoire à allouer à cet objet.

listest mutable. Vous pouvez y ajouter ou supprimer des éléments. Il doit en connaître la taille (pour implication interne). Il se redimensionne selon les besoins.

Il n'y a pas de repas gratuits - ces capacités ont un coût. D'où la surcharge de mémoire pour les listes.

La taille du tuple est préfixée, ce qui signifie qu'à l'initialisation du tuple, l'interpréteur alloue suffisamment d'espace pour les données contenues, et c'est la fin, ce qui le rend immuable (ne peut pas être modifié), alors qu'une liste est un objet mutable impliquant donc dynamique allocation de mémoire, donc 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 copier les données), il alloue de l'espace supplémentaire pour les ajouts futurs, les modifications, ... résume.