)]}'
{
  "commit": "dc7a859752cc7571865b330667de29b43a909e1c",
  "tree": "983ae525461ba06f5d0ed323df2ad8b2dfeea810",
  "parents": [
    "b379ab768caedbdc803f8c232af614235ae04835"
  ],
  "author": {
    "name": "Dmitriy Korchemkin",
    "email": "dmitriy.korchemkin@gmail.com",
    "time": "Fri Oct 06 15:55:21 2023 +0000"
  },
  "committer": {
    "name": "Dmitriy Korchemkin",
    "email": "dmitriy.korchemkin@gmail.com",
    "time": "Mon Oct 09 13:55:30 2023 +0000"
  },
  "message": "Single-threaded operations on small vectors\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\nIn order to minimize overhead of trying to execute small tasks using a\nlarge number of threads, task scheduling mechanism was changed to avoid\nscheduling all tasks at once.\n\nHowever, there is still a large difference in exectuion time because the\nmain thread always launches the next thread before starting doing the\nwork. This leads to several orders of magnitude slowdown when going from\na single-threaded execution (which follows a fast-forward path to a\nsingle loop over all indices, without any synchronization involved)\nto a two-thread execution:\n\n/bin/parallel_vector_operations_benchmark\n-------------------------------------------\nBenchmark                              Time\n-------------------------------------------\nSetZero/128                         12.8 ns\nSetZeroParallel/128/1               16.6 ns\nSetZeroParallel/128/2               2211 ns\n\nIn order to eliminate this effect, we limit the block-size of parallel\nexecution of vector operations to 2^16 elements (thus, starting parallel\nexecution only for vectors of at least 2^17 elements).\n\nThreshold of 2^16 elements was choosen by evaluating thresholds from\n2^10 to 2^20 (only powers of 2), with 2^14..2^20 significantly reducing\nworst-case runtime degradation.\n\nDetails can be found in discussion of the issue at\nhttps://github.com/ceres-solver/ceres-solver/issues/1016\n\nChange-Id: I555c882d63ee53323ceb426743b970f989b65503\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "5bd279214405cd58852582e422cb061c68da43fe",
      "old_mode": 33188,
      "old_path": "internal/ceres/CMakeLists.txt",
      "new_id": "f9fc2415f5d6464219baa9e0bb3b3f8017eea5d9",
      "new_mode": 33188,
      "new_path": "internal/ceres/CMakeLists.txt"
    },
    {
      "type": "modify",
      "old_id": "b7f57f025d25ea615bd1d73b4c8dafb8c482fb0e",
      "old_mode": 33188,
      "old_path": "internal/ceres/eigen_vector_ops.h",
      "new_id": "6ebff8891ef4d94e6be8aa19bb2dd34619dbae98",
      "new_mode": 33188,
      "new_path": "internal/ceres/eigen_vector_ops.h"
    },
    {
      "type": "modify",
      "old_id": "549dbe592fdffc70a9b4092f89dc6f2fd2393ac4",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_for.h",
      "new_id": "11db1fbc4886c5146bf2c45dea71039a6c7556cd",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_for.h"
    },
    {
      "type": "modify",
      "old_id": "b18a1c6a1e35a5294b3545bdb835ae3ad4fbc3b4",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_for_test.cc",
      "new_id": "58a27d4cf1eca4e6dc47be0764b6f62d06154d13",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_for_test.cc"
    },
    {
      "type": "modify",
      "old_id": "707751be2a019bff82532890d29b3fac4da45675",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_invoke.h",
      "new_id": "398f8f28f3dc953adf47cb806802edad0bcf5250",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_invoke.h"
    },
    {
      "type": "modify",
      "old_id": "6fe756ad609e3235f9a6c925b816decc45ebb884",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_vector_operations_benchmark.cc",
      "new_id": "8b55def9a643b6f52d5b5d3e415ba3cb14d07054",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_vector_operations_benchmark.cc"
    },
    {
      "type": "rename",
      "old_id": "133d7ce86edf47b1a0615a78cf853975cb7eeddf",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_for.cc",
      "new_id": "2154ecea506bfbb96e25301d6052fb6146b777a6",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_vector_ops.cc",
      "score": 79
    },
    {
      "type": "modify",
      "old_id": "20d6dbcf7f05fe62750cb8256c0f69d64f8adc56",
      "old_mode": 33188,
      "old_path": "internal/ceres/parallel_vector_ops.h",
      "new_id": "812950a6db995c955f8b9665b36c29414677af41",
      "new_mode": 33188,
      "new_path": "internal/ceres/parallel_vector_ops.h"
    }
  ]
}