Python 2.0b1 List comprehensions are slow

[Kevin O'Connor]

[Message mailed and posted]

On Wed, Sep 13, 2000 at 12:12:12AM -0400, Tim Peters wrote:
> [possibly Guido; way behind on email]
> > Ways to optimize this (in 2.1; as Tim explained 2.0 is too close to
> > release) might include:
> 
> [Kevin O'Connor]
> > Well, it is your call, but the patch attached to this message speeds up
> > list comprehensions by as much as 30% for me.
[...]
> Since no code is using listcomps today, the case for mucking in this area to
> speed *them* after the first beta is, frankly, non-existent.  The speed of a
> new feature simply isn't a bug.  And, believe it or not, most Python users
> don't care about 30% (if they did, they wouldn't be using Python <wink>).

Fair enough.  I would count myself in that "most Python users" group as
well.

> "The right thing" for extreme cases would be to add a member to list objects
> to record the number of elements allocated as well as the number used.  Then
> mildly exponential growth could be assured regardless of size, and without
> all this indirect brittle trickery.  Guido doesn't want to boost the size of
> the basic list object now, but the "extra memory" for this info is *already*
> being consumed one way or another by the platform malloc, and if we move to
> PyMalloc we can exploit that *it* has to know this info too.

I agree 100% with this analysis.  The patch was intended to be a quick "no
loss" speed improvement.  I would much rather see the allocation size
stored somewhere accessible to python - it allows for much more
"intelligent" allocation and deallocation.  (For example, with the current
scheme, if a list just happened to flip-flop between 10 and 11 items then
realloc would be constantly called - and be expected to actually alter the
allocation size.)
It also permits lists created from other lists (slices, map, etc.) to be
allocated to exact amounts while still being sane on append operations.
This may be a short-coming of my patch - however, I'm not sure it is really
all that significant.  An extra 36 bytes (on 32-bit machines - 72 bytes on
64-bit machines) per list, in a worst case scenario, doesn't seem
extravagant; I'm sure the list header and garbage control would make the
extra padding irrelevant.

Of course, waiting for 2.0 is not a problem,
-Kevin

> there-are-20-things-i-should-have-been-doing-now-instead-of-this!-ly
>     y'rs  - tim

Yes, but were they as fun?

-- 
 ------------------------------------------------------------------------
 | Kevin O'Connor                     "BTW, IMHO we need a FAQ for      |
 | koconnor at cse.buffalo.edu            'IMHO', 'FAQ', 'BTW', etc. !"    |
 ------------------------------------------------------------------------