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/include/ceres/gradient_problem_solver.h b/include/ceres/gradient_problem_solver.h index db706f7..6e16dd7 100644 --- a/include/ceres/gradient_problem_solver.h +++ b/include/ceres/gradient_problem_solver.h
@@ -303,6 +303,10 @@ // Time (in seconds) spent evaluating the gradient. double gradient_evaluation_time_in_seconds; + // Time (in seconds) spent minimizing the interpolating polynomial + // to compute the next candidate step size as part of a line search. + double line_search_polynomial_minimization_time_in_seconds; + // Number of parameters in the probem. int num_parameters;
diff --git a/include/ceres/solver.h b/include/ceres/solver.h index a5efa2a..791630d 100644 --- a/include/ceres/solver.h +++ b/include/ceres/solver.h
@@ -832,6 +832,26 @@ // Time (in seconds) spent doing inner iterations. double inner_iteration_time_in_seconds; + // Cumulative timing information for line searches performed as part of the + // solve. Note that in addition to the case when the Line Search minimizer + // is used, the Trust Region minimizer also uses a line search when + // solving a constrained problem. + + // Time (in seconds) spent evaluating the univariate cost function as part + // of a line search. + double line_search_cost_evaluation_time_in_seconds; + + // Time (in seconds) spent evaluating the gradient of the univariate cost + // function as part of a line search. + double line_search_gradient_evaluation_time_in_seconds; + + // Time (in seconds) spent minimizing the interpolating polynomial + // to compute the next candidate step size as part of a line search. + double line_search_polynomial_minimization_time_in_seconds; + + // Total time (in seconds) spent performing line searches. + double line_search_total_time_in_seconds; + // Number of parameter blocks in the problem. int num_parameter_blocks; @@ -871,6 +891,9 @@ // Number of residuals in the reduced problem. int num_residuals_reduced; + // Is the reduced problem bounds constrained. + bool is_constrained; + // Number of threads specified by the user for Jacobian and // residual evaluation. int num_threads_given;
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; }