[0/5] optimizations for many odb alternates

Message

Eric Wong June 27, 2021, 2:47 a.m. UTC

Cc-ing Rene and Peff for their previous work on loose object
caching speedups (and also Peff on crit-bit trees).

I'm expecting a use case involving tens of thousands of
repos being tied together by alternates.  I realize this is
an odd case, but there's some fairly small changes that
give significant speedups and memory savings.

I can't seem to get consistent benchmarks on my workstation
(since it doubles as a public-facing server :x), but things
seem generally in the ballpark...

1/5 is a resend and the biggest obvious time improvement
(at some cost to space).

2/5 and 4/5 are pretty obvious; 3/5 should be obvious, too,
but my arithmetic is terrible :x

5/5 is a big (and easily measured) space improvement that
will negate space regression caused by 1/5 (and then some).
I'm not sure if there's much or any change in time in
either direction, though...

Eric Wong (5):
  speed up alt_odb_usable() with many alternates
  avoid strlen via strbuf_addstr in link_alt_odb_entry
  make object_directory.loose_objects_subdir_seen a bitmap
  oidcpy_with_padding: constify `src' arg
  oidtree: a crit-bit tree for odb_loose_cache

 Makefile                |   3 +
 alloc.c                 |   6 ++
 alloc.h                 |   1 +
 cbtree.c                | 167 ++++++++++++++++++++++++++++++++++++++++
 cbtree.h                |  56 ++++++++++++++
 hash.h                  |   2 +-
 object-file.c           |  68 +++++++++-------
 object-name.c           |  28 +++----
 object-store.h          |  24 +++++-
 object.c                |   2 +
 oidtree.c               |  94 ++++++++++++++++++++++
 oidtree.h               |  29 +++++++
 t/helper/test-oidtree.c |  45 +++++++++++
 t/helper/test-tool.c    |   1 +
 t/helper/test-tool.h    |   1 +
 t/t0069-oidtree.sh      |  52 +++++++++++++
 16 files changed, 530 insertions(+), 49 deletions(-)
 create mode 100644 cbtree.c
 create mode 100644 cbtree.h
 create mode 100644 oidtree.c
 create mode 100644 oidtree.h
 create mode 100644 t/helper/test-oidtree.c
 create mode 100755 t/t0069-oidtree.sh