optimizations for many alternates
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v3 Latest5 patches 4 repliesIn review
- v25 patches 13 repliesSuperseded
- v15 patches 4 repliesSuperseded
Patches in v3 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/5 | speed up alt_odb_usable() with many alternatesdir.c dir.h object-file.c +2 more | +42 | 3 replies | |
| 2/5 | avoid strlen via strbuf_addstr in link_alt_odb_entryobject-file.c | +4 | 1 reply | |
| 3/5 | make object_directory.loose_objects_subdir_seen a bitmapobject-file.c object-store.h | +9 | 0 replies | |
| 4/5 | oidcpy_with_padding: constify `src' arghash.h | +1 | 0 replies | |
| 5/5 | oidtree: a crit-bit tree for odb_loose_cacheMakefile cbtree.c cbtree.h +9 more | +478 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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 '