creating really big lists

[Hrvoje Niksic]

Dr Mephesto <dnhkng at googlemail.com> writes:

> I would like to create a pretty big list of lists; a list 3,000,000
> long, each entry containing 5 empty lists. My application will
> append data each of the 5 sublists, so they will be of varying
> lengths (so no arrays!).
>
> Does anyone know the most efficient way to do this? I have tried:
>
> list = [[[],[],[],[],[]] for _ in xrange(3000000)]

You might want to use a tuple as the container for the lower-level
lists -- it's more compact and costs less allocation-wise.

But the real problem is not list allocation vs tuple allocation, nor
is it looping in Python; surprisingly, it's the GC.  Notice this:

$ python
Python 2.5.1 (r251:54863, May  2 2007, 16:56:35)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import time
>>> t0=time.time(); l=[([],[],[],[],[]) for _ in xrange(3000000)];
>>> t1=time.time()
>>> t1-t0
143.89971613883972

Now, with the GC disabled:
$ python
Python 2.5.1 (r251:54863, May  2 2007, 16:56:35)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import gc
>>> gc.disable()
>>> import time
>>> t0=time.time(); l=[([],[],[],[],[]) for _ in xrange(3000000)];
>>> t1=time.time()
>>> t1-t0
2.9048631191253662

The speed difference is staggering, almost 50-fold.  I suspect GC
degrades the (amortized) linear-time list building into quadratic
time.  Since you allocate all the small lists, the GC gets invoked
every 700 or so allocations, and has to visit more and more objects in
each pass.  I'm not sure if this can be fixed (shouldn't the
generational GC only have to visit the freshly created objects rather
than all of them?), but it has been noticed on this group before.

If you're building large data structures and don't need to reclaim
cyclical references, I suggest turning GC off, at least during
construction.