numpy/numpy — pull request #3329 by JDWarner (2013-05-12 05:45:24+00:00)
Title: ENH: improved, faster algorithm for array padding

Overview
--------
The current implementation of `np.pad`, based on vector functions and `np.apply_along_axis`, scales poorly with dimensionality. When attempting to pad an array of shape (40, 40, 40, 40) by 5, execution times are above 20s for most modes, and some over 90s (see below). `pad` becomes functionally unusable on rank >5 arrays. A cursory profile shows the culprit is `np.apply_along_axis`, which was core to the old algorithm. A new approach was needed.

This new implementation is a completely new method which is fully vectorized, building each abstracted n-dimensional "padding block" in a single step and then using `np.concatenate`. Each dimension is padded individually, taking advantage of the inherent separability of padding. Result: for all combinations of inputs tested this new version is faster, and it scales much better. Execution times are ~25% lower for small rank 1 arrays to >99% lower for rank 4+ arrays (see below).

The API is entirely preserved. Some minor functionality changes were made to enable this in the input parsing blocks/private functions. Unfortunately the prior API allowed a user to pass a vector function as `mode`, which could not be generalized into the new framework. Thus, the original, slow execution loop is retained exclusively to retain backwards compatibility with this option.

One test was changed, because this algorithm now uses proper IEEE correct rounding before re-casting padded results calculated as floating point data instead of truncation via simple `.astype()`. Values of 5.5 are now properly rounded to 6 in this test. All other tests pass.

**Todo**: With permission I'd like to add a `mode='zero'` shortcut for brevity, as this is a very common case. Other shortcuts might also be useful, like `cval` instead of `constant_values`, for those who flirt with RSI.

Time Tests
-----
Time to pad a (40, 40, 40, 40) array by 5 before and after each dimension on a Core i7 processor. Call used:
```python
test4d = np.arange(40 ** 4).reshape(40, 40, 40, 40)
%timeit np.pad(test4d, 5, mode='mode')
```

**Old (current) version**
constant: 17.5
linear_ramp: 109.6
edge: 21.1
maximum: 33.2
minimum: 33.4
median: 66.6
mean: 47.6
reflect: 93.03
symmetric: 94.8
wrap: 88.3

**New version**
constant: 0.167
linear_ramp: 0.367
edge: 0.185
maximum: 0.252
minimum: 0.256
median: 0.783
mean: 0.466
reflect: 0.142
symmetric: 0.140
wrap: 0.144