Timing Difference: insert vs. append & reverse

[Bryan Olson]

Tim Peters wrote:

 > I'm one of the handful of people who might actually "do
 > something" about this kind of issue, and I was telling you that I
 > won't.  Your chances of seeing what you suggest are highly correlated
 > with finding someone who will "do something" <wink>.  I don't know
 > whether Raymond Hettinger is interested in pursuing this further, but
 > if he isn't either (that's my guess), then the only realistic chance
 > is if you do the work yourself.

Looking at the source, I'm worried.  Append and pop[-1] are not
really amortized O(1); at best they're commonly-average O(1).
Alternating appends and pops at certain border values will call
realloc for every operation.  The pop-reallocs free the extra
memory; if the allocator uses that memory for other requests,
the following append will have to copy the entire list.


 > In the basic list type, yes, it's more valuable in Python to save the
 > 8 bytes.  The speed of "left end" insert/remove is insignificant for
 > most Python apps, and is quite fast anyway for small lists.  It's a
 > major concern for *some* Python apps, and the deque type serves those
 > better than fudging the list type could.

The leave-it-to-realloc method seems to be an effort to save one
word (either a pointer or a size) per list.  With two more
words, I think we could make operations on both ends amortized
O(1).  The only lists for which this would be a substantial
portion are empty lists. Currently, empty lists require four
words (type_pointer, refcount, size=0, item_pointer=NULL) plus
malloc's bookkeeping. Any non-empty list additionally allocates
space for at least 8 pointers, plus malloc's bookkeeping.


-- 
--Bryan