[Python-Dev] int/float freelists vs pymalloc

[Christian Heimes]

Andrew MacIntyre wrote:
> For the int case, that patch is slower than no free list at all.  For the
> float case its very slightly faster (55.3s vs 55.5s) than no free list at
> all.  Slower than the trunk code for both cases.  Did you run the test
> scripts on your own machine?

I've used a simple timeit call to bench mark the memory allocation. The
first statement saturates the free lists and the second one benchmarks
memory allocation and float creation.

./python -m timeit -n10 -s "[float(x) for x in list(range(1000))]" "for
i in range(100): [float(x) for x in list(range(1000))]"

I've done some experiments with a fixed length *free_list[] like dict
and listobject.c. A fixed length list is faster than a single linked
list. I'm going to upload the patch later.

> In addition to the pure performance aspect, there is the issue of memory
> utilisation.  The current trunk code running the int test case in my
> original post peaks at 151MB according to top on my FreeBSD box, dropping
> back to about 62MB after the dict is destroyed (without a compaction).
> The same script running on the no-freelist build of the interpreter peaks
> at 119MB, with a minima of around 57MB.

I wonder why the free list has such a huge impact in memory usage. Int
objects are small (4 byte pointer to type, 4 byte Py_ssize_t and 4 byte
value). A thousand int object should consume less than 20kB including
overhead and padding.

> On the 2 platforms I have, the current trunk code for ints would appear
> to be as good as it gets speed-wise.  If the memory utilisation issue
> were to be considered significant, dropping the int freelist would have
> its attractions...
> 
> As far as floats go, all the indications I have suggest that the current
> freelist code has a performance problem.  Ditching the freelist and
> reverting to inlined PyObject_New()/PyObject_Del() semantics would be an
> attractive course as it appears to perform to within a whisker of the
> best alternatives while simplifying the object's code and taking
> advantage of pymalloc, however there are a number of other
> platforms/compilers that need testing before it would be prudent to do
> so.

I can test the code on Linux and Windows XP. My tests have shown that a
linked free list doesn't give a considerable performance boost - even
for code that allocates and frees a lot of ints and floats at once. But
a fixed length pointer array gives a measurable performance gain.

> The compaction routine you added to trunk gets the job done as far as
> freelist pruning goes, but I can't say I find it anything other than an
> ugly solution (though there is precedent for the concept via the gc
> module).

Yeah, I won't argue with that. The compaction function is a crutch.

Christian