Single-threaded operations on small vectors

As pointed out by several users, introduction of parallel operations on
vectors severely impacts solver performance on small problems, with time
consumption increasing with the number of threads.

In order to minimize overhead of trying to execute small tasks using a
large number of threads, task scheduling mechanism was changed to avoid
scheduling all tasks at once.

However, there is still a large difference in exectuion time because the
main thread always launches the next thread before starting doing the
work. This leads to several orders of magnitude slowdown when going from
a single-threaded execution (which follows a fast-forward path to a
single loop over all indices, without any synchronization involved)
to a two-thread execution:

Benchmark                              Time
SetZero/128                         12.8 ns
SetZeroParallel/128/1               16.6 ns
SetZeroParallel/128/2               2211 ns

In order to eliminate this effect, we limit the block-size of parallel
execution of vector operations to 2^16 elements (thus, starting parallel
execution only for vectors of at least 2^17 elements).

Threshold of 2^16 elements was choosen by evaluating thresholds from
2^10 to 2^20 (only powers of 2), with 2^14..2^20 significantly reducing
worst-case runtime degradation.

Details can be found in discussion of the issue at

Change-Id: I555c882d63ee53323ceb426743b970f989b65503
8 files changed
tree: 983ae525461ba06f5d0ed323df2ad8b2dfeea810
  1. .github/
  2. bazel/
  3. cmake/
  4. config/
  5. data/
  6. docs/
  7. examples/
  8. include/
  9. internal/
  10. scripts/
  11. .clang-format
  12. .gitignore
  13. BUILD
  14. CITATION.cff
  15. CMakeLists.txt
  18. package.xml

Android Linux macOS Windows

Ceres Solver

Ceres Solver is an open source C++ library for modeling and solving large, complicated optimization problems. It is a feature rich, mature and performant library which has been used in production at Google since 2010. Ceres Solver can solve two kinds of problems.

  1. Non-linear Least Squares problems with bounds constraints.
  2. General unconstrained optimization problems.

Please see for more information.