Timing Difference: insert vs. append & reverse
fakeaddress at nowhere.org
Sat Aug 7 08:50:05 CEST 2004
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.
More information about the Python-list