Strange timing data for list.pop()

[Roy Smith]

In the recent "transforming a list into a string" thread, we've been
discussing the fact that list.pop() is O(1), but list.pop(0) is O(n). I
decided to do a little timing experiment. To be sure, I did verify
experimentally the expected result, but along the way, I came upon an
interesting artifact that I'm at a loss to explain.

I used the following to generate some timing numbers for pop() on
various sized lists:

import time
for power in range (20):
i = 2 ** power
list = [1] * i
t0 = time.time ()
list.pop ()
t1 = time.time ()
t = t1 - t0
print i, t

I know wall clock time isn't a good way to time things, but it was a
first cut before I dove into the manual and found os.times(). The
interesting thing is the data that I got with the above code:

1 7.70092010498e-05
2 6.91413879395e-06
4 5.96046447754e-06
8 5.00679016113e-06
16 5.00679016113e-06
32 5.00679016113e-06
64 5.00679016113e-06
128 5.00679016113e-06
256 4.05311584473e-06
512 5.00679016113e-06
1024 5.00679016113e-06
2048 5.96046447754e-06
4096 9.05990600586e-06
8192 9.05990600586e-06
16384 9.05990600586e-06
32768 1.4066696167e-05
65536 2.31266021729e-05
131072 3.09944152832e-05
262144 3.60012054443e-05
524288 3.38554382324e-05

I plotted the data. http://www.panix.com/~roy/pop-times.png

An interesting shaped curve! I haven't done any curve fitting, but by
eye it looks something like k - log (1/n). The data is quite
repeatable, too. Admitting that clock time is a silly thing to be
measuring here, anybody have any clue what might be causing this
behavior?

This is on an otherwise idle 768 Mbyte PowerBook running OSX-10.3.4 and
Python 2.3.4.

[Terry Reedy]

"Roy Smith" <ro*@panix.com> wrote in message
news:ro***********************@reader1.panix.com.. .

In the recent "transforming a list into a string" thread, we've been
discussing the fact that list.pop() is O(1), but list.pop(0) is O(n). I
decided to do a little timing experiment. To be sure, I did verify
experimentally the expected result, but along the way, I came upon an
interesting artifact that I'm at a loss to explain.

I used the following to generate some timing numbers for pop() on
various sized lists:

import time
for power in range (20):
i = 2 ** power
list = [1] * i
t0 = time.time ()
list.pop ()
t1 = time.time ()
t = t1 - t0
print i, t

I know wall clock time isn't a good way to time things, but it was a
first cut before I dove into the manual and found os.times(). The
interesting thing is the data that I got with the above code:

1 7.70092010498e-05
2 6.91413879395e-06
4 5.96046447754e-06
8 5.00679016113e-06
16 5.00679016113e-06
32 5.00679016113e-06
64 5.00679016113e-06
128 5.00679016113e-06
256 4.05311584473e-06
512 5.00679016113e-06
1024 5.00679016113e-06
2048 5.96046447754e-06
4096 9.05990600586e-06
8192 9.05990600586e-06
16384 9.05990600586e-06
32768 1.4066696167e-05
65536 2.31266021729e-05
131072 3.09944152832e-05
262144 3.60012054443e-05
524288 3.38554382324e-05

I plotted the data. http://www.panix.com/~roy/pop-times.png
This appears to be a fitted spline or somesuch rather than the data itself.
Also, the data should better be plotted against power rather than 2**power.
Then you would see a flat region across half the plot.
An interesting shaped curve! I haven't done any curve fitting, but by
eye it looks something like k - log (1/n). The data is quite
repeatable, too. Admitting that clock time is a silly thing to be
measuring here, anybody have any clue what might be causing this
behavior?

cache effect when you exceed 2**10?

Terry J. Reedy

[Istvan Albert]

Roy Smith wrote:

anybody have any clue what might be causing this behavior?

Bad experimental setup.

Use the timeit module. Average your measurements.

[Roy Smith]

In article <cM********************@giganews.com>,
Istvan Albert <ia*****@mailblocks.com> wrote:

Roy Smith wrote:

anybody have any clue what might be causing this behavior?

Bad experimental setup.

Of course it was a bad experimental setup. I didn't measure what I set
out to measure. But, I did measure something interesting, and I'm
trying to figure out what it was.

[Pierre-Frédéric Caillaud]

Of course it was a bad experimental setup. I didn't measure what I set
out to measure. But, I did measure something interesting, and I'm
trying to figure out what it was.

That's how some great scientific discoveries were made ;)