)]}'
{
  "commit": "a0cd0854aad4241f5c998195bdf7ca2abb59b493",
  "tree": "df5b32b0b716046b37661fa6e6cca6663c4dadb8",
  "parents": [
    "7b53262b7fe113847ca186236b7a8e6a61ff415c"
  ],
  "author": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Thu May 30 17:38:15 2019 -0700"
  },
  "committer": {
    "name": "Sameer Agarwal",
    "email": "sameeragarwal@google.com",
    "time": "Thu May 30 18:15:01 2019 -0700"
  },
  "message": "Speed up InvertPSDMatrix\n\nFor matrices of size \u003c\u003d 4, Eigen implements an optimized matrix\ninverse, which is orders of magnitude faster than computing the\nCholesky factorization and inverting it. This can have a significant\nimpact on the performance of the SchurEliminator.\n\nThis change implements this optimization, adds tests and benchmarks.\n\nBefore this change on my MacBook Pro\n\n-----------------------------------------------------------------------------------\nBenchmark                                            Time           CPU Iterations\n-----------------------------------------------------------------------------------\nBenchmarkFixedSizedInvertPSDMatrix\u003c1\u003e                0 ns          0 ns 1000000000\nBenchmarkFixedSizedInvertPSDMatrix\u003c2\u003e              102 ns        101 ns    6504851\nBenchmarkFixedSizedInvertPSDMatrix\u003c3\u003e     \t   164 ns        164 ns    4297669\nBenchmarkFixedSizedInvertPSDMatrix\u003c4\u003e              200 ns        200 ns    3933623\nBenchmarkFixedSizedInvertPSDMatrix\u003c5\u003e              353 ns        353 ns    1930454\nBenchmarkFixedSizedInvertPSDMatrix\u003c6\u003e              428 ns        427 ns    1629074\nBenchmarkFixedSizedInvertPSDMatrix\u003c7\u003e              559 ns        558 ns    1211639\nBenchmarkFixedSizedInvertPSDMatrix\u003c8\u003e              527 ns        527 ns    1000000\nBenchmarkFixedSizedInvertPSDMatrix\u003c9\u003e              873 ns        873 ns     902713\nBenchmarkFixedSizedInvertPSDMatrix\u003c10\u003e             892 ns        892 ns     787410\nBenchmarkFixedSizedInvertPSDMatrix\u003c11\u003e            1201 ns       1201 ns     564334\nBenchmarkFixedSizedInvertPSDMatrix\u003c12\u003e            1081 ns       1080 ns     588359\nBenchmarkDynamicallyInvertPSDMatrix/1              322 ns        322 ns    2244892\nBenchmarkDynamicallyInvertPSDMatrix/2              362 ns        362 ns    1869693\nBenchmarkDynamicallyInvertPSDMatrix/3              455 ns        455 ns    1604092\nBenchmarkDynamicallyInvertPSDMatrix/4              443 ns        443 ns    1578062\nBenchmarkDynamicallyInvertPSDMatrix/5              648 ns        647 ns     963232\nBenchmarkDynamicallyInvertPSDMatrix/6              756 ns        755 ns     899766\nBenchmarkDynamicallyInvertPSDMatrix/7              906 ns        905 ns     740506\nBenchmarkDynamicallyInvertPSDMatrix/8              885 ns        885 ns     790657\nBenchmarkDynamicallyInvertPSDMatrix/9             1219 ns       1219 ns     600503\nBenchmarkDynamicallyInvertPSDMatrix/10            1267 ns       1266 ns     534555\nBenchmarkDynamicallyInvertPSDMatrix/11            1580 ns       1579 ns     469591\nBenchmarkDynamicallyInvertPSDMatrix/12            1366 ns       1365 ns     514513\n\nafter this change:\n\n-----------------------------------------------------------------------------------\nBenchmark                                            Time           CPU Iterations\n-----------------------------------------------------------------------------------\nBenchmarkFixedSizedInvertPSDMatrix\u003c1\u003e                0 ns          0 ns 1000000000\nBenchmarkFixedSizedInvertPSDMatrix\u003c2\u003e                1 ns          1 ns 1000000000\nBenchmarkFixedSizedInvertPSDMatrix\u003c3\u003e                1 ns          1 ns  514399512\nBenchmarkFixedSizedInvertPSDMatrix\u003c4\u003e                2 ns          2 ns  320587683\nBenchmarkFixedSizedInvertPSDMatrix\u003c5\u003e              372 ns        372 ns    1856986\nBenchmarkFixedSizedInvertPSDMatrix\u003c6\u003e              446 ns        446 ns    1552502\nBenchmarkFixedSizedInvertPSDMatrix\u003c7\u003e              571 ns        570 ns    1208021\nBenchmarkFixedSizedInvertPSDMatrix\u003c8\u003e              586 ns        584 ns    1090988\nBenchmarkFixedSizedInvertPSDMatrix\u003c9\u003e             1003 ns       1001 ns     753279\nBenchmarkFixedSizedInvertPSDMatrix\u003c10\u003e            1074 ns       1070 ns     689974\nBenchmarkFixedSizedInvertPSDMatrix\u003c11\u003e            1361 ns       1351 ns     545388\nBenchmarkFixedSizedInvertPSDMatrix\u003c12\u003e            1160 ns       1158 ns     615742\nBenchmarkDynamicallyInvertPSDMatrix/1              326 ns        326 ns    2206552\nBenchmarkDynamicallyInvertPSDMatrix/2              362 ns        361 ns    1820982\nBenchmarkDynamicallyInvertPSDMatrix/3              432 ns        431 ns    1696361\nBenchmarkDynamicallyInvertPSDMatrix/4              473 ns        472 ns    1294115\nBenchmarkDynamicallyInvertPSDMatrix/5              657 ns        656 ns     917888\nBenchmarkDynamicallyInvertPSDMatrix/6              804 ns        802 ns     884050\nBenchmarkDynamicallyInvertPSDMatrix/7              936 ns        935 ns     679565\nBenchmarkDynamicallyInvertPSDMatrix/8              915 ns        915 ns     695548\nBenchmarkDynamicallyInvertPSDMatrix/9             1299 ns       1293 ns     583256\nBenchmarkDynamicallyInvertPSDMatrix/10            1300 ns       1296 ns     562959\nBenchmarkDynamicallyInvertPSDMatrix/11            1617 ns       1610 ns     480393\nBenchmarkDynamicallyInvertPSDMatrix/12            1380 ns       1379 ns     503934\n\nChange-Id: Id0d3bbe6d610ee7a3004bb8e2b657b90307b9805\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "3670aa4f3fac23632fc7c3a679513d041db85f1a",
      "old_mode": 33188,
      "old_path": "internal/ceres/CMakeLists.txt",
      "new_id": "22b5d073d5e51934779eb8492346c8769489a5b2",
      "new_mode": 33188,
      "new_path": "internal/ceres/CMakeLists.txt"
    },
    {
      "type": "modify",
      "old_id": "2319fea02a0b0c468c5cbd1b0610e2f7bb847839",
      "old_mode": 33188,
      "old_path": "internal/ceres/invert_psd_matrix.h",
      "new_id": "60f6a5752a9301ea320a8138c3ab0feabda80cce",
      "new_mode": 33188,
      "new_path": "internal/ceres/invert_psd_matrix.h"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "5aab6b613d87c0e2e10143bdd7cb493d4b0ec4ff",
      "new_mode": 33188,
      "new_path": "internal/ceres/invert_psd_matrix_benchmark.cc"
    },
    {
      "type": "modify",
      "old_id": "5da9c113b505ff3893752076cf89c833f959c175",
      "old_mode": 33188,
      "old_path": "internal/ceres/invert_psd_matrix_test.cc",
      "new_id": "0078e2144f985f0b31abde5956cac90214697143",
      "new_mode": 33188,
      "new_path": "internal/ceres/invert_psd_matrix_test.cc"
    }
  ]
}