array, list, performance...

[Tim Peters]

[Kragen Sitaker]
> >>> import MetaPy.Speed
> >>> def mklist(n):
> ...     ar = []
> ...     for ii in xrange(n):
> ...             ar.append(ii)
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(0))
>  1.7825510264682151e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(1))
>  2.862680041153042e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(10))
>  7.8054009556034588e-05
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(100))
>  0.00057740376706547905
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(1000))
>  0.0055893541133707342
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(10000))
>  0.055918868174255905
> >>> MetaPy.Speed.seconds_per_call(lambda: mklist(100000))
> 0.59515897688580466
>
> Looks linear to me.

[Scott Gilbert]
> In a very practical sense your test is the one that matters, since
> it's usually time that we care about.  Your test could just as easily
> be measuring how linear the memory allocator is or whether cache
> effects are linear, since either of those could dwarf the cost of the
> list operations.  Who knows, you might actually have a realloc() that
> does something smart.

In the old days, Guido was running on a Solaris box whose realloc eventually
moved a growing list to the end of memory, so that subsequent growth only
resulted in an sbrk call to boost the VM highwater mark.  This was pretty
common, and gave linear time for such tests despite outraged theoreticians'
attempts to demonstrate it was quadratic time <wink>.  The sbrk gimmick
fails if you're growing *more* than one list repeatedly, though, and for
that reason simplified benchmarks may not have anything to do with real-life
performance.  More modern systems eventually move a growing thing into its
own mmap'ed memory segment, and then the true behavior depends on how some
other inscrutable OS subsystem behaves.

> Also, it's pretty tough to tell the difference between O(N) and
> O(N*log(N)) with such small numbers.

Yup!

> Here's some code that just counts the operations:
> [followed by code and some output]
> ...
> The powers of 10 wave up and down a bit, but the powers of 2 make a
> nice .08 .08 .05 pattern.  Still looks linear, but it has bouts of
> being non-linear before the next major step compensates for it.  It
> doesn't look to be O(N*N), and that's what really matters for large N.

It's linear.  Ponder the comment in listobject.c:

	/* Round up:
	 * If n <       256, to a multiple of        8.
	 * If n <      2048, to a multiple of       64.
	 * If n <     16384, to a multiple of      512.
	 * If n <    131072, to a multiple of     4096.
	 * If n <   1048576, to a multiple of    32768.
	 * If n <   8388608, to a multiple of   262144.
	 * If n <  67108864, to a multiple of  2097152.
	 * If n < 536870912, to a multiple of 16777216.
	 * ...
	 * If n < 2**(5+3*i), to a multiple of 2**(3*i).
	 ...

The last line implies that overallocation, when it occurs, is never by less
than n/32 "extra" elements [2**(3*i)/2**(5+3*i) == 1/2**5].  That puts a
lower bound of 3.125% on excess, and that alone is enough to guarantee
amortized linear time.  Let r = 1+1/32.  If the final size is N, then
(ignoring details <wink>) you had to copy N/r elements on the last resize,
N/r**2 on the penultimate resize, N/r**3 on the one before that, etc.  The
total number of element copies is thus bounded above by N/r + N/r**2 + ... =
N/r * (1 + 1/r + 1/r**2 + ...) = N/(r-1) = 32*N.  Add N more for the
individual appends to get an upper bound of 33*N operations.  Then your "N /
operations" statistic is bounded below by N/(33*N) = 1/33 ~= 0.03.  You
never saw a number near that low because overallocation actually varies
between factors of 1/32 and 1/4 (right after a boundary is crossed in the
table) "extra" elements.

This may seem like too-mild overallocation anyway, but "even on Win95" most
reallocs under this scheme don't actually copy anything.  So much for trying
to guess what happens <wink>.