List limits

[Jeff Epler]

I'm referring to Python 2.2's C headers as I answer this question.  I
believe some of may have changed by 2.4.

The number of elements in a "variable-sized object" (those with
Py_VAR_HEAD; I believe this includes lists, tuples, and strings) is
stored in a platform 'int'.

On most (desktop) systems, this means the limit of any sized object is
no more than 2**31-1, or about 2 billion.

On those same systems, a list object of length 128 million, give or
take, approximately 512 megabytes of memory will be allocated for the
list object itself (4 bytes for each pointer-to-element).  If each
element of the list is distinct, those objects will each require
additional memory---The smallest useful Python object takes around 16
bytes, IIRC, which would bring the total memory required to around 2560
megabytes if I didn't screw up my arithmetic.  This is close to (or
over, depending on the system) the maximum amount of physical RAM these
machines can accomodate, and the maximum amount of address space
available to a single program.

While performing list-resizing operations, there may be a temporary need
for two copies of the list object itself, bumping the memory used up to 3
gigs.

Finally, the speed of some operations (l.index(item), l.pop(0),
l.insert(0, item)) are related linearly to the size of the list, so your
program may slow down as the lists it manipulates grow.  Others, such as
l[i], l.pop(), and l.append(item), are constant-time or amortized-constant-
time.

Jeff
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20041220/d4350424/attachment.sig>