list.pop(0) vs. collections.dequeue

[Steven D'Aprano]

On Sun, 24 Jan 2010 20:12:11 -0800, Steve Howell wrote:

>> > The most ambitious proposal is to fix the memory manager itself to
>> > allow the release of memory from the start of the chunk.
>>
>> That's inappropriate given the memory fragmentation it would cause.
>>
>>
> Bullshit.  Memory managers consolidate free memory chunks all the time. 
> That's their job.


So let me get this straight... 

You've complained that Python's list.pop(0) is lame because it moves 
memory around. And your solution to that is to have the memory manager 
move the memory around instead?

Perhaps I'm missing something, but I don't see the advantage here. At 
best, you consolidate all those moves you wanted to avoid and do them all 
at once instead of a few at a time. At worst, you get a situation where 
the application periodically, and unpredictably, grinds to a halt while 
the memory manager tries to defrag all those lists.


>> Really, you're describing a problem that arises in a few programs but
>> up til now, as far as I know, everyone has found deque to be an
>> adequate solution.
> 
> Wrong.  Many programs delete the first element of the list.

I'm sure they do. Many programs do all sorts of things, of varying 
sensibleness. But I'm pretty sure I've never written a program that 
deleted the first element of a list. Even if I have, it's a vanishingly 
small use-case for me. YMMV.



>> Your approach of snarling against list is not persuading anyone that
>> list needs to be changed, because most everyone is satisfied with the
>> existing solution.
> 
> Please provide evidence of that.  I am pretty sure that everybody who
> chooses alternatives to Python would disagree.

Do you honestly believe that "everybody" who prefers another language 
over Python does so because they dislike the performance of list.pop(0)?



>> You might change approaches and discuss deque, what's wrong with it,
>> and whether it can be fixed.  Getting a change approved for deque is
>> probably much easier than getting one approved for list, just because
>> nowhere near as many things depend on deque's performance.
> 
> Again...I am not looking to improve deque, which is a perfectly valid
> data structure for a limited set of problems.
> 
>> And when discussing performance in this contextc additive constants do
>> matter.
> 
> Wrong again.  Operations that mutate lists are already expensive, and a
> few checks to see if unreleased memory can be reclaimed are totally
> NEGLIGIBLE.

Popping from the end of the list isn't expensive. Reversing lists is 
relatively cheap. In-place modifications are very cheap.



-- 
Steven