Why isn't preallocating faster than using append?

Question

I was trying to create an example where preallocating a numpy array is quicker than using .append on a list, but ended up proving the opposite.

import numpy as np
import time

t = time.time()
emptyList   = []
for i in range(int(1e8)):
    emptyList.append(1)
print("Append: ", time.time() - t)

t = time.time()
emptyList   = np.empty(int(1e8))
for i in range(int(1e8)):
    emptyList[i] = 1
print("Preallocate: ", time.time() - t)

Which gives the following output:

Append:  12.733097314834595
Preallocate:  19.008652925491333

I'm very confused as to why appending to a list is quicker in this case. I've also tried using random numbers instead of '1' everywhere, but got the same result.

Also worth noting: When doing code timing like this, the builtin `timeit` module is better for more robust testing. It can automatically run hundreds or thousands of tests and give you statistics about mean and range of timings — G. Anderson, Jun 14 '21 at 21:47
Another observation: a list with size 1e8 is not a small and might take up several hundred of mb in ram. Depending on the free ram in your system, using the numpy array afterwards might involves a lot of swapping and therefore is slower. As a reference, having a list that large on my linux machine shows 900mb ram in use by the python process. — cicolus, Jun 14 '21 at 21:50
I guess I'll stop using numpy arrays to preallocate any large lists then. — Cyrano Chatziantoniou, Jun 14 '21 at 21:56

score 4 · Answer 1 · answered Jun 14 '21 at 21:42

It's because python lists aren't actually linked lists; they are implemented underneath as arrays: https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython

When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don’t require an actual resize.

They are being smarter than simply increasing each time a single append is requested, similar to how TCP works with a multiplicative increase.

Other reading: https://www.geeksforgeeks.org/internal-working-of-list-in-python/

How is Python's List Implemented?

Prune · Accepted Answer · 2021-06-14T21:47:26.627

4

Please note that you're not using the same class in both examples. You're comparing append for the built-in Python type list against assignment to -- not a list, but to allocate and assign to a NumPy array.

I would expect them to be much closer, but that's not the issue: you have two items here, allocation and assignment.

When I run your code as given, I get

Append:       16.296499013900757
Preallocate:  16.835283517837524

When I change the second loop to eliminate the NumPy overhead:

emptyList   = [0] * (int(1e8))

Result:

Append:       23.76796054840088
Preallocate:  11.050438404083252

edited Jun 14 '21 at 21:47

answered Jun 14 '21 at 21:44

Prune

76,765
14
60
81

2

OP says: "I was trying to create an example where preallocating a numpy array is quicker than using .append on a list", so it looks like they indeed _intended_ to compare different classes – ForceBru Jun 14 '21 at 21:47
1

I was unaware of the difference, this is a much better apples to apples comparison! Also very interesting that numpy brings such a large overhead with it. – Cyrano Chatziantoniou Jun 14 '21 at 21:52

score 0 · Answer 3 · answered Jan 10 '22 at 19:58

It is not possible to edit @Prune example, I offer this snippet of code in the attempt to propose an inclusive and complete example of her point:

import time

nb_rep = 1e7
t = time.time()
emptyList = []
for i in range(int(nb_rep)):
    emptyList.append(1)
print("Append: ", time.time() - t)

t = time.time()
emptyList = [1] * int(nb_rep)
for i in range(int(nb_rep)):
    emptyList[i] = 1
print("Preallocate: ", time.time() - t)

t = time.time()
emptyList = np.empty(int(nb_rep))
for i in range(int(nb_rep)):
    emptyList[i] = 1
print("Preallocate Numpy: ", time.time() - t)

the result locally:

Append:  0.6769435405731201
Preallocate:  0.5485126972198486
Preallocate Numpy:  0.9414911270141602

Why isn't preallocating faster than using append?

3 Answers3