tree 983ae525461ba06f5d0ed323df2ad8b2dfeea810
parent b379ab768caedbdc803f8c232af614235ae04835
author Dmitriy Korchemkin <dmitriy.korchemkin@gmail.com> 1696607721 +0000
committer Dmitriy Korchemkin <dmitriy.korchemkin@gmail.com> 1696859730 +0000

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:

/bin/parallel_vector_operations_benchmark
-------------------------------------------
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
https://github.com/ceres-solver/ceres-solver/issues/1016

Change-Id: I555c882d63ee53323ceb426743b970f989b65503