Huge time difference on creating numpy.zeros for tiny difference in size of array

Question

I was trying to determine the time complexity of doing numpy.zeros so I ran the following tests. It seems to be linear with the size of the array you're creating, but at a certain point there is a huge disparity on how much time it takes. Here are the interesting cases where hardly changing the array size at all changes the creation time by an order of magnitude.

python -m timeit -n 1000 -s "import numpy" "numpy.zeros(64500, dtype=float)"
10000 loops, best of 3: 33.5 usec per loop


python -m timeit -s "import numpy" "numpy.zeros(65000, dtype=float)"
1000 loops, best of 3: 418 usec per loop

That is a huge disparity! Below an array of size 64500 the time complexity is roughly linear with array size, and above an array of size 65000 the time complexity is roughly linear. Why is there such a staggering time difference here?

My understanding is that internally Python stores everything in its own special heap. Is this occurring because numpy uses C, and it stores arrays of a certain size on the C stack and arrays of another size on the C heap? I'm not even sure if that question makes sense.

I'm using 32-bit python 3.3.1 and numpy 1.7.0rc1 on a Windows 7 machine.

Answer 1

I had the same problem on my computer. Don't know to explain it.

I plotted the time divided by the length of the array, so it is supposed to stay constant if the time complexity is linear.

the plot is average of 10 runs, so the high peak is keep seeming in every trial

(The numbers on the x axis are log of the array size, while the y is time in second divided by the array size)