Timing Difference: insert vs. append & reverse

[Tim Peters]

[Bryan Olson]
> 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.

...

> The leave-it-to-realloc method seems to be an effort to save one
> word (either a pointer or a size) per list.

What are you looking at?  I've been talking about Python 2.4 (as
evidenced by my saying 2.4 over and over <wink>).  Its list
implementation is not realloc-happy, and has both allocated-size and
used-size members.  The earlier leave-it-to-realloc gimmick was indeed
an extreme effort to save bytes.  The 2.4 implementation is simpler,
clearer, faster, and better-behaved in several respects.

> With two more words, I think we could make operations on both ends
> amortize O(1).

As before, I don't care about this.  The 2.4 deque is O(1) on both
ends straightforwardly and more efficiently.

> 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 3 for the gc header (every list object gets one, although that's
not apparent from staring at listobject.h), plus 1 (not in 2.3 but in
2.4) to store the # of allocated slots.  That's a total of 8.

> plus malloc's bookkeeping.

The list struct is allocated via pymalloc, which allocates in 8-byte
chunks with trivial overhead beyond that (just a few percent).  So not
even 1 bit can be added to the 2.4 list struct without losing another
8 bytes, under *most* C compilers for 32-bit machines.  The Microsoft
C compilers are exceptions (they stick 4 bytes of padding in the gc
header, so there are 4 wasted bytes now (2.4) in the list struct under
MSVC).

> Any non-empty list additionally allocates space for at least 8 pointers, ...

In 2.4 that's been reduced to 4.