[Python-Dev] int/float freelists vs pymalloc

M.-A. Lemburg mal at egenix.com
Wed Feb 13 10:52:36 CET 2008

On 2008-02-13 08:02, Andrew MacIntyre wrote:
> Christian Heimes wrote:
>> Andrew MacIntyre wrote:
>>> 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've tried a single linked free list myself. I used the ob_type field to
>> daisy chain the int and float objects. Although the code was fairly
>> short it was slightly slower than an attempt without a free list at all.
>> pymalloc is fast. It's very hard to beat it though.
> I'm speculating that CPU cache effects can make these differences.  The
> performance of the current trunk float freelist is depressing, given that
> the same strategy works so well for ints.
> I seem to recall Tim Peters paying a lot of attention to cache effects
> when he went over the PyMalloc code before the 2.3 release, which would
> contribute to its performance.
>> A fixed size LIFO array like PyFloatObject
>> *free_list[PyFloat_MAXFREELIST] increased the speed slightly. IMHO a
>> value of about 80-200 floats and ints is realistic for most apps. More
>> objects in the free lists could keep too many pymalloced areas occupied.
> I tested the updated patch you added to issue 2039.  With the int
> freelist set to 500 and the float freelist set to 100, its about the same
> as the no-freelist version for my tests, but PyBench shows the simple
> float arithmetic to be about 10% better.
> I'm inclined to set the int LIFO a bit larger than you suggest, simply as
> ints are so commonly used - hence the value of 500 I used.  Floats are
> much less common by comparison.  Even an int LIFO of 500 is only going to
> tie up ~8kB on a 32bit box (~16kB on 64bit), which is insignificant
> enough that I can't see a need for a compaction routine.
> A 200 entry float LIFO would only account for ~4kB on 32bit (~8kB on
> 64bit).

It is difficult to tell what good limits for free lists should
be. This depends a lot on the application focus, e.g. a financial
application is going to need lots of floats, while a word
processor or parser will need more integers.

I think the main difference between the current free list
implementation and Christian's patches is that the current
implementation bypasses pymalloc altogether and allocates
the objects directly using the system malloc().

The objects in the free list then cannot keep artificially keep
pymalloc pools alive.

Furthermore, the current free list implementation works
by allocating 1k chunks of memory for more than just one
object whenever it finds that the free list is empty.

Christian's patches and your free list removal patch, cause
all allocations to be done via pymalloc. Christian's free
list can also result in nearly empty pymalloc pools to stay
alive due to the use of a linked list rather than an
array of objects.

Finally (and I don't know if you've missed that), the integer
implementation uses sharing for small integers. In the current
implementation all integers between -5 and 257 are only ever
allocated once and then reused whenever an integer in this
range is needed. The shared integers are not subject to any
of the extra free list handling or pymalloc overhead.

This results in a significant boost, since integers in this
range are *very* common and also causes the comparison between
integers and floats to become biased - floats don't have
this optimization.

I still think that dropping the free lists can be worthwhile,
but pymalloc would need to get further optimizations to give
better performance for often requested size classes (the 16 byte
class on 32bit architectures, the 24 byte class on 64bit

Marc-Andre Lemburg

Professional Python Services directly from the Source  (#1, Feb 13 2008)
>>> Python/Zope Consulting and Support ...        http://www.egenix.com/
>>> mxODBC.Zope.Database.Adapter ...             http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/

:::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,MacOSX for free ! ::::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611

More information about the Python-Dev mailing list