Change MathematicalProgram::x_initial_guess_ from Eigen::VectorXd to std::vector<double>

[hongkai-dai]

When we need to push new entries to an array, using std::vector is much faster than Eigen::Vector.

Currently MathematicalProgram::x_initial_guess_ has the type of Eigen::VectorXd, and we often call conservativeResize on this vector, which is slow. I think it is better to change its type to std::vector<double>. And the return type of its getter function will be changed from Eigen::VectorXd to Eigen::Map<const Eigen::VectorXd>

Eigen::Map<const Eigen::VectorXd> MathematicalProgram::x_initial_guess() const {
}

@jwnimmer-tri WDYT?

[jwnimmer-tri]

I think we should never pursue any performance improvement without first building a peer-reviewed, application-level benchmark that demonstrates the symptom.

[hongkai-dai]

I have the following code to illustrate that using Eigen::VectorXd::conservativeResize() is much slower than std::vector<double>::push_back

#include <Eigen/Core>
#include <chrono>
#include <iostream>

void InsertWithEigenVector() {
  Eigen::VectorXd x(0);
  for (int i = 0; i < 10000; ++i) {
    x.conservativeResize(x.rows() + 1, Eigen::NoChange);
    x(x.rows() - 1) = i;
  }
}

void InsertWithStdVector() {
  std::vector<double> x{};
  for (int i = 0; i < 10000; ++i) {
    x.push_back(i);
  }
}

int main() {
  auto t1 = std::chrono::high_resolution_clock::now();
  InsertWithStdVector();
  auto t2 = std::chrono::high_resolution_clock::now();
  InsertWithEigenVector();
  auto t3 = std::chrono::high_resolution_clock::now();

  auto std_vector_ms_int = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1);
  auto eigen_vector_ms_int = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2);
  std::cout << "std vector takes " << std_vector_ms_int.count() << "us\n";
  std::cout << "Eigen vector takes " << eigen_vector_ms_int.count() << "us\n";

}

The result is

std vector takes 573us
Eigen vector takes 1371120us

[jwnimmer-tri]

That is not an application-level benchmark. That is a micro-benchmark of some irrelevant example.

The question we care about is, how long does it take to set up and solve a MathematicalProgram with (in this case) 10,000 decision variables, and what fraction of that time is spent resizing this storage? Taking 1 second to deal with storage costs is nothing if the program already takes 30 minutes to set up and solve.

What is the actual user experience slow-down we are aiming to resolve with work our on this topic?

What research project or demo program is slow, and a sample-based profiler showed that this section of the code was the most important facet to focus our effort on optimizing?

[hongkai-dai]

I agree that I don't have a benchmark yet. And as you said, improving this part of the code might not affect the overall performance by much.

But I still think changing Eigen::VectorXd to std::vector<double> is a net win, it will speed up constructing the program a bit. This is the same reason why we had #16472 a few years ago, that changed VectorX<symbolic::Variable> decision_variables_ to std::vector<symbolic::Variable> decision_variables_. So while this is not a high priority task, I think it is worth doing (probably during the holidays).

[jwnimmer-tri]

The question is one of cost-benefit. I agree there is probably a non-zero benefit. However, deprecating a method comes with a real and non-trivial cost, both for us and our users. Is the cost worth it? Only if the benefit is measurable.

Depending on the benchmark, there might also be a case for having the initial guess be zero-cost to maintain (e.g., nullopt) since many programs would not have a program-specific guess in the first place (they would pass the guess to Solve())? Those are the kinds of things that become more clear when we have benchmark(s).