[Patches] [ python-Patches-947476 ] Apply freelist technique to
empty lists
SourceForge.net
noreply at sourceforge.net
Tue May 4 21:13:32 EDT 2004
Patches item #947476, was opened at 2004-05-04 01:47
Message generated for change (Comment added) made by tim_one
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: Accepted
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
>Assigned to: Raymond Hettinger (rhettinger)
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: Tim Peters (tim_one)
Date: 2004-05-04 21:13
Message:
Logged In: YES
user_id=31435
Marked Accepted & assigned back to you. If Armin wants
more changes, he (or you, or I, or ...) can fiddle it later.
What's here is fine!
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2004-05-04 20:28
Message:
Logged In: YES
user_id=80475
Any further ideas or should I go ahead and put this one in?
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2004-05-04 13: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 13: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 12: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 12: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 12: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 11: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 11: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 11: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 10: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