MAINT: Rewrite numpy.pad without concatenate #11358
Conversation
Passes unit tests: - TestConstant - TestEdge - TestZeroPadWidth - TestLegacyVectorFunction - TestNdarrayPadWidth - TestUnicodeInput - TestLinearRamp
|
I was hoping it might be possible to achieve this more incrementally, without throwing out all of the old docstrings |
I thought about doing this incrementally but I see no easy way to do that and think that would make this PR and the rewrite in general more tedious and complicated. Right now I'm still heavily iterating and changing the code. Therefore I didn't pay too much attention to the (old & new) docstrings. But I'll try to reuse what I can of the old docstrings when I reach that stage. |
Creating the linear ramp as an array with 1-sized dimensions except for the one given by `axis` allows implicit broadcasting to the needed shape. This seems to be even a little bit faster that doing this by hand and allows the simplicifaction of the algorithm. Note: Profiling and optimization will be done again at a later stage.
Addresses feedback raised in PR.
This completes the first draft of the complete rewrite meaning all unit tests should pass from this commit onwards.
The set functions were nearly the same, apart from some index offsets. Merging them reduces code duplication.
The rewrite in past commits fixed this bug.
And include test to protect against regression.
Major changes & goals: Don't deal with pad area in the front and back separately. This modularity isn't needed and makes handling of the right edge more awkward. All modes now deal with the left and right side at the same time. Move the creation of the linear ramps fully to its own function which behaves like a vectorized version of linspace. Separate calculation and application of the pad area where possible. This means that _get_edges can be reused for _get_linear_ramps. Combine _normalize_shape and _validate_lengths in a single function which should handles common cases faster. Add new mode "empty" which leaves the padded areas undefined. Add documentation where it was missing.
Reduce branching and try to make the calculation of the various indices easier to understand.
|
Not sure what the failure in Shippable is about. @seberg, @eric-wieser, @mattip I think that I have addressed all your suggestions and feel like this is close to being acceptable. Do you want to do a final iteration or do you agree? |
Keep parametrization ordered, otherwise pytest-xdist might believe that different tests were collected during parallelization causing test failures.
|
Should I add this PR to the release notes for 1.17? If so, how detailed should I explain the changes? The fix for #11216 and the new mode "empty" are obvious but what is the convention on describing internal optimizations, especially if their effect is heavily dependent on the chosen input? |
|
There is an |
as well as the new mode "empty" in release notes (see numpygh-11358).
|
This seems ready to go in. |
|
I resolved the merge conflict with the recent changes in #4808. Is there anything else blocking this? Should I perhaps send a small note on the mailing list? |
|
No, nothing blocking it, except I want to make one more careful pass and was sick and then tied down in long experiments and other things :/ for a while. Thanks for fixing the conflict and sorry about the delay when it probably could simply have been been merged for a while. |
|
@seberg Oh, no worries. I hope you're feeling better! I'm aware that changes of this scope do need careful consideration and that we are all doing this in our free time. There is no immediate reason to rush this. So if that wasn't clear, take my comment above as a curious query and not as a request. Please don't feel obligated to rush this! 🙂 |
|
OK, read through it once more and of course found no issues, so I could just squash and merge (probably will just do that tomorrow or so). Frankly, the biggest "issue" I saw is one of the Some things to maybe open an issue for:
I bet both were already discussed previously ;). |
Yep, I think both points came up already with the same conclusions.
Reading this now, I'm a little bit confused myself. I'm not sure anymore about the first part "must be padded with a single function". I guess it's a note meant to remind me of an earlier failed attempt. I remember that I found implementing these modes the most challenging. I'll explain the second part about "non-integer multiples" with an example: In this case, we perform 2 iterations to pad the dimension. First we pad by 4 elements and then only by 2 elements. With non-integer multiples of the original shape, I think I meant that we can only pad by a fraction of the original shape (in this case 2). I guess these notes are obsolete and in any case worded very badly. I'll remove them as they aren't useful now. |
These notes are badly worded or actually misleading. For a better explanation on how these functions work have a look at the context and comments just above the lines calling these functions.
|
@lagru and everyone else, thanks a lot. This is all a bit improvement. Sorry if it took a bit long to merge. |
|
Big thanks from me as well! I feel like the improvement was substantial thanks to everyone involved (especially @eric-wieser and @seberg). |
|
While this is still fresh in people's memory cache, maybe some of the open issues that mention pad (not all are actually about |
* ENH: Add support for constant, edge, linear_ramp to new numpy.pad Passes unit tests: - TestConstant - TestEdge - TestZeroPadWidth - TestLegacyVectorFunction - TestNdarrayPadWidth - TestUnicodeInput - TestLinearRamp * MAINT: Simplify diff / change order of functions * MAINT: Revert to old handling of keyword-only arguments * ENH: Add support for stat modes * ENH: Add support for "reflect" mode * MAINT: Remove _slice_column * ENH: Add support for "symmetric" mode * MAINT: Simplify mode "linear_ramp" Creating the linear ramp as an array with 1-sized dimensions except for the one given by `axis` allows implicit broadcasting to the needed shape. This seems to be even a little bit faster that doing this by hand and allows the simplicifaction of the algorithm. Note: Profiling and optimization will be done again at a later stage. * MAINT: Reorder arguments of a sum and fix typo Addresses feedback raised in PR. * ENH: Add support for "wrap" mode This completes the first draft of the complete rewrite meaning all unit tests should pass from this commit onwards. * MAINT: Merge functions for "reflect" and "symmetric" mode The set functions were nearly the same, apart from some index offsets. Merging them reduces code duplication. * TST: Add regression test for numpygh-11216 The rewrite in past commits fixed this bug. * BUG: Fix edge case for _set_wrap_both when pad_amt contains 0. And include test to protect against regression. * MAINT: Simplify and optimize pad modes Major changes & goals: Don't deal with pad area in the front and back separately. This modularity isn't needed and makes handling of the right edge more awkward. All modes now deal with the left and right side at the same time. Move the creation of the linear ramps fully to its own function which behaves like a vectorized version of linspace. Separate calculation and application of the pad area where possible. This means that _get_edges can be reused for _get_linear_ramps. Combine _normalize_shape and _validate_lengths in a single function which should handles common cases faster. Add new mode "empty" which leaves the padded areas undefined. Add documentation where it was missing. * TST: Don't use np.empty in unit tests * MAINT: Reorder workflow in numpy.pad and deal with empty dimensions Only modes "constant" and "empty" can extend dimensions of size 0. Deal with this edge case gracefully for all other modes either fail or return empty array with padded non-zero dimensions. Handle default values closer to their actual usage. And validate keyword arguments that must be numbers. * MAINT: Add small tweaks to control flow and documentation * BUG: Ensure wrap mode works if right_pad is 0 * ENH: Use reduced region of interest for iterative padding When padding multiple dimensions iteratively corner values are unnecessarily overwritten multiple times. This function reduces the working area for the first dimensions so that corners are excluded. * MAINT: Restore original argument order in _slice_at_axis * MAINT: Keep original error message of broadcast_to * MAINT: Restore old behavior for non-number end_values. * BENCH: Make the pad benchmark pagefault in setup * ENH/TST: Preserve memory layout (order) of the input array and add appropriate unit test. * STY: Revert cosmetical changes to reduce diff * MAINT: Pin dtype to float64 for np.pad's benchmarks * MAINT: Remove redundant code path in _view_roi * MAINT/TST: Provide proper error message for unsupported modes and add appropriate unit test. * STY: Keep docstrings consistent and fix typo. * MAINT: Simplify logical workflow in pad * MAINT: Remove dtype argument from _linear_ramp The responsibility of rounding (but without type conversion) is not really need in _linear_ramp and only makes it a little bit harder to reason about. * DOC: Add version tag to new argument "empty" * MAINT: Default to C-order for padded arrays unless the input is F-contiguous. * MAINT: Name slice of original area consistently for all arguments describing the same thing. * STY: Reduce vertical space * MAINT: Remove shape argument from _slice_at_axis Simplifies calls to this function and the function itself. Using `(...,)` instead should keep this unambiguous. This change is not compatible with Python 2.7 which doesn't support this syntax outside sequence slicing. If that is wanted one could use `(Ellipsis,)` instead. * TST: Test if end_values of linear_ramp are exact which was not given in the old implementation `_arange_ndarray`. * DOC: Improve comments and wrap long line * MAINT: Refactor index_pair to width_pair Calling the right value an index is just plain wrong as it can't be used as such. * MAINT: Make _linear_ramp compatible with size=0 * MAINT: Don't rely on negative indices for slicing Calculating the proper positive index of the start of the right pad area makes it possible to omit the extra code paths for a width of 0. This should make the code easier to reason about. * MAINT: Skip calculation of right_stat if identical If the input area for both sides is the same we don't need to calculate it twice. * TST: Adapt tests from numpygh-12789 to rewrite of pad * TST: Add tests for mode "empty" * TST: Test dtype persistence for all modes * TST: Test exception for unsupported modes * TST: Test repeated wrapping for each side individually. Reaches some only partially covered if-statments in _set_wrap_both. * TST: Test padding of empty dimension with constant * TST: Test if end_values of linear_ramp are exact which was not given in the old implementation `_arange_ndarray`. (Was accidentally overwritten during the last merge). * TST: Test persistence of memory layout Adapted from an older commit 3ac4d2a which was accidentally overwritten during the last merge. * MAINT: Simplify branching in _set_reflect_both Reduce branching and try to make the calculation of the various indices easier to understand. * TST: Parametrize TestConditionalShortcuts class * TST: Test empty dimension padding for all modes * TST: Keep test parametrization ordered Keep parametrization ordered, otherwise pytest-xdist might believe that different tests were collected during parallelization causing test failures. * DOC: Describe performance improvement of np.pad as well as the new mode "empty" in release notes (see numpygh-11358). * DOC: Remove outdated / misleading notes These notes are badly worded or actually misleading. For a better explanation on how these functions work have a look at the context and comments just above the lines calling these functions.
Description / Motivation
As suggested in #11033 (comment) and #11126 the current implementation of numpy.pad uses copies more than necessary. Currently most of the pad modes use
numpy.concatenateunder the hood to create the new array. This has to happen twice for each padded axis. It might be faster to pre-allocate the returned array once with the correct final shape and just set the appropriate edge values instead of concatenating them.Roadmap
Related
Closes #11126 (Initial proposal of this PR)
Closes #11216 (search for issue number in
test_arraypad.py)