Timing Difference: insert vs. append & reverse
Tim Peters
tim.peters at gmail.com
Sat Aug 7 03:23:23 EDT 2004
[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.
More information about the Python-list
mailing list