)]}'
{
  "commit": "92d8ed8ac101d62183d51f280b90efb1de1bda5c",
  "tree": "8979963947ae78dcdf979c1fd81a06d0dde1ad28",
  "parents": [
    "90e07f0a342df836a33b92e179eb105243dba88d"
  ],
  "author": {
    "name": "Eric Wong",
    "email": "e@80x24.org",
    "time": "Wed Jul 07 23:10:19 2021 +0000"
  },
  "committer": {
    "name": "Junio C Hamano",
    "email": "gitster@pobox.com",
    "time": "Wed Jul 07 21:28:04 2021 -0700"
  },
  "message": "oidtree: a crit-bit tree for odb_loose_cache\n\nThis saves 8K per `struct object_directory\u0027, meaning it saves\naround 800MB in my case involving 100K alternates (half or more\nof those alternates are unlikely to hold loose objects).\n\nThis is implemented in two parts: a generic, allocation-free\n`cbtree\u0027 and the `oidtree\u0027 wrapper on top of it.  The latter\nprovides allocation using alloc_state as a memory pool to\nimprove locality and reduce free(3) overhead.\n\nUnlike oid-array, the crit-bit tree does not require sorting.\nPerformance is bound by the key length, for oidtree that is\nfixed at sizeof(struct object_id).  There\u0027s no need to have\n256 oidtrees to mitigate the O(n log n) overhead like we did\nwith oid-array.\n\nBeing a prefix trie, it is natively suited for expanding short\nobject IDs via prefix-limited iteration in\n`find_short_object_filename\u0027.\n\nOn my busy workstation, p4205 performance seems to be roughly\nunchanged (+/-8%).  Startup with 100K total alternates with no\nloose objects seems around 10-20% faster on a hot cache.\n(800MB in memory savings means more memory for the kernel FS\ncache).\n\nThe generic cbtree implementation does impose some extra\noverhead for oidtree in that it uses memcmp(3) on\n\"struct object_id\" so it wastes cycles comparing 12 extra bytes\non SHA-1 repositories.  I\u0027ve not yet explored reducing this\noverhead, but I expect there are many places in our code base\nwhere we\u0027d want to investigate this.\n\nMore information on crit-bit trees: https://cr.yp.to/critbit.html\n\nSigned-off-by: Eric Wong \u003ce@80x24.org\u003e\nSigned-off-by: Junio C Hamano \u003cgitster@pobox.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "c3565fc0f8f7df81232deca663bf55e14737ae97",
      "old_mode": 33188,
      "old_path": "Makefile",
      "new_id": "a1525978fb6bc50117819d029ab33147cfdf1ccf",
      "new_mode": 33188,
      "new_path": "Makefile"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "b0c65d810f5e5432a8e04270d6c80deefab6d052",
      "new_mode": 33188,
      "new_path": "cbtree.c"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "fe4587087e8820268e746eecd289c5fc0ea9ca10",
      "new_mode": 33188,
      "new_path": "cbtree.h"
    },
    {
      "type": "modify",
      "old_id": "91ded8c22ae9fa15350290a496fac0bdb8cb817f",
      "old_mode": 33188,
      "old_path": "object-file.c",
      "new_id": "35f3e7e9bb74c24ffa556f1a452983342671b6f2",
      "new_mode": 33188,
      "new_path": "object-file.c"
    },
    {
      "type": "modify",
      "old_id": "64202de60b1f5af3f09b15ba9c6240d7bb136930",
      "old_mode": 33188,
      "old_path": "object-name.c",
      "new_id": "3263c19457fa3ff89d95536a18a7b03f2d9beb2a",
      "new_mode": 33188,
      "new_path": "object-name.c"
    },
    {
      "type": "modify",
      "old_id": "ab6d469970e999af1d5951d3c871062918e81af9",
      "old_mode": 33188,
      "old_path": "object-store.h",
      "new_id": "e679acc4c31316cee2863579721e6c0f97210831",
      "new_mode": 33188,
      "new_path": "object-store.h"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "7eb0e9ba050115014d4b633fcd55dc8d5a90d7fc",
      "new_mode": 33188,
      "new_path": "oidtree.c"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "77898f510a12272ae2302805896eaf9eecb5ce7d",
      "new_mode": 33188,
      "new_path": "oidtree.h"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "180ee28dd935fc3aa94f513e72131abc4f523c96",
      "new_mode": 33188,
      "new_path": "t/helper/test-oidtree.c"
    },
    {
      "type": "modify",
      "old_id": "c5bd0c6d4c7abc0649e526d94924b05b0127ea53",
      "old_mode": 33188,
      "old_path": "t/helper/test-tool.c",
      "new_id": "9d37debf28ab2f11f0c507c5eb01698c329e7d7a",
      "new_mode": 33188,
      "new_path": "t/helper/test-tool.c"
    },
    {
      "type": "modify",
      "old_id": "e8069a3b2222b9982bb346f033f08c796f0b205d",
      "old_mode": 33188,
      "old_path": "t/helper/test-tool.h",
      "new_id": "f683a2f59c406fc4f682e22c92ed6250ea031da2",
      "new_mode": 33188,
      "new_path": "t/helper/test-tool.h"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "bfb1397d7b23610539803bb5c40484df6b02c836",
      "new_mode": 33261,
      "new_path": "t/t0069-oidtree.sh"
    }
  ]
}