[Python-Dev] int/float freelists vs pymalloc

[Andrew MacIntyre]

Christian Heimes wrote:
> 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))]"

Try testing with 1000000 rather than 1000.  My testing was deliberately
looking at the handling of large numbers of ints/floats, because small
numbers (eg 1000) are not enough to make wasted memory recovery
worthwhile.

> 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.

I tried a LIFO stack implementation (though I won't claim to have done it
well), and found it slightly slower than no freelist at all. The
advantage of such an approach is that the known size of the stack makes
deallocating excess objects easy (and thus no need for
sys.compact_free_list() ).

I have been guilty of not paying attention to the performance of the
small cases.

>> 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.

My test script allocates 4000000 ints - ~48MB.  Much of the memory 
"pulse" is the creation/deletion of a dict with 2000000 items (25MB?).

Its interesting to watch the freelist case, as first time through the
loop the process size peaks at 109MB, then at the end of the 2nd pass it
peaks at 151MB which is maintained on subsequent passes through the loop.
(BTW, on this machine just starting the python interpreter leaves the
process size at a bit over 3MB).

The no-freelist build peaks at its maximum of 119MB on the first pass
through the loop.

>> 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.

I've added my research patches to issue 2039, so I'd be interested to 
know how they rate in comparison.  In addition to the small case testing
mentioned above, I would suggest you do some large case testing (such as
with the scripts I included in my original posting) as this is the 
justification for the effort on wasted memory recovery.

Cheers,
Andrew.

-- 
-------------------------------------------------------------------------
Andrew I MacIntyre                     "These thoughts are mine alone..."
E-mail: andymac at bullseye.apana.org.au  (pref) | Snail: PO Box 370
        andymac at pcug.org.au             (alt) |        Belconnen ACT 2616
Web:    http://www.andymac.org/               |        Australia