Assemble new container in xpad by keeper · Pull Request #1808 · xtensor-stack/xtensor · GitHub

This pull request aims to reduce the overhead of xt::pad by creating a new container with padded shape, then copying the source object into the new container when using constant mode.

For example, when padding a 3x3 matrix with ((1, 1), (2, 2)), firstly a 5x7 matrix is created, then the original 3x3 matrix will be put into new_maxtrix[1:4, 2:5].

Although this code passed unittest, however here are something need to be dealt with:

Now xt::pad doesn't work with constant object (perhaps add std::remove_const in line 100?)
Whether or not other modes can also be built with the same fashion
Messed up diff after line 116. It just reduces the indentation but the diff make it hard to read

Any suggestions would be appreciated!

Edit:

Fixes #1806

Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

Previous commit does constant mode outside of for-loop, therefore the if-else block in for-loop is not necessary anymore. The diff looks a mess but it just reduces the indent. Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

Thanks @keeper for this initial step. With some work I'm sure we can come up with a nice ways to avoid the costly reallocations.

Some discussion points:

For constant the approach seems largely ok, though it could be improved because I think that you are assigning the interior twice. Did you time the new implementation and compare it to NumPy (and to the current implementation)?
Could you comment on how we could generalise to the other modes? Did you envision two branches: one constant and one in which views are used in the padded regions?
Something to reflect on is @emmenlau 's good suggestion to use SIMDified assignment, however I'm not the greatest expert here.

When using constant mode, `auto out = e;` is never used and it causes extra overhead, move it after constant mode handling fixes this. Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

Suggestion from: xtensor-stack#1808 (comment) Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

Sorry for late response.

For constant the approach seems largely ok

I did had some compile errors when passing const xarray<T> & to xt::pad() with my version, so I think I'm not dealing with the type in xt::pad() correctly and that's an issue I need to resolve. I'll attach the compile error.

Did you time the new implementation and compare it to NumPy (and to the current implementation)?

You are right about assigning the value twice, after correcting the issue it is as fast as Numpy :)

Could you comment on how we could generalise to the other modes?

I'm sorry that I can't answer this question just yet. I'm not familiar with other modes and need to understand them first, then I can figure out with what approach I may be able to optimize them.

Did you envision two branches: one constant and one in which views are used in the padded regions?

And I'm afraid that I don't fully understand your question. For "branch", do you mean the code path it goes? For example in my implementation when the mode is constant it goes to a block of code for constant mode and return the result, and other modes go their paths?

If that's the case I think I prefer this way. But it's just a personal preference when handling different cases.

Something to reflect on is @emmenlau 's good suggestion to use SIMDified assignment, however I'm not the greatest expert here.

Neither do I, but it sounds interesting. My only concern is, doesn't it make xt::pad() depend on xsimd?

--
Thank you again for the review and suggestions. I added the type alias and the performance improvement, and I'll look into other improvements later.

[1]: compile log: https://gist.github.com/keeper/32728c812782a44a0cfb81eab068543a
[2]: test code: https://gist.github.com/keeper/cd13e426cfd16f77c5bd878bd4dd2212

Thanks for tackling this!

General remarks regarding SIMD assignment:

xsimd is an optional dependency of xtensor. It is up to the end user to enable it or not when building its code depending on xtensor.
in order to avoid spreading #ifdef XSIMD everywhere in the code, a wrapper file (xtensor_simd.hpp) provides similar API to that of xsimd when this latter is not found or enabled.

This means that when dealing with SIMD assignment, the only matter to consider is whether the classes involved in the assignment provide a load_simd method or not. If they do, vectorized assignment should work out of the box.

@keeper Thanks indeed once more.

Did you envision two branches: one constant and one in which views are used in the padded regions?

And I'm afraid that I don't fully understand your question. For "branch", do you mean the code path it goes? For example in my implementation when the mode is constant it goes to a block of code for constant mode and return the result, and other modes go their paths?

If that's the case I think I prefer this way. But it's just a personal preference when handling different cases.

My strategy was to do algorithm depend stuff as deep down as possible. Most algorithms just constitute to selecting a different set of indices from the input matrix, the rest of the implementation in generic. This is however somewhat different from constant, as it does not rely on selecting a part of the input matrix. So it could make sense to implement constant differently from the rest.

@keeper I applied your code also to the other pad-modes. I think that this version should be a lot more efficient. Thanks for you help!

The minor changes listed below, that could improve performance, can be implemented in a dedicated PR. Indeed this one has been opened for a while, so I'm in favor of merging it.

Thanks @JohanMabille ! I integrated your comments. Let's merge once everything turns green.

Some further reformatting is needed in the future to make some of the modes recursive. I think I can do it quickly for wrap using the same approach as I used for xt::tile. At the same time I think that neither symmetric nor reflect can be recursive. Or is it just my imagination that is lacking?

I don't see either how it is possible.

keeper added 2 commits November 9, 2019 02:46

xpad: Assemble a new expaned container then copy input value into it

2802b52

Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

keeper mentioned this pull request Nov 8, 2019

xt::pad performance issue #1806

Closed

tdegeus reviewed Nov 12, 2019

View reviewed changes

Comment thread include/xtensor/xpad.hpp Outdated

keeper added 2 commits November 18, 2019 01:21

xpad: Avoid assigning out twice when using constant mode

27e010b

When using constant mode, `auto out = e;` is never used and it causes extra overhead, move it after constant mode handling fixes this. Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

xpad: Add type alias for return value

394739a

Suggestion from: xtensor-stack#1808 (comment) Signed-off-by: Phidias Chiang <phidias.chiang@gmail.com>

JohanMabille requested changes Nov 18, 2019

View reviewed changes

Comment thread include/xtensor/xpad.hpp Outdated

Comment thread include/xtensor/xpad.hpp Outdated

Comment thread include/xtensor/xpad.hpp Outdated

Comment thread include/xtensor/xpad.hpp Outdated

Comment thread include/xtensor/xpad.hpp Outdated

tdegeus mentioned this pull request Nov 28, 2019

np.tile implementation issues #1821

Closed

Extending strided view to all algorithms

6b83512

tdegeus marked this pull request as ready for review January 10, 2020 19:15

Merge branch 'master' into assemble-container-in-xpad-v2

2b9dc0a

tdegeus requested review from JohanMabille and tdegeus January 10, 2020 20:55

tdegeus reviewed Jan 10, 2020

View reviewed changes

Comment thread include/xtensor/xpad.hpp

tdegeus mentioned this pull request Jan 13, 2020

New release tdegeus/GooseEYE#49

Closed

JohanMabille approved these changes Jan 21, 2020

View reviewed changes

Comment thread include/xtensor/xpad.hpp

Comment thread include/xtensor/xpad.hpp Outdated

Comment thread include/xtensor/xpad.hpp Outdated

tdegeus added 2 commits January 22, 2020 07:03

Moving vector allocation outside loop

e9c5f43

Avoiding dynamic allocation

1056a14

tdegeus merged commit 1f58d9e into xtensor-stack:master Jan 22, 2020

Assemble new container in xpad by keeper · Pull Request #1808 · xtensor-stack/xtensor · GitHub

Repository navigation

Assemble new container in xpad - #1808

Assemble new container in xpad#1808tdegeus merged 8 commits intoxtensor-stack:masterxtensor-stack/xtensor:masterfrom keeper:assemble-container-in-xpad-v2keeper/xtensor:assemble-container-in-xpad-v2Copy head branch name to clipboard

Conversation

keeper commented Nov 8, 2019 • edited by tdegeus Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tdegeus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

keeper commented Nov 17, 2019

Uh oh!

JohanMabille left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

tdegeus commented Nov 19, 2019

Uh oh!

tdegeus commented Jan 10, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

JohanMabille left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

tdegeus commented Jan 22, 2020

Uh oh!

JohanMabille commented Jan 23, 2020

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Assemble new container in xpad#1808
tdegeus merged 8 commits into
xtensor-stack:masterfrom
keeper:assemble-container-in-xpad-v2

keeper commented Nov 8, 2019 •
edited by tdegeus
Loading

JohanMabille left a comment •
edited
Loading

tdegeus commented Jan 10, 2020 •
edited
Loading