Creating a List of Empty Lists

[Duncan Booth]

Robin Becker <robin at jessikat.fsnet.co.uk> wrote in 
news:LIGj15A6Vc1$EwNO at jessikat.fsnet.co.uk:

> 
> C:\tmp>\python23\python ttt.py
> list ()              = 1.72
> list []              = 3.27
> comprehension        = 0.81
> copy                 = 3.94
> cCopy.copy           = 1.59
> lambda z: z[:]       = 1.14
> lambda z: list(z)    = 4.73
> lambda z: []         = 0.95
> f=lambda z: []       = 0.95
> 
> like /F though I am extremely puzzled about the list result. 

I just had a look at listobject.c, in particular the code for list_fill.

static int
list_fill(PyListObject *result, PyObject *v)
{
	PyObject *it;      /* iter(v) */
	int n;		   /* guess for result list size */
	int i;

	n = result->ob_size;

	/* Special-case list(a_list), for speed. */
	if (PyList_Check(v)) {
		if (v == (PyObject *)result )
			return 0; /* source is destination, we're done */
		return list_ass_slice(result, 0, n, v);
	}

	/* Empty previous contents */
	if (n != 0) {
		if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
			return -1;
	}

	/* Get iterator.  There may be some low-level efficiency to be gained
	 * by caching the tp_iternext slot instead of using PyIter_Next()
	 * later, but premature optimization is the root etc.
	 */
    	... and so on
}

Timing 'python \python23\lib\timeit.py "list([])"' gave times around 
4.5uSec per loop, whereas the same with "list(())" gives about 2.3uSec per 
loop.

Putting #ifdef 0/#endif around the 'special case for speed' block makes the 
first case go from 4.5uS to 2.4uS, and the second case also speeds up 
marginally for good measure.

So it looks suspiciously like a premature optimisation 'for speed' should 
say 'for reduced speed'.

Next I tried:
python \python23\lib\timeit.py -s"r=range(10000)" "list(r)"

and
python \python23\lib\timeit.py -s"r=tuple(range(10000))" "list(r)"

For this length of list the optimisation is a clear winner.

It looks to me as though the breakeven is around 100 elements in the list. 
With fewer than 100 elements the optimisation slows things down, with more 
it speeds them up.

I put the tests in a batch file:

------ test.bat --------
@echo off
@echo Length: 0
python \python23\lib\timeit.py -s"r=[]" "list(r)"
python \python23\lib\timeit.py -s"r=()" "list(r)"
@echo Length: 1
python \python23\lib\timeit.py -s"r=range(1)" "list(r)"
python \python23\lib\timeit.py -s"r=tuple(range(1))" "list(r)"
@echo Length: 10
python \python23\lib\timeit.py -s"r=range(10)" "list(r)"
python \python23\lib\timeit.py -s"r=tuple(range(10))" "list(r)"
@echo Length: 100
python \python23\lib\timeit.py -s"r=range(100)" "list(r)"
python \python23\lib\timeit.py -s"r=tuple(range(100))" "list(r)"
@echo Length: 1000
python \python23\lib\timeit.py -s"r=range(1000)" "list(r)"
python \python23\lib\timeit.py -s"r=tuple(range(1000))" "list(r)"
@echo Length: 10000
python \python23\lib\timeit.py -s"r=range(10000)" "list(r)"
python \python23\lib\timeit.py -s"r=tuple(range(10000))" "list(r)"
------------------------
With the original code I get:

C:\Pythonsrc\python\dist\src\PCbuild>test
Length: 0
100000 loops, best of 3: 4.38 usec per loop
100000 loops, best of 3: 2.32 usec per loop
Length: 1
100000 loops, best of 3: 5.26 usec per loop
100000 loops, best of 3: 2.4 usec per loop
Length: 10
100000 loops, best of 3: 5.39 usec per loop
100000 loops, best of 3: 2.84 usec per loop
Length: 100
100000 loops, best of 3: 7.44 usec per loop
100000 loops, best of 3: 7.26 usec per loop
Length: 1000
10000 loops, best of 3: 28.5 usec per loop
10000 loops, best of 3: 50.4 usec per loop
Length: 10000
1000 loops, best of 3: 258 usec per loop
1000 loops, best of 3: 505 usec per loop

With the optimisation code completely removed I get:
C:\Pythonsrc\python\dist\src\PCbuild>test
Length: 0
100000 loops, best of 3: 2.21 usec per loop
100000 loops, best of 3: 2.24 usec per loop
Length: 1
100000 loops, best of 3: 2.34 usec per loop
100000 loops, best of 3: 2.36 usec per loop
Length: 10
100000 loops, best of 3: 2.84 usec per loop
100000 loops, best of 3: 2.85 usec per loop
Length: 100
100000 loops, best of 3: 7.56 usec per loop
100000 loops, best of 3: 7.13 usec per loop
Length: 1000
10000 loops, best of 3: 53.2 usec per loop
10000 loops, best of 3: 50.4 usec per loop
Length: 10000
1000 loops, best of 3: 549 usec per loop
1000 loops, best of 3: 534 usec per loop

With the optimisation tweaked to ignore 0 length lists entirely and only 
'optimise' for lists with more than 100 elements:

C:\Pythonsrc\python\dist\src\PCbuild>test
Length: 0
1000000 loops, best of 3: 1.39 usec per loop
100000 loops, best of 3: 2.31 usec per loop
Length: 1
100000 loops, best of 3: 2.28 usec per loop
100000 loops, best of 3: 2.33 usec per loop
Length: 10
100000 loops, best of 3: 2.85 usec per loop
100000 loops, best of 3: 2.84 usec per loop
Length: 100
100000 loops, best of 3: 7.43 usec per loop
100000 loops, best of 3: 7.14 usec per loop
Length: 1000
10000 loops, best of 3: 28.4 usec per loop
10000 loops, best of 3: 50.2 usec per loop
Length: 10000
1000 loops, best of 3: 256 usec per loop
1000 loops, best of 3: 532 usec per loop

The relevant part of list_fill now looks like this:

	/* Special-case list(a_list), for speed. */
	if (PyList_Check(v)) {
		int vsize = ((PyListObject*)v)->ob_size;
		if (v == (PyObject *)result || vsize==0)
			return 0; /* nothing to copy */
		if (vsize > 100)
			return list_ass_slice(result, 0, n, v);
	}


-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?