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

[Stephen J. Turnbull]

Antoine Pitrou writes:
 > On Fri, 07 Feb 2014 20:05:41 +0900
 > "Stephen J. Turnbull" <stephen at xemacs.org>
 > wrote:
 > > 
 > >  > 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.
 > > 
 > > The problem is that it would have to have unholy carnal knowledge of
 > > OS internals (eg, of malloc).  First off, availability itself is
 > > non-portable, depending on a lot of things (eg, placement of malloc
 > > metadata and Python object metadata).
 > 
 > ??? I don't understand what you're talking about.

Obviously.

 > It is perfectly possible while being portable. The proof is that
 > bytearray has a limited variant of that optimization (not for
 > insertions, but for deletions at the front).

What about "list.insert(whatever, 0)" looks like a deletion operation
to you?

Certainly, it would be possible to keep an additional start pointer,
and advance that for deletions at position 0, then use that space for
insertions at 0 (or perhaps "early" in the list) if available.  But
the OP refers to *allocation*, and specifically disallows "reserving
space".  So it's clear he's not talking about a feature like that,
he's talking about finding *new* space.