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
