[Cython] [cython-users] freelist benchmarks

[mark florisson]

On 24 February 2013 15:58, Stefan Behnel <stefan_ml at behnel.de> wrote:
> 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.

Thanks for the explanation Stefan, this is the one I was thinking of,
but I suppose it'd need an extra pointer to the pure init function in
the type.

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

What about using pyextensible type from SEP 200 and using a custom
freelist entry on the type?

> Stefan
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups "cython-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to cython-users+unsubscribe at googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>