Velocity Reviews > maximum length of a list & tuple

# maximum length of a list & tuple

Lupe
Guest
Posts: n/a

 04-08-2004
hi,

I'm finishing a small program which uses recursion for less than 100 levels.

Each time the function is called, it compares an element of a list (which is
a list too) to other elements, which all amounts to millions of
comparisons.

The program is working for short lists but not for longer ones. I think
there are two possible problems: either disk space is not enough to save
lists as the program is executed or there is a finite manageable list
lenght that is reached by the program.

hence my question:

is there a limit? which one? I'm using list.append()

I'll rewrite that part of the code and will overcome the problem, since I
only need a few elements of the list generated, but I'm still curious about

Lupe

Ed Suominen
Guest
Posts: n/a

 04-09-2004
I think the limit is 1000 recursion levels, but you shouldn't need to ever
get anywhere near that. Use generators to break up the iteration of your
list comparisons.

-Ed Suominen

Lupe wrote:

> hi,
>
> I'm finishing a small program which uses recursion for less than 100
> levels.
>
> Each time the function is called, it compares an element of a list (which
> is a list too) to other elements, which all amounts to millions of
> comparisons.
>
> The program is working for short lists but not for longer ones. I think
> there are two possible problems: either disk space is not enough to save
> lists as the program is executed or there is a finite manageable list
> lenght that is reached by the program.
>
> hence my question:
>
> is there a limit? which one? I'm using list.append()
>
> I'll rewrite that part of the code and will overcome the problem, since I
> only need a few elements of the list generated, but I'm still curious
>
>
> Lupe

Lupe
Guest
Posts: n/a

 04-09-2004
I just would like to know if there is any limit to a list or tuple.

Larry Bates
Guest
Posts: n/a

 04-09-2004
I've constructed lists with 100,000+ elements and
they have worked flawlessly.

FYI,
Larry Bates
Syscon, Inc.

"Lupe" <(E-Mail Removed)> wrote in message
news:c54lq3\$2pe1sf\$(E-Mail Removed)-berlin.de...
> hi,
>
> I'm finishing a small program which uses recursion for less than 100

levels.
>
> Each time the function is called, it compares an element of a list (which

is
> a list too) to other elements, which all amounts to millions of
> comparisons.
>
> The program is working for short lists but not for longer ones. I think
> there are two possible problems: either disk space is not enough to save
> lists as the program is executed or there is a finite manageable list
> lenght that is reached by the program.
>
> hence my question:
>
> is there a limit? which one? I'm using list.append()
>
> I'll rewrite that part of the code and will overcome the problem, since I
> only need a few elements of the list generated, but I'm still curious

>
>
> Lupe

Josiah Carlson
Guest
Posts: n/a

 04-10-2004
> I just would like to know if there is any limit to a list or tuple.

It depends on how much memory you have.

Run the following and the last thing it prints out is your limit...

c = 1
while c < 2**32:
try:
d = [1]*c
print c
c *= 2
except:
break

- Josiah

Tim Roberts
Guest
Posts: n/a

 04-11-2004
Josiah Carlson <(E-Mail Removed)> wrote:

>> I just would like to know if there is any limit to a list or tuple.

>
>It depends on how much memory you have.
>
>Run the following and the last thing it prints out is your limit...
>
> c = 1
> while c < 2**32:
> try:
> d = [1]*c
> print c
> c *= 2
> except:
> break

Interesting experiment. I get 64M on my 384MB machine, which suggests 4
bytes per list entry. Of course, now my swap file is packed full, and all
my apps are running slowly while they page themselves back in...
--
- Tim Roberts, http://www.velocityreviews.com/forums/(E-Mail Removed)
Providenza & Boekelheide, Inc.

Josiah Carlson
Guest
Posts: n/a

 04-11-2004
>>Run the following and the last thing it prints out is your limit...
>>
>> c = 1
>> while c < 2**32:
>> try:
>> d = [1]*c
>> print c
>> c *= 2
>> except:
>> break

>
>
> Interesting experiment. I get 64M on my 384MB machine, which suggests 4
> bytes per list entry. Of course, now my swap file is packed full, and all
> my apps are running slowly while they page themselves back in...

Far more than 4 bytes per list entry. 4 bytes to store the integers
themselves, but since integers are Python objects, and lists are arrays
of pointers to list objects, there is quite a bit of other extra stuff
attached.

I can't remember exactly how much extra stuff, but it can be found by
looking through the sources. You could check the amount of memory used
before, and the memory used at peak, and divide it by your 64M to find
out how much is used. I just did, but I'll also leave it as an exercise

- Josiah

Peter Hansen
Guest
Posts: n/a

 04-12-2004
Josiah Carlson wrote:

>>> Run the following and the last thing it prints out is your limit...
>>>
>>> c = 1
>>> while c < 2**32:
>>> try:
>>> d = [1]*c
>>> print c
>>> c *= 2
>>> except:
>>> break

>>
>>
>>
>> Interesting experiment. I get 64M on my 384MB machine, which suggests 4
>> bytes per list entry. Of course, now my swap file is packed full, and
>> all
>> my apps are running slowly while they page themselves back in...

>
>
> Far more than 4 bytes per list entry. 4 bytes to store the integers
> themselves, but since integers are Python objects, and lists are arrays
> of pointers to list objects, there is quite a bit of other extra stuff
> attached.

Actually, unless I'm mistaken that stores only one integer, and a whole
lot of references to it... which are just pointers (4 bytes each).

The technique is probably flawed in other ways, however, as it
is likely subject to memory fragmentation and other problems.

-Peter

Josiah Carlson
Guest
Posts: n/a

 04-12-2004
> Actually, unless I'm mistaken that stores only one integer, and a whole
> lot of references to it... which are just pointers (4 bytes each).
>
> The technique is probably flawed in other ways, however, as it
> is likely subject to memory fragmentation and other problems.

You can't just store the integer. How would you differentiate between
an integer in a list and a pointer? Answer: you must use PyIntObjects.
Use the source.

According to intobject.c, intobject.h and object.h, the structure of
every intobject (after the macros have been expanded) is as follows:

typedef struct {
int ob_refcnt;
_typeobject *ob_type;
long ob_ival;
} PyIntObject;

The size of each of those on a 32 bit machine is 4 bytes, plus the
pointer from the list (another 4 bytes), which leaves us with a total of
16 bytes per integer object in the list.

Checking the memory usage of Python before and after the creation of 1
million integer list, I get a /very/ consistant ~16 bytes per. That
would be 12 bytes for the object, and 4 bytes for each pointer in the
intobject.c and/or intobject.h, but yeah. Generally 16 bytes per integer.

As for memory fragmentation, considering how memory paging and
segmentation works, that's all underlying stuff that the OS deals with.
I could go on as to why it doesn't matter in this case (considering
the large mallocs necessary for the creation of large lists), but I'll
leave that as an exercise to the reader.

Again, from the source, 12 bytes for the object, 4 bytes for the pointer
in the list, total of 16 bytes per intobject in a list.

- Josiah

Peter Hansen
Guest
Posts: n/a

 04-12-2004
Josiah Carlson wrote:

>> Actually, unless I'm mistaken that stores only one integer, and a whole
>> lot of references to it... which are just pointers (4 bytes each).
>>
>> The technique is probably flawed in other ways, however, as it
>> is likely subject to memory fragmentation and other problems.

>
> You can't just store the integer. How would you differentiate between
> an integer in a list and a pointer? Answer: you must use PyIntObjects.
> Use the source.

Python does not recognize anything called "pointers" at the language
level, only internally.

What I was saying is that the only PyIntObject created was one with
the ob_ival of 1. Then a list containing one pointer to it was
created. Then it was replicated "c" times. Only one integer.

Please refute that claim rather than just arguing a bunch of other
points, none of which I dispute but all of which I claim are irrelevant
to the question at hand.

> Checking the memory usage of Python before and after the creation of 1
> million integer list, I get a /very/ consistant ~16 bytes per. That
> would be 12 bytes for the object, and 4 bytes for each pointer in the
> list.

Please post the expression you are using, for comparison.

> I could go on as to why it doesn't matter in this case (considering the
> large mallocs necessary for the creation of large lists), but I'll leave
> that as an exercise to the reader.

Please go on about it. I'd like to see where you discuss what happens
to the previously memory that was held in earlier lists, as it iterates
through the loop creating exponentially larger lists.

> Again, from the source, 12 bytes for the object, 4 bytes for the pointer
> in the list, total of 16 bytes per intobject in a list.

Nice. So each entry in the list is 4 bytes (as I indicated). And if
they all point to a single instance of the integer 1, how many extra
bytes do you think that allocates?

-Peter