[Python-ideas] Question about `list.insert`

[Chris Angelico]

On Fri, Feb 7, 2014 at 10:15 PM, Ned Batchelder <ned at nedbatchelder.com> wrote:
> On 2/7/14 5:14 AM, Ram Rachum wrote:
>>
>> Okay, now that I've posted on python-list, and among the 80% of joke posts
>> in my thread, there was a 20% of posts that assured me that Python's list
>> has no such behavior and that I should use deque, I now ask on Python-ideas:
>> Is there a good reason why `list.insert(whatever, 0)` doesn't
>> opportunistically try to allocate more space at the left side of the list,
>> so as to save the expensive operation of moving all the items? I'm not
>> saying it should reserve space there, just check if that space is available,
>> and if so use it. Is there any reason why not?
>>
> "check if that space is available": this is not a simple operation. Only the
> memory allocator knows what blocks of memory are allocated and which are
> not.  Memory allocators typically don't support the operation of "extend my
> memory block downward if possible."

Checking if space is available could be done without any fiddling with
malloc, though. All it requires is an optimization of pop(0) followed
by insert(0,foo). That is, when you poop(0), the list just marks
itself as having one junk entry before the first entry (presumably it
already keeps track of spare space at the end, so this would be just
one more integer), which can then be reused later. But apart from
maybe reducing the memory copying (the same optimization could mean
that repeated pop(0) calls would incur less copying, too), there's not
a huge gain.

ChrisA