Why tuples use less space in memory than lists in Python?

Small tutorial on basic classes in Python with code examples 
17 October 2017   2592

Let's create a Python tuple:

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

and list

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

Tuple will use less memory than list. Let's figure out why.

 lists are variable-sized while tuples are fixed-size.

So tuples can store the elements directly inside the struct, lists on the other hand need a layer of indirection (it stores a pointer to the elements). This layer of indirection is a pointer, on 64bit systems that's 64bit, hence 8bytes.

But there's another thing that lists do: They over-allocate. Otherwise list.append would be an O(n) operation always - to make it amortized O(1) (much faster) it over-allocates. But now it has to keep track of the allocated size and the filled size (tuples only need to store one size, because allocated and filled size are always identical). That means each list has to store another "size" which on 64bit systems is a 64bit integer, again 8 bytes.

So lists need at least 16 bytes more memory than tuples. Because of the over-allocation. Over-allocation means it allocates more space than needed. However, the amount of over-allocation depends on "how" you create the list and the append/deletion history:

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

Some handy links on this topic:

  • tuple struct
  • list struct

Two BIPs For Upcoming Taproot Softfork to be Published

As reported, new BIPs describe the version of SegWit based on the signatures of Schnorr, Taproot, Merkle branches and the semantics of the script system
07 May 2019   316

Peter Wuille, a well-known Bitcoin developer and Blockstream employee, has published two proposals to improve the first cryptocurrency protocol (BIP), which involves the implementation of softfork to implement Taproot technology.

In recent years, the developers have published several separate proposals, including on the introduction of merklized abstract syntax trees (MAST), the signatures of Shnorr and Taproot itself. Probably, these updates can be combined in a single softfork, since the successive implementation, according to Vella, will be at the expense of efficiency.

The new BIPs describe the version of SegWit based on the signatures of Schnorr, Taproot, and Merkle branches, as well as the semantics of the script system. These proposals focus exclusively on the technologies mentioned and do not include other functionality that can be implemented independently.

The update code is available for review and edits in the repository on GitHub, and according to it, is written in Python.