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

[Stephen J. Turnbull]

Ram Rachum writes:

 > 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,

For complexity of collections the best reference I know is

    https://wiki.python.org/moin/TimeComplexity

 > 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 would imagine those things
are placed at the beginning of a data structure, but your OS may vary.
Even if somehow they were placed at the end of the allocation block,
you'd have to ask malloc if there is an empty block before it, and
then futz with the malloc metadata if you were to try to snarf that
block.  Sounds like a great way to crash Python to me.

I'll take collections.deque, thankyouverymuch.

A general note: implementations of Python builtins are generally quite
well-tuned, but not at the expense of excessive complexity.  Python's
threshold for "excessive" is pretty low, but nonetheless most builtins
are very efficient by now.

P.S. ISTR posting via Googlegroups is deprecated.