array, list, performance...

[Scott Gilbert]

Kragen Sitaker <kragen at pobox.com> wrote: 
> >>> 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.

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.  Also, it's pretty tough to tell the difference
between O(N) and O(N*log(N)) with such small numbers.

Here's some code that just counts the operations:

def roundupsize(n):
    "Very similar to what is actually in listobject.c"
    nbits = 0
    n2 = n>>5
    n2>>=3
    nbits+= 3
    while n2:
      n2>>=3
      nbits+=3
    return ((n>>nbits) + 1) << nbits

def count(N):
    ops = 0
    size = 0
    i = 0
    while i<N:
        i += 1
        if i>size:
            # have to pay for a copy and append
            ops += size
            ops += 1
            size = roundupsize(i)
        else:
            # only pay for append
            ops += 1
    return ops

# N, ops, N/ops for powers of 10
1 1 1.0
10 18 0.555555555556
100 724 0.138121546961
1000 12264 0.0815394651011
10000 139536 0.0716660933379
100000 1590432 0.0628759984709
1000000 18333760 0.0545441851535
10000000 165188736 0.0605368152947
100000000 1425399552 0.0701557678054


# N, ops, N/ops for powers of 2
1 1 1.0
2 2 1.0
4 4 1.0
8 8 1.0
16 24 0.666666666667
32 80 0.4
64 288 0.222222222222
128 1088 0.117647058824
256 4224 0.0606060606061
512 5888 0.0869565217391
1024 12288 0.0833333333333
2048 37376 0.0547945205479
4096 50688 0.0808080808081
8192 101888 0.0804020100503
16384 302592 0.0541455160745
32768 409088 0.0801001251564
65536 818688 0.0800500312695
131072 2424320 0.054065469905
262144 3276288 0.0800125019534
524288 6553088 0.0800062504883
1048576 19398144 0.0540554807718
2097152 26213888 0.0800015625305
4194304 52428288 0.0800007812576
8388608 155188736 0.0540542323896
16777216 209714688 0.080000195313
33554432 419429888 0.0800000976564


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.