--- On Wed, 1/27/10, Raymond Hettinger <raymond.hettin...@gmail.com> wrote:
> From: Raymond Hettinger <raymond.hettin...@gmail.com>
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Martin v. Löwis" <mar...@v.loewis.de>
> Cc: "Steve Howell" <showel...@yahoo.com>, python-dev@python.org
> Date: Wednesday, January 27, 2010, 1:49 PM
>
> On Jan 27, 2010, at 11:38 AM, Martin v. Löwis wrote:
>
> >> Lists are indeed used *everywhere* and *vast*
> quantities, which is
> >> why optimizations on list operations are
> worthwhile to pursue.
> >
> > Unfortunately, the proposed change is a pessimisation,
> not an
> > optimisation. We probably shouldn't discuss it
> further, at least not
> > until a PEP gets written by its proponents.
> >
>
> I concur (on both points).
>
> AFAICT, the performance of the proposal:
>
> * increases space requirements by a small fixed amount
>
> * s.append() performance slightly degraded.
>
> * the s.insert(0, value) case isn't helped -- still O(n)
>
> * repeated s.pop(0) have amortized O(1) but either
> needs to waste space indefinitely (likely
> not what
> the programmer intended by popping off
> values)
> or needs to do occasional memmoves (which
> isn't
> as good as a deque which never moves the
> data).
>
> * the resize performance doesn't work well with the
> memory allocator -- while a series of
> appends can often
> resize in-place without a need to do an
> O(n) memmove,
> but a series of pop(0) calls doesn't have
> a resize in-place
> option.
>
> What currently unknown is the effect on third-party
> extensions
> and debugging tools that access the structure directly.
> Also, am not sure if this affects psyco or the other
> implementations such as Jython which may implement
> lists in terms of existing Java containers.
>
> ISTM, the *only* benefit is that an occasional s.pop(0)
> will perform better than it does now but not as well
> as a deque which never has to move data).
>
>
I agree with most of what's said above, with a few clarifications.
The speedup is not limited to pop(0); it also considerably speeds up code like
below:
n = 800000
for i in range(n):
x = lst[:10]
del lst[:10]
Understood that it is a contrived benchmark, and real code like that could be
replaced with a technique that Nones out the used up elements and advances a
start pointer.
Prepends are still O(N) for most use cases, but prepends will reclaim space at
the front if it's there in O(1).
The biggest performance tradeoff, the extra space requirement in PyListObject,
can be eliminated, albeit with a pretty ugly hack.
Since there is a lot of discussion about tradeoffs, I would remind folks that
asking somebody to use a deque instead of a list also forces tradeoffs; you
lose the comfort and familiarity of lists (not to be underestimated) as well as
some features (you can't spell d[:10] as d[:10] for example).
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
