[eigen] Signed or unsigned indexing

[Henrik Mannerström]

This issue seems to warrant a separate message thread.

I'd like to offer my two cents: As much as I like Eigen I think there is a
strict ordering "c++ language" > "stl" > "Eigen". More than once have I
developed something and only at some later point brought in Eigen. Code
written in std:size_t fashion has then needed refactoring. So, if there
would be a vote, I'd vote for size_t indexing. I think smooth
interoperability with stl is valuable.

Best,
Henrik

Hi all,
while I would not want to argue with Gael nor with the numerous C++
experts advocating signed integers, today's reality is different. Some
libraries, the most prominent being the standard library, use unsigned
integers as indices. Therefore, mixing signed and unsigned types is sadly
unavoidable when using Eigen, which is a major annoyance (at least for me,
working with -pedantic -Werror).
In my opinion, using Eigen with -DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t
should just work, regardless of the developers' personal preference for
signed integers.
Best,
Marton

I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?

See also: http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eig
en.27s_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more compatible
with libraries that made the right choice of using signed types.
For sparse matrices, I agree that we might try to allow for unsigned
types as the StorageIndex type. This should be doable while keeping signed
64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael

I see the “downcounting” argument at https://listengine.tuxfamily.o
rg/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back

Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
*Sent:* 13 January 2017 12:26
*Subject:* Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
I think you are mixing Eigen::RowMajor with Eigen::RowMajorBit. I agree
that the bit flags could be managed differently using individual type
traits, but regarding Eigen::RowMajor, it is currently used as a template
Matrix<...., RowMajor|DontAlign>
which is pretty convenient to write compared to having to subclass some
default_matrix_traits class to customize the options. With
RowMajor|DontAlign, RowMajor could still be instance of an
integral_constant-like type with operator | overloaded.... Actually I've
started to think about such an approach for Eigen::Dynamic, so that one can
M = N*2+1
and get M==Dynamic if N==Dynamic. Currently we always have to write: M =
N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's easy to
forget about checking for Dynamic, especially when combining multiple
compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing

feature

is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report

entry

[1]. and a old pull-request with various discussions [2]. The Tensor

module

also support reshape [3].
However, the feature is still not there because we never converged

about how

to properly handle the ambiguity between col-major / row-major

orders, also

called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the

storage

order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose

twice)

B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in

generic code)

* not all expressions have a natural storage order (e.g., a+a^T,

a*b)

* needs a hard copy if, e.g., the user want to stack columns of a
row-major input

ColMajor,

RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one.

However, we

yet have to specify how to pass this option at compile-time, what Auto
means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I

already

mentioned, some expressions do not has any natural storage order. We

could

address this issue by limiting the use of 'Auto' to expressions for

which

- Any expressions with the DirectAccessBit flags (it means we are

dealing

with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic

expression)

- Any expression with the LinearAccessBit flag: it means the

expression can

be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear

view

with no constraints of the stacking order? Then we could add a fourth

option

meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is perhaps

the

most common and predictable choice given that the default storage is

column

major too.
template<typename RowsType=Index,typename ColType=Index,typename

Order=Xxxx>

DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the optional
order.
Then for the name of the options we cannot use "RowMajor"/"ColMajor"

because

they already are defined as "static const int" and we need objects

with

different types here. Moreover, col-major/row-major does not extend

well to

multi-dimension tensors. I also don't really like the reference to

Fortran/C

as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time & runtime
A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute

one of

the dimension to match the given matrix size. We cannot reuse "Auto"

here

A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we

need a

compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Ei

gen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#
markdown-header-operation-reshapeconst-dimensions-new_dims

[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/

numpy.reshape.html

[Brad Bell]

Post by Henrik Mannerström
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there
is a strict ordering "c++ language" > "stl" > "Eigen".

I would like to suggest that value_type should be defined (same as
Scalar) for Eigen matrices. It seems to me to be the standard for the
c++ language. For example, see the standard containers listed on
http://en.cppreference.com/w/cpp/container/deque
... snip ...

[Christoph Hertzberg]

Post by Brad Bell
I would like to suggest that value_type should be defined (same as
Scalar) for Eigen matrices. It seems to me to be the standard for the

Please check:

http://eigen.tuxfamily.org/bz/show_bug.cgi?id=360
https://bitbucket.org/eigen/eigen/commits/2a120c7a1519/


Cheers,
Christoph
--
Dipl. Inf., Dipl. Math. Christoph Hertzberg

Universität Bremen
FB 3 - Mathematik und Informatik
AG Robotik
Robert-Hooke-Straße 1
28359 Bremen, Germany

Zentrale: [phone]

Besuchsadresse der Nebengeschäftsstelle:
Robert-Hooke-Straße 5
28359 Bremen, Germany

Tel.: [phone]
Empfang: [phone]
Fax: [phone]
E-Mail: ***@informatik.uni-bremen.de

Weitere Informationen: http://www.informatik.uni-bremen.de/robotik

[Benoit Jacob]

It's complicated. The use of signed indexing has a long history
specifically in numerical linear algebra, see FORTRAN/BLAS/LAPACK. Also
some large C++ shops such as Google have entirely turned away from unsigned

You should not use the unsigned integer types such as uint32_t, unless
there is a valid reason such as representing a bit pattern rather than a
number, or you need defined overflow modulo 2^N. In particular, do not use
unsigned types to say a number will never be negative. Instead, use
assertions for this.

I only mention this to say, there are valid points on both sides of this
argument. Neither choice will make much more than half of users happy. (I
actually don't like the Google C++ style that much, and I wouldn't mind
unsigned personally).

The only thing that would be really bad would be to try to make both
signednesses fully supported. That would mean keeping only the intersection
of the sets of advantages of either signedness, having to deal with the
union of the sets of constraints.

Benoit

This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there is a
strict ordering "c++ language" > "stl" > "Eigen". More than once have I
developed something and only at some later point brought in Eigen. Code
written in std:size_t fashion has then needed refactoring. So, if there
would be a vote, I'd vote for size_t indexing. I think smooth
interoperability with stl is valuable.
Best,
Henrik

Hi all,
while I would not want to argue with Gael nor with the numerous C++
experts advocating signed integers, today's reality is different. Some
libraries, the most prominent being the standard library, use unsigned
integers as indices. Therefore, mixing signed and unsigned types is sadly
unavoidable when using Eigen, which is a major annoyance (at least for me,
working with -pedantic -Werror).
In my opinion, using Eigen with -DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t
should just work, regardless of the developers' personal preference for
signed integers.
Best,
Marton

I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?

See also: http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eig
en.27s_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more compatible
with libraries that made the right choice of using signed types.
For sparse matrices, I agree that we might try to allow for unsigned
types as the StorageIndex type. This should be doable while keeping signed
64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael

I see the “downcounting” argument at https://listengine.tuxfamily.o
rg/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back

Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
*Sent:* 13 January 2017 12:26
*Subject:* Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
I think you are mixing Eigen::RowMajor with Eigen::RowMajorBit. I agree
that the bit flags could be managed differently using individual type
traits, but regarding Eigen::RowMajor, it is currently used as a template
Matrix<...., RowMajor|DontAlign>
which is pretty convenient to write compared to having to subclass some
default_matrix_traits class to customize the options. With
RowMajor|DontAlign, RowMajor could still be instance of an
integral_constant-like type with operator | overloaded.... Actually I've
started to think about such an approach for Eigen::Dynamic, so that one can
M = N*2+1
and get M==Dynamic if N==Dynamic. Currently we always have to write: M
= N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's easy to
forget about checking for Dynamic, especially when combining multiple
compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing

feature

is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report

entry

[1]. and a old pull-request with various discussions [2]. The Tensor

module

also support reshape [3].
However, the feature is still not there because we never converged

about how

to properly handle the ambiguity between col-major / row-major

orders, also

called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the

storage

order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose

twice)

B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in

generic code)

* not all expressions have a natural storage order (e.g.,

a+a^T, a*b)

* needs a hard copy if, e.g., the user want to stack columns of

a

row-major input

ColMajor,

RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one.

However, we

yet have to specify how to pass this option at compile-time, what

Auto

means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I

already

mentioned, some expressions do not has any natural storage order. We

could

address this issue by limiting the use of 'Auto' to expressions for

which

- Any expressions with the DirectAccessBit flags (it means we are

dealing

with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic

expression)

- Any expression with the LinearAccessBit flag: it means the

expression can

be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear

view

with no constraints of the stacking order? Then we could add a

fourth option

meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is

perhaps the

most common and predictable choice given that the default storage is

column

major too.
template<typename RowsType=Index,typename ColType=Index,typename

Order=Xxxx>

DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the

optional

order.
Then for the name of the options we cannot use "RowMajor"/"ColMajor"

because

they already are defined as "static const int" and we need objects

with

different types here. Moreover, col-major/row-major does not extend

well to

multi-dimension tensors. I also don't really like the reference to

Fortran/C

as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time &

runtime

A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute

one of

the dimension to match the given matrix size. We cannot reuse "Auto"

here

A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we

need a

compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Ei

gen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#
markdown-header-operation-reshapeconst-dimensions-new_dims

[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/

numpy.reshape.html

[Francois Fayard]

Let me give you my 2 cents on this signed/unsigned problem:

- The core C++ language is using signed integers for indexing. If p is a pointer, p[k] is defined for k being a std::ptrdiff_t which is the Index type used by Eigen
- The C++ standard library is using unsigned integers for indexing: std::size_t

So, if you want to choose: (core C++) > (STL) > (Eigen). You have to go and use signed integers. Most people in the standard committees think that using unsigned integers for indexing was a mistake, including Bjarne Stroustrup, Herb Sutter and Chandler Carruth. You can see their argument in this video, at 42:38 and 1:02:50 (

).

Using unsigned integers is just an error-prone. For instance, if you have an array v and you are looking from the first element k when you go from b downto a such that v[k] = 0, with unsigned integers, you just need to write:
for (int k = b; k >= a, —k) {
if (v[k] == 0) {
return k;
}
}
If you do that with unsigned integers, good luck to write something simple that does not get crazy when a = 0 (It was a real bug I found in an image program that was searching for something from right to left inside a rectangle of interest).

In terms of performance, the compiler can also do more things with signed integers as overflow for signed integers is undefined behavior. This is not the case for unsigned integers (they warp). As a consequence, a compiler can assume that p[k] and p[k + 1] are next to each other in memory if k is signed. It can’t do that if k is unsigned (think of the mess it can lead for people working on auto-vectorization). With signed integer 10 * k / 2 = 5 * k. This is not the case with unsigned integers. I believe that "unsigned integers" should be renamed "modulo integers” because unsigned integers are just Z/(2^n Z). And I have taught enough Mathematics to know that most people are (or should be) scared of Z/(2^n Z) :-)

The only advantage of unsigned integers on a performance point of view is division: it is faster with unsigned integers. But I never had this bottleneck in real programs.

An argument used by “unsigned” people is that you get an extra bit for array indices. This is just nonsense. First, it only happens on 32-bit systems with char arrays of more than 2 million elements. Have you ever considered *char* arrays that long? Now, the must funny part is that if you look at the implementation of std::vector<T>, it stores 3 pointers, including the begin and the end of the array. To get its size, the vector returns static_cast<std::size_t>(end - begin). And end - begin is just at std::ptrdiff_t, so if the vector has more than 2 million elements, you just get undefined behavior. So std::vector can’t even use that bit !!! By the way, this is why std::vector<T>::max_size() is 2 million with libc++ (clang). And nobody seems to complain.

On the other side, I understand people who use std::size_t for indexing because it is consistent with the standard library.

François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

You should not use the unsigned integer types such as uint32_t, unless there is a valid reason such as representing a bit pattern rather than a number, or you need defined overflow modulo 2^N. In particular, do not use unsigned types to say a number will never be negative. Instead, use assertions for this.
I only mention this to say, there are valid points on both sides of this argument. Neither choice will make much more than half of users happy. (I actually don't like the Google C++ style that much, and I wouldn't mind unsigned personally).
The only thing that would be really bad would be to try to make both signednesses fully supported. That would mean keeping only the intersection of the sets of advantages of either signedness, having to deal with the union of the sets of constraints.
Benoit
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there is a strict ordering "c++ language" > "stl" > "Eigen". More than once have I developed something and only at some later point brought in Eigen. Code written in std:size_t fashion has then needed refactoring. So, if there would be a vote, I'd vote for size_t indexing. I think smooth interoperability with stl is valuable.
Best,
Henrik
Hi all,
while I would not want to argue with Gael nor with the numerous C++ experts advocating signed integers, today's reality is different. Some libraries, the most prominent being the standard library, use unsigned integers as indices. Therefore, mixing signed and unsigned types is sadly unavoidable when using Eigen, which is a major annoyance (at least for me, working with -pedantic -Werror).
In my opinion, using Eigen with -DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t should just work, regardless of the developers' personal preference for signed integers.
Best,
Marton
I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?
See also: http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eigen.27s_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more compatible with libraries that made the right choice of using signed types.
For sparse matrices, I agree that we might try to allow for unsigned types as the StorageIndex type. This should be doable while keeping signed 64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael
I see the “downcounting” argument at https://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back…
Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
Sent: 13 January 2017 12:26
Subject: Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
Matrix<...., RowMajor|DontAlign>
M = N*2+1
and get M==Dynamic if N==Dynamic. Currently we always have to write: M = N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's easy to forget about checking for Dynamic, especially when combining multiple compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing feature
is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report entry
[1]. and a old pull-request with various discussions [2]. The Tensor module
also support reshape [3].
However, the feature is still not there because we never converged about how
to properly handle the ambiguity between col-major / row-major orders, also
called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the storage
order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose twice)
B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in generic code)
* not all expressions have a natural storage order (e.g., a+a^T, a*b)
* needs a hard copy if, e.g., the user want to stack columns of a
row-major input
C) Give the user an option to decide which order to use between: ColMajor,
RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one. However, we
yet have to specify how to pass this option at compile-time, what Auto
means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I already
mentioned, some expressions do not has any natural storage order. We could
address this issue by limiting the use of 'Auto' to expressions for which
- Any expressions with the DirectAccessBit flags (it means we are dealing
with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic expression)
- Any expression with the LinearAccessBit flag: it means the expression can
be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear view
with no constraints of the stacking order? Then we could add a fourth option
meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is perhaps the
most common and predictable choice given that the default storage is column
major too.
template<typename RowsType=Index,typename ColType=Index,typename Order=Xxxx>
DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the optional
order.
Then for the name of the options we cannot use "RowMajor"/"ColMajor" because
they already are defined as "static const int" and we need objects with
different types here. Moreover, col-major/row-major does not extend well to
multi-dimension tensors. I also don't really like the reference to Fortran/C
as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time & runtime
A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute one of
the dimension to match the given matrix size. We cannot reuse "Auto" here
A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we need a
compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Eigen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#markdown-header-operation-reshapeconst-dimensions-new_dims
[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.reshape.html

[Massimiliano Janes]

Post by Francois Fayard
- The core C++ language is using signed integers for indexing. If p is a pointer, p[k] is defined for k being a std::ptrdiff_t which is the Index type used by Eigen
- The C++ standard library is using unsigned integers for indexing: std::size_t

actually, std random access iterators do accept signed indices as well. size_t indices are used at the container level only.
This actually makes sense to me, considering that interfaces should be minimal and that unsigneds has a simpler
set of invalid values when representing non negative quantities ( signeds need to specify the behaviour of
passing two bounds instead of one, this increases the complexity of documentation, pre/postcondition checks and tests ).

premising that I’m definitely in the signed party, I think most signed/size_t interoperability problems come from using
containers when iterators/ranges/views should be used; in my experience ( for what it’s worth :) ) if containers decays to views
ASAP most unsigned to signed indices conversions disappear, leaving just few controlled casts/checks where appropriate.

[Francois Fayard]

Post by Massimiliano Janes
actually, std random access iterators do accept signed indices as well. size_t indices are used at the container level only.
This actually makes sense to me, considering that interfaces should be minimal and that unsigneds has a simpler
set of invalid values when representing non negative quantities ( signeds need to specify the behaviour of
passing two bounds instead of one, this increases the complexity of documentation, pre/postcondition checks and tests ).

For pre/postcondition check, this is not really an issue as

T& operator[](std::ptrdiff_t i) {
assert(static_cast<std::size_t>(i) < static_cast<std::size_t>(size()));

return data_[i];
}

does not do more work than the unsigned version. I agree that it looks strange, but as it is inside a library, I am not worried.

Post by Massimiliano Janes
premising that I’m definitely in the signed party, I think most signed/size_t interoperability problems come from using
containers when iterators/ranges/views should be used; in my experience ( for what it’s worth :) ) if containers decays to views. ASAP most unsigned to signed indices conversions disappear, leaving just few controlled casts/checks where appropriate.

Many people still need to work with indices. If you work with an array of structure

struct Point {
double x;
double y;
double z;
}
std::vector<Point>

you can work with iterators. But if you work with a structure of array

struct ArrayPoint {
std::vector<double> x;
std::vector<double> y;
std::vector<double> z;
}

it is much more easier to work with indices. Also, there are structure for which it is impossible to get efficient iterators, for instance a matrix where there is padding at the end of the matrix. Such structures can’t be traversed with iterators as efficiently as indices. So indices are still needed today.

[Mark Borgerding]

Well made points. These greatly expand on points I made on this list
in May 2010.


From the linked video...

"I think one of the sad things about the standard library is that the
indices are unsigned whereas array indices are unsigned.
You are sort of doomed to have confusion and problems with that. [...]
It is a major bug source. Which is why I'm saying, 'stay as simple as
you can. Use [signed] integers until you really, really need something
else.' "
-- Bjarne Stroustrop

This opinion was echoed by several of the esteemed panel and opposed by
none: Bjarne Stroustrup, Andrei Alexandrescu, Herb Sutter, Scott
Meyers, Chandler Carruth, Sean Parent, Michael Wong, and Stephan T. Lavavej.

" They [the unsigned ordinals in the STL] are wrong. We're sorry. We
were young."


I would add...
It is human nature to forget that these "integer" data type we're
discussing are only approximations of integers over a finite range.
The approximation is most horribly broken at the point of
over/underflow. For signed types, that point is often comfortably far
from where our calculations happen.
For unsigned types, that boundary point at the busiest spot, zero.


-- Mark

Post by Francois Fayard
- The core C++ language is using signed integers for indexing. If p is a pointer, p[k] is defined for k being a std::ptrdiff_t which is the Index type used by Eigen
- The C++ standard library is using unsigned integers for indexing: std::size_t
So, if you want to choose: (core C++) > (STL) > (Eigen). You have to go and use signed integers. Most people in the standard committees think that using unsigned integers for indexing was a mistake, including Bjarne Stroustrup, Herb Sutter and Chandler Carruth. You can see their argument in this video, at 42:38 and 1:02:50 ( http://youtu.be/Puio5dly9N8 ).
for (int k = b; k >= a, —k) {
if (v[k] == 0) {
return k;
}
}
If you do that with unsigned integers, good luck to write something simple that does not get crazy when a = 0 (It was a real bug I found in an image program that was searching for something from right to left inside a rectangle of interest).
In terms of performance, the compiler can also do more things with signed integers as overflow for signed integers is undefined behavior. This is not the case for unsigned integers (they warp). As a consequence, a compiler can assume that p[k] and p[k + 1] are next to each other in memory if k is signed. It can’t do that if k is unsigned (think of the mess it can lead for people working on auto-vectorization). With signed integer 10 * k / 2 = 5 * k. This is not the case with unsigned integers. I believe that "unsigned integers" should be renamed "modulo integers” because unsigned integers are just Z/(2^n Z). And I have taught enough Mathematics to know that most people are (or should be) scared of Z/(2^n Z) :-)
The only advantage of unsigned integers on a performance point of view is division: it is faster with unsigned integers. But I never had this bottleneck in real programs.
An argument used by “unsigned” people is that you get an extra bit for array indices. This is just nonsense. First, it only happens on 32-bit systems with char arrays of more than 2 million elements. Have you ever considered *char* arrays that long? Now, the must funny part is that if you look at the implementation of std::vector<T>, it stores 3 pointers, including the begin and the end of the array. To get its size, the vector returns static_cast<std::size_t>(end - begin). And end - begin is just at std::ptrdiff_t, so if the vector has more than 2 million elements, you just get undefined behavior. So std::vector can’t even use that bit !!! By the way, this is why std::vector<T>::max_size() is 2 million with libc++ (clang). And nobody seems to complain.
On the other side, I understand people who use std::size_t for indexing because it is consistent with the standard library.
François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

You should not use the unsigned integer types such as uint32_t, unless there is a valid reason such as representing a bit pattern rather than a number, or you need defined overflow modulo 2^N. In particular, do not use unsigned types to say a number will never be negative. Instead, use assertions for this.
I only mention this to say, there are valid points on both sides of this argument. Neither choice will make much more than half of users happy. (I actually don't like the Google C++ style that much, and I wouldn't mind unsigned personally).
The only thing that would be really bad would be to try to make both signednesses fully supported. That would mean keeping only the intersection of the sets of advantages of either signedness, having to deal with the union of the sets of constraints.
Benoit
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there is a strict ordering "c++ language" > "stl" > "Eigen". More than once have I developed something and only at some later point brought in Eigen. Code written in std:size_t fashion has then needed refactoring. So, if there would be a vote, I'd vote for size_t indexing. I think smooth interoperability with stl is valuable.
Best,
Henrik
Hi all,
while I would not want to argue with Gael nor with the numerous C++ experts advocating signed integers, today's reality is different. Some libraries, the most prominent being the standard library, use unsigned integers as indices. Therefore, mixing signed and unsigned types is sadly unavoidable when using Eigen, which is a major annoyance (at least for me, working with -pedantic -Werror).
In my opinion, using Eigen with -DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t should just work, regardless of the developers' personal preference for signed integers.
Best,
Marton
I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?
See also: http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eigen.27s_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more compatible with libraries that made the right choice of using signed types.
For sparse matrices, I agree that we might try to allow for unsigned types as the StorageIndex type. This should be doable while keeping signed 64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael
I see the “downcounting” argument at https://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back…
Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
Sent: 13 January 2017 12:26
Subject: Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
Matrix<...., RowMajor|DontAlign>
M = N*2+1
and get M==Dynamic if N==Dynamic. Currently we always have to write: M = N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's easy to forget about checking for Dynamic, especially when combining multiple compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing feature
is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report entry
[1]. and a old pull-request with various discussions [2]. The Tensor module
also support reshape [3].
However, the feature is still not there because we never converged about how
to properly handle the ambiguity between col-major / row-major orders, also
called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the storage
order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose twice)
B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in generic code)
* not all expressions have a natural storage order (e.g., a+a^T, a*b)
* needs a hard copy if, e.g., the user want to stack columns of a
row-major input
C) Give the user an option to decide which order to use between: ColMajor,
RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one. However, we
yet have to specify how to pass this option at compile-time, what Auto
means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I already
mentioned, some expressions do not has any natural storage order. We could
address this issue by limiting the use of 'Auto' to expressions for which
- Any expressions with the DirectAccessBit flags (it means we are dealing
with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic expression)
- Any expression with the LinearAccessBit flag: it means the expression can
be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear view
with no constraints of the stacking order? Then we could add a fourth option
meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is perhaps the
most common and predictable choice given that the default storage is column
major too.
template<typename RowsType=Index,typename ColType=Index,typename Order=Xxxx>
DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the optional
order.
Then for the name of the options we cannot use "RowMajor"/"ColMajor" because
they already are defined as "static const int" and we need objects with
different types here. Moreover, col-major/row-major does not extend well to
multi-dimension tensors. I also don't really like the reference to Fortran/C
as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time & runtime
A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute one of
the dimension to match the given matrix size. We cannot reuse "Auto" here
A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we need a
compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Eigen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#markdown-header-operation-reshapeconst-dimensions-new_dims
[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.reshape.html

[Benoit Jacob]

Sure, from the compiler authors perspective, the current behavior of signed
integers in C++ is ideal. Since overflow is undefined behavior, for them it
is optimization opportunities. They can do all sorts of optimizations
thanks to being able to assume that overflow does not happen.

But from the perspective of software developers, the undefined behavior in
signed overflow is danger.

That leads to one of the strongest arguments in favor of unsigned: at
least, that has well-defined (wrapping) overflow behavior. That might be
'broken', but it isn't nearly as dangerous as the undefined behavior of
signed overflow!

The point I want to make is: compiler users (us, here) and compiler authors
have inherently different, sometimes conflicting, agenda.

Again --- not advocating for unsigned indices! Just saying it's not
clear-cut either way.

Benoit

Well made points. These greatly expand on points I made on this list in
May 2010.
From the linked video...
"I think one of the sad things about the standard library is that the
indices are unsigned whereas array indices are unsigned.
You are sort of doomed to have confusion and problems with that. [...] It
is a major bug source. Which is why I'm saying, 'stay as simple as you
can. Use [signed] integers until you really, really need something else.' "
-- Bjarne Stroustrop
This opinion was echoed by several of the esteemed panel and opposed by
none: Bjarne Stroustrup, Andrei Alexandrescu, Herb Sutter, Scott Meyers,
Chandler Carruth, Sean Parent, Michael Wong, and Stephan T. Lavavej.
" They [the unsigned ordinals in the STL] are wrong. We're sorry. We were
young."
I would add...
It is human nature to forget that these "integer" data type we're
discussing are only approximations of integers over a finite range.
The approximation is most horribly broken at the point of over/underflow.
For signed types, that point is often comfortably far from where our
calculations happen.
For unsigned types, that boundary point at the busiest spot, zero.
-- Mark

Post by Francois Fayard
- The core C++ language is using signed integers for indexing. If p is a
pointer, p[k] is defined for k being a std::ptrdiff_t which is the Index
type used by Eigen
- The C++ standard library is using unsigned integers for indexing: std::size_t
So, if you want to choose: (core C++) > (STL) > (Eigen). You have to go
and use signed integers. Most people in the standard committees think that
using unsigned integers for indexing was a mistake, including Bjarne
Stroustrup, Herb Sutter and Chandler Carruth. You can see their argument in
this video, at 42:38 and 1:02:50 ( https://www.youtube.com/watch?
v=Puio5dly9N8 ).
Using unsigned integers is just an error-prone. For instance, if you have
an array v and you are looking from the first element k when you go from b
for (int k = b; k >= a, —k) {
if (v[k] == 0) {
return k;
}
}
If you do that with unsigned integers, good luck to write something
simple that does not get crazy when a = 0 (It was a real bug I found in an
image program that was searching for something from right to left inside a
rectangle of interest).
In terms of performance, the compiler can also do more things with signed
integers as overflow for signed integers is undefined behavior. This is not
the case for unsigned integers (they warp). As a consequence, a compiler
can assume that p[k] and p[k + 1] are next to each other in memory if k is
signed. It can’t do that if k is unsigned (think of the mess it can lead
for people working on auto-vectorization). With signed integer 10 * k / 2
= 5 * k. This is not the case with unsigned integers. I believe that
"unsigned integers" should be renamed "modulo integers” because unsigned
integers are just Z/(2^n Z). And I have taught enough Mathematics to know
that most people are (or should be) scared of Z/(2^n Z) :-)
The only advantage of unsigned integers on a performance point of view is
division: it is faster with unsigned integers. But I never had this
bottleneck in real programs.
An argument used by “unsigned” people is that you get an extra bit for
array indices. This is just nonsense. First, it only happens on 32-bit
systems with char arrays of more than 2 million elements. Have you ever
considered *char* arrays that long? Now, the must funny part is that if you
look at the implementation of std::vector<T>, it stores 3 pointers,
including the begin and the end of the array. To get its size, the vector
returns static_cast<std::size_t>(end - begin). And end - begin is just at
std::ptrdiff_t, so if the vector has more than 2 million elements, you just
get undefined behavior. So std::vector can’t even use that bit !!! By the
way, this is why std::vector<T>::max_size() is 2 million with libc++
(clang). And nobody seems to complain.
On the other side, I understand people who use std::size_t for indexing
because it is consistent with the standard library.
François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

Post by Benoit Jacob
It's complicated. The use of signed indexing has a long history
specifically in numerical linear algebra, see FORTRAN/BLAS/LAPACK. Also
some large C++ shops such as Google have entirely turned away from unsigned
You should not use the unsigned integer types such as uint32_t, unless
there is a valid reason such as representing a bit pattern rather than a
number, or you need defined overflow modulo 2^N. In particular, do not use
unsigned types to say a number will never be negative. Instead, use
assertions for this.
I only mention this to say, there are valid points on both sides of this
argument. Neither choice will make much more than half of users happy. (I
actually don't like the Google C++ style that much, and I wouldn't mind
unsigned personally).
The only thing that would be really bad would be to try to make both
signednesses fully supported. That would mean keeping only the intersection
of the sets of advantages of either signedness, having to deal with the
union of the sets of constraints.
Benoit
2017-01-20 8:25 GMT-05:00 Henrik Mannerström <
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there is
a strict ordering "c++ language" > "stl" > "Eigen". More than once have I
developed something and only at some later point brought in Eigen. Code
written in std:size_t fashion has then needed refactoring. So, if there
would be a vote, I'd vote for size_t indexing. I think smooth
interoperability with stl is valuable.
Best,
Henrik
Hi all,
while I would not want to argue with Gael nor with the numerous C++
experts advocating signed integers, today's reality is different. Some
libraries, the most prominent being the standard library, use unsigned
integers as indices. Therefore, mixing signed and unsigned types is sadly
unavoidable when using Eigen, which is a major annoyance (at least for me,
working with -pedantic -Werror).
In my opinion, using Eigen with -DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t
should just work, regardless of the developers' personal preference for
signed integers.
Best,
Marton
I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?
See also: http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eigen.27s
_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more compatible
with libraries that made the right choice of using signed types.
For sparse matrices, I agree that we might try to allow for unsigned
types as the StorageIndex type. This should be doable while keeping signed
64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael
I see the “downcounting” argument at https://listengine.tuxfamily.o
rg/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back

Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
Sent: 13 January 2017 12:26
Subject: Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
I think you are mixing Eigen::RowMajor with Eigen::RowMajorBit. I agree
that the bit flags could be managed differently using individual type
traits, but regarding Eigen::RowMajor, it is currently used as a template
Matrix<...., RowMajor|DontAlign>
which is pretty convenient to write compared to having to subclass some
default_matrix_traits class to customize the options. With
RowMajor|DontAlign, RowMajor could still be instance of an
integral_constant-like type with operator | overloaded.... Actually I've
started to think about such an approach for Eigen::Dynamic, so that one can
M = N*2+1
and get M==Dynamic if N==Dynamic. Currently we always have to write: M =
N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's easy to
forget about checking for Dynamic, especially when combining multiple
compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing feature
is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report entry
[1]. and a old pull-request with various discussions [2]. The Tensor module
also support reshape [3].
However, the feature is still not there because we never converged about how
to properly handle the ambiguity between col-major / row-major orders, also
called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the storage
order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose twice)
B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in generic code)
* not all expressions have a natural storage order (e.g., a+a^T, a*b)
* needs a hard copy if, e.g., the user want to stack columns of a
row-major input
C) Give the user an option to decide which order to use between: ColMajor,
RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one. However, we
yet have to specify how to pass this option at compile-time, what Auto
means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I already
mentioned, some expressions do not has any natural storage order. We could
address this issue by limiting the use of 'Auto' to expressions for which
- Any expressions with the DirectAccessBit flags (it means we are dealing
with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic expression)
- Any expression with the LinearAccessBit flag: it means the expression can
be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear view
with no constraints of the stacking order? Then we could add a fourth option
meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is perhaps the
most common and predictable choice given that the default storage is column
major too.
template<typename RowsType=Index,typename ColType=Index,typename Order=Xxxx>
DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the optional
order.
Then for the name of the options we cannot use "RowMajor"/"ColMajor" because
they already are defined as "static const int" and we need objects with
different types here. Moreover, col-major/row-major does not extend well to
multi-dimension tensors. I also don't really like the reference to Fortran/C
as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time & runtime
A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute one of
the dimension to match the given matrix size. We cannot reuse "Auto" here
A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we need a
compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Ei
gen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#
markdown-header-operation-reshapeconst-dimensions-new_dims
[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/
numpy.reshape.html

[François Fayard]

Hi Benoit,

Could you please elaborate on why it is dangerous? On most cases I know of, when there is overflow, the signed version leads to unsigned behaviour, and the unsigned version leads to something such as a crash or an infinite loop. In the end, I would say that both cases are equally bad.

Do you have a concrete example where the signed version leads to more dangerous bugs than the unsigned version?

But from the perspective of software developers, the undefined behavior in signed overflow is danger.
That leads to one of the strongest arguments in favor of unsigned: at least, that has well-defined (wrapping) overflow behavior. That might be 'broken', but it isn't nearly as dangerous as the undefined behavior of signed overflow!
Benoit

[Benoit Jacob]

Hi Francois,

There is no question that unsigned overflow can already be very dangerous,
leading to crashes etc.

"Undefined behavior" is its own class of danger, though. When the compiler
sees undefined behavior, it can do absolutely anything... an old version of
GCC was emitting code to run some some video game, to illustrate that point.

here is a little 'study' of the actual behavior of compilers on undefined
behavior that I made while I was working at a Web browser vendor:

https://raw.githubusercontent.com/bjacob/builtin-unreachable-study/master/notes

That was actually a study of the effect of using __builtin_unreachable. But
any kind of undefined behavior is in principle equivalent to that.

As you can see there, it's pretty crazy the optimizations that GCC does
when it takes undefined behavior seriously, e.g.
- removing 'ret' instructions at the end of functions, allowing code to
continue running past the end of a function's code!
- removing bounds checks on switch statements implemented as jump-tables,
thus allowing to jump to unintended addresses!

Benoit

Post by François Fayard
Hi Benoit,
Could you please elaborate on why it is dangerous? On most cases I know
of, when there is overflow, the signed version leads to unsigned behaviour,
and the unsigned version leads to something such as a crash or an infinite
loop. In the end, I would say that both cases are equally bad.
Do you have a concrete example where the signed version leads to more
dangerous bugs than the unsigned version?

Post by Benoit Jacob
But from the perspective of software developers, the undefined behavior

in signed overflow is danger.

Post by Benoit Jacob
That leads to one of the strongest arguments in favor of unsigned: at

least, that has well-defined (wrapping) overflow behavior. That might be
'broken', but it isn't nearly as dangerous as the undefined behavior of
signed overflow!

Post by Benoit Jacob
Benoit

[François Fayard]

Hi Benoit,

Thanks for your notes on undefined behaviour which are quite interesting, especially the "switch" one that looks scary. But we always come back to those "nasal deamons" and these stories around the big bad wolf that you hear a lot but you never really get in real life. Yes, with undefined behaviour, anything can happen, but I believe that it should be seen from a practical point of view:

-1- Do we know of any disaster (such as Ariane 5) that could have been avoided using signed or unsigned integers?
-2- Do we know of any security flaw that could have been avoided using signed or unsigned integers?
-3- Do we know of any bugs that could have been avoided using signed or unsigned integers?

For the third question, my answer is yes. I've heard of so many bugs caused by a misuse of unsigned integers that could have been avoided by using signed integers.

Now, I understand that you are concerned about the answers to question 1 and 2. I understand why people could be scared of "undefined behaviour". But I would like to get some concrete examples of things that really went wrong because of the usage of signed integers. I've never seen any, but I have to admit that I don't have any experience in security. If you look at the CERT C coding standard, they are equally concerned about warping behaviour of unsigned integers and undefined behaviour of signed integers.

As a side note, I would be more concerned about the fact that Eigen does not use any error reporting mechanism. For instance, I have no idea what could happen when I ask a Cholesky decomposition on a matrix that is symmetric but not positive. And it is not something that could be easily checked before asking for the decomposition.

François

Post by Benoit Jacob
Hi Francois,
There is no question that unsigned overflow can already be very dangerous, leading to crashes etc.
"Undefined behavior" is its own class of danger, though. When the compiler sees undefined behavior, it can do absolutely anything... an old version of GCC was emitting code to run some some video game, to illustrate that point.
https://raw.githubusercontent.com/bjacob/builtin-unreachable-study/master/notes
That was actually a study of the effect of using __builtin_unreachable. But any kind of undefined behavior is in principle equivalent to that.
As you can see there, it's pretty crazy the optimizations that GCC does when it takes undefined behavior seriously, e.g.
- removing 'ret' instructions at the end of functions, allowing code to continue running past the end of a function's code!
- removing bounds checks on switch statements implemented as jump-tables, thus allowing to jump to unintended addresses!
Benoit

[Gael Guennebaud]

Post by François Fayard
For instance, I have no idea what could happen when I ask a Cholesky
decomposition on a matrix that is symmetric but not positive. And it is not
something that could be easily checked before asking for the decomposition.

https://eigen.tuxfamily.org/dox/classEigen_1_1LDLT.html#ae0eaebda205d5578085c3f9ea7b042d4

gael

[Martin Beeger]

Hey!

Post by Benoit Jacob
That leads to one of the strongest arguments in favor of unsigned: at
least, that has well-defined (wrapping) overflow behavior. That might
be 'broken', but it isn't nearly as dangerous as the undefined
behavior of signed overflow!

But if you take this point of view the unsigned-signed promotion and
comparison rules are just a as big hazard. We should never be forced to
really think about them.
E.g. try to wrap your had around the following:
signed int a{-1 };
unsigned int b{1};
according to C++ language rules now a < b is false.

This is possible through consistent use of one type of indexes, sizes,
slices etc. And negative slices and strides have well-defined meaning
and should be allowed, so they must be signed. Deciding on a
case-by-case basis forces peoples into all the nitty gritty details of
integer promotion and comparision, which is exactly what we should IMHO
protect users from.

So that argument works both ways.

Martin

[Martin Beeger]

Some more thoughts on this topic:

* Jon Kalb (signed integer fraction) has pointed out that repeatedly
obnoxious bugs with unsigned integer underflow and bounds wraparound
when subtracting sizes went unnoticed very very long even in libraries
like STL & boost.

* Andrej Alexandrescu pointed out that whether using indices or pointers
in algorithmic loops is faster seems to change every five years or so.
That means, that using indices instead of pointers is a valid strategy
and may increase your performance.

* That the specified wraparound behaviour when using loop indices
inhibits a class of optimizations and therefore especially for fixed but
unknown loop lengths there is a inherent performance hit of using
unsigned. See CppCon 2016 Michael Spencer - My Little Optimizer:
undefined behaviour is magic.

* When pressed to answer why or how it came that std::size_t became
unsigned Stoustrup replied: Someone had a case for needing to reserve
more than half the address space in a vector and the number of elements
to be strictly positive. (sadly I could not find the reference here)
Which is funny, because you cannot actually use more than half, as Mark
pointed out.

Post by Francois Fayard
On the other side, I understand people who use std::size_t for
indexing because it is consistent with the standard library.

* Eric Nieblers STL2 project has plans on using signed. See discussion
here:https://github.com/ericniebler/stl2/issues/182. So if Eigen now
chooses unsigned for compatibility and the project STL2 ever flies, we
might look like fools ;)

For me the argument that loop optimization suffers from using unsigned
and this is inherent in the language (and cannot be fully solved by
compiler vendors) is the strongest argument, as performance matters for
Eigen's loop and indexes might likely end up being used in their exit
conditions.

Regards, Martin

Post by Francois Fayard
Well made points. These greatly expand on points I made on this list
in May 2010.
From the linked video...
"I think one of the sad things about the standard library is that the
indices are unsigned whereas array indices are unsigned.
You are sort of doomed to have confusion and problems with that. [...]
It is a major bug source. Which is why I'm saying, 'stay as simple as
you can. Use [signed] integers until you really, really need something
else.' "
-- Bjarne Stroustrop
This opinion was echoed by several of the esteemed panel and opposed
by none: Bjarne Stroustrup, Andrei Alexandrescu, Herb Sutter, Scott
Meyers, Chandler Carruth, Sean Parent, Michael Wong, and Stephan T. Lavavej.
" They [the unsigned ordinals in the STL] are wrong. We're sorry. We
were young."
I would add...
It is human nature to forget that these "integer" data type we're
discussing are only approximations of integers over a finite range.
The approximation is most horribly broken at the point of
over/underflow. For signed types, that point is often comfortably far
from where our calculations happen.
For unsigned types, that boundary point at the busiest spot, zero.
-- Mark

Post by Francois Fayard
- The core C++ language is using signed integers for indexing. If p
is a pointer, p[k] is defined for k being a std::ptrdiff_t which is
the Index type used by Eigen
- The C++ standard library is using unsigned integers for indexing: std::size_t
So, if you want to choose: (core C++) > (STL) > (Eigen). You have to
go and use signed integers. Most people in the standard committees
think that using unsigned integers for indexing was a mistake,
including Bjarne Stroustrup, Herb Sutter and Chandler Carruth. You
can see their argument in this video, at 42:38 and 1:02:50 (
http://youtu.be/Puio5dly9N8 ).
Using unsigned integers is just an error-prone. For instance, if you
have an array v and you are looking from the first element k when
you go from b downto a such that v[k] = 0, with unsigned integers,
for (int k = b; k >= a, —k) {
if (v[k] == 0) {
return k;
}
}
If you do that with unsigned integers, good luck to write something
simple that does not get crazy when a = 0 (It was a real bug I found
in an image program that was searching for something from right to
left inside a rectangle of interest).
In terms of performance, the compiler can also do more things with
signed integers as overflow for signed integers is undefined
behavior. This is not the case for unsigned integers (they warp). As
a consequence, a compiler can assume that p[k] and p[k + 1] are next
to each other in memory if k is signed. It can’t do that if k is
unsigned (think of the mess it can lead for people working on
auto-vectorization). With signed integer 10 * k / 2 = 5 * k. This is
not the case with unsigned integers. I believe that "unsigned
integers" should be renamed "modulo integers” because unsigned
integers are just Z/(2^n Z). And I have taught enough Mathematics to
know that most people are (or should be) scared of Z/(2^n Z) :-)
The only advantage of unsigned integers on a performance point of
view is division: it is faster with unsigned integers. But I never
had this bottleneck in real programs.
An argument used by “unsigned” people is that you get an extra bit
for array indices. This is just nonsense. First, it only happens on
32-bit systems with char arrays of more than 2 million elements. Have
you ever considered *char* arrays that long? Now, the must funny part
is that if you look at the implementation of std::vector<T>, it
stores 3 pointers, including the begin and the end of the array. To
get its size, the vector returns static_cast<std::size_t>(end -
begin). And end - begin is just at std::ptrdiff_t, so if the vector
has more than 2 million elements, you just get undefined behavior. So
std::vector can’t even use that bit !!! By the way, this is why
std::vector<T>::max_size() is 2 million with libc++ (clang). And
nobody seems to complain.
On the other side, I understand people who use std::size_t for
indexing because it is consistent with the standard library.
François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

Post by Benoit Jacob
It's complicated. The use of signed indexing has a long history
specifically in numerical linear algebra, see FORTRAN/BLAS/LAPACK.
Also some large C++ shops such as Google have entirely turned away
You should not use the unsigned integer types such as uint32_t,
unless there is a valid reason such as representing a bit pattern
rather than a number, or you need defined overflow modulo 2^N. In
particular, do not use unsigned types to say a number will never be
negative. Instead, use assertions for this.
I only mention this to say, there are valid points on both sides of
this argument. Neither choice will make much more than half of users
happy. (I actually don't like the Google C++ style that much, and I
wouldn't mind unsigned personally).
The only thing that would be really bad would be to try to make both
signednesses fully supported. That would mean keeping only the
intersection of the sets of advantages of either signedness, having
to deal with the union of the sets of constraints.
Benoit
2017-01-20 8:25 GMT-05:00 Henrik Mannerström
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think
there is a strict ordering "c++ language" > "stl" > "Eigen". More
than once have I developed something and only at some later point
brought in Eigen. Code written in std:size_t fashion has then needed
refactoring. So, if there would be a vote, I'd vote for size_t
indexing. I think smooth interoperability with stl is valuable.
Best,
Henrik
On Thu, Jan 19, 2017 at 10:58 PM, Márton Danóczy
Hi all,
while I would not want to argue with Gael nor with the numerous C++
experts advocating signed integers, today's reality is different.
Some libraries, the most prominent being the standard library, use
unsigned integers as indices. Therefore, mixing signed and unsigned
types is sadly unavoidable when using Eigen, which is a major
annoyance (at least for me, working with -pedantic -Werror).
In my opinion, using Eigen with
-DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t should just work, regardless
of the developers' personal preference for signed integers.
Best,
Marton
On 19 January 2017 at 13:00, Gael Guennebaud
On Thu, Jan 19, 2017 at 11:31 AM, Andrew Fitzgibbon
I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?
http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eigen.27s_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more
compatible with libraries that made the right choice of using signed
types.
For sparse matrices, I agree that we might try to allow for unsigned
types as the StorageIndex type. This should be doable while keeping
signed 64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael
I see the “downcounting” argument at
https://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back…
Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
Sent: 13 January 2017 12:26
Subject: Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
I think you are mixing Eigen::RowMajor with Eigen::RowMajorBit. I
agree that the bit flags could be managed differently using
individual type traits, but regarding Eigen::RowMajor, it is
currently used as a template parameter to Matrix, Array,
Matrix<...., RowMajor|DontAlign>
which is pretty convenient to write compared to having to subclass
some default_matrix_traits class to customize the options. With
RowMajor|DontAlign, RowMajor could still be instance of an
integral_constant-like type with operator | overloaded.... Actually
I've started to think about such an approach for Eigen::Dynamic, so
M = N*2+1
M = N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's
easy to forget about checking for Dynamic, especially when combining
multiple compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing feature
is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report entry
[1]. and a old pull-request with various discussions [2]. The Tensor module
also support reshape [3].
However, the feature is still not there because we never converged about how
to properly handle the ambiguity between col-major / row-major orders, also
called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the storage
order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose twice)
B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in generic code)
* not all expressions have a natural storage order (e.g., a+a^T, a*b)
* needs a hard copy if, e.g., the user want to stack columns of a
row-major input
C) Give the user an option to decide which order to use between: ColMajor,
RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one. However, we
yet have to specify how to pass this option at compile-time, what Auto
means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I already
mentioned, some expressions do not has any natural storage order. We could
address this issue by limiting the use of 'Auto' to expressions for which
- Any expressions with the DirectAccessBit flags (it means we are dealing
with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic expression)
- Any expression with the LinearAccessBit flag: it means the expression can
be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear view
with no constraints of the stacking order? Then we could add a fourth option
meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is perhaps the
most common and predictable choice given that the default storage is column
major too.
template<typename RowsType=Index,typename ColType=Index,typename Order=Xxxx>
DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the optional
order.
Then for the name of the options we cannot use
"RowMajor"/"ColMajor" because
they already are defined as "static const int" and we need objects with
different types here. Moreover, col-major/row-major does not extend well to
multi-dimension tensors. I also don't really like the reference to Fortran/C
as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time & runtime
A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute one of
the dimension to match the given matrix size. We cannot reuse "Auto" here
A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we need a
compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Eigen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#markdown-header-operation-reshapeconst-dimensions-new_dims
[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.reshape.html

[Benoit Jacob]

a couple of notes:

- i dont believe there is any chance at all of Eigen changing this now --
at least I had been writing in this thread assuming only idle discussion.
That would be a very intrusive breaking change to make at this point.

- i do agree with the argument that unsigned makes decrementing loop
error-prone at 0. It is the same argument that was made on this mailing
list many years ago and motivated the choice of signed indices. We are in
violent agreement! :-) I just wanted to point out how it's not clear-cut as
both signednesses come with strengths and weaknesses.

The C++ committee theoretically could acknowledge that 2's complement has
won and make signed overflow well-defined behavior (as wrapping); if they
did that, that would remove one of the main issues with signed and arguably
that would start to make it look like a no-brained. But compiler authors
wouldn't like that, because it would take away the optimization
opportunities.

Benoit

Post by Martin Beeger
* Jon Kalb (signed integer fraction) has pointed out that repeatedly
obnoxious bugs with unsigned integer underflow and bounds wraparound when
subtracting sizes went unnoticed very very long even in libraries like STL
& boost.
* Andrej Alexandrescu pointed out that whether using indices or pointers
in algorithmic loops is faster seems to change every five years or so. That
means, that using indices instead of pointers is a valid strategy and may
increase your performance.
* That the specified wraparound behaviour when using loop indices inhibits
a class of optimizations and therefore especially for fixed but unknown
loop lengths there is a inherent performance hit of using unsigned. See
CppCon 2016 Michael Spencer - My Little Optimizer: undefined behaviour is
magic. http://youtu.be/g7entxbQOCc
* When pressed to answer why or how it came that std::size_t became
unsigned Stoustrup replied: Someone had a case for needing to reserve more
than half the address space in a vector and the number of elements to be
strictly positive. (sadly I could not find the reference here) Which is
funny, because you cannot actually use more than half, as Mark pointed out.

Post by Francois Fayard
On the other side, I understand people who use std::size_t for indexing
because it is consistent with the standard library.

* Eric Nieblers STL2 project has plans on using signed. See discussion
here:https://github.com/ericniebler/stl2/issues/182. So if Eigen now
chooses unsigned for compatibility and the project STL2 ever flies, we
might look like fools ;)
For me the argument that loop optimization suffers from using unsigned and
this is inherent in the language (and cannot be fully solved by compiler
vendors) is the strongest argument, as performance matters for Eigen's loop
and indexes might likely end up being used in their exit conditions.
Regards, Martin

Post by Francois Fayard
Well made points. These greatly expand on points I made on this list in
May 2010.
From the linked video...
"I think one of the sad things about the standard library is that the
indices are unsigned whereas array indices are unsigned.
You are sort of doomed to have confusion and problems with that. [...] It
is a major bug source. Which is why I'm saying, 'stay as simple as you
can. Use [signed] integers until you really, really need something else.' "
-- Bjarne Stroustrop
This opinion was echoed by several of the esteemed panel and opposed by
none: Bjarne Stroustrup, Andrei Alexandrescu, Herb Sutter, Scott Meyers,
Chandler Carruth, Sean Parent, Michael Wong, and Stephan T. Lavavej.
" They [the unsigned ordinals in the STL] are wrong. We're sorry. We
were young."
I would add...
It is human nature to forget that these "integer" data type we're
discussing are only approximations of integers over a finite range.
The approximation is most horribly broken at the point of
over/underflow. For signed types, that point is often comfortably far from
where our calculations happen.
For unsigned types, that boundary point at the busiest spot, zero.
-- Mark

Post by Francois Fayard
- The core C++ language is using signed integers for indexing. If p is a
pointer, p[k] is defined for k being a std::ptrdiff_t which is the Index
type used by Eigen
- The C++ standard library is using unsigned integers for indexing: std::size_t
So, if you want to choose: (core C++) > (STL) > (Eigen). You have to go
and use signed integers. Most people in the standard committees think that
using unsigned integers for indexing was a mistake, including Bjarne
Stroustrup, Herb Sutter and Chandler Carruth. You can see their argument in
this video, at 42:38 and 1:02:50 ( https://www.youtube.com/watch?
v=Puio5dly9N8 ).
Using unsigned integers is just an error-prone. For instance, if you
have an array v and you are looking from the first element k when you go
from b downto a such that v[k] = 0, with unsigned integers, you just need
for (int k = b; k >= a, —k) {
if (v[k] == 0) {
return k;
}
}
If you do that with unsigned integers, good luck to write something
simple that does not get crazy when a = 0 (It was a real bug I found in an
image program that was searching for something from right to left inside a
rectangle of interest).
In terms of performance, the compiler can also do more things with
signed integers as overflow for signed integers is undefined behavior. This
is not the case for unsigned integers (they warp). As a consequence, a
compiler can assume that p[k] and p[k + 1] are next to each other in memory
if k is signed. It can’t do that if k is unsigned (think of the mess it can
lead for people working on auto-vectorization). With signed integer 10 * k
/ 2 = 5 * k. This is not the case with unsigned integers. I believe that
"unsigned integers" should be renamed "modulo integers” because unsigned
integers are just Z/(2^n Z). And I have taught enough Mathematics to know
that most people are (or should be) scared of Z/(2^n Z) :-)
The only advantage of unsigned integers on a performance point of view
is division: it is faster with unsigned integers. But I never had this
bottleneck in real programs.
An argument used by “unsigned” people is that you get an extra bit for
array indices. This is just nonsense. First, it only happens on 32-bit
systems with char arrays of more than 2 million elements. Have you ever
considered *char* arrays that long? Now, the must funny part is that if you
look at the implementation of std::vector<T>, it stores 3 pointers,
including the begin and the end of the array. To get its size, the vector
returns static_cast<std::size_t>(end - begin). And end - begin is just at
std::ptrdiff_t, so if the vector has more than 2 million elements, you just
get undefined behavior. So std::vector can’t even use that bit !!! By the
way, this is why std::vector<T>::max_size() is 2 million with libc++
(clang). And nobody seems to complain.
On the other side, I understand people who use std::size_t for indexing
because it is consistent with the standard library.
François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

Post by Benoit Jacob
It's complicated. The use of signed indexing has a long history
specifically in numerical linear algebra, see FORTRAN/BLAS/LAPACK. Also
some large C++ shops such as Google have entirely turned away from unsigned
You should not use the unsigned integer types such as uint32_t, unless
there is a valid reason such as representing a bit pattern rather than a
number, or you need defined overflow modulo 2^N. In particular, do not use
unsigned types to say a number will never be negative. Instead, use
assertions for this.
I only mention this to say, there are valid points on both sides of
this argument. Neither choice will make much more than half of users happy.
(I actually don't like the Google C++ style that much, and I wouldn't mind
unsigned personally).
The only thing that would be really bad would be to try to make both
signednesses fully supported. That would mean keeping only the intersection
of the sets of advantages of either signedness, having to deal with the
union of the sets of constraints.
Benoit
2017-01-20 8:25 GMT-05:00 Henrik Mannerström <
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there
is a strict ordering "c++ language" > "stl" > "Eigen". More than once have
I developed something and only at some later point brought in Eigen. Code
written in std:size_t fashion has then needed refactoring. So, if there
would be a vote, I'd vote for size_t indexing. I think smooth
interoperability with stl is valuable.
Best,
Henrik
Hi all,
while I would not want to argue with Gael nor with the numerous C++
experts advocating signed integers, today's reality is different. Some
libraries, the most prominent being the standard library, use unsigned
integers as indices. Therefore, mixing signed and unsigned types is sadly
unavoidable when using Eigen, which is a major annoyance (at least for me,
working with -pedantic -Werror).
In my opinion, using Eigen with -DEIGEN_DEFAULT_DENSE_INDEX_TYPE=size_t
should just work, regardless of the developers' personal preference for
signed integers.
Best,
Marton
I wonder if a rethink of reshape could allow a move to
unsigned index types, assuming I understand correctly
that Dynamic would be of another type. It’s always been a
bit clunky getting “size_t-correctness” right for mixed
Eigen/STL code, and compilers complain increasingly
nowadays. Perhaps now might be a time to give it a try?
See also: http://eigen.tuxfamily.org/index.php?title=FAQ#Why_Eigen.27s
_API_is_using_signed_integers_for_sizes.2C_indices.2C_etc..3F
Maybe one day we'll get a "fixed" std-v2 that would be more compatible
with libraries that made the right choice of using signed types.
For sparse matrices, I agree that we might try to allow for unsigned
types as the StorageIndex type. This should be doable while keeping signed
64 bits integers for the API (rows, cols, nonZeros, etc.)
We might also think about solutions to ease the mix of Eigen/STL code...
gael
I see the “downcounting” argument at https://listengine.tuxfamily.o
rg/lists.tuxfamily.org/eigen/2009/03/msg00099.html,
but that appears fairly strongly to be a special case where
one would anyway want to benchmark, check sizes etc.
Finally, I think we are in a world where sparse arrays with
entries in the 2-4billion range are reasonably common,
and one could conceivably be pleased to get the extra bit
back

Thanks again for a great library!
A.
Dr Andrew Fitzgibbon FREng FBCS FIAPR
Partner Scientist
Microsoft HoloLens, Cambridge, UK
http://aka.ms/awf
Sent: 13 January 2017 12:26
Subject: Re: [eigen] Let's get reshape in shape for 3.4
Also, regarding them RowMajor/ColMajor int/type issue - perhaps stuff
them in a new namespace or class - storage ? Too bad StorageOrder is
already used in so many places. Honestly I'm all for you making them
types and things working uniformly from there. I have used them
myself as integers with the flags bitset, but only for enable_if logic
which would be rendered obsolete if you had a collection of C++11
inspired type traits (instead they get repeated on the web a few
places). Sorry if I'm not being very detailed, it's been a while
since I've needed these, but my point is that it was basically a flaw
to use them as int's in the first place, in user code - and so I
encourage you to change things so it all works fluidly in the new api
without fear of upsetting users. Although perhaps that is a daunting
task...
I think you are mixing Eigen::RowMajor with Eigen::RowMajorBit. I agree
that the bit flags could be managed differently using individual type
traits, but regarding Eigen::RowMajor, it is currently used as a template
Matrix<...., RowMajor|DontAlign>
which is pretty convenient to write compared to having to subclass some
default_matrix_traits class to customize the options. With
RowMajor|DontAlign, RowMajor could still be instance of an
integral_constant-like type with operator | overloaded.... Actually I've
started to think about such an approach for Eigen::Dynamic, so that one can
M = N*2+1
and get M==Dynamic if N==Dynamic. Currently we always have to write: M
= N==Dynamic ? Dynamic : 2*N+1 which is error prone because it's easy to
forget about checking for Dynamic, especially when combining multiple
compile-time identifiers.
gael
-Jason

Hi Gael,
Glad to see all the new api's you're moving in for the new year.
I actually prefer C if C is a superset of B - that is the way it works
in Numpy - oder is overridable in several places, but mainly things
follow the matrix types you are working with (which would be
expressions here).
I haven't thought about the details but is there any reason
A.reshaped(4, n/2) work via constexprs or something on the 4? I
imagine even if it did you're trying to cover for C++98 though, but I
think fix<4> is a fair bit ugly.
As for the placeholder for a solvable dimension - the matlab
convension is the empty matrix and I welcome that notion (warped as a
Null, Nil, Empty, Filled, DontCare, Placeholder, CalcSize (this and
the next are more explicit), or AutoSized
-Jason
On Thu, Jan 12, 2017 at 10:35 AM, Gael Guennebaud

Hi everyone,
just after generic indexing/slicing, another long standing missing feature
is reshape. So let's make it for 3.4.
This is not the first time we discuss it. There is a old bug report entry
[1]. and a old pull-request with various discussions [2]. The Tensor module
also support reshape [3].
However, the feature is still not there because we never converged about how
to properly handle the ambiguity between col-major / row-major orders, also
called Fortran versus C style orders (e.g., in numpy doc [4]).
A) Interpret the indices in column major only, regardless of the storage
order.
- used in MatLab and Armadillo
- pros: simple strategy
- cons: not very friendly for row-major inputs (needs to transpose twice)
B) Follows the storage order of the given expression
- used by the Tensor module
- pros: easiest implementation
* results depends on storage order (need to be careful in generic code)
* not all expressions have a natural storage order (e.g., a+a^T, a*b)
* needs a hard copy if, e.g., the user want to stack columns of a
row-major input
C) Give the user an option to decide which order to use between: ColMajor,
RowMajor, Auto
- used by numpy [4] with default to RowMajor (aka C-like order)
- pros: give full control to the user
- cons: the API is a bit more complicated
At this stage, option C) seems to be the only reasonable one. However, we
yet have to specify how to pass this option at compile-time, what Auto
means, and what is the default strategy.
Regarding 'Auto', it is similar to option (B) above. However, as I already
mentioned, some expressions do not has any natural storage order. We could
address this issue by limiting the use of 'Auto' to expressions for which
- Any expressions with the DirectAccessBit flags (it means we are dealing
with a Matrix, Map, sub-matrix, Ref, etc. but not with a generic expression)
- Any expression with the LinearAccessBit flag: it means the expression can
be efficiently processed as a 1D vector.
Any other situation would raise a static_assert.
But what if I really don't care and just want to, e.g., get a linear view
with no constraints of the stacking order? Then we could add a fourth option
meaning 'IDontCare', perhaps 'AnyOrder' ?
For the default behavior, I would propose 'ColMajor' which is perhaps the
most common and predictable choice given that the default storage is column
major too.
template<typename RowsType=Index,typename ColType=Index,typename Order=Xxxx>
DenseBase::reshaped(RowsType rows,ColType cols,Order = Order());
template<typename Order= Xxxx >
DenseBase.reshaped(Order = Order());
Note that I used "reshaped" with a "d" on purpose.
The storage order of the resulting expression would match the optional
order.
Then for the name of the options we cannot use "RowMajor"/"ColMajor" because
they already are defined as "static const int" and we need objects with
different types here. Moreover, col-major/row-major does not extend well to
multi-dimension tensors. I also don't really like the reference to Fortran/C
as in numpy. "Forward"/"Backward" are confusing too. Any ideas?
The rows/cols parameters could also be a mix of compile-time & runtime
A.reshaped(fix<4>,n/2);
And maybe we could even allow a placeholder to automatically compute one of
the dimension to match the given matrix size. We cannot reuse "Auto" here
A.reshaped(5,Auto);
Again, any ideas for a good placeholder name? (numpy uses -1 but we need a
compile-time identifier)
cheers,
gael
[1] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=437
[2] https://bitbucket.org/eigen/eigen/pull-requests/41
[3]
https://bitbucket.org/eigen/eigen/src/default/unsupported/Ei
gen/CXX11/src/Tensor/README.md?fileviewer=file-view-default#
markdown-header-operation-reshapeconst-dimensions-new_dims
[4]
https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/
numpy.reshape.html

[François Fayard]

My experience is to always take Andrei's advices with a grain of salt:

- For the pointer/index difference, I have never been able to measure any difference in between the 2. I'll be glad to get a sample code where one can measure any difference.

- Once the war of signed/unsigned comes to an end, there is also the problem of 32/64 bits integers on a 64-bit machine. If you have bandwidth problems, or vectorized code, the choice is obvious: use 32-bits indices. But what should you do in other cases? One has to know that when if p is a pointer and k is a 32-bit integer, to get the address of p[k] one need to convert first k to a 64-bit integer. So, you might think that using 64-bit indices is better on x86-64. I even found a very contrived benchmark where it is indeed more efficient. But for almost every code, it just does not make any difference.
Andrei Alexandrescu claims that it is better to use 32 bits integers because Intel processors have more ports that can work on them, so it increases instruction level parallelism. I did not try too hard, but I have never been able to find a benchmark that shows a difference.

So be careful with Andrei. His claims are extremely difficult to check.

* Andrej Alexandrescu pointed out that whether using indices or pointers in algorithmic loops is faster seems to change every five years or so. That means, that using indices instead of pointers is a valid strategy and may increase your performance.

[Gael Guennebaud]

Post by François Fayard
- Once the war of signed/unsigned comes to an end, there is also the
problem of 32/64 bits integers on a 64-bit machine. If you have bandwidth
problems, or vectorized code, the choice is obvious: use 32-bits indices.
But what should you do in other cases? One has to know that when if p is a
pointer and k is a 32-bit integer, to get the address of p[k] one need to
convert first k to a 64-bit integer. So, you might think that using 64-bit
indices is better on x86-64. I even found a very contrived benchmark where
it is indeed more efficient. But for almost every code, it just does not
make any difference.

I remember we observed a clear speedup when we moved from int to ptrdiff_t
in Eigen. That was before we release 2.0, so with much older compilers (gcc
4.2) and older hardware (core2).

Actually, both questions are highly related because when you start mixing
32 and 64 bits integers, I have to admit that unsigned types win here
because the conversion is a no op in this case, whereas signed types
require a special treatment. In Eigen, this happens when using SparseMatrix
or PermutationMatrix for which 32 bits signed integers are used by default
so save memory usage. All these conversions are explicitly handled by a
convert_index<To,From>(From x) helper function with assertion checking. To
overcome the signed conversion overhead, we could add a
convert_positive_index<To,From>(From x) variant asserting that x>0 and
enforcing a cheap conversion (as in the unsigned case).

Then regarding Eigen moving to unsigned integers (or supporting unsigned
integers, that's the same), that's not gonna happen because there are
numerous places where we truly need signed integers, and as previously
stated by others this would mean that for every use of the current Index
type we would have to carefully think whether it should be signed or
unsigned (considering possible future usages for which negative indices
could make sense), and then be extremely careful for every operations
(addition, comparison, assignment,etc) involving two Index types to be sure
they are both signed or both unsigned. We have enough subtleties to take
of. Sorry.

Regarding the "extra bit" argument, it does make sense for the StorageIndex
type when the number of non-zeros is in [2^31..2^32] on a 64 bits system.
For instance, SparseMatrix<double,0,unsigned int> would save 1/4 of memory
consumption compared to SparseMatrix<double,0,Index>. I'm sure this justify
all the pain of supporting both signed and unsigned types as the
StorageIndex.

gael

[Francois Fayard]

I remember we observed a clear speedup when we moved from int to ptrdiff_t in Eigen. That was before we release 2.0, so with much older compilers (gcc 4.2) and older hardware (core2).

I am not sure that you would see that with newer compilers. The reason is that the undefined behavior for overflow with signed integers allows 32-bit signed integers to be implemented as 64-bit signed integers when compiled if the compiler believes that this is useful. I am sure that this optimization was not made on earlier versions of compilers which is why you got a speedup at that time. I have not measured any difference with recent compilers except in very contrived examples like the one that is attached at the end of this email (with a recursive function).

Actually, both questions are highly related because when you start mixing 32 and 64 bits integers, I have to admit that unsigned types win here because the conversion is a no op in this case, whereas signed types require a special treatment.

Even though I understand your point, I still disagree that unsigned integers win here. Performance is not always about counting operations, but more often about letting the compiler reason about the code. As I said before, a compiler is allowed to change your integer from 32-bit to 64-bit it thinks that it makes a difference. It is not allowed with unsigned integers. Have a look at the concrete example from bzip2 given by Chandler Carruth at 39:20 on http://youtu.be/yG1OZ69H_-o

Then regarding Eigen moving to unsigned integers (or supporting unsigned integers, that's the same), that's not gonna happen because there are numerous places where we truly need signed integers, and as previously stated by others this would mean that for every use of the current Index type we would have to carefully think whether it should be signed or unsigned (considering possible future usages for which negative indices could make sense), and then be extremely careful for every operations (addition, comparison, assignment,etc) involving two Index types to be sure they are both signed or both unsigned. We have enough subtleties to take of. Sorry.

I am supporting the signed camp, so I am very happy with the current position of Eigen :-)

Regarding the "extra bit" argument, it does make sense for the StorageIndex type when the number of non-zeros is in [2^31..2^32] on a 64 bits system. For instance, SparseMatrix<double,0,unsigned int> would save 1/4 of memory consumption compared to SparseMatrix<double,0,Index>. I'm sure this justify all the pain of supporting both signed and unsigned types as the StorageIndex.

I totally understand this one.

==== weird example where 64-bit integer indexing is faster than 32-bit integer indexing ====

//==============================================================================
//
// InsideLoop
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.txt for details.
//
//==============================================================================

// This benchmark was designed to figure out if there is a difference in terms
// of performance between 32-bit integers and 64-bit integers.
//
// int long
//
// Intel compiler 17.0 37 39
// Clang 3.9 37 37
// Gcc 4.7 44 38
// Gcc 6.2 45 38
//
// So it seems that gcc is the only one to struggle with int where the
// performance goes down.

#define INT long

#include <cstdio>
#include <limits>
#include <random>

const INT n = 10;
const INT x_finish = n - 2;
const INT y_finish = n - 2;
char maze[n * n];

const char free_cell = 0;
const char barrier_cell = 1;
const char traversed_cell = 2;

INT minimum(INT a, INT b) { return a < b ? a : b; }

INT find_min_path_32(INT x, INT y, INT best_path_length,
INT current_path_length) {
maze[y * n + x] = traversed_cell;
++current_path_length;
if (current_path_length >= best_path_length) {
maze[y * n + x] = free_cell;
return std::numeric_limits<INT>::max();
}
if (x == x_finish && y == y_finish) {
maze[y * n + x] = free_cell;
return current_path_length;
}
INT length = std::numeric_limits<INT>::max();
if (x > 0 && maze[y * n + (x - 1)] == free_cell) {
INT rest_length =
find_min_path_32(x - 1, y, best_path_length, current_path_length);
length = minimum(rest_length, length);
}
if (x < n - 1 && maze[y * n + (x + 1)] == free_cell) {
INT rest_length =
find_min_path_32(x + 1, y, best_path_length, current_path_length);
length = minimum(rest_length, length);
}
if (y > 0 && maze[(y - 1) * n + x] == free_cell) {
INT rest_length =
find_min_path_32(x, y - 1, best_path_length, current_path_length);
length = minimum(rest_length, length);
}
if (y < n - 1 && maze[(y + 1) * n + x] == free_cell) {
INT rest_length =
find_min_path_32(x, y + 1, best_path_length, current_path_length);
length = minimum(rest_length, length);
}
if (length >= best_path_length) {
maze[y * n + x] = free_cell;
return std::numeric_limits<INT>::max();
} else {
maze[y * n + x] = free_cell;
return length;
}
}

void maze() {
const INT x_start = 1;
const INT y_start = 1;

std::mt19937 generator{};
std::uniform_int_distribution<INT> distribution{0, 4};

for (INT i = 0; i < n * n; ++i) {
if (distribution(generator) == 0) {
maze[i] = barrier_cell;
} else {
maze[i] = free_cell;
}
}
maze[y_start * n + x_start] = free_cell;
maze[y_finish * n + x_finish] = free_cell;
for (INT y = n - 1; y >= 0; --y) {
for (INT x = 0; x < n; ++x) {
if (maze[y * n + x] == free_cell) {
std::printf(".");
} else {
std::printf("O");
}
}
std::printf("\n");
}

INT length =
find_min_path_32(x_start, y_start, std::numeric_limits<INT>::max(), 0);

std::printf("Best path length: %d\n", static_cast<int>(length));
}

[Gael Guennebaud]

Post by Gael Guennebaud
I remember we observed a clear speedup when we moved from int to

ptrdiff_t in Eigen. That was before we release 2.0, so with much older
compilers (gcc 4.2) and older hardware (core2).
I am not sure that you would see that with newer compilers. The reason is
that the undefined behavior for overflow with signed integers allows 32-bit
signed integers to be implemented as 64-bit signed integers when compiled
if the compiler believes that this is useful. I am sure that this
optimization was not made on earlier versions of compilers which is why you
got a speedup at that time. I have not measured any difference with recent
compilers except in very contrived examples like the one that is attached
at the end of this email (with a recursive function).

That's easy to check, I simply measured:

EIGEN_DONT_INLINE
void foo(MatrixXf &A, MatrixXf &B, Index i, Index j, Index n, Index m)
{
A.block(i, j, n, m) += B.block(i+1, j+1, n, m);
}

and got 15% of speed difference between int and ptrdiff_t using either gcc6
or clang3.9.

Post by Gael Guennebaud
Actually, both questions are highly related because when you start

mixing 32 and 64 bits integers, I have to admit that unsigned types win
here because the conversion is a no op in this case, whereas signed types
require a special treatment.
Even though I understand your point, I still disagree that unsigned
integers win here. Performance is not always about counting operations, but
more often about letting the compiler reason about the code. As I said
before, a compiler is allowed to change your integer from 32-bit to 64-bit
it thinks that it makes a difference. It is not allowed with unsigned
integers. Have a look at the concrete example from bzip2 given by Chandler
Carruth at 39:20 on http://youtu.be/yG1OZ69H_-o

I measured the conversion of 1000 integers from 'int' or 'unsigned int' to
'long' and observe 25% of speed difference using either clang or gcc (in
favour of unsigned int). But, when used to index another buffer, like
data[indices[i]] as in sparse stuff, I cannot see any difference anymore.

gael

[f***@insideloop.io]

Post by Gael Guennebaud
EIGEN_DONT_INLINE
void foo(MatrixXf &A, MatrixXf &B, Index i, Index j, Index n, Index m)
{
A.block(i, j, n, m) += B.block(i+1, j+1, n, m);
}
and got 15% of speed difference between int and ptrdiff_t using either
gcc6 or clang3.9.

I have just tested this kind of code on a 32x32 matrix, and the version
using 64-bit integers is indeed 25% faster than the version using 32-bit
integers with Eigen.

But if I code the same thing in plain C++ (without Eigen), with for
loops,
I get exactly the same timings with 32-bit integers and 64-bit integers
with both the Intel compilers and clang. With gcc, the version with
32-bit
integers is 4% faster (see codes below).

My feeling is the fact that Eigen is written with intrinsics turns off
many
compiler optimizations. Therefore, the difference in between 32-bit and
64-bit integers is very Eigen-specific.
If there was such a difference in between 32-bit and 64-bit integers
indexing
in plain C/C++, nobody would index anymore with ints in C.

Post by Gael Guennebaud
I measured the conversion of 1000 integers from 'int' or 'unsigned
int' to 'long' and observe 25% of speed difference using either clang
or gcc (in favour of unsigned int).

My claim was not that there was no difference in between converting int
and
unsigned to long, but rather that this conversion does not happen as
often as
you might think and almost never makes any difference. For instance, a
compiler
might change

void f(double* p, long n) {
for (int k = 0; k < n; ++k) {
p[k] += 1.0;
}
}

to (look at the new type for k)

void f(double* p, long n) {
for (long k = 0; k < n; ++k) {
p[k] += 1.0;
}
}

because overflow for signed integers is undefined behavior. This
transformation
would be impossible with unsigned integers because of warping behavior.
So signed
integers give more flexibility to the compiler. Even though the
conversion from
int to long is more costly than the conversion from unsigned to long,
the compiler
is often allowed to remove this conversion either completely or at least
from the
inner loop with signed integers.

For 32-bit/64-bit integers, there are some corner cases where one is
clearly better
than the other. This code which tries to find the index of the smallest
element of
an array:

int index_smallest(float* p, int n) {
float small_value = std::numeric_limits<float>::max();
int small_k = -1;
for (int k = 0; k < n; ++k) {
if (p[k] < small_value) {
small_value = p[k];
small_k = k;
}
}
return k;
}

The Intel compiler is smart enough to vectorize this loop (this is a
reduction). But
as both small_value and small_k have to be carried in vector registers,
one could
understand that it is more efficient if their type have the same size.
This is what
happens. So if your array is of float, use int for indexes. Using 64-bit
integers
might lead to a 2x slowdown. But if your array is made of doubles, it is
better to
use a 64-bit integer :-)

Francois


PS: Here are the codes used for my benchmark
==== Plain C++
#include <cstddef>

//#define INT std::ptrdiff_t
#define INT int

int main() {
const int nb_time = 10000000;

const INT n = 32;
float* A = new float[n * n];
float* B = new float[n * n];
for (INT j = 0; j < n; ++j) {
for (INT i = 0; i < n; ++i) {
A[j * n + i] = 0.0f;
B[j * n + i] = 0.0f;
}
}

for (int k = 0; k < nb_time; ++k) {
for (INT j = 0; j < n; ++j) {
for (INT i = 0; i < n; ++i) {
A[j * n + i] += B[j * n + i];
}
}
}

return 0;
}
====

==== Eigen
//#define EIGEN_DEFAULT_DENSE_INDEX_TYPE std::ptrdiff_t
#define EIGEN_DEFAULT_DENSE_INDEX_TYPE int

#include <Eigen/Dense>

int main() {
const int nb_time = 10000000;

const int n = 32;
Eigen::Matrix<float, Eigen::Dynamic, Eigen::Dynamic> A(n, n);
Eigen::Matrix<float, Eigen::Dynamic, Eigen::Dynamic> B(n, n);
for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
A(i, j) = 0.0f;
B(i, j) = 0.0f;
}
}

for (int k = 0; k < nb_time; ++k) {
A.block(0, 0, n, n) += B.block(0, 0, n, n);
}

return 0;
}
====

[Francois Fayard]

Here is an example of the Intel compiler missing vectorization because of unsigned integers, and the explanation for Advisor : Loading Image...

François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

Post by Henrik Mannerström
This issue seems to warrant a separate message thread.
I'd like to offer my two cents: As much as I like Eigen I think there is a strict ordering "c++ language" > "stl" > "Eigen". More than once have I developed something and only at some later point brought in Eigen. Code written in std:size_t fashion has then needed refactoring. So, if there would be a vote, I'd vote for size_t indexing. I think smooth interoperability with stl is valuable.
Best,
Henrik

[Francois Fayard]

By, the way, on this case, the Intel compiler is wrong to complain.The loop is countable, and its trip count is nb_point.

I have sent this as a bug to the Intel compiler team and it seems that they don’t really care. There are so many cases where unsigned integers is a nightmare for them that they just don’t seem to bother anymore.

Another example is this one, from Chandler Carruth at 39:20,

François Fayard
Founder & Consultant - Inside Loop
Applied Mathematics & High Performance Computing

Great points, thank you!
- Henrik