)]}'
{
  "commit": "354002f989e7abdab9a4c17291662ab6e3102283",
  "tree": "36d2fc04af2b52d1a87a22f0ecad4c66a8bf18a7",
  "parents": [
    "a9b3fcff426eb33644413f766fdc785af937d9ed"
  ],
  "author": {
    "name": "Dmitriy Korchemkin",
    "email": "dmitriy.korchemkin@gmail.com",
    "time": "Fri Oct 06 18:19:12 2023 +0000"
  },
  "committer": {
    "name": "Dmitriy Korchemkin",
    "email": "dmitriy.korchemkin@gmail.com",
    "time": "Fri Oct 06 20:25:16 2023 +0000"
  },
  "message": "Schedule task in ParallerFor from the previous task\n\nAs pointed out by several users, introduction of parallel operations on\nvectors severely impacts solver performance on small problems, with time\nconsumption increasing with the number of threads.\n\nThe problem is two-fold:\n - Single-threaded execution is faster than multi-threaded\n - Overhead of multi-threaded execution increases dramaticaly when\n   number of threads is increased\n\nSupposedly, the second problem is due to ParallelInvoke scheduling\na task for each thread via ThreadPool.\nWhen the time required to perform computations is smaller than costs of\nscheduling task, runtime becomes linear in num_threads.\nMoreover, main thread competes with working threads for mutex in\nConcurrentQueue.\n\nIn order to limit scheduling overhead and minimize lock contention,\neach new task is scheduled from the previous one, if:\n - Number of scheduled tasks is less than num_threads\n - At the moment of creating the task not all work has been done\n\nCorrectness is granted by atomicity of thread_id counter.\n\nSchedulerBenchmark mini-benchmark was added to illustrate the issue.\nEach iteration of parallel loop performs change of a single value.\n\nWith the previous scheduling strategy, increasing number of threads\nleads to significant increase of runtime:\n-----------------------------------------------------\nBenchmark                           Time   Iterations\n-----------------------------------------------------\nSchedulerBenchmark/128/1         14.1 ns     49496153\nSchedulerBenchmark/128/2         3965 ns       240173\nSchedulerBenchmark/128/4        13162 ns        71478\nSchedulerBenchmark/128/8        30643 ns        29614\nSchedulerBenchmark/128/16       63694 ns        10000\nSchedulerBenchmark/256/1         24.1 ns     28943598\nSchedulerBenchmark/256/2         3878 ns       227498\nSchedulerBenchmark/256/4        13293 ns        69817\nSchedulerBenchmark/256/8        31117 ns        32640\nSchedulerBenchmark/256/16       59503 ns        14910\nSchedulerBenchmark/1024/1        56.7 ns     12048398\nSchedulerBenchmark/1024/2        4346 ns       203140\nSchedulerBenchmark/1024/4       13487 ns        66736\nSchedulerBenchmark/1024/8       30982 ns        33090\nSchedulerBenchmark/1024/16      63199 ns        14762\nSchedulerBenchmark/4096/1         189 ns      3633540\nSchedulerBenchmark/4096/2        5932 ns       131884\nSchedulerBenchmark/4096/4       14784 ns        61236\nSchedulerBenchmark/4096/8       35857 ns        29276\nSchedulerBenchmark/4096/16      63934 ns        10000\n\nWith new scheduling strategy, increasing requested number of threads\ndoes not result in that high increase of runtime\n-----------------------------------------------------\nBenchmark                           Time   Iterations\n-----------------------------------------------------\nSchedulerBenchmark/128/1         14.1 ns     49323498\nSchedulerBenchmark/128/2         2411 ns       362916\nSchedulerBenchmark/128/4         3556 ns       243026\nSchedulerBenchmark/128/8         4346 ns       200626\nSchedulerBenchmark/128/16        5066 ns       169698\nSchedulerBenchmark/256/1         24.2 ns     28960018\nSchedulerBenchmark/256/2         2330 ns       388470\nSchedulerBenchmark/256/4         3864 ns       219233\nSchedulerBenchmark/256/8         4399 ns       195225\nSchedulerBenchmark/256/16        5111 ns       161858\nSchedulerBenchmark/1024/1        55.9 ns     12204777\nSchedulerBenchmark/1024/2        2541 ns       329807\nSchedulerBenchmark/1024/4        3977 ns       222628\nSchedulerBenchmark/1024/8        4607 ns       193548\nSchedulerBenchmark/1024/16       5031 ns       160285\nSchedulerBenchmark/4096/1         188 ns      3714433\nSchedulerBenchmark/4096/2        4203 ns       188284\nSchedulerBenchmark/4096/4        4832 ns       171811\nSchedulerBenchmark/4096/8        5605 ns       159093\nSchedulerBenchmark/4096/16       6425 ns       126861\n\n(both runs were executed on 28-core 56-thread cpu)\n\nChange-Id: I91eca783280598997bfe6abd28019847731692e4\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "0436178d6a66cac68207a6e5bd8e5aa0793df959",
      "old_mode": 33188,
      "old_path": "internal/ceres/CMakeLists.txt",
      "new_id": "5bd279214405cd58852582e422cb061c68da43fe",
      "new_mode": 33188,
      "new_path": "internal/ceres/CMakeLists.txt"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "f1cd0d91e354bf2058b9fd4b44c475eb4b69feee",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_for_benchmark.cc"
    },
    {
      "type": "modify",
      "old_id": "3e67e37bb7920c0c08ce406b806db4667864d355",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_invoke.h",
      "new_id": "707751be2a019bff82532890d29b3fac4da45675",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_invoke.h"
    }
  ]
}