)]}'
{
  "commit": "31e3cb4375f92e56f27b83c4583523c14a712b2d",
  "tree": "81ed497ee77f7862e067d28590e33b34be71459b",
  "parents": [
    "a6b90b7ec5c238692dc323e25ef927e4433edb1d"
  ],
  "author": {
    "name": "Gal Paikin",
    "email": "paiking@google.com",
    "time": "Mon Dec 07 15:18:34 2020 +0100"
  },
  "committer": {
    "name": "Gal Paikin",
    "email": "paiking@google.com",
    "time": "Wed Jan 27 02:22:51 2021 -0500"
  },
  "message": "Compare getting all refs except specific refs with seek and with filter\n\nThere are currently two ways to get all refs except a specific ref, we\nadd two methods that perform both and compare the two different approaches.\n\nThis change adds two methods that compares the two different approaches\nof such query:\n1. Get all the refs, and then filter by refs that don\u0027t start with the\nprefix (current approach).\n2. Get all refs until encountering a ref that is part of the prefix we\nshould exclude, skip using seekPastPrefix, and continue (new approach).\nThis works since the refs are sorted.\n\nSpecifically in Gerrit, we often have thousands of refs that are not\nrefs/changes, and millions of refs/changes, hence the second approach\nshould be much faster. In Jgit in general it\u0027s still expected to provide\na better result even if we\u0027re skipping a smaller chunk of the refs\nsince the complexity here is O(logn) with a binary search, rather than\nO(number of skipped refs).\n\nWe ran this benchmark on a big chunk of chromium/src\u0027s reftable. To run\nit, we first create the reftable:\n\n  git ls-remote https://chromium.googlesource.com/chromium/src \u003e lsr\n\n  bazel build org.eclipse.jgit.pgm:jgit \u0026\u0026 rm -rf /tmp/reftable* \u0026\u0026 \\\n    ./bazel-bin/org.eclipse.jgit.pgm/jgit debug-benchmark-reftable \\\n    --test write_stack lsr /tmp/reftable\n\nThen, we actually test the created reftable. Note that we can\u0027t test all\nof them at once since there are multiple ones, but below is a good\nexample.\n\nbazel build org.eclipse.jgit.pgm:jgit  \u0026\u0026 \\\n./bazel-bin/org.eclipse.jgit.pgm/jgit debug-benchmark-reftable \\\n--test get_refs_excluding_ref --ref refs/changes \\\nlsr /tmp/reftable/000000000001-0000001e0371.ref\n\nResult:\ntotal time the action took using seek:      36925 usec\ntotal time the action took using filter:     874382 usec\nnumber of refs that start with prefix: 4266.\nnumber of refs that don\u0027t start with prefix: 1962695.\n\nSimilarly for Android\u0027s biggest repository, platform/frameworks/base\n(still only partial result):\ntotal time the action took using seek:       9020 usec\ntotal time the action took using filter:     143166 usec\nnumber of refs that start with prefix: 296.\nnumber of refs that don\u0027t start with prefix: 60400.\n\nIn conclusion, it\u0027s easy to see an improvement of a factor of 15-20x for\nlarge Gerrit repositories!\n\nSigned-off-by: Gal Paikin \u003cpaiking@google.com\u003e\nChange-Id: I36d9b63eb259804c774864429cf2c761cd099cc3\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "630fac549e25b9550ded4a2d4bcd23a279f96a42",
      "old_mode": 33188,
      "old_path": "org.eclipse.jgit.pgm/src/org/eclipse/jgit/pgm/debug/BenchmarkReftable.java",
      "new_id": "f23f4cf0eaf00d0c4e1b5bb02ba9a23481507e73",
      "new_mode": 33188,
      "new_path": "org.eclipse.jgit.pgm/src/org/eclipse/jgit/pgm/debug/BenchmarkReftable.java"
    }
  ]
}