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

[spir]

On 02/07/2014 11: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?

It is not possible, because it would change the pointer (to the actual "stock" 
of items), that must point to the first item, and be also known by the memory 
allocator as such. In principle, one can have a "fake" pointer with some part of 
the data actually positioned *before* the address it points to. This is in fact 
the way "Pascal arrays" (and strings) are commonly implemented, with their sizes 
prefixed to the first item. Bit this introduces some complication (eg one must 
recompute the original pointer for dealloc) and must be designed right from the 
start at the lowest level.

The only practicle way would be to systematically reserve memory space before 
the start item [*], for such cases. It is not worth it for a very specific 
operation like like.insert_anywhere (even less list.insert_at_start), which is 
not (in my view) the proper point of lists (arrays, in fact). We should use 
proper collections whenever we need inserting (and removing) at arbitrary 
locations. 99% lists do not need that. As I see it, lists are for, in order of 
importance:

* put new item (at the end) (also when used as a stack, =push)
* iterate (in order)

* read item (anywhere)
* change item (anywhere)

* take or remove last item (only when used only as a stack, =pop)

The deal may possibly be different if arrays were python's only collection (like 
link lists in lisp or tables in lua).

d

[*] I sometimes wish strings would reserve place for exactly one more code at 
the _end_, for cases when one must ensure a string (often read from file) 
terminates with a newline ;-)