Skip to content

optimizations for many alternates

Eric Wong git 3 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest5 patches 4 repliesIn review
  2. v25 patches 13 repliesSuperseded
  3. v15 patches 4 repliesSuperseded

Patches in v3 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/5speed up alt_odb_usable() with many alternatesdir.c dir.h object-file.c +2 more+42 -123 replies
2/5avoid strlen via strbuf_addstr in link_alt_odb_entryobject-file.c+4 -41 reply
3/5make object_directory.loose_objects_subdir_seen a bitmapobject-file.c object-store.h+9 -40 replies
4/5oidcpy_with_padding: constify `src' arghash.h+1 -10 replies
5/5oidtree: a crit-bit tree for odb_loose_cacheMakefile cbtree.c cbtree.h +9 more+478 -300 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.

Read the v3 thread

Cover letter [PATCH v3 0/5] optimizations for many alternates

Implemented suggestions from Ævar and René, noticed a few more things that's probably worth exploring at some point...

TODO items unrelated to this series (probably for somebody else):

* try fspatheq and fspathhash in more places in hopes it can reduce binary + icache size

* favor ${#var} (instead of "wc -c" as as suggested by Ævar) to reduce fork+execve overhead in tests. We already use ${#var} in t/test-lib-functions.sh, and it works in shells I've tried (dash, posh, ksh93, bash --posix)

* reduce internal redundancies (hash functions, hash table and memory pool implementations, etc.)

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 +
 cbtree.c                | 167 ++++++++++++++++++++++++++++++++++++++++
 cbtree.h                |  56 ++++++++++++++
 dir.c                   |  10 +++
 dir.h                   |   2 +
 hash.h                  |   2 +-
 object-file.c           |  75 ++++++++++--------
 object-name.c           |  28 +++----
 object-store.h          |  14 +++-
 object.c                |   2 +
 oidtree.c               | 104 +++++++++++++++++++++++++
 oidtree.h               |  22 ++++++
 t/helper/test-oidtree.c |  49 ++++++++++++
 t/helper/test-tool.c    |   1 +
 t/helper/test-tool.h    |   1 +
 t/t0069-oidtree.sh      |  49 ++++++++++++
 16 files changed, 534 insertions(+), 51 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

Interdiff against v2:

alloc.c +0 -6
index ca1e178c5a..957a0af362 100644
@@ -14,7 +14,6 @@
 #include "tree.h"
 #include "commit.h"
 #include "tag.h"
-#include "oidtree.h"
 #include "alloc.h"
 
 #define BLOCKING 1024
@@ -124,11 +123,6 @@ void *alloc_commit_node(struct repository *r)
 	return c;
 }
 
-void *alloc_from_state(struct alloc_state *alloc_state, size_t n)
-{
-	return alloc_node(alloc_state, n);
-}
-
 static void report(const char *name, unsigned int count, size_t size)
 {
 	fprintf(stderr, "%10s: %8u (%"PRIuMAX" kB)\n",
alloc.h +0 -1
index 4032375aa1..371d388b55 100644
@@ -13,7 +13,6 @@ void init_commit_node(struct commit *c);
 void *alloc_commit_node(struct repository *r);
 void *alloc_tag_node(struct repository *r);
 void *alloc_object_node(struct repository *r);
-void *alloc_from_state(struct alloc_state *, size_t n);
 void alloc_report(struct repository *r);
 
 struct alloc_state *allocate_alloc_state(void);
dir.c +10 -0
index ebe5ec046e..20b942d161 100644
@@ -84,11 +84,21 @@ int fspathcmp(const char *a, const char *b)
 	return ignore_case ? strcasecmp(a, b) : strcmp(a, b);
 }
 
+int fspatheq(const char *a, const char *b)
+{
+	return !fspathcmp(a, b);
+}
+
 int fspathncmp(const char *a, const char *b, size_t count)
 {
 	return ignore_case ? strncasecmp(a, b, count) : strncmp(a, b, count);
 }
 
+unsigned int fspathhash(const char *str)
+{
+	return ignore_case ? strihash(str) : strhash(str);
+}
+
 int git_fnmatch(const struct pathspec_item *item,
 		const char *pattern, const char *string,
 		int prefix)
dir.h +2 -0
index e3db9b9ec6..2af7bcd7e5 100644
@@ -489,7 +489,9 @@ int remove_dir_recursively(struct strbuf *path, int flag);
 int remove_path(const char *path);
 
 int fspathcmp(const char *a, const char *b);
+int fspatheq(const char *a, const char *b);
 int fspathncmp(const char *a, const char *b, size_t count);
+unsigned int fspathhash(const char *str);
 
 /*
  * The prefix part of pattern must not contains wildcards.
object-file.c +10 -8
index 6c397fb4f1..35f3e7e9bb 100644
@@ -539,14 +539,12 @@ static int alt_odb_usable(struct raw_object_store *o,
 		o->odb_by_path = kh_init_odb_path_map();
 		assert(!o->odb->next);
 		p = kh_put_odb_path_map(o->odb_by_path, o->odb->path, &r);
-		if (r < 0) die_errno(_("kh_put_odb_path_map"));
 		assert(r == 1); /* never used */
 		kh_value(o->odb_by_path, p) = o->odb;
 	}
-	if (!fspathcmp(path->buf, normalized_objdir))
+	if (fspatheq(path->buf, normalized_objdir))
 		return 0;
 	*pos = kh_put_odb_path_map(o->odb_by_path, path->buf, &r);
-	if (r < 0) die_errno(_("kh_put_odb_path_map"));
 	/* r: 0 = exists, 1 = never used, 2 = deleted */
 	return r == 0 ? 0 : 1;
 }
@@ -2474,21 +2472,25 @@ struct oidtree *odb_loose_cache(struct object_directory *odb,
 
 	bitmap = &odb->loose_objects_subdir_seen[word_index];
 	if (*bitmap & mask)
-		return &odb->loose_objects_cache;
-
+		return odb->loose_objects_cache;
+	if (!odb->loose_objects_cache) {
+		ALLOC_ARRAY(odb->loose_objects_cache, 1);
+		oidtree_init(odb->loose_objects_cache);
+	}
 	strbuf_addstr(&buf, odb->path);
 	for_each_file_in_obj_subdir(subdir_nr, &buf,
 				    append_loose_object,
 				    NULL, NULL,
-				    &odb->loose_objects_cache);
+				    odb->loose_objects_cache);
 	*bitmap |= mask;
 	strbuf_release(&buf);
-	return &odb->loose_objects_cache;
+	return odb->loose_objects_cache;
 }
 
 void odb_clear_loose_cache(struct object_directory *odb)
 {
-	oidtree_destroy(&odb->loose_objects_cache);
+	oidtree_clear(odb->loose_objects_cache);
+	FREE_AND_NULL(odb->loose_objects_cache);
 	memset(&odb->loose_objects_subdir_seen, 0,
 	       sizeof(odb->loose_objects_subdir_seen));
 }
object-store.h +2 -12
index b507108d18..e679acc4c3 100644
@@ -24,7 +24,7 @@ struct object_directory {
 	 * Be sure to call odb_load_loose_cache() before using.
 	 */
 	uint32_t loose_objects_subdir_seen[8]; /* 256 bits */
-	struct oidtree loose_objects_cache;
+	struct oidtree *loose_objects_cache;
 
 	/*
 	 * Path to the alternative object store. If this is a relative path,
@@ -33,18 +33,8 @@ struct object_directory {
 	char *path;
 };
 
-static inline int odb_path_eq(const char *a, const char *b)
-{
-	return !fspathcmp(a, b);
-}
-
-static inline int odb_path_hash(const char *str)
-{
-	return ignore_case ? strihash(str) : __ac_X31_hash_string(str);
-}
-
 KHASH_INIT(odb_path_map, const char * /* key: odb_path */,
-	struct object_directory *, 1, odb_path_hash, odb_path_eq);
+	struct object_directory *, 1, fspathhash, fspatheq);
 
 void prepare_alt_odb(struct repository *r);
 char *compute_alternate_path(const char *path, struct strbuf *err);
oidtree.c +30 -20

93 lines not on this page · raw message

oidtree.h +7 -14
index 73399bb978..77898f510a 100644
@@ -3,27 +3,20 @@
 
 #include "cbtree.h"
 #include "hash.h"
+#include "mem-pool.h"
 
-struct alloc_state;
 struct oidtree {
-	struct cb_tree t;
-	struct alloc_state *mempool;
+	struct cb_tree tree;
+	struct mem_pool mem_pool;
 };
 
-#define OIDTREE_INIT { .t = CBTREE_INIT, .mempool = NULL }
-
-static inline void oidtree_init(struct oidtree *ot)
-{
-	cb_init(&ot->t);
-	ot->mempool = NULL;
-}
-
-void oidtree_destroy(struct oidtree *);
+void oidtree_init(struct oidtree *);
+void oidtree_clear(struct oidtree *);
 void oidtree_insert(struct oidtree *, const struct object_id *);
 int oidtree_contains(struct oidtree *, const struct object_id *);
 
-typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *arg);
+typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *data);
 void oidtree_each(struct oidtree *, const struct object_id *,
-			size_t oidhexlen, oidtree_iter, void *arg);
+			size_t oidhexsz, oidtree_iter, void *data);
 
 #endif /* OIDTREE_H */
t/helper/test-oidtree.c +7 -5
index e0da13eea3..180ee28dd9 100644
@@ -10,11 +10,12 @@ static enum cb_next print_oid(const struct object_id *oid, void *data)
 
 int cmd__oidtree(int argc, const char **argv)
 {
-	struct oidtree ot = OIDTREE_INIT;
+	struct oidtree ot;
 	struct strbuf line = STRBUF_INIT;
 	int nongit_ok;
 	int algo = GIT_HASH_UNKNOWN;
 
+	oidtree_init(&ot);
 	setup_git_directory_gently(&nongit_ok);
 
 	while (strbuf_getline(&line, stdin) != EOF) {
@@ -34,14 +35,15 @@ int cmd__oidtree(int argc, const char **argv)
 			char buf[GIT_MAX_HEXSZ + 1] = { '0' };
 			memset(&oid, 0, sizeof(oid));
 			memcpy(buf, arg, strlen(arg));
-			buf[hash_algos[algo].hexsz] = 0;
+			buf[hash_algos[algo].hexsz] = '\0';
 			get_oid_hex_any(buf, &oid);
 			oid.algo = algo;
 			oidtree_each(&ot, &oid, strlen(arg), print_oid, NULL);
-		} else if (!strcmp(line.buf, "destroy"))
-			oidtree_destroy(&ot);
-		else
+		} else if (!strcmp(line.buf, "clear")) {
+			oidtree_clear(&ot);
+		} else {
 			die("unknown command: %s", line.buf);
+		}
 	}
 	return 0;
 }
t/t0069-oidtree.sh +15 -18
index 0594f57c81..bfb1397d7b 100755
@@ -3,35 +3,32 @@
 test_description='basic tests for the oidtree implementation'
 . ./test-lib.sh
 
+maxhexsz=$(test_oid hexsz)
 echoid () {
 	prefix="${1:+$1 }"
 	shift
 	while test $# -gt 0
 	do
-		echo "$1"
+		shortoid="$1"
 		shift
-	done | awk -v prefix="$prefix" -v ZERO_OID=$ZERO_OID '{
-		printf("%s%s", prefix, $0);
-		need = length(ZERO_OID) - length($0);
-		for (i = 0; i < need; i++)
-			printf("0");
-		printf "\n";
-	}'
+		difference=$(($maxhexsz - ${#shortoid}))
+		printf "%s%s%0${difference}d\\n" "$prefix" "$shortoid" "0"
+	done
 }
 
 test_expect_success 'oidtree insert and contains' '
-	cat >expect <<EOF &&
-0
-0
-0
-1
-1
-0
-EOF
+	cat >expect <<-\EOF &&
+		0
+		0
+		0
+		1
+		1
+		0
+	EOF
 	{
 		echoid insert 444 1 2 3 4 5 a b c d e &&
 		echoid contains 44 441 440 444 4440 4444
-		echo destroy
+		echo clear
 	} | test-tool oidtree >actual &&
 	test_cmp expect actual
 '
@@ -44,7 +41,7 @@ test_expect_success 'oidtree each' '
 		echo each 3211
 		echo each 3210
 		echo each 32100
-		echo destroy
+		echo clear
 	} | test-tool oidtree >actual &&
 	test_cmp expect actual
 '