Timing Difference: insert vs. append & reverse | Bytes (2024)

Dear all,
I tried the test program below. My interest is to examine timing
differences between insert vs. append & reverse for a list. My results
on my XP Python 2.3.4 are as follows:
time_reverse 0.889999389648
time_insert 15.7750005722
Over multiple runs ... the time taken to insert at the head of a list,
vs. the time taken to append to a list and then reverse it is
typically 16 or 17 times longer.
I would have expected the insert operation to be faster than the
combined append & reverse operations. Is this behaviour surprising, or
is there a good reason why there is this large performance difference?
Thanks,
John

fromtimeimporttime

deftest():
time_reverse=0.0
time_insert=0.0

forlindxinxrange(100):
tmp1=[]
time_reverse-=time()
forindxinxrange(10000):
tmp1.append(ind x)
tmp1.reverse()
time_reverse+=time()

tmp2=[]
time_insert-=time()
forindxinxrange(10000):
tmp2.insert(0, indx)
time_insert+=time()
asserttmp1==tmp2
print"time_rever se ", time_reverse
print"time_inser t ", time_insert

test()

Subscribe Reply

br************* **********@yaho o.com (Bryan Olson) wrote in
news:1a******** *************** **@posting.goog le.com:

If you expected insert to be faster, perhaps you thought that Python
used a linked-list implementation. It doesn't do this, because in
practice (for most applications) a [array] based implementation gives
better performance.

True, but an array implementation can easily support amortized
constant-time insert/delete at *either* end (without breaking
constant-time indexing). The same trick of keeping extra space
at the tail end can work at the head; it requires keeping one
additional offset to show where the occupied cells start.

If the OP had said he expected insert and append to be the same speed I
might buy that, but he expected insert to be faster than append.

Clarification.. .

Duncan Booth <du**********@i nvalid.invalid> wrote in message

True, but an array implementation can easily support amortized
constant-time insert/delete at *either* end (without breaking
constant-time indexing). The same trick of keeping extra space
at the tail end can work at the head; it requires keeping one
additional offset to show where the occupied cells start.

If the OP had said he expected insert and append to be the same speed I
might buy that, but he expected insert to be faster than append.

Actually, I never said that ... I said "I would have expected the
insert operation to be faster than the combined append & reverse
operations." The object of my test code was to fill out a list in
the reverse order to which I had the list items available.
I would have expected:
tmp2 =[]
for indx in xrange(10000):
tmp2.insert(0, indx)

to be faster than

tmp1 =[]
for indx in xrange(10000):
tmp1.append(ind x)
tmp1.reverse()

because the insert case does not require the reverse operation. This
would be the case if the insert operated at (approximately) the same
speed as the append, rather then the insert (at position 0) being
16-17 times slower than the append. I guess I somewhat expected it to
be as Bryan Olson stated:"an array implementation can easily support
amortized constant-time insert/delete at *either* end (without
breaking constant-time indexing)."

John

Duncan Booth wrote:

Bryan Olson:

[Duncan Booth had written:]

If you expected insert to be faster, perhaps you thought that Python
used a linked-list implementation. It doesn't do this, because in
practice (for most applications) a [array] based implementation gives
better performance.

True, but an array implementation can easily support amortized
constant-time insert/delete at *either* end (without breaking
constant-time indexing). The same trick of keeping extra space
at the tail end can work at the head; it requires keeping one
additional offset to show where the occupied cells start.

If the OP had said he expected insert and append to be the same speed I
might buy that but [...]

Hmmm ... let me clarify what I'm selling: We can make lists
perform efficiently as double-ended queues without breaking
anything or perceptibly hurting anyone's efficiency. Until this
thread, I hadn't realized that Python's lists are much slower
than Perl's in important cases:

http://perlmonks.thepen.com/17890.html
Would this be a PEP-size change, or just a small fix?
--
--Bryan

[Bryan Olson]

Hmmm ... let me clarify what I'm selling: We can make lists
perform efficiently as double-ended queues without breaking
anything or perceptibly hurting anyone's efficiency. Until this
thread, I hadn't realized that Python's lists are much slower
than Perl's in important cases:

http://perlmonks.thepen.com/17890.html

Would this be a PEP-size change, or just a small fix?

"Futile" is closer -- it's been debated to death repeatedly. Python
2.4 adds a deque type instead, with O(1) insert/remove at both ends,
regardless of access pattern. That's O(1) per operation (not just
amortized O(1) -- the deque type never needs to move entries).

Tim Peters wrote:

[Bryan Olson]

[...] I hadn't realized that Python's lists are much slower
than Perl's in important cases:

http://perlmonks.thepen.com/17890.html

Would this be a PEP-size change, or just a small fix?

"Futile" is closer -- it's been debated to death repeatedly. Python
2.4 adds a deque type instead, with O(1) insert/remove at both ends,
regardless of access pattern. That's O(1) per operation (not just
amortized O(1) -- the deque type never needs to move entries).

But it breaks (efficient) indexing. Since we can have it all
like Perl, why not?

Googling up "dequeue" together with "O(1)" in comp.lang.pytho n,
(and with the misspelling "deque" which returns more results) I
see some discussion, but very little reason against the
enhancement. One post by Tim Peters suggests difficulty of
implementation as a major reason.
--
--Bryan

[Bryan Olson, on complicating the list object again, and 2.4's deque type]

But it breaks (efficient) indexing. Since we can have it all
like Perl, why not?

As I said, the best Perl can do is O(1) amortized. 2.4's deque does
better than that, and that can be important in classes like Python's
Queue.Queue where threads typically block waiting for pops and pushes
(but has no use at all for random access).

If you follow the link you gave last time and read to the bottom
following the other links, you'll find that Perl lists had
quadratic-time behavior under the steady-state queue pattern for a
long time. That was eventually fixed -- or so they say. Small
details are both tricky and vital. 2.4's deque implementation is
obviously immune to "bad" patterns, steady-state queue or otherwise.

Most immediately damning, adding another member to the list struct (to
keep track of the "low bound") would increase the size of every list
object by 8 bytes, on 32-bit boxes. Python lists are easy to spell,
use and access, and some Python apps use millions of small lists.
They wouldn't appreciate the RAM hit for a mostly-useless feature.
Most Perl programmers seem to be so confused by Perl lists that they
only use them when they have to, to shift function arguments in and
out <0.6 wink>. That's a use case for lists Python doesn't have at
all.

You can pursue it if you want to, but with the 2.4 deque type I have
no interest in messing more with the list type.

Tim Peters wrote:

[Bryan Olson, on complicating the list object again, and 2.4's dequetype]

But it breaks (efficient) indexing. Since we can have it all
like Perl, why not?

As I said, the best Perl can do is O(1) amortized.

In fact, as both of us said.
If you follow the link you gave last time and read to the bottom
following the other links, you'll find that Perl lists had
quadratic-time behavior under the steady-state queue pattern for a
long time. That was eventually fixed -- or so they say. Small
details are both tricky and vital.
Agreed. But those Perl wizards, misguided as they may be, are
pretty sharp.
2.4's deque implementation is
obviously immune to "bad" patterns, steady-state queue or otherwise.

Most immediately damning, adding another member to the list struct (to
keep track of the "low bound") would increase the size of every list
object by 8 bytes, on 32-bit boxes. Python lists are easy to spell,
use and access, and some Python apps use millions of small lists.
They wouldn't appreciate the RAM hit for a mostly-useless feature.
Most Perl programmers seem to be so confused by Perl lists that they
only use them when they have to, to shift function arguments in and
out <0.6 wink>.
We must know different Perl programmers.
That's a use case for lists Python doesn't have at
all.

You can pursue it if you want to, but with the 2.4 deque type I have
no interest in messing more with the list type.

I'm talking about facilities and their implementations , not
people. True, when I pointed out that Perl nails this one, I
was kinda' thinking the comparison might motivate Pythoners to
pursue the same enhancement. It was certainly *not* meant to
deride anyone who contributed to implementing Python.

Is Tim the superior Pythoner? Duh. Does Python rock? Sure.
Is saving four-or-eight bytes more or less valuable than
providing efficient insert at both ends? With all due respect
to Python and the people who implemented it, Perl kicks on this
one.
--
--Bryan

[Bryan Olson, on deques & Python's list type]
....

Agreed. But those Perl wizards, misguided as they may be, are
pretty sharp.
Yup.

....

[Tim]

You can pursue it if you want to, but with the 2.4 deque type I have
no interest in messing more with the list type.

[Bryan] I'm talking about facilities and their implementations , not people.
Sure! 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.
True, when I pointed out that Perl nails this one,
Which part I disagree with, for reasons already given.
I was kinda' thinking the comparison might motivate Pythoners to
pursue the same enhancement.
And the desire for efficient "both ends" operation led to 2.4's deque
type, which isn't "the same" enhancement because it didn't end up in
the base list type, but is a better enhancement for people who truly
need both-ends performance.
It was certainly *not* meant to deride anyone who contributed to implementing
Python.
I didn't read it that way.
Is Tim the superior Pythoner? Duh. Does Python rock? Sure.
Is saving four-or-eight bytes more or less valuable than
providing efficient insert at both ends?
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 majority who don't care
don't pay for it.
With all due respect to Python and the people who implemented it, Perl kicks
on this one.

I agree that Perl has a good approach here. I think Python's is better, though.

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=NU LL) plus
malloc's bookkeeping. Any non-empty list additionally allocates
space for at least 8 pointers, plus malloc's bookkeeping.
--
--Bryan

[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 straightforward ly 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=NU LL)
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.