Strange timing data for list.pop()

[Terry Reedy]

"Roy Smith" <roy at panix.com> wrote in message
news:roy-57B296.13170501082004 at 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