Python list append timings

Question

cat /proc/meminfo

MemTotal: 3981272 kB

I ran this simple test in python

#!/usr/bin/env python
import sys
num = int(sys.argv[1])
li = []
for i in xrange(num):
    li.append(i)


$ time ./listappend.py 1000000

real    0m0.342s
user    0m0.304s
sys 0m0.036s

$ time ./listappend.py 2000000

real    0m0.646s
user    0m0.556s
sys 0m0.084s

$ time ./listappend.py 4000000

real    0m1.254s
user    0m1.136s
sys 0m0.116s

$ time ./listappend.py 8000000

real    0m2.424s
user    0m2.176s
sys 0m0.236s

$ time ./listappend.py 16000000

real    0m4.832s
user    0m4.364s
sys 0m0.452s

$ time ./listappend.py 32000000

real    0m9.737s
user    0m8.637s
sys 0m1.028s

$ time ./listappend.py 64000000

real    0m56.296s
user    0m17.797s
sys     0m3.180s

Question:

The time for 64000000 is 6 times more than the time for 32000000 but before that the times were simply doubling. Why so ?

Answer 1

TL;DR - Due to RAM being insufficient & the memory being swapped out to secondary storage.

I ran the program with different sizes on my box. Here are the results

/usr/bin/time ./test.py 16000000
2.90user 0.26system 0:03.17elapsed 99%CPU 513480maxresident
0inputs+0outputs (0major+128715minor)pagefaults

/usr/bin/time ./test.py 32000000
6.10 user 0.49 system 0:06.64 elapsed 99%CPU 1022664maxresident
40inputs (2major+255998minor)pagefaults

/usr/bin/time ./test.py 64000000
12.70 user 0.98 system 0:14.09 elapsed 97%CPU 2040132maxresident
4272inputs (22major+510643minor)pagefaults

/usr/bin/time ./test.py 128000000
30.57 user 23.29 system 27:12.32 elapsed 3%CPU 3132276maxresident
19764880inputs (389184major+4129375minor)pagefaults

• User time the time the program ran as the user. (running user logic)
• System time the time the program executed as the system. (i.e., time spent in system calls)

• Elapsed time The total time the program executed. (includes waiting time..)

  Elapsed time = User time + System Time + time spent waiting
  

• Major Page Fault Occurs when a page of memory isn't in RAM & has to be fetched from a secondary device like a Hard Disk.

• 16M list size: list is mostly in memory. Hence no page faults.

• 32M list size: parts of list has to be swapped out of memory. Hence the little bit bump from exact two fold increase of elapsed time .
• 64M list size: increase in elapsed time is more than two fold due to 22 major pagefaults.
• 128M list size: The elapsed time has increased from 14 sec to over 27 minutes !! The waiting time is almost 26 minutes. This is due to a huge number of pagefaults (389184). Also notice the CPU usage is down to 3% from 99% due the the massive waiting time.

As unutbu pointed out python interpreter allocating a O(n*n) extra space for lists as they grow the situation is only worsened.

Answer 2

According to effbot:

The time needed to append an item to the list is “amortized constant”; whenever the list needs to allocate more memory, it allocates room for a few items more than it actually needs, to avoid having to reallocate on each call (this assumes that the memory allocator is fast; for huge lists, the allocation overhead may push the behaviour towards O(n*n)).

(my emphasis).

As you append more items to the list, the reallocator will try to reserve ever-larger amounts of memory. Once you've consumed all your physical memory (RAM) and your OS starts using swap space, the shuffling of data from disk to RAM or vice versa will make your program very slow.