92

I just changed a program I am writing to hold my data as numpy arrays as I was having performance issues, and the difference was incredible. It originally took 30 minutes to run and now takes 2.5 seconds!

I was wondering how it does it. I assume it is that the because it removes the need for for loops but beyond that I am stumped.

3
  • 6
    I'm guessing it's because numpy arrays are implemented in C rather than in Python. Commented Dec 5, 2011 at 12:55
  • 16
    @NoufalIbrahim: Python lists are also implemented in C.
    – Fred Foo
    Commented Dec 5, 2011 at 12:59
  • 15
    Pretty vague question without any indication of what the two different programs were doing and how they were implemented. Commented Dec 5, 2011 at 13:02

6 Answers 6

131

Numpy arrays are densely packed arrays of homogeneous type. Python lists, by contrast, are arrays of pointers to objects, even when all of them are of the same type. So, you get the benefits of locality of reference.

Also, many Numpy operations are implemented in C, avoiding the general cost of loops in Python, pointer indirection and per-element dynamic type checking. The speed boost depends on which operations you're performing, but a few orders of magnitude isn't uncommon in number crunching programs.

5
  • 5
    How is it possible to offer Python front-end for these C-written operations? What is this technique named?
    – user3046287
    Commented Mar 4, 2017 at 11:52
  • This cannot be true. Python lists are not arrays of pointers when the elements are primitive types, like integers. A quick way to test that is to save a number into a variable and form an array with that variable in it. If you change the variable, the array does not change.
    – Rohan
    Commented Jun 2, 2017 at 2:09
  • 18
    @Rohan Remember even primitive types are objects. So when you added that variable to the list, you are really just adding the object that particular variable points to to the list. In this case, this object is a number. So when you change the variable, or more precisely, rebinds the name to a new integer, you are not changing the properties of the original object, i.e., the original number. Hence it is expected that the 'corresponding' number in the array does not change its value.
    – Kun
    Commented Jul 23, 2017 at 1:09
  • @Kun so if I understand you correctly, if the value in the second list that is changed were not a primitive type, you are changing the contents of the "same" object, whereas if you change a primitive type, your are now referencing a different object? Commented Dec 28, 2020 at 5:45
  • @Rohan that's totally wrong. The test you propose wouldn't even demonstrate that. Commented Oct 21, 2021 at 0:02
27

numpy arrays are specialized data structures. This means you don't only get the benefits of an efficient in-memory representation, but efficient specialized implementations as well.

E.g. if you are summing up two arrays the addition will be performed with the specialized CPU vector operations, instead of calling the python implementation of int addition in a loop.

3
  • 2
    These (specialized operations and dynamic optimization) are the correct answers. Minor factors such as pre-fetching and locality of reference only become significant after the main performance factors (interpreter overhead) are addressed.
    – Dave
    Commented Dec 5, 2011 at 13:15
  • 4
    locality of reference is important for two reasons: because of the locality itself (and its effects on caching), and because a lack of indirection means that the instructions to process indirection can be skipped. Commented Dec 5, 2011 at 14:13
  • Correct. One mechanism is Atlas (math-atlas.sourceforge.net/faq.html#what), which are specialized libraries that can use machine-specific instructions.
    – dfrankow
    Commented Jul 2, 2021 at 17:21
5

Consider the following code:

import numpy as np
import time

a = np.random.rand(1000000)
b = np.random.rand(1000000)

tic = time.time()
c = np.dot(a, b)
toc = time.time()

print("Vectorised version: " + str(1000*(toc-tic)) + "ms")

c = 0
tic = time.time()
for i in range(1000000):
    c += a[i] * b[i]
toc = time.time()

print("For loop: " + str(1000*(toc-tic)) + "ms")

Output:

Vectorised version: 2.011537551879883ms
For loop: 539.8685932159424ms

Here Numpy is much faster because it takes advantage of parallelism (which is the case of Single Instruction Multiple Data (SIMD)), while traditional for loop can't make use of it.

4
  • 2
    Please consider adding your code as text (using the code markup), as opposed to an image of your code. It makes your answer more accessible to readers.
    – Gavin
    Commented May 2, 2019 at 6:10
  • 4
    It seems to be unlikely that paralellism is the main reason for a 250x improvement. There aren't 250 CPU threads over which to parallelize.
    – Christian
    Commented Mar 17, 2020 at 14:08
  • 1
    This is the best fit explanation
    – Cozy
    Commented Jun 12, 2020 at 8:08
  • 4
    No, numpy does not make use low level parallelism (though a particular BLAS library may use it for dot.) The primary speed difference is due to compiled loops versus interpreted ones.
    – hpaulj
    Commented Sep 18, 2021 at 14:32
1

Numpy arrays are stored in memory as continuous blocks of memory and python lists are stored as small blocks which are scattered in memory so memory access is easy and fast in a numpy array and memory access is difficult and slow in a python list.

source: https://algorithmdotcpp.blogspot.com/2022/01/prove-numpy-is-faster-than-normal-list.html

1
  • While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review Commented Jan 14, 2022 at 17:56
0

Numpy arrays are extremily similar to 'normal' arrays such as those in c. Notice that every element has to be of the same type. The speedup is great because you can take advantage of prefetching and you can instantly access any element in array by it's index.

1
  • 2
    Could you elaborate on how having the same type for each element makes computations faster?
    – Rohan
    Commented Jun 2, 2017 at 2:10
-1

You still have for loops, but they are done in c. Numpy is based on Atlas, which is a library for linear algebra operations.

http://math-atlas.sourceforge.net/

When facing a big computation, it will run tests using several implementations to find out which is the fastest one on our computer at this moment. With some numpy builds comutations may be parallelized on multiple cpus. So you will have highly optimized c running on continuous memory blocks.

3
  • 11
    Numpy isn't based on Atlas. It can use, if available, a BLAS implementation for a very, very small subset of its functionality (basically dot, gemv and gemm). That BLAS can be the built-in reference BLAS it ships with, or Atlas, or Intel MKL (the enthought distribution is built with this).
    – talonmies
    Commented Dec 5, 2011 at 13:16
  • @talonmies Hi, can you please provide some useful links that contain documentation about what you say ?
    – SebMa
    Commented Jul 18, 2018 at 13:09
  • 2
    @SebMa See numpy.org/install, chapter "NumPy packages & accelerated linear algebra libraries".
    – Thomas
    Commented Mar 7, 2021 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.