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

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

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

GNOME to Report on Struggle With Patent Troll

The GNOME Foundation is charged with patent infringement 9,936,086 in the Shotwell photo manager
22 October 2019   77

The GNOME Foundation reported on actions taken to protect against legal action brought forward by Rothschild Patent Imaging LLC, a patent troll company. Rothschild Patent Imaging LLC proposed withdrawing the lawsuit in exchange for the purchase of a license to use the patent at Shotwell. The license amount is expressed in a five-digit number. Despite the fact that buying a license would be the easiest way out, and litigation would require a lot of money and hassle, the GNOME Foundation decided not to agree to the deal and fight to the end.

Consent would jeopardize other open source projects that could potentially be victims of this patent troll. As long as the patent used for lawsuits, covering obvious and widely used methods of working with images, continues to be valid, it can be used as a weapon to carry out other attacks. A special fund called the GNOME Patent Troll Defense Fund has been set up to finance the protection of GNOME in court and to invalidate a patent (for example, by proving the facts of earlier use of the technologies described in the patent).

Shearman & Sterling was involved in the defense of the GNOME Foundation, which has already sent three documents to the court:

  1. Application for the complete dismissal of the case. The defense considers that the patent appearing in the case is insolvent, and the technologies described in it are not applicable for the protection of intellectual property in software;
  2. The answer to the lawsuit, which calls into question the fact that GNOME should be the defendant in such claims. The document made an attempt to prove that the patent specified in the lawsuit cannot be used to make claims against Shotwell and any other free software.
  3. A counterclaim that will prevent Rothschild Patent Imaging LLC from retreating and choosing a less obstinate victim to attack when it understands the seriousness of GNOME’s intention to fight for invalidating the patent.

The GNOME Foundation is charged with patent infringement 9,936,086 in the Shotwell photo manager. The patent is dated 2008 and describes a technique for wirelessly connecting an image capture device (telephone, web-camera) to an image-receiving device (computer) and then selectively transmitting images with filtering by date, location and other parameters. According to the plaintiff, for the infringement of the patent, it is sufficient to have the import function from the camera, the ability to group images according to certain criteria and send images to external sites (for example, a social network or photo service).