[Python-Dev] pymalloc killer

[Tim Peters]

>> i.e., all  references to pool->capacity *could* be replaced by
>> capacity[pool->szidx],  where "capacity" is a new small (at most
>> 32 uints) file-static const vector computed at compile-time.

[Marangozov, Vladimir (Vladimir) -- I hope you're noticing that your
 name as reported by your email headers is getting stranger all the
 time <wink>]

> The comparison in the "try to extend the free list" code is executed
> very frequently, so probing a static vector this way will slow down the
> thing noticeably. I've tried that. We are very much running after speed
> here.

Gotcha.  I was left partly unhappy with the "bulletproof address check" for
the same reason (needing to index into a static vector of arena base
addresses).

> ...
[on "the division" and "the multiplication" optimizations]
> Do both, despite that the multiplication optimization is more important.
> (for one division we have #blocks multiplications for a full pool)

Two things have shifted since you wrote this code:

+ The architecture trend has been to make division ever-slower in
  comparison to multiplication (e.g., Itanium doesn't even have an
  integer division instruction); on some boxes integer division is over
  100 cycles now, at the same time integer multiplication is down to a
  few.

+ We can fit fewer objects into a pool now.  For example, on Windows,
  Python container types are 16 bytes bigger than they used to be, due
  to gc-header overhead (and an empty dict is actually up to 148 bytes
  on Windows now!).

We could shift that back by making pools larger, but if they exceed the size
of a system page then cutting a legit pointer back to a pool-aligned address
may yield an invalid address.  So it gets dicey short of teaching Python how
to ask the OS directly for pages.

> 1) I think that adding back one uint slot (lastoffset) is not a problem
>    (and we end up with the perfect balance of having a pool header layout
>     with 4 pointers and 4 integers <wink>).

Yes, that is perfect <wink>.

> 2) Now, with the advent of lastoffset, we can easily get rid off the
>    division as well. For this, we switch to offset calculus for figuring
>    out whether the free list can be extended. This means that 'capacity'
>    becomes 'highoffset'. The 'highoffset' is the highwater not to be
>    exceeded by more than 'size' bytes by 'lastoffest'.
>
>    a) the test becomes then:  if (pool->lastoffset <= pool->highoffset)
>                                   ...
>                                   pool->lastoffset += size;
>                                   pool->freeblock = (block *)pool + \
>                                                     pool->lastoffset;
>
>    b) in the pool_init code:  pool->lastoffset = POOL_OVERHEAD + size;
>                               pool->highoffset = POOL_SIZE - size - size;
>
>    and you'll need to adjust the code accordingly at the places where
>    you're using 'capacity' per se (and adapt the comments, of course).

I'll do this, but I expect I'll use a nextoffset instead of a lastoffset, in
order to let the two additions in 2a proceed in parallel, and to skip one of
the subtracts in 2b.  Hey, if we're gonna optimize, I'm not gonna miss a
cycle.

> This should pretty much settle these murky optimizations for now.

Cool!  Thanks for your help.  You should come back to Python, you know -- we
don't know what you're doing instead, but we all have to suspect it's
comparatively worthless <wink>.