list.pop(0) vs. collections.dequeue

[Steve Holden]

Steve Howell wrote:
> On Jan 24, 11:28 am, a... at pythoncraft.com (Aahz) wrote:
>> In article <b4440231-f33f-49e1-9d6f-5fbce0a63... at b2g2000yqi.googlegroups.com>,
>> Steve Howell  <showel... at yahoo.com> wrote:
>>
>>
>>
>>> Even with realloc()'s brokenness, you could improve pop(0) in a way
>>> that does not impact list access at all, and the patch would not change
>>> the time complexity of any operation; it would just add negligible
>>> extract bookkeeping within list_resize() and a few other places.
>> Again, your responsibility is to provide a patch and a spectrum of
>> benchmarking tests to prove it.  Then you would still have to deal with
>> the objection that extensions use the list internals -- that might be an
>> okay sell given the effort otherwise required to port extensions to
>> Python 3, but that's not the way to bet.
>>
> 
> Ok, I just submitted a patch to python-dev that illustrates a 100x
> speedup on an admittedly artificial program.  It still has a long way
> to go, but it demonstrates proof of concept.  I'm done for the day,
> but tomorrow I will try to polish it up and improve it, even if its
> doomed for rejection.  Apologies to all I have offended in this
> thread.  I frankly found some of the pushback to be a bit hasty and
> disrespectful, but I certainly overreacted to some of the criticism.
> And now I'm in the awkward position of asking the people I offended to
> help me with the patch.  If anybody can offer me a hand in
> understanding some of CPython's internals, particularly with regard to
> memory management, it would be greatly appreciated.
> 
> (Sorry I don't have a link to the python-dev posting; it is not
> showing up in the archives yet for some reason.)
> 
> 
Fortunately for you this is a very welcoming group, and particularly
responsive to individuals who have seen the error of their ways ;-)

regards
 Steve
-- 
Steve Holden           +1 571 484 6266   +1 800 494 3119
PyCon is coming! Atlanta, Feb 2010  http://us.pycon.org/
Holden Web LLC                 http://www.holdenweb.com/
UPCOMING EVENTS:        http://holdenweb.eventbrite.com/