I tried implementing a freelist. Patch attached, mostly adapted from the one in dictobject.c, but certainly needs a bit of cleanup.
The results are not bad, about 10-20% faster:
Original:
$ ./python -m timeit 'sum(range(1, 100000))'
1000 loops, best of 3: 1.86 msec per loop
$ ./python -m timeit -s 'l = list(range(1000, 10000))' '[(i*2+5) // 7 for i in l]'
1000 loops, best of 3: 1.05 msec per loop
With freelist:
$ ./python -m timeit 'sum(range(1, 100000))'
1000 loops, best of 3: 1.52 msec per loop
$ ./python -m timeit -s 'l = list(range(1000, 10000))' '[(i*2+5) // 7 for i in l]'
1000 loops, best of 3: 931 usec per loop