[pypy-dev] range list implementation

[Carl Friedrich Bolz]

Hi all!

Just a few words about the range list implementation I wrote during the
last few days (when I was fed up with the config branch...). There is a
new list implementation W_RangeListObject. The idea is that calling
range will not immediately allocate the whole list but only store start,
stop and step into the range list object. The range list object behaves
like a perfectly normal list to the user. For some operations the range
list is 'forced', that is the full list is generated. This is especially
the case for operations that mutate the list. The following operations
on the range list keep it in its non-forced memory-saving form:

 * iteration
 * len
 * getitem
 * getitem with a slice (which returns a new range list)
 * iter
 * repr
 * reverse
 * sort

The reverse and sort method are admittedly somewhat useless (who
constructs a range and sorts it?) but were easy to do. It would be
possible to add support for more operations, but I doubt that it would
be useful.

I have not timed the result extensively, but you can pull tricks
like that:

>>>> import sys
>>>> r = range(sys.maxint)
>>>> len(r)
2147483647
>>>> iter(r)
<sequenceiterator object at 0x083ddba0>
>>>> print r[1000:2000:30]
[1000, 1030, 1060, 1090, 1120, 1150, 1180, 1210, 1240, 1270, 1300, 1330,
1360, 1390, 1420, 1450, 1480, 1510, 1540, 1570, 1600, 1630, 1660, 1690,
1720, 1750, 1780, 1810, 1840, 1870, 1900, 1930, 1960, 1990]

Some very trivial timings:

2.877 seconds CPython versus 0.026 seconds pypy-c-withrangelist for the
following snippet which is of course written in a way to showcase the
advantages of range lists. Of course CPython uses a lot more memory too
:-)

import time
t1 = time.time()
result = []
for i in range(10000):
    result.append(range(i))
t2 = time.time()
print t2 - t1

It remains to be seen what sort of benefits this gives for realistic
applications.

Cheers,

Carl Friedrich