[Patches] [ python-Patches-947476 ] Apply freelist technique to empty lists

SourceForge.net noreply at sourceforge.net
Tue May 4 13:41:33 EDT 2004


Patches item #947476, was opened at 2004-05-04 00:47
Message generated for change (Comment added) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=947476&group_id=5470

Category: Core (C code)
Group: Python 2.4
Status: Open
Resolution: None
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Armin Rigo (arigo)
Summary: Apply freelist technique to empty lists

Initial Comment:
Saves malloc/free and reduces fragmentation for the 
ubiquitous operation of instantiating and freeing empty 
lists.

Improves the timing of timeit.py "[]" by about a quarter.

----------------------------------------------------------------------

>Comment By: Raymond Hettinger (rhettinger)
Date: 2004-05-04 12:41

Message:
Logged In: YES 
user_id=80475

Attaching a new patch that incorporates both Tim and Armin's
suggestions.  The PyListObject portion is always reclaimed
whenever there is room in the free list.  The header is
always re-used when available.  This provides some benefit
to lists of all sizes and it simplifies the patch a bit.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2004-05-04 12:08

Message:
Logged In: YES 
user_id=31435

WRT ints, the free list is chained together via abusing the 
ob_type field, and there's no other field in a PyIntObject 
guaranteed large enough to hold a pointer (or guaranteed to 
be pointer-aligned).

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-05-04 11:48

Message:
Logged In: YES 
user_id=80475

The needs of the different types vary enough to make a
single macro set unlikely.  Also, macros tend to hide what
is going on under the hood making it difficult to discern
genuine optimizations.

Sound like there may be room for improvement for integers. 
Sticking with small steps though, I'll take lists today and
leave integers for another patch on another day.

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2004-05-04 11:40

Message:
Logged In: YES 
user_id=4771

Wouldn't it be nice to have a set of macros for free lists,
something that could easily be dropped in any object
implementation and that would do the right thing, e.g. cache
the ob_type?

When looking at integers, I can't help noticing that they
reinitialize the ob_type field at each object creation. 
Would it pay to try to remove that?


----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-05-04 11:02

Message:
Logged In: YES 
user_id=80475

Okay, I see.  If that was an issue, it was fixed by
incorporating your suggestion which means that the freelist
will almost never be starved.


----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2004-05-04 10:58

Message:
Logged In: YES 
user_id=31435

FWIW, I like this.  The list header could also be reclaimed 
from the freelist regardless of list size, a la

if (free list isn't empty) {
    op = pop off the free list;
    do object initialization;
    if (size == 0) {
        finish & return;
    }
else {
    op = PyObject_GC_New(...);
    if (op == NULL) error;
}

Note that PyMalloc isn't involved in allocating list *guts* 
regardless of list size.  They're allocated with 
PyMem_MALLOC, which is the system malloc().  That's a 
murkier tradoff (if the guts get "too big" for PyMalloc later, 
the PyMalloc realloc function is a bit slower than calling the 
system realloc, since the former has the additional overhead 
of deducing that it needs to call the latter; OTOH, we no 
longer call a realloc function on every stinkin' append 
anymore).

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2004-05-04 10:53

Message:
Logged In: YES 
user_id=4771

Ok.  I meant that lists that are still empty when they are
destructed are probably not too common, although most lists
are created empty.


----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-05-04 10:38

Message:
Logged In: YES 
user_id=80475

Attaching a revised patch that incorporates your suggestion
about always being able to save/restore the PyListObject part.

The a priori reason empty lists are so common is that most
lists are built up from zero.  Also, there is a lot a
testing for a==[] and default instantiation in expressions
like mydict.setdefault(k, []).append(v).

A posteriori, it is easy to get a quick visual on the this,
add a printf("*") on one side of the "if" and printf(".") on
the other.  Then run the test suite.  The pattern of
PyList_New(0) calls completely dominate the output.  It
looks like about 90% of the PyList_New calls are for size 0
(this pattern holds is not unique -- it holds across the
whole test suite).

The patch captures the benefit for the most common cases and
avoids the code complexity and overhead of tracking multiple
blocks of different sized memory blocks (that is what
PyMalloc is supposed to be good at).

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2004-05-04 09:34

Message:
Logged In: YES 
user_id=4771

Why is the idea restricted to empty lists?  A priori I don't
see why empty lists are so common.  On the other hand we
should be able to save and restore the PyListObject part of
any list using the same mecanism.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=947476&group_id=5470



More information about the Patches mailing list