Compute & report timing information for line searches.
- We now compute & report the cumulative time spent performing the
following tasks as part of a line search:
- Evaluation of the univariate cost function value & gradient.
- Minimization of the interpolating polynomial.
- Total time spent performing line searches.
- This information is now reported for all minimizers, although only in
the case of a constrained problem for the TR minimizer.
- Remove LineSearch::Function abstraction in place of using
LineSearchFunction implementation directly, and remove virtual
functions from LineSearchFunction.
-- LineSearch::Function added an unnecessary level of abstraction since
the user always had to create a LineSearchFunction anyway to use a
Ceres Evaluator, and it added an unncessary virtual function call.
Change-Id: Ia4e1921d78f351ae119875aa97a3ea5e8b5d9877
diff --git a/internal/ceres/gradient_problem_solver.cc b/internal/ceres/gradient_problem_solver.cc
index 4024f4c..4fda929 100644
--- a/internal/ceres/gradient_problem_solver.cc
+++ b/internal/ceres/gradient_problem_solver.cc
@@ -138,6 +138,7 @@
solver_summary.fixed_cost = 0.0;
solver_summary.preprocessor_time_in_seconds = 0.0;
solver_summary.postprocessor_time_in_seconds = 0.0;
+ solver_summary.line_search_polynomial_minimization_time_in_seconds = 0.0;
minimizer->Minimize(minimizer_options, solution.data(), &solver_summary);
@@ -146,6 +147,8 @@
summary->initial_cost = solver_summary.initial_cost;
summary->final_cost = solver_summary.final_cost;
summary->iterations = solver_summary.iterations;
+ summary->line_search_polynomial_minimization_time_in_seconds =
+ solver_summary.line_search_polynomial_minimization_time_in_seconds;
if (summary->IsSolutionUsable()) {
parameters = solution;
@@ -172,6 +175,7 @@
total_time_in_seconds(-1.0),
cost_evaluation_time_in_seconds(-1.0),
gradient_evaluation_time_in_seconds(-1.0),
+ line_search_polynomial_minimization_time_in_seconds(-1.0),
num_parameters(-1),
num_local_parameters(-1),
line_search_direction_type(LBFGS),
@@ -246,12 +250,14 @@
StringAppendF(&report, "\nTime (in seconds):\n");
- StringAppendF(&report, "\n Cost evaluation %23.3f\n",
+ StringAppendF(&report, "\n Cost evaluation %23.4f\n",
cost_evaluation_time_in_seconds);
- StringAppendF(&report, " Gradient evaluation %23.3f\n",
+ StringAppendF(&report, " Gradient evaluation %23.4f\n",
gradient_evaluation_time_in_seconds);
+ StringAppendF(&report, " Polynomial minimization %17.4f\n",
+ line_search_polynomial_minimization_time_in_seconds);
- StringAppendF(&report, "Total %25.3f\n\n",
+ StringAppendF(&report, "Total %25.4f\n\n",
total_time_in_seconds);
StringAppendF(&report, "Termination: %25s (%s)\n",
diff --git a/internal/ceres/line_search.cc b/internal/ceres/line_search.cc
index 0d645ac..8c2624e 100644
--- a/internal/ceres/line_search.cc
+++ b/internal/ceres/line_search.cc
@@ -28,17 +28,19 @@
//
// Author: sameeragarwal@google.com (Sameer Agarwal)
+#include "ceres/line_search.h"
+
#include <iomanip>
#include <iostream> // NOLINT
-#include "ceres/line_search.h"
-
-#include "ceres/fpclassify.h"
+#include "glog/logging.h"
#include "ceres/evaluator.h"
#include "ceres/internal/eigen.h"
+#include "ceres/fpclassify.h"
+#include "ceres/map_util.h"
#include "ceres/polynomial.h"
#include "ceres/stringprintf.h"
-#include "glog/logging.h"
+#include "ceres/wall_time.h"
namespace ceres {
namespace internal {
@@ -106,8 +108,9 @@
direction_(evaluator->NumEffectiveParameters()),
evaluation_point_(evaluator->NumParameters()),
scaled_direction_(evaluator->NumEffectiveParameters()),
- gradient_(evaluator->NumEffectiveParameters()) {
-}
+ gradient_(evaluator->NumEffectiveParameters()),
+ initial_evaluator_residual_time_in_seconds(0.0),
+ initial_evaluator_jacobian_time_in_seconds(0.0) {}
void LineSearchFunction::Init(const Vector& position,
const Vector& direction) {
@@ -142,6 +145,54 @@
return direction_.lpNorm<Eigen::Infinity>();
}
+void LineSearchFunction::ResetTimeStatistics() {
+ const map<string, double> evaluator_time_statistics =
+ evaluator_->TimeStatistics();
+ initial_evaluator_residual_time_in_seconds =
+ FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0);
+ initial_evaluator_jacobian_time_in_seconds =
+ FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0);
+}
+
+void LineSearchFunction::TimeStatistics(
+ double* cost_evaluation_time_in_seconds,
+ double* gradient_evaluation_time_in_seconds) const {
+ const map<string, double> evaluator_time_statistics =
+ evaluator_->TimeStatistics();
+ *cost_evaluation_time_in_seconds =
+ FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0) -
+ initial_evaluator_residual_time_in_seconds;
+ // Strictly speaking this will slightly underestimate the time spent
+ // evaluating the gradient of the line search univariate cost function as it
+ // does not count the time spent performing the dot product with the direction
+ // vector. However, this will typically be small by comparison, and also
+ // allows direct subtraction of the timing information from the totals for
+ // the evaluator returned in the solver summary.
+ *gradient_evaluation_time_in_seconds =
+ FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0) -
+ initial_evaluator_jacobian_time_in_seconds;
+}
+
+void LineSearch::Search(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const {
+ const double start_time = WallTimeInSeconds();
+ *CHECK_NOTNULL(summary) = LineSearch::Summary();
+
+ summary->cost_evaluation_time_in_seconds = 0.0;
+ summary->gradient_evaluation_time_in_seconds = 0.0;
+ summary->polynomial_minimization_time_in_seconds = 0.0;
+
+ options().function->ResetTimeStatistics();
+ this->DoSearch(step_size_estimate, initial_cost, initial_gradient, summary);
+ options().function->
+ TimeStatistics(&summary->cost_evaluation_time_in_seconds,
+ &summary->gradient_evaluation_time_in_seconds);
+
+ summary->total_time_in_seconds = WallTimeInSeconds() - start_time;
+}
+
// Returns step_size \in [min_step_size, max_step_size] which minimizes the
// polynomial of degree defined by interpolation_type which interpolates all
// of the provided samples with valid values.
@@ -217,16 +268,15 @@
ArmijoLineSearch::ArmijoLineSearch(const LineSearch::Options& options)
: LineSearch(options) {}
-void ArmijoLineSearch::Search(const double step_size_estimate,
- const double initial_cost,
- const double initial_gradient,
- Summary* summary) {
- *CHECK_NOTNULL(summary) = LineSearch::Summary();
+void ArmijoLineSearch::DoSearch(const double step_size_estimate,
+ const double initial_cost,
+ const double initial_gradient,
+ Summary* summary) const {
CHECK_GE(step_size_estimate, 0.0);
CHECK_GT(options().sufficient_decrease, 0.0);
CHECK_LT(options().sufficient_decrease, 1.0);
CHECK_GT(options().max_num_iterations, 0);
- Function* function = options().function;
+ LineSearchFunction* function = options().function;
// Note initial_cost & initial_gradient are evaluated at step_size = 0,
// not step_size_estimate, which is our starting guess.
@@ -245,8 +295,7 @@
// gradient at the current query point.
const bool interpolation_uses_gradient_at_current_sample =
options().interpolation_type == CUBIC;
- const double descent_direction_max_norm =
- static_cast<const LineSearchFunction*>(function)->DirectionInfinityNorm();
+ const double descent_direction_max_norm = function->DirectionInfinityNorm();
++summary->num_function_evaluations;
if (interpolation_uses_gradient_at_current_sample) {
@@ -277,6 +326,7 @@
return;
}
+ const double polynomial_minimization_start_time = WallTimeInSeconds();
const double step_size =
this->InterpolatingPolynomialMinimizingStepSize(
options().interpolation_type,
@@ -285,6 +335,8 @@
current,
(options().max_step_contraction * current.x),
(options().min_step_contraction * current.x));
+ summary->polynomial_minimization_time_in_seconds +=
+ (WallTimeInSeconds() - polynomial_minimization_start_time);
if (step_size * descent_direction_max_norm < options().min_step_size) {
summary->error =
@@ -318,11 +370,10 @@
WolfeLineSearch::WolfeLineSearch(const LineSearch::Options& options)
: LineSearch(options) {}
-void WolfeLineSearch::Search(const double step_size_estimate,
- const double initial_cost,
- const double initial_gradient,
- Summary* summary) {
- *CHECK_NOTNULL(summary) = LineSearch::Summary();
+void WolfeLineSearch::DoSearch(const double step_size_estimate,
+ const double initial_cost,
+ const double initial_gradient,
+ Summary* summary) const {
// All parameters should have been validated by the Solver, but as
// invalid values would produce crazy nonsense, hard check them here.
CHECK_GE(step_size_estimate, 0.0);
@@ -454,15 +505,15 @@
FunctionSample* bracket_low,
FunctionSample* bracket_high,
bool* do_zoom_search,
- Summary* summary) {
- Function* function = options().function;
+ Summary* summary) const {
+ LineSearchFunction* function = options().function;
FunctionSample previous = initial_position;
FunctionSample current = ValueAndGradientSample(step_size_estimate, 0.0, 0.0);
current.value_is_valid = false;
const double descent_direction_max_norm =
- static_cast<const LineSearchFunction*>(function)->DirectionInfinityNorm();
+ function->DirectionInfinityNorm();
*do_zoom_search = false;
*bracket_low = initial_position;
@@ -592,6 +643,7 @@
const FunctionSample unused_previous;
DCHECK(!unused_previous.value_is_valid);
// Contracts step size if f(current) is not valid.
+ const double polynomial_minimization_start_time = WallTimeInSeconds();
const double step_size =
this->InterpolatingPolynomialMinimizingStepSize(
options().interpolation_type,
@@ -600,6 +652,8 @@
current,
previous.x,
max_step_size);
+ summary->polynomial_minimization_time_in_seconds +=
+ (WallTimeInSeconds() - polynomial_minimization_start_time);
if (step_size * descent_direction_max_norm < options().min_step_size) {
summary->error =
StringPrintf("Line search failed: step_size too small: %.5e "
@@ -640,8 +694,8 @@
FunctionSample bracket_low,
FunctionSample bracket_high,
FunctionSample* solution,
- Summary* summary) {
- Function* function = options().function;
+ Summary* summary) const {
+ LineSearchFunction* function = options().function;
CHECK(bracket_low.value_is_valid && bracket_low.gradient_is_valid)
<< std::scientific << std::setprecision(kErrorMessageNumericPrecision)
@@ -695,8 +749,7 @@
}
const int num_bracketing_iterations = summary->num_iterations;
- const double descent_direction_max_norm =
- static_cast<const LineSearchFunction*>(function)->DirectionInfinityNorm();
+ const double descent_direction_max_norm = function->DirectionInfinityNorm();
while (true) {
// Set solution to bracket_low, as it is our best step size (smallest f())
@@ -739,6 +792,7 @@
// value that will therefore be ignored.
const FunctionSample unused_previous;
DCHECK(!unused_previous.value_is_valid);
+ const double polynomial_minimization_start_time = WallTimeInSeconds();
solution->x =
this->InterpolatingPolynomialMinimizingStepSize(
options().interpolation_type,
@@ -747,6 +801,8 @@
upper_bound_step,
lower_bound_step.x,
upper_bound_step.x);
+ summary->polynomial_minimization_time_in_seconds +=
+ (WallTimeInSeconds() - polynomial_minimization_start_time);
// No check on magnitude of step size being too small here as it is
// lower-bounded by the initial bracket start point, which was valid.
//
diff --git a/internal/ceres/line_search.h b/internal/ceres/line_search.h
index 97b9bc6..ea72f74 100644
--- a/internal/ceres/line_search.h
+++ b/internal/ceres/line_search.h
@@ -44,6 +44,7 @@
class Evaluator;
struct FunctionSample;
+class LineSearchFunction;
// Line search is another name for a one dimensional optimization
// algorithm. The name "line search" comes from the fact one
@@ -57,7 +58,7 @@
// algorithms, e.g., Armijo, Wolfe etc.
class LineSearch {
public:
- class Function;
+ struct Summary;
struct Options {
Options()
@@ -147,31 +148,7 @@
// The one dimensional function that the line search algorithm
// minimizes.
- Function* function;
- };
-
- // An object used by the line search to access the function values
- // and gradient of the one dimensional function being optimized.
- //
- // In practice, this object will provide access to the objective
- // function value and the directional derivative of the underlying
- // optimization problem along a specific search direction.
- //
- // See LineSearchFunction for an example implementation.
- class Function {
- public:
- virtual ~Function() {}
- // Evaluate the line search objective
- //
- // f(x) = p(position + x * direction)
- //
- // Where, p is the objective function of the general optimization
- // problem.
- //
- // g is the gradient f'(x) at x.
- //
- // f must not be null. The gradient is computed only if g is not null.
- virtual bool Evaluate(double x, double* f, double* g) = 0;
+ LineSearchFunction* function;
};
// Result of the line search.
@@ -181,13 +158,27 @@
optimal_step_size(0.0),
num_function_evaluations(0),
num_gradient_evaluations(0),
- num_iterations(0) {}
+ num_iterations(0),
+ cost_evaluation_time_in_seconds(-1.0),
+ gradient_evaluation_time_in_seconds(-1.0),
+ polynomial_minimization_time_in_seconds(-1.0),
+ total_time_in_seconds(-1.0) {}
bool success;
double optimal_step_size;
int num_function_evaluations;
int num_gradient_evaluations;
int num_iterations;
+ // Cumulative time spent evaluating the value of the cost function across
+ // all iterations.
+ double cost_evaluation_time_in_seconds;
+ // Cumulative time spent evaluating the gradient of the cost function across
+ // all iterations.
+ double gradient_evaluation_time_in_seconds;
+ // Cumulative time spent minimizing the interpolating polynomial to compute
+ // the next candidate step size across all iterations.
+ double polynomial_minimization_time_in_seconds;
+ double total_time_in_seconds;
string error;
};
@@ -208,10 +199,10 @@
// search.
//
// Summary::success is true if a non-zero step size is found.
- virtual void Search(double step_size_estimate,
- double initial_cost,
- double initial_gradient,
- Summary* summary) = 0;
+ void Search(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
double InterpolatingPolynomialMinimizingStepSize(
const LineSearchInterpolationType& interpolation_type,
const FunctionSample& lowerbound_sample,
@@ -224,16 +215,41 @@
const LineSearch::Options& options() const { return options_; }
private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const = 0;
+
+ private:
LineSearch::Options options_;
};
-class LineSearchFunction : public LineSearch::Function {
+// An object used by the line search to access the function values
+// and gradient of the one dimensional function being optimized.
+//
+// In practice, this object provides access to the objective
+// function value and the directional derivative of the underlying
+// optimization problem along a specific search direction.
+class LineSearchFunction {
public:
explicit LineSearchFunction(Evaluator* evaluator);
- virtual ~LineSearchFunction() {}
void Init(const Vector& position, const Vector& direction);
- virtual bool Evaluate(double x, double* f, double* g);
+ // Evaluate the line search objective
+ //
+ // f(x) = p(position + x * direction)
+ //
+ // Where, p is the objective function of the general optimization
+ // problem.
+ //
+ // g is the gradient f'(x) at x.
+ //
+ // f must not be null. The gradient is computed only if g is not null.
+ bool Evaluate(double x, double* f, double* g);
double DirectionInfinityNorm() const;
+ // Resets to now, the start point for the results from TimeStatistics().
+ void ResetTimeStatistics();
+ void TimeStatistics(double* cost_evaluation_time_in_seconds,
+ double* gradient_evaluation_time_in_seconds) const;
private:
Evaluator* evaluator_;
@@ -246,6 +262,13 @@
// scaled_direction = x * direction_;
Vector scaled_direction_;
Vector gradient_;
+
+ // We may not exclusively own the evaluator (e.g. in the Trust Region
+ // minimizer), hence we need to save the initial evaluation durations for the
+ // value & gradient to accurately determine the duration of the evaluations
+ // we invoked. These are reset by a call to ResetTimeStatistics().
+ double initial_evaluator_residual_time_in_seconds;
+ double initial_evaluator_jacobian_time_in_seconds;
};
// Backtracking and interpolation based Armijo line search. This
@@ -257,10 +280,12 @@
public:
explicit ArmijoLineSearch(const LineSearch::Options& options);
virtual ~ArmijoLineSearch() {}
- virtual void Search(double step_size_estimate,
- double initial_cost,
- double initial_gradient,
- Summary* summary);
+
+ private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
};
// Bracketing / Zoom Strong Wolfe condition line search. This implementation
@@ -274,23 +299,26 @@
public:
explicit WolfeLineSearch(const LineSearch::Options& options);
virtual ~WolfeLineSearch() {}
- virtual void Search(double step_size_estimate,
- double initial_cost,
- double initial_gradient,
- Summary* summary);
+
// Returns true iff either a valid point, or valid bracket are found.
bool BracketingPhase(const FunctionSample& initial_position,
const double step_size_estimate,
FunctionSample* bracket_low,
FunctionSample* bracket_high,
bool* perform_zoom_search,
- Summary* summary);
+ Summary* summary) const;
// Returns true iff final_line_sample satisfies strong Wolfe conditions.
bool ZoomPhase(const FunctionSample& initial_position,
FunctionSample bracket_low,
FunctionSample bracket_high,
FunctionSample* solution,
- Summary* summary);
+ Summary* summary) const;
+
+ private:
+ virtual void DoSearch(double step_size_estimate,
+ double initial_cost,
+ double initial_gradient,
+ Summary* summary) const;
};
} // namespace internal
diff --git a/internal/ceres/line_search_minimizer.cc b/internal/ceres/line_search_minimizer.cc
index ad28ffb..d36545d 100644
--- a/internal/ceres/line_search_minimizer.cc
+++ b/internal/ceres/line_search_minimizer.cc
@@ -375,6 +375,14 @@
WallTimeInSeconds() - start_time
+ summary->preprocessor_time_in_seconds;
+ summary->line_search_cost_evaluation_time_in_seconds +=
+ line_search_summary.cost_evaluation_time_in_seconds;
+ summary->line_search_gradient_evaluation_time_in_seconds +=
+ line_search_summary.gradient_evaluation_time_in_seconds;
+ summary->line_search_polynomial_minimization_time_in_seconds +=
+ line_search_summary.polynomial_minimization_time_in_seconds;
+ summary->line_search_total_time_in_seconds +=
+ line_search_summary.total_time_in_seconds;
++summary->num_successful_steps;
if (iteration_summary.gradient_max_norm <= options.gradient_tolerance) {
diff --git a/internal/ceres/solver.cc b/internal/ceres/solver.cc
index c21927c..de170c3 100644
--- a/internal/ceres/solver.cc
+++ b/internal/ceres/solver.cc
@@ -349,6 +349,10 @@
summary->dense_linear_algebra_library_type = options.dense_linear_algebra_library_type; // NOLINT
summary->dogleg_type = options.dogleg_type;
summary->inner_iteration_time_in_seconds = 0.0;
+ summary->line_search_cost_evaluation_time_in_seconds = 0.0;
+ summary->line_search_gradient_evaluation_time_in_seconds = 0.0;
+ summary->line_search_polynomial_minimization_time_in_seconds = 0.0;
+ summary->line_search_total_time_in_seconds = 0.0;
summary->inner_iterations_given = options.use_inner_iterations;
summary->line_search_direction_type = options.line_search_direction_type; // NOLINT
summary->line_search_interpolation_type = options.line_search_interpolation_type; // NOLINT
@@ -558,6 +562,10 @@
residual_evaluation_time_in_seconds(-1.0),
jacobian_evaluation_time_in_seconds(-1.0),
inner_iteration_time_in_seconds(-1.0),
+ line_search_cost_evaluation_time_in_seconds(-1.0),
+ line_search_gradient_evaluation_time_in_seconds(-1.0),
+ line_search_polynomial_minimization_time_in_seconds(-1.0),
+ line_search_total_time_in_seconds(-1.0),
num_parameter_blocks(-1),
num_parameters(-1),
num_effective_parameters(-1),
@@ -568,6 +576,7 @@
num_effective_parameters_reduced(-1),
num_residual_blocks_reduced(-1),
num_residuals_reduced(-1),
+ is_constrained(false),
num_threads_given(-1),
num_threads_used(-1),
num_linear_solver_threads_given(-1),
@@ -773,14 +782,26 @@
num_inner_iteration_steps);
}
+ const bool print_line_search_timing_information =
+ minimizer_type == LINE_SEARCH ||
+ (minimizer_type == TRUST_REGION && is_constrained);
+
StringAppendF(&report, "\nTime (in seconds):\n");
StringAppendF(&report, "Preprocessor %25.4f\n",
preprocessor_time_in_seconds);
StringAppendF(&report, "\n Residual evaluation %23.4f\n",
residual_evaluation_time_in_seconds);
+ if (print_line_search_timing_information) {
+ StringAppendF(&report, " Line search cost evaluation %10.4f\n",
+ line_search_cost_evaluation_time_in_seconds);
+ }
StringAppendF(&report, " Jacobian evaluation %23.4f\n",
jacobian_evaluation_time_in_seconds);
+ if (print_line_search_timing_information) {
+ StringAppendF(&report, " Line search gradient evaluation %6.4f\n",
+ line_search_gradient_evaluation_time_in_seconds);
+ }
if (minimizer_type == TRUST_REGION) {
StringAppendF(&report, " Linear solver %23.4f\n",
@@ -792,6 +813,11 @@
inner_iteration_time_in_seconds);
}
+ if (print_line_search_timing_information) {
+ StringAppendF(&report, " Line search polynomial minimization %.4f\n",
+ line_search_polynomial_minimization_time_in_seconds);
+ }
+
StringAppendF(&report, "Minimizer %25.4f\n\n",
minimizer_time_in_seconds);
diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index c41b189..2f81fcb 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -147,6 +147,7 @@
summary->termination_type = NO_CONVERGENCE;
summary->num_successful_steps = 0;
summary->num_unsuccessful_steps = 0;
+ summary->is_constrained = options.is_constrained;
const int num_parameters = evaluator->NumParameters();
const int num_effective_parameters = evaluator->NumEffectiveParameters();
@@ -398,6 +399,16 @@
if (use_line_search) {
const LineSearch::Summary line_search_summary =
DoLineSearch(options, x, gradient, cost, delta, evaluator);
+
+ summary->line_search_cost_evaluation_time_in_seconds +=
+ line_search_summary.cost_evaluation_time_in_seconds;
+ summary->line_search_gradient_evaluation_time_in_seconds +=
+ line_search_summary.gradient_evaluation_time_in_seconds;
+ summary->line_search_polynomial_minimization_time_in_seconds +=
+ line_search_summary.polynomial_minimization_time_in_seconds;
+ summary->line_search_total_time_in_seconds +=
+ line_search_summary.total_time_in_seconds;
+
if (line_search_summary.success) {
delta *= line_search_summary.optimal_step_size;
}
