Source-linked AI summary
The NumPy array: a structure for efficient numerical computation
Stefan Van Der Walt, S. Chris Colbert, Gaël Varoquaux
TL;DR
High-level Python data structures are not ideally suited to high-performance numerical computation. The paper presents NumPy arrays and shows that vectorization, memory sharing without copying, and broadcasting enable efficient computation with significant performance gains as datasets grow large.
Problem
Python’s high-level data structures are not ideally suited to high-performance numerical computation.
Method
The paper presents NumPy arrays and uses vectorization, memory sharing without copying, and broadcasting to implement efficient numerical computations.
Results
NumPy enables significant performance gains as datasets grow large by reducing Python-loop overhead, avoiding data copies, and reducing operation counts.
Takeaways & Limitations
NumPy arrays provide a high-level structure for concise numerical computation while retaining control over memory allocation and performance.
Takeaways & Limitations
Vectorization and broadcasting are not universally optimal; repeated operations on very large memory regions may benefit from an outer loop with a vectorized inner loop.
Abstract
from arXiv · showhide
In the Python world, NumPy arrays are the standard representation for numerical data. Here, we show how these arrays enable efficient implementation of numerical computations in a high-level language. Overall, three techniques are applied to improve performance: vectorizing calculations, avoiding copying data in memory, and minimizing operation counts. We first present the NumPy array structure, then show how to use it for efficient computation, and finally how to share array data with other libraries.
Introduction
Python’s general-purpose data structures are not ideally suited to high-performance numerical computation, motivating the development of the multidimensional NumPy array. NumPy arrays provide uniform, shaped collections whose elements can be indexed and sliced using familiar Python notation.
- NumPy arrays were developed as a data structure for efficient array computation because Python’s lists and dictionaries are not ideally suited to high-performance numerical computation.
- A NumPy array is a multidimensional, uniform collection characterized by its element type and shape.Arrays can represent matrices and higher-dimensional data, including numbers, booleans, and dates.
- Array elements and subarrays can be accessed with bracket indexing and standard start:stop:step slicing, using zero-based indexing.Examples include selecting initial rows, column ranges, and every second row.
The structure of a NumPy array: a view on memory
A NumPy array describes memory through metadata that specifies where data begins, what elements it contains, its shape, and how elements are traversed. By changing this metadata, NumPy can reinterpret the same memory as different arrays without copying data, making such operations highly efficient.
- The structure of a NumPy array: a view on memory: A NumPy array describes memory using a data pointer, data type, shape, strides, and flags governing modification and memory layout.Shape specifies array dimensions, while strides specify the byte skips needed to reach subsequent elements.
- The structure of a NumPy array: a view on memory: NumPy’s strided memory model lets multiple array views interpret the same underlying memory differently without copying data.A view can select only every second element by changing strides, while modifications remain shared between the view and the original array.
- The structure of a NumPy array: a view on memory: Changing strides can transpose or reshape an array at zero cost, provided the compatible metadata still references the same memory.The shape, strides, and data type may also be specified manually to create varied interpretations of the underlying data.
- The structure of a NumPy array: a view on memory: The resulting arrays differ in interpretation through shape, strides, and data type, but all point to the same memory and require no copying.Because these operations avoid memory copies, they are extremely efficient.
Numerical operations on arrays: vectorization
NumPy accelerates element-wise computation by vectorizing operations over arrays rather than using explicit loops. It also supports broadcasting across compatible shapes without physically constructing expanded arrays, saving memory.
- Vectorization: Vectorization groups element-wise operations, allowing NumPy to perform computations on large datasets much faster than traditional for-loops.NumPy implements vectorized operations in C, producing a significant speed improvement.
- Vectorization: NumPy applies arithmetic element-wise to arrays, including subtraction between two arrays.For example, b - a produces array([2, 6, 10]).
- Broadcasting: When arrays have compatible but unequal shapes, NumPy broadcasts operations across their shared dimensions.Broadcasting expands arrays conceptually so operations become viable.
- Broadcasting: Broadcasted arrays are never physically constructed; NumPy accesses the appropriate elements during computation to save memory.The operation is valid only under NumPy’s broadcasting rules.
Broadcasting Rules
NumPy broadcasts two arrays when corresponding dimensions are equal, or when either dimension is 1 or None. In such cases, the output dimension expands to the larger size, producing shape (2, 4, 3) for the example arrays.
- Broadcasting Rules: Broadcasting requires each pair of corresponding dimensions to be equal or for either dimension to be 1 or None.When a dimension is 1 or None, NumPy expands it to the larger corresponding dimension.
- Broadcasting Rules: The example arrays with shapes (2, 4, 3) and (4, 1) are compatible for the operation z = x + y.
- Broadcasting Rules: The broadcasting operation yields an output array of shape (2, 4, 3).
Vectorization and broadcasting examples
NumPy vectorization and broadcasting make array computations substantially faster while preserving concise code and control over memory allocation. The examples also show that slicing, in-place updates, and optimized inner loops improve performance, with caching limitations for very large repeated operations.
- Vectorized function evaluation: 1 milisecond versus approximately 500 miliseconds: applying a function to a NumPy array uses a fast vectorized loop, though large temporaries can reduce scalability.The computation expands into multiple temporary arrays as input size grows.
- In-place vectorization: 600 microseconds: NumPy’s in-place operations nearly double the speed of naive vectorization without allocating new memory.The example avoids computing 3*x in-place because that would modify the original input array.
- Slicing and differencing: 100 times faster: NumPy slicing makes forward finite differencing concise for a 1000-element array compared with a Pure Python for-loop.Subtracting adjacent slices produces the numerator and denominator arrays for the forward divided difference.
- Matrix operations and broadcasting: 9 miliseconds: NumPy projects 100000 three-dimensional points to pixel coordinates with a 70x speedup over a Python for-loop by combining dot products, element-wise division, and broadcasting.The division broadcasts each row by its third coordinate.
- Limitation: Vectorization and broadcasting are not universal solutions: for repeated operations on very large memory regions, an outer for-loop with a vectorized inner loop may use the system cache more effectively.The limitation concerns optimal cache use rather than the clarity or concision of the array code.
Sharing data
This section shows how NumPy avoids copying data when working with foreign memory and disk-backed arrays. It also demonstrates how the array interface exposes externally allocated memory to NumPy and allows shared updates.
- Memory mapping: Memory mapping lets NumPy address only part of a very large disk-stored array without loading the entire array into memory.Memory-mapped arrays use the same interface as other NumPy arrays, and altered data can be written back to disk with flush.
- Foreign memory: NumPy can use foreign memory without copying it, including memory allocated by external C++ or Fortran libraries, through the __array_interface__ protocol.The protocol describes a memory block using fields including its data address and shape, allowing NumPy to view objects with a valid __array_interface__ dictionary as arrays.
- Foreign memory: Modifying a NumPy view can update the underlying foreign memory, as demonstrated when changing byte values transforms the MutableString from abcde to cdefg.The example exposes a ctypes-allocated string buffer as a uint8 array and shows that array updates propagate to the original string.
- Foreign memory: NumPy’s array interface can interpret any block of memory when the required metadata is supplied in an __array_interface__ dictionary.The MutableString example illustrates this general mechanism by exposing externally allocated memory as a NumPy array.
- Structured arrays: Structured arrays store homogeneous compound elements and can represent records containing fields such as timestamps and positions.They are useful for reading complex binary files whose records contain multiple typed fields.
Conclusion
NumPy’s N-dimensional array is a high-level structure that supports efficient numerical computation through vectorization, data sharing without copying, and broadcasting. These capabilities provide significant performance gains as datasets grow large.
- NumPy’s N-dimensional array facilitates vectorization of for-loops in a high-level data structure.
- Its memory description enables many operations without copying data, improving performance as datasets grow large.
- Broadcasting combines multidimensional arrays to reduce the number of operations in numerical computation.