Heya fellas,

I wrote the following code which will perform a lexicographical sort on an Eigen matrix, adapted from IGL:

Code: Select all

// The input here is an Eigen::MatrixXd Xi

auto num_cols = Xi.cols();
auto num_rows = Xi.rows();

Eigen::MatrixXi IX(num_rows, 1);
for(Eigen::DenseIndex i = 0; i < num_rows; i++)
   IX(i) = i;

auto index_less_than = [&Xi, num_cols](Eigen::DenseIndex i, Eigen::DenseIndex j)
{
   //const Eigen::VectorXd &row1 = Xi.row(i);
   //const Eigen::VectorXd &row2 = Xi.row(j);
   //return std::lexicographical_compare(row1.data(), row1.data() + num_cols, row2.data(), row2.data() + num_cols);
   for (Eigen::DenseIndex c = 0; c<num_cols; c++)
   {
      if (Xi.coeff(i, c) < Xi.coeff(j, c)) return true;
      else if (Xi.coeff(j, c) < Xi.coeff(i, c)) return false;
   }
   return false;
};

std::sort(IX.data(), IX.data() + IX.size(), index_less_than);

Eigen::MatrixXd dataXi(num_rows, num_cols);

for(Eigen::DenseIndex i = 0; i < num_rows; i++)
   dataXi.row(i) = Xi.row(IX(i));


The above code works as expected. Now I'm trying to optimize it and clean it up a bit. I changed index_less_than to:

Code: Select all

auto index_less_than = [&Xi, num_cols](Eigen::DenseIndex i, Eigen::DenseIndex j)
{
   const Eigen::VectorXd &row1 = Xi.row(i);
   const Eigen::VectorXd &row2 = Xi.row(j);
   return std::lexicographical_compare(row1.data(), row1.data() + num_cols, row2.data(), row2.data() + num_cols);
};


It also works but I noticed a performance hit when using STL for this. The code above is slower than the one before.

Both VectorXd in the above code are necessary since Xi is column major (and this is a project requirement). I believe this is the major factor in the performance hit I'm noticing.

Is there an alternative way to perform this without such a hit on performance?

Just to quantify the performance hit, I ran a loop on this for 10k iterations with a 4x2 matrix and I'm noticing a difference in performance between 2 and 3 times slower for the second approach.

This is because "const Eigen::VectorXd &row1 = Xi.row(i);" performs a deep copy. You can fix the issue with:

Ref<const VectorXd> row1 = Xi.row(i);

This will perform a deep copy only if needed, for instance if Xi is row-major.

ggael I don't think your suggestion works for my case.

VectorXd is column-major, so is my matrix Xi. Wouldn't Ref expect a Xi.column instead of a Xi.row?

I made the following changes according to your suggestion:

Code: Select all

Eigen::Ref<const Eigen::VectorXd> row1 = Xi.row(i);
Eigen::Ref<const Eigen::VectorXd> row2 = Xi.row(j);
return std::lexicographical_compare(row1.data(), row1.data() + num_cols, row2.data(), row2.data() + num_cols);


and it breaks at line 505 in Assign.h:

Code: Select all

eigen_assert(rows() == other.rows() && cols() == other.cols());

Sorry, I'm very tired. Indeed, my suggestion would work if Xi was row-major. In your case, you're left with two options:

1 - do the manual loop as before.

2 - write an iterator incrementing the pointer of Xi.outerStride().

Sorry, I'm very tired.

No problem, man. I thank you very much for your kind assistance.

I'm sticking with option 1 for now since it's a time critical loop. Thanks again!