From ff53b046f287273443d1013e704796a452de37af Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 Sep 2014 14:49:34 +0600 Subject: Libmv: update ceres to latest upstream version This brings faster BlockRandomAccessSparseMatrix::SymmetricRightMultiply. --- extern/libmv/third_party/ceres/ChangeLog | 38 +++++++++++++--------- .../internal/ceres/block_jacobi_preconditioner.cc | 4 --- .../internal/ceres/block_jacobi_preconditioner.h | 1 - .../ceres/block_random_access_sparse_matrix.cc | 19 ++++++----- .../ceres/block_random_access_sparse_matrix.h | 4 +++ .../third_party/ceres/internal/ceres/solver.cc | 2 +- 6 files changed, 37 insertions(+), 31 deletions(-) (limited to 'extern') diff --git a/extern/libmv/third_party/ceres/ChangeLog b/extern/libmv/third_party/ceres/ChangeLog index ee67da5afb9..6f921542019 100644 --- a/extern/libmv/third_party/ceres/ChangeLog +++ b/extern/libmv/third_party/ceres/ChangeLog @@ -1,3 +1,25 @@ +commit 9e11cd16d09403b9270e621e839d5948b6a74b8d +Author: Sameer Agarwal +Date: Mon Sep 29 14:27:58 2014 -0700 + + Faster BlockRandomAccessSparseMatrix::SymmetricRightMultiply. + + Trade a small amount of memory to improve the cache coherency of + the SymmetricRightMultiply operation. + + The resulting code leads to a 10-20% speedup in the linear solver + end to end. + + Change-Id: I8ab2fe152099e849b211b5b19e4ef9f03d8e7f1c + +commit 46b8461fd010c1e7ffce6bb2bdf8a84b659d5e09 +Author: Sameer Agarwal +Date: Mon Sep 29 15:10:58 2014 -0700 + + Various minor fixes from William Rucklidge. + + Change-Id: Ibe731d5db374ad8ee148d62a9fdd8d726b607a3f + commit b44cfdef25f6bf0917a23b3fd65cce38aa6a3362 Author: Sameer Agarwal Date: Mon Sep 29 07:53:54 2014 -0700 @@ -647,19 +669,3 @@ Date: Thu Aug 7 12:19:10 2014 -0700 construction is the right thing to do. Change-Id: I3bfdc89bb0027c8d67cde937e8f2fa385d89c30c - -commit cfb36463f9c1f806121779d651c7105ad899bb20 -Author: Sameer Agarwal -Date: Tue Aug 5 14:42:33 2014 -0700 - - Small fixes from William Rucklidge. - - Change-Id: I0be52f0f1e53cedccffe4807dc664a2f3fb4a8e4 - -commit 9a41132a0523af407b53644c07900f86aa6fceac -Author: Sameer Agarwal -Date: Mon Aug 4 22:45:53 2014 -0700 - - Small changes from Jim Roseborough. - - Change-Id: Ic8b19ea5c5f4f8fd782eb4420b30514153087d18 diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc index ea49f077e37..7f79a4f993d 100644 --- a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc +++ b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.cc @@ -102,9 +102,5 @@ void BlockJacobiPreconditioner::RightMultiply(const double* x, m_->RightMultiply(x, y); } -void BlockJacobiPreconditioner::LeftMultiply(const double* x, double* y) const { - m_->RightMultiply(x, y); -} - } // namespace internal } // namespace ceres diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h index 85792970925..e23e0e2d24c 100644 --- a/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h +++ b/extern/libmv/third_party/ceres/internal/ceres/block_jacobi_preconditioner.h @@ -60,7 +60,6 @@ class BlockJacobiPreconditioner : public BlockSparseMatrixPreconditioner { // Preconditioner interface virtual void RightMultiply(const double* x, double* y) const; - virtual void LeftMultiply(const double* x, double* y) const; virtual int num_rows() const { return m_->num_rows(); } virtual int num_cols() const { return m_->num_rows(); } diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc index 9da16a469d5..c43a9b78feb 100644 --- a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc +++ b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.cc @@ -88,6 +88,8 @@ BlockRandomAccessSparseMatrix::BlockRandomAccessSparseMatrix( ++it) { const int row_block_size = blocks_[it->first]; const int col_block_size = blocks_[it->second]; + cell_values_.push_back(make_pair(make_pair(it->first, it->second), + values + pos)); layout_[IntPairToLong(it->first, it->second)] = new CellInfo(values + pos); pos += row_block_size * col_block_size; @@ -156,20 +158,19 @@ void BlockRandomAccessSparseMatrix::SetZero() { void BlockRandomAccessSparseMatrix::SymmetricRightMultiply(const double* x, double* y) const { - for (LayoutType::const_iterator it = layout_.begin(); - it != layout_.end(); - ++it) { - int row; - int col; - LongToIntPair(it->first, &row, &col); - + vector< pair, double*> >::const_iterator it = + cell_values_.begin(); + for (; it != cell_values_.end(); ++it) { + const int row = it->first.first; const int row_block_size = blocks_[row]; const int row_block_pos = block_positions_[row]; + + const int col = it->first.second; const int col_block_size = blocks_[col]; const int col_block_pos = block_positions_[col]; MatrixVectorMultiply( - it->second->values, row_block_size, col_block_size, + it->second, row_block_size, col_block_size, x + col_block_pos, y + row_block_pos); @@ -179,7 +180,7 @@ void BlockRandomAccessSparseMatrix::SymmetricRightMultiply(const double* x, // triangular multiply also. if (row != col) { MatrixTransposeVectorMultiply( - it->second->values, row_block_size, col_block_size, + it->second, row_block_size, col_block_size, x + row_block_pos, y + col_block_pos); } diff --git a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h index a4f89d8130f..51b5d20cfe0 100644 --- a/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h +++ b/extern/libmv/third_party/ceres/internal/ceres/block_random_access_sparse_matrix.h @@ -111,6 +111,10 @@ class BlockRandomAccessSparseMatrix : public BlockRandomAccessMatrix { typedef HashMap LayoutType; LayoutType layout_; + // In order traversal of contents of the matrix. This allows us to + // implement a matrix-vector which is 20% faster than using the + // iterator in the Layout object instead. + vector, double*> > cell_values_; // The underlying matrix object which actually stores the cells. scoped_ptr tsm_; diff --git a/extern/libmv/third_party/ceres/internal/ceres/solver.cc b/extern/libmv/third_party/ceres/internal/ceres/solver.cc index e1c5ee30ba5..3512e156f9e 100644 --- a/extern/libmv/third_party/ceres/internal/ceres/solver.cc +++ b/extern/libmv/third_party/ceres/internal/ceres/solver.cc @@ -123,7 +123,7 @@ bool TrustRegionOptionsAreValid(const Solver::Options& options, string* error) { if (options.linear_solver_type == ITERATIVE_SCHUR && options.use_explicit_schur_complement && options.preconditioner_type != SCHUR_JACOBI) { - *error = "use_explicit_schur_complement only supports" + *error = "use_explicit_schur_complement only supports " "SCHUR_JACOBI as the preconditioner."; return false; } -- cgit v1.2.3