[Python-Dev] Optimization of the Year

[Kurt B. Kaiser]

"Raymond Hettinger" <raymond.hettinger at verizon.net> writes:

> AFAICT, this is a straight-win with no trade-offs along the way.
> The only offsetting cost is adding two fields to the list
> structure (Tim said that was bad but I don't remember why).

He said:
==============
That Python's builtin list calls realloc() on every append is pretty gross,
but it's also a tradeoff, saving the bytes in the list header that would be
required to remember how many allocated-but-unused slots exist.  If you've
got a million tiny lists (and some apps do), burning an additional 8MB for
something your app doesn't really need isn't attractive (on a 32-bit box
today, the list header is 16 bytes; pymalloc aligns to 8-byte boundaries, so
the next possible size is 24 bytes).  list's very small overallocation (in
the ballpark of 5%) is also aimed at minimizing memory burden.  Speed isn't
everything, tradeoffs are hard, and something loses when something else is
favored.  (BTW, I never would have considered implementing a resizable list
type *without* keeping a field to record the amount of overallocation, so
this isn't the tradeoff I would have made <wink>.)
==============
-- 
KBK