Discussion:
[eigen] On the implementation of STL iterator for Eigen::Matrix
Gael Guennebaud
2018-10-02 12:53:49 UTC
Permalink
Hi list,

we're eventually implementing STL iterators to iterator over the
coefficients of a vector/matrix as well as over the columns or rows of a
matrix, and your inputs might be welcome to help converging to a stable
API, see below.

You can watch the WIP in PR 519 [1], and find some background in bug 231
[2]. Basically, to avoid ambiguities, we decided that iterators over
coefficients would be defined for 1D expression only, meaning that to
iterate over the elements of a 2D Matrix you'll have to explicitly reshape
it as a 1D vector first. Some typical examples:

VectorXd v;
MatrixXd A;
for(auto x : v) {...}
for(auto x : A.col(j)) {...}
for(auto x : A.row(i)) {...}
for(auto x : A.reshaped()) {...}

The last line iterate in column-major order regardless of the storage order
of A. So far so good. Things get more tricky now.

To iterate over rows or columns, we need to define a proxy telling so. One
option is to reuse (abuse?) rowwise()/colwise():

for(auto x : A.rowwise()) { ... }

Is it obvious to everyone that this line is iterating over the rows of A
and is thus a synonym for:

for(int i=0;i<A.rows();++i) { auto x = A.row(i); ... }

??

On my side, I'm rather reading it as "iterate over all elements of A in
row-major order", which is unfortunate as if I'm not alone with such an
interpretation, then we need to come up with new names. Since rows()/cols()
are already taken, we could think of:

for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
?????

Feel free to share your opinion on that question as well as on the other
minor issues discussed in the PR.

thanks,
gael

[1] https://bitbucket.org/eigen/eigen/pull-requests/519/
[2] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=231
Brook Milligan
2018-10-02 13:14:58 UTC
Permalink
we're eventually implementing STL iterators to iterator over the coefficients of a vector/matrix as well as over the columns or rows of a matrix, and your inputs might be welcome to help converging to a stable API, see below.
You can watch the WIP in PR 519 [1], and find some background in bug 231 [2]. Basically, to avoid ambiguities, we decided that iterators over coefficients would be defined for 1D expression only, meaning that to iterate over the elements of a 2D Matrix you'll have to explicitly reshape it as a 1D vector first.
Have you considered a solution such as used by Boost GIL (Generic Image Library)? That has the concept of "pixel locators" which allow both 1-D and 2-D (i.e., up/down, right/left) movement through the pixels of an image.

In fact, I would be surprised if you cannot adapt a matrix to the GIL "image" concept and get a whole lot for free.

In any case, I think it would be worth investigating before you settle on the arbitrary restriction of a 1-D-only API.

Cheers,
Brook
Christoph Hertzberg
2018-10-02 13:28:19 UTC
Permalink
Hi, thanks for the interest!
Post by Brook Milligan
we're eventually implementing STL iterators to iterator over the coefficients of a vector/matrix as well as over the columns or rows of a matrix, and your inputs might be welcome to help converging to a stable API, see below.
You can watch the WIP in PR 519 [1], and find some background in bug 231 [2]. Basically, to avoid ambiguities, we decided that iterators over coefficients would be defined for 1D expression only, meaning that to iterate over the elements of a 2D Matrix you'll have to explicitly reshape it as a 1D vector first.
Have you considered a solution such as used by Boost GIL (Generic Image Library)? That has the concept of "pixel locators" which allow both 1-D and 2-D (i.e., up/down, right/left) movement through the pixels of an image.
In fact, I would be surprised if you cannot adapt a matrix to the GIL "image" concept and get a whole lot for free.
In any case, I think it would be worth investigating before you settle on the arbitrary restriction of a 1-D-only API.
The main idea here is to have something which is compatible with the std
algorithms. And ranged-for-loops.
Glancing over the GIL documentation on PixelLocators they seem to
intentionally distinguish them from Iterators (which they implement, as
well).

I would not rule out that Eigen could also provide something like 2D
locators (not sure if there is a direct use case for that, though). But
that would be independent of the current iterator implementation (of
course, some code could be shared).


Christoph
--
Dr.-Ing. Christoph Hertzberg

Besuchsadresse der Nebengeschäftsstelle:
DFKI GmbH
Robotics Innovation Center
Robert-Hooke-Straße 5
28359 Bremen, Germany

Postadresse der Hauptgeschäftsstelle Standort Bremen:
DFKI GmbH
Robotics Innovation Center
Robert-Hooke-Straße 1
28359 Bremen, Germany

Tel.: +49 421 178 45-4021
Zentrale: +49 421 178 45-0
E-Mail: ***@dfki.de

Weitere Informationen: http://www.dfki.de/robotik
-----------------------------------------------------------------------
Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH
Firmensitz: Trippstadter Straße 122, D-67663 Kaiserslautern
Geschaeftsfuehrung: Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster
(Vorsitzender) Dr. Walter Olthoff
Vorsitzender des Aufsichtsrats: Prof. Dr. h.c. Hans A. Aukes
Amtsgericht Kaiserslautern, HRB 2313
Sitz der Gesellschaft: Kaiserslautern (HRB 2313)
USt-Id.Nr.: DE 148646973
Steuernummer: 19/672/50006
-----------------------------------------------------------------------
Gael Guennebaud
2018-10-02 15:00:37 UTC
Permalink
Post by Brook Milligan
Have you considered a solution such as used by Boost GIL (Generic Image
Library)? That has the concept of "pixel locators" which allow both 1-D
and 2-D (i.e., up/down, right/left) movement through the pixels of an image.
In fact, I would be surprised if you cannot adapt a matrix to the GIL
"image" concept and get a whole lot for free.
In any case, I think it would be worth investigating before you settle on
the arbitrary restriction of a 1-D-only API.
The main goal here was to provide iterators for compatibility with STL
algorithm, those are purely 1D iterators.

I'm not sure that hybrid 1D/2D iterators are that useful with Eigen because
Eigen is designed so that you don't have to write loops over the elements.
But if there are good use cases, we can still extend the API later on to
support hybrid 1D/2D iterators.

gael
Patrik Huber
2018-10-02 13:35:52 UTC
Permalink
Hi Gael,

It's fantastic to see this being added to Eigen, thanks a lot for all the
work.
Post by Gael Guennebaud
Post by Gael Guennebaud
for(auto x : A.rowwise()) { ... }
Is it obvious to everyone that this line is iterating over the rows of A
and is thus a synonym for [...]

My first thought was that this would probably "take rows from A, one at a
time" and then loop over the columns of each row, but somehow that didn't
make too much sense. After thinking about it for a bit, I can also
definitely read it as iterating over the rows of A and I think that makes
more sense actually. But after reading the PR and bug 231 (and after my own
confusion), I definitely see that there's ambiguity.
I also didn't find allRows() or rowSet() more clear at first. Looking at it
for a bit longer and thinking about it, I find allRows() quite clear though.
In all the cases I'd probably have to check the documentation to make sure
that the code I am writing is really doing what I want to do. So in that
sense you could maybe say none of the solutions is really great, as an API
should be as intuitive as possible. But we all know in practice that's not
always possible, so I think both allRows() and rowwise() would do the job
perfectly fine, and I'd say allRows() is slightly more clear in my opinion.
Post by Gael Guennebaud
Post by Gael Guennebaud
for(auto x : A.reshaped()) {...}
I also don't find this too clear. Does it reshape col-wise or row-wise? I'd
say this would depend on the storage order you choose, and since when not
specified, Eigen defaults to col-major storage order, I'd say this must
reshape col-wise. Anyway it's probably fine because in Matlab or NumPy, you
also don't know what their reshape() functions do, unless you check the
documentation or already know the storage order they use.
Does that line incur a copy of A btw to reshape it, or does it work like
Eigen::Map and provide a view on the original data?

Maybe this one's a silly question: I suppose looping over the rows/cols
will work with "const auto&" too, so there are no copies?

Hope that's somehow helpful feedback.

Cheers,
Patrik
Post by Gael Guennebaud
Hi list,
we're eventually implementing STL iterators to iterator over the
coefficients of a vector/matrix as well as over the columns or rows of a
matrix, and your inputs might be welcome to help converging to a stable
API, see below.
You can watch the WIP in PR 519 [1], and find some background in bug 231
[2]. Basically, to avoid ambiguities, we decided that iterators over
coefficients would be defined for 1D expression only, meaning that to
iterate over the elements of a 2D Matrix you'll have to explicitly reshape
VectorXd v;
MatrixXd A;
for(auto x : v) {...}
for(auto x : A.col(j)) {...}
for(auto x : A.row(i)) {...}
for(auto x : A.reshaped()) {...}
The last line iterate in column-major order regardless of the storage
order of A. So far so good. Things get more tricky now.
To iterate over rows or columns, we need to define a proxy telling so. One
for(auto x : A.rowwise()) { ... }
Is it obvious to everyone that this line is iterating over the rows of A
for(int i=0;i<A.rows();++i) { auto x = A.row(i); ... }
??
On my side, I'm rather reading it as "iterate over all elements of A in
row-major order", which is unfortunate as if I'm not alone with such an
interpretation, then we need to come up with new names. Since rows()/cols()
for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
?????
Feel free to share your opinion on that question as well as on the other
minor issues discussed in the PR.
thanks,
gael
[1] https://bitbucket.org/eigen/eigen/pull-requests/519/
[2] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=231
Christoph Hertzberg
2018-10-02 14:19:58 UTC
Permalink
Post by Patrik Huber
Post by Gael Guennebaud
Post by Gael Guennebaud
for(auto x : A.rowwise()) { ... }
Is it obvious to everyone that this line is iterating over the rows of A
and is thus a synonym for [...]
My first thought was that this would probably "take rows from A, one at a
time" and then loop over the columns of each row, but somehow that didn't
make too much sense. After thinking about it for a bit, I can also
definitely read it as iterating over the rows of A and I think that makes
more sense actually. But after reading the PR and bug 231 (and after my own
confusion), I definitely see that there's ambiguity.
I also didn't find allRows() or rowSet() more clear at first. Looking at it
for a bit longer and thinking about it, I find allRows() quite clear though.
In all the cases I'd probably have to check the documentation to make sure
that the code I am writing is really doing what I want to do. So in that
sense you could maybe say none of the solutions is really great, as an API
should be as intuitive as possible. But we all know in practice that's not
always possible, so I think both allRows() and rowwise() would do the job
perfectly fine, and I'd say allRows() is slightly more clear in my opinion.
Overall, I'd say the main problem is to have appropriate documentation
then. When introducing new members `allRows()`, I don't see why
A.allRows().norm(); A.allRows().reverseInPlace(); // etc
should not work as well. And to be honest, the meaning of
A.colwise().replicate(2) I find a bit arbitrary, too (without checking
the documentation). It could also mean:
[A.col(0), A.col(0), A.col(1), A.col(1), ...]

At the moment, the single purpose of allRows()/allCols() would be using
it with .begin() and .end(), even though they have very similar
functionality to rowwise()/colwise().
But if adding new functions is consensus, I'm totally ok with that.
Post by Patrik Huber
Post by Gael Guennebaud
Post by Gael Guennebaud
for(auto x : A.reshaped()) {...}
I also don't find this too clear. Does it reshape col-wise or row-wise? [...]
Yes, that is one topic we are currently debating about ...
Post by Patrik Huber
Does that line incur a copy of A btw to reshape it, or does it work like
Eigen::Map and provide a view on the original data?
Usually, Eigen will never produce copies until you explicitly assign
expressions to matrices (Some exceptions: Using .eval(), or products
which either could alias or involve more than two factors)

A.reshaped() will actually be writable as long as A is writable.
Post by Patrik Huber
Maybe this one's a silly question: I suppose looping over the rows/cols
will work with "const auto&" too, so there are no copies?
Yes, and without the const this should also be writable (did not try it yet)
Post by Patrik Huber
Hope that's somehow helpful feedback.
Thanks for the feedback!


Christoph
Post by Patrik Huber
Cheers,
Patrik
Post by Gael Guennebaud
Hi list,
we're eventually implementing STL iterators to iterator over the
coefficients of a vector/matrix as well as over the columns or rows of a
matrix, and your inputs might be welcome to help converging to a stable
API, see below.
You can watch the WIP in PR 519 [1], and find some background in bug 231
[2]. Basically, to avoid ambiguities, we decided that iterators over
coefficients would be defined for 1D expression only, meaning that to
iterate over the elements of a 2D Matrix you'll have to explicitly reshape
VectorXd v;
MatrixXd A;
for(auto x : v) {...}
for(auto x : A.col(j)) {...}
for(auto x : A.row(i)) {...}
for(auto x : A.reshaped()) {...}
The last line iterate in column-major order regardless of the storage
order of A. So far so good. Things get more tricky now.
To iterate over rows or columns, we need to define a proxy telling so. One
for(auto x : A.rowwise()) { ... }
Is it obvious to everyone that this line is iterating over the rows of A
for(int i=0;i<A.rows();++i) { auto x = A.row(i); ... }
??
On my side, I'm rather reading it as "iterate over all elements of A in
row-major order", which is unfortunate as if I'm not alone with such an
interpretation, then we need to come up with new names. Since rows()/cols()
for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
?????
Feel free to share your opinion on that question as well as on the other
minor issues discussed in the PR.
thanks,
gael
[1] https://bitbucket.org/eigen/eigen/pull-requests/519/
[2] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=231
--
Dr.-Ing. Christoph Hertzberg

Besuchsadresse der Nebengeschäftsstelle:
DFKI GmbH
Robotics Innovation Center
Robert-Hooke-Straße 5
28359 Bremen, Germany

Postadresse der Hauptgeschäftsstelle Standort Bremen:
DFKI GmbH
Robotics Innovation Center
Robert-Hooke-Straße 1
28359 Bremen, Germany

Tel.: +49 421 178 45-4021
Zentrale: +49 421 178 45-0
E-Mail: ***@dfki.de

Weitere Informationen: http://www.dfki.de/robotik
-----------------------------------------------------------------------
Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH
Firmensitz: Trippstadter Straße 122, D-67663 Kaiserslautern
Geschaeftsfuehrung: Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster
(Vorsitzender) Dr. Walter Olthoff
Vorsitzender des Aufsichtsrats: Prof. Dr. h.c. Hans A. Aukes
Amtsgericht Kaiserslautern, HRB 2313
Sitz der Gesellschaft: Kaiserslautern (HRB 2313)
USt-Id.Nr.: DE 148646973
Steuernummer: 19/672/50006
-----------------------------------------------------------------------
Gael Guennebaud
2018-10-02 22:14:08 UTC
Permalink
[...] So in that sense you could maybe say none of the solutions is really
great, as an API should be as intuitive as possible. But we all know in
practice that's not always possible, so I think both allRows() and
rowwise() would do the job perfectly fine, and I'd say allRows() is
slightly more clear in my opinion.
thank you for sharing your opinion.
Post by Gael Guennebaud
Post by Gael Guennebaud
for(auto x : A.reshaped()) {...}
I also don't find this too clear. Does it reshape col-wise or row-wise?
I'd say this would depend on the storage order you choose, and since when
not specified, Eigen defaults to col-major storage order, I'd say this must
reshape col-wise. Anyway it's probably fine because in Matlab or NumPy, you
also don't know what their reshape() functions do, unless you check the
documentation or already know the storage order they use.
yes, that's definitely something you have to check in the doc, I don't see
any way to make it cristal clear from the name unless you name it:

A.reshaped_column_major_to_1D_column()

;)
Does that line incur a copy of A btw to reshape it, or does it work like
Eigen::Map and provide a view on the original data?
It's only a view, just like everywhere else in Eigen.
Maybe this one's a silly question: I suppose looping over the rows/cols
will work with "const auto&" too, so there are no copies?
no need for a const ref:

for(auto c : A.allCols()) {}

already does the job fine because it is equivalent to:

for(MatrixXd::ColXpr c : A.allCols()) {}

and ColXpr (aka a Block<>) is already a light-weight reference to the
column of A.

gael
Post by Gael Guennebaud
Hi list,
we're eventually implementing STL iterators to iterator over the
coefficients of a vector/matrix as well as over the columns or rows of a
matrix, and your inputs might be welcome to help converging to a stable
API, see below.
You can watch the WIP in PR 519 [1], and find some background in bug 231
[2]. Basically, to avoid ambiguities, we decided that iterators over
coefficients would be defined for 1D expression only, meaning that to
iterate over the elements of a 2D Matrix you'll have to explicitly reshape
VectorXd v;
MatrixXd A;
for(auto x : v) {...}
for(auto x : A.col(j)) {...}
for(auto x : A.row(i)) {...}
for(auto x : A.reshaped()) {...}
The last line iterate in column-major order regardless of the storage
order of A. So far so good. Things get more tricky now.
To iterate over rows or columns, we need to define a proxy telling so.
for(auto x : A.rowwise()) { ... }
Is it obvious to everyone that this line is iterating over the rows of A
for(int i=0;i<A.rows();++i) { auto x = A.row(i); ... }
??
On my side, I'm rather reading it as "iterate over all elements of A in
row-major order", which is unfortunate as if I'm not alone with such an
interpretation, then we need to come up with new names. Since rows()/cols()
for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
?????
Feel free to share your opinion on that question as well as on the other
minor issues discussed in the PR.
thanks,
gael
[1] https://bitbucket.org/eigen/eigen/pull-requests/519/
[2] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=231
Wood, Tobias
2018-10-03 09:58:14 UTC
Permalink
Hello,

I find `for (auto x: a.rowwise()) {}` immediately intuitive, far more than any of the other suggestions. Maybe that’s because I already do a lot of rowwise()/colwise() operations?

I also find `for (auto x: A.reshape()) {}` intuitive, because I’ve written the equivalent in Matlab countless times `for x = A(:);`

Thanks,
Toby
Gael Guennebaud
2018-10-08 19:30:12 UTC
Permalink
For those who cares, here is the end of the story: I ended up with re-using
the rowwise()/colwise() pair and the PR is merged.

cheers,
gael
Post by Wood, Tobias
Hello,
I find `for (auto x: a.rowwise()) {}` immediately intuitive, far more than
any of the other suggestions. Maybe that’s because I already do a lot of
rowwise()/colwise() operations?
I also find `for (auto x: A.reshape()) {}` intuitive, because I’ve written
the equivalent in Matlab countless times `for x = A(:);`
Thanks,
Toby
Peter
2018-10-02 14:20:11 UTC
Permalink
Dear Gael,
Post by Gael Guennebaud
for(auto x : A.rowwise()) { ... }
  for(int i=0;i<A.rows();++i) { auto x = A.row(i); ... }
My first thought was "why using rowwise() if we already have A.rows()",
followed by "so it must be the elements of the rows".
In results, I find it precise, and obvious after thinking about it.
Post by Gael Guennebaud
On my side, I'm rather reading it as "iterate over all elements of A in row-major order", which is unfortunate as if I'm not alone with such an interpretation, then we need to come up with new names. Since rows()/cols() are
Not my interpretation.
Post by Gael Guennebaud
for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
?????
I'd prefer A.rowwise().

Best regards,
Peter
Joseph Mirabel
2018-10-03 08:25:07 UTC
Permalink
Dear Gael,

Thank you for your great job.

Hopefully, I will not add more doubts with my suggestions.

for(auto x : A.irows()) { ... }
for(auto x : A.icols()) { ... }
for(auto x : A.icoeffs()) { ... }
(or iRows, to make sure the eyes do not remove the 'i')

the prefix i being for iterator. Users need to understand that iterator
methods are prefixed with i. Once, this is known, I think there is no
hard time remembering names for the one who writes the code. And I do
not see ambiguities for the one who reads it.

There are also longer options or the use of an intermediate class, like:
for(auto x : A.iterator().rows()) { ... }
Post by Gael Guennebaud
for(auto x : A.rowwise()) { ... }
I agree it is ambiguous. I would need to check the doc.
Post by Gael Guennebaud
for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
Both are clear to me.

Best regards,
Joseph
David Tellenbach
2018-10-03 10:39:34 UTC
Permalink
Hi Gael,

thanks for the great work!
Post by Gael Guennebaud
for(auto x : A.rowwise()) { ... }
On my side, I'm rather reading it as "iterate over all elements of A in row-major order",
Exactly what I was thinking and I would definitely have to consult the docs.

I guess
Post by Gael Guennebaud
for(auto x : A.allRows()) { … }
is okay but also not completely intuitive. Since something like
Post by Gael Guennebaud
for(auto x : A.rows()) { … }
would be the most intuitive, I really like Joseph's idea of using
something similar to
Post by Gael Guennebaud
for(auto x : A.irows()) { … }
Thanks,
David
Gael Guennebaud
2018-10-03 11:56:14 UTC
Permalink
Post by Gael Guennebaud
On my side, I'm rather reading it as "iterate over all elements of A in
row-major order", which is unfortunate as if I'm not alone with such an
interpretation, then we need to come up with new names. Since rows()/cols()
for(auto x : A.allRows()) { ... }
for(auto x : A.rowSet()) { ... }
?????
After a bit more thoughts, abusing rowwise()/colwise() is perhaps not that
bad if we redefine the return type of A.rowwise() as "a view of the 2D
matrix A as a linear collection of row-vectors with vector-wise
broadcasting facilities". With such a definition, partial reductions and
broadcasting sill make sense:

A.rowwise().sum()
A.rowwise() - some_row_vector

and this open the doors for new usages, e.g.:

auto row_list = A.rowwise();

for (auto row : row_list) { ... }
auto it = find_if( row_list.begin(), row_list.end(), [](auto row) { return
row.squaredNorm()==0; } );

but also, provided we add operator[] and size() members:

for (int i=0; i<row_list.size(); ++i) { auto row = row_list[i]; ... }

In an ideal world I would rename the current rows()/cols() methods to
nrows()/ncols(), and rename rowwise()/colwise() to rows()/cols(), but that
cannot happen ;)

gael
Wood, Tobias
2018-10-03 12:44:01 UTC
Permalink
That’s essentially how I’ve always thought of rowwise()! Consider this e-mail a +1 / thumbs-up
I like all of the examples given.

Toby
Loading...