[Cython] [cython-users] freelist benchmarks

[Stefan Behnel]

mark florisson, 24.02.2013 15:50:
> On 24 February 2013 13:52, Stefan Behnel wrote:
>> for those who haven't notice my other e-mail, I implemented a new extension
>> type decorator "@cython.freelist(N)" that replaces the normal object
>> creation and deallocation with a freelist of N recently freed objects.
>> Currently, it's only supported for types that do not have a base class (and
>> lifting that restriction is not all that easy).
> 
> Very cool! I've been wanting that for a while now :)

So did I.


> What's the hurdle with base classes?

The problem is that the current way types are being instantiated is
recursive. The top-most base class calls tp_alloc() and then each step in
the hierarchy adds its bit of initialisation. If you want to introduce a
freelist into this scheme, then it's still the top-most class that does the
allocation, so it would need to manage all freelists of all of its children
in order to return the right object struct for a given instantiation request.

This cannot really be done at compile time. Imagine a subtype in a
different module, for example, for which the code requests a freelist. The
compilation of the base type wouldn't even know that it's supposed to
manage a freelist at all, only the subtype knows it.

There are a couple of ways to deal with this. One is to replicate the
freelist in the base type for all subtypes that it finds at runtime. That
might actually be the easiest way to do it, but it requires a bit of memory
management in order to add a new freelist when a new subtype is found at
runtime. It also means that we'd have to find the right freelist before we
can get an object from it (or not, if it's empty), which would likely be an
operation that's linear with the number of subtypes. And the freelist set
would better be bounded in size to prevent users from flooding it with lots
and lots of subtypes.

Another option would be to split the initialisation up into two functions,
one that allocates *and* initialises the instance and one that *only*
initialises it. That would allow each hierarchy level to manage its own
freelists and to take its own decision about where to get the object from.
This approach comes with a couple of tricky details, as CPython doesn't
provide support for this. So we'd need to find a way to handle type
hierarchies that are implemented across modules.

Maybe the best approach would be to let the base type manage everything and
just statically limit the maximum number of subtypes for which it provides
separate freelists, at a first come, first serve basis. And the freelist
selection could be based on the object struct size (tp_basicsize) instead
of the specific type. As long as we don't support inheriting from variable
size objects (like tuple/bytes), that would cut down the problem quite
nicely. I think I should just give it a try at some point.

Stefan