commit dc7a859752cc7571865b330667de29b43a909e1c
author Dmitriy Korchemkin <dmitriy.korchemkin@gmail.com> Fri Oct 06 15:55:21 2023 +0000
committer Dmitriy Korchemkin <dmitriy.korchemkin@gmail.com> Mon Oct 09 13:55:30 2023 +0000
tree 983ae525461ba06f5d0ed323df2ad8b2dfeea810
parent b379ab768caedbdc803f8c232af614235ae04835

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