| Re: [eigen] Signed or unsigned indexing |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
> On Jan 21, 2017, at 10:42 AM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:
>
> 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 https://www.youtube.com/watch?v=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));
}