Por que as tuplas ocupam menos espaço na memória do que as listas?

A tupleocupa menos espaço de memória em Python:

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

enquanto lists ocupa mais espaço na memória:

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

O que acontece internamente no gerenciamento de memória Python?

Presumo que você esteja usando CPython e com 64 bits (obtive os mesmos resultados no meu CPython 2.7 de 64 bits). Pode haver diferenças em outras implementações Python ou se você tiver um Python de 32 bits.

Independentemente da implementação, lists são de tamanho variável enquanto tuples são de tamanho fixo.

Assim, tuples podem armazenar os elementos diretamente dentro da estrutura; por outro lado, as listas precisam de uma camada de indireção (ela armazena um ponteiro para os elementos). Essa camada de indireção é um ponteiro, em sistemas de 64 bits que é 64 bits, portanto, 8 bytes.

Mas há outra coisa que eles listfazem: eles alocam em excesso. Caso contrário, list.appendseria uma O(n)operação sempre - para torná-la amortizada O(1)(muito mais rápido !!!) ela superaloca. Mas agora ele precisa manter o controle do tamanho alocado e do tamanho preenchido (os tamanhos tuplesó precisam armazenar um tamanho, porque o tamanho alocado e preenchido são sempre idênticos). Isso significa que cada lista deve armazenar outro "tamanho" que em sistemas de 64 bits é um número inteiro de 64 bits, novamente 8 bytes.

Portanto, os lists precisam de pelo menos 16 bytes a mais de memória do que os tuples. Por que eu disse "pelo menos"? Por causa da superalocação. Superalocação significa que aloca mais espaço do que o necessário. No entanto, a quantidade de superalocação depende de "como" você cria a lista e do histórico de acréscimo / exclusão:

>>> 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

Imagens

Resolvi criar algumas imagens para acompanhar a explicação acima. Talvez sejam úteis

É assim que (esquematicamente) é armazenado na memória em seu exemplo. Eu destaquei as diferenças com os ciclos vermelhos (mão livre):

Na verdade, isso é apenas uma aproximação porque os intobjetos também são objetos Python e o CPython até reutiliza pequenos inteiros, então uma representação provavelmente mais precisa (embora não tão legível) dos objetos na memória seria:

Links Úteis:

• tuple struct no repositório CPython para Python 2.7
• list struct no repositório CPython para Python 2.7
• int struct no repositório CPython para Python 2.7

Observe que __sizeof__realmente não retorna o tamanho "correto"! Ele apenas retorna o tamanho dos valores armazenados. No entanto, quando você usa, sys.getsizeofo resultado é diferente:

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

Existem 24 bytes "extras". Eles são reais , essa é a sobrecarga do coletor de lixo que não é considerada no __sizeof__método. Isso porque geralmente você não deve usar métodos mágicos diretamente - use as funções que sabem como tratá-los, neste caso: sys.getsizeof(que na verdade adiciona a sobrecarga de GC ao valor retornado de __sizeof__).

Vou dar um mergulho mais profundo na base de código CPython para que possamos ver como os tamanhos são realmente calculados. Em seu exemplo específico , nenhuma superalocação foi realizada, então não tocarei nisso .

Vou usar valores de 64 bits aqui, como você.

O tamanho de lists é calculado a partir da seguinte função 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);
}

Aqui Py_TYPE(self)está uma macro que captura ob_typede self(retornando PyList_Type) enquanto _PyObject_SIZEoutra macro captura tp_basicsizedesse tipo. tp_basicsizeé calculado como sizeof(PyListObject)onde PyListObjectestá a estrutura da instância.

A PyListObjectestrutura possui três campos:

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

estes têm comentários (que cortei) explicando o que são, siga o link acima para lê-los. PyObject_VAR_HEADexpande-se em três campos de 8 byte ( ob_refcount, ob_typee ob_size) para uma 24contribuição byte.

Então, por enquanto resé:

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

ou:

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

Se a instância da lista tiver elementos que estão alocados. a segunda parte calcula sua contribuição. self->allocated, como o nome indica, contém o número de elementos alocados.

Sem quaisquer elementos, o tamanho das listas é calculado para ser:

>>> [].__sizeof__()
40

ou seja, o tamanho da estrutura da instância.

tupleobjetos não definem uma tuple_sizeoffunção. Em vez disso, eles usam object_sizeofpara calcular seu tamanho:

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);
}

Isso, como para lists, agarra o tp_basicsizee, se o objeto tiver um diferente de zero tp_itemsize(o que significa que ele tem instâncias de comprimento variável), ele multiplica o número de itens na tupla (pelos quais ele obtém via Py_SIZE) tp_itemsize.

tp_basicsizenovamente usa sizeof(PyTupleObject)onde a PyTupleObjectestrutura contém :

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

Portanto, sem nenhum elemento (ou seja, Py_SIZEretornos 0), o tamanho das tuplas vazias é igual a sizeof(PyTupleObject):

>>> ().__sizeof__()
24

Hã? Bem, aqui está uma esquisitice para a qual não encontrei uma explicação, o tp_basicsizede tuples é calculado da seguinte maneira:

sizeof(PyTupleObject) - sizeof(PyObject *)

por que um 8byte adicional é removido tp_basicsizeé algo que não consegui descobrir. (Veja o comentário de MSeifert para uma possível explicação)

Mas, essa é basicamente a diferença em seu exemplo específico . lists também mantêm vários elementos alocados que ajudam a determinar quando alocar em excesso novamente.

Agora, quando elementos adicionais são adicionados, as listas de fato realizam essa superalocação para obter anexos O (1). Isso resulta em tamanhos maiores, pois o de MSeifert cobre bem em sua resposta.

A resposta da MSeifert cobre isso amplamente; para mantê-lo simples, você pode pensar em:

tupleé imutável. Depois de definido, você não pode alterá-lo. Portanto, você sabe com antecedência quanta memória precisa alocar para esse objeto.

listé mutável. Você pode adicionar ou remover itens de ou para ele. Tem que saber o tamanho dele (para impl. Interno). Ele é redimensionado conforme necessário.

Não há refeições gratuitas - esses recursos têm um custo. Daí a sobrecarga de memória para listas.

O tamanho da tupla é prefixado, o que significa que na inicialização da tupla o interpretador aloca espaço suficiente para os dados contidos, e ponto final, dando-lhe imutável (não pode ser modificado), enquanto uma lista é um objeto mutável, portanto, implicando dinâmico alocação de memória, para evitar a alocação de espaço cada vez que você anexar ou modificar a lista (alocar espaço suficiente para conter os dados alterados e copiar os dados para eles), ele aloca espaço adicional para anexos futuros, modificações, ... resume tudo.