From 56a5f3afa74c70261dd2319ad76a6810e102026c Mon Sep 17 00:00:00 2001 From: Anders Kaseorg Date: Thu, 9 Dec 2010 01:42:25 -0500 Subject: describe: Use for_each_rawref Don't waste time checking for dangling refs; they wouldn't affect the output of 'git describe' anyway. Although this does not gain much performance by itself, it does in conjunction with the next commits. Signed-off-by: Anders Kaseorg Signed-off-by: Junio C Hamano --- builtin/describe.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/builtin/describe.c b/builtin/describe.c index 43caff2ffe..700f740154 100644 --- a/builtin/describe.c +++ b/builtin/describe.c @@ -418,7 +418,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix) return cmd_name_rev(i + argc, args, prefix); } - for_each_ref(get_name, NULL); + for_each_rawref(get_name, NULL); if (!found_names && !always) die("No names found, cannot describe anything."); -- cgit v1.2.3 From 1e1ade1833db42a75f2792b4472748721f73c827 Mon Sep 17 00:00:00 2001 From: Anders Kaseorg Date: Thu, 9 Dec 2010 01:43:32 -0500 Subject: describe: Do not use a flex array in struct commit_name Now add_to_known_names overwrites commit_names in place when multiple tags point to the same commit. This will make it easier to store commit_names in a hash table. Signed-off-by: Anders Kaseorg Signed-off-by: Junio C Hamano --- builtin/describe.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/builtin/describe.c b/builtin/describe.c index 700f740154..5b8461d87f 100644 --- a/builtin/describe.c +++ b/builtin/describe.c @@ -38,7 +38,7 @@ struct commit_name { unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */ unsigned name_checked:1; unsigned char sha1[20]; - char path[FLEX_ARRAY]; /* more */ + const char *path; }; static const char *prio_names[] = { "head", "lightweight", "annotated", @@ -85,15 +85,15 @@ static void add_to_known_names(const char *path, struct commit_name *e = commit->util; struct tag *tag = NULL; if (replace_name(e, prio, sha1, &tag)) { - size_t len = strlen(path)+1; - free(e); - e = xmalloc(sizeof(struct commit_name) + len); + if (!e) { + e = xmalloc(sizeof(struct commit_name)); + commit->util = e; + } e->tag = tag; e->prio = prio; e->name_checked = 0; hashcpy(e->sha1, sha1); - memcpy(e->path, path, len); - commit->util = e; + e->path = path; } found_names = 1; } -- cgit v1.2.3 From 3cfa4db3226ccef8845589029090d9398b207ba3 Mon Sep 17 00:00:00 2001 From: Anders Kaseorg Date: Thu, 9 Dec 2010 01:46:08 -0500 Subject: describe: Store commit_names in a hash table by commit SHA1 describe is currently forced to look up the commit at each tag in order to store the struct commit_name pointers in struct commit.util. For --exact-match queries, those lookups are wasteful. In preparation for removing them, put the commit_names into a hash table, indexed by commit SHA1, that can be used to quickly check for exact matches. Signed-off-by: Anders Kaseorg Signed-off-by: Junio C Hamano --- builtin/describe.c | 38 +++++++++++++++++++++++++++++++++----- 1 file changed, 33 insertions(+), 5 deletions(-) diff --git a/builtin/describe.c b/builtin/describe.c index 5b8461d87f..8149233059 100644 --- a/builtin/describe.c +++ b/builtin/describe.c @@ -6,6 +6,7 @@ #include "exec_cmd.h" #include "parse-options.h" #include "diff.h" +#include "hash.h" #define SEEN (1u<<0) #define MAX_TAGS (FLAG_BITS - 1) @@ -22,7 +23,7 @@ static int tags; /* Allow lightweight tags */ static int longformat; static int abbrev = DEFAULT_ABBREV; static int max_candidates = 10; -static int found_names; +static struct hash_table names; static const char *pattern; static int always; static const char *dirty; @@ -34,6 +35,8 @@ static const char *diff_index_args[] = { struct commit_name { + struct commit_name *next; + unsigned char peeled[20]; struct tag *tag; unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */ unsigned name_checked:1; @@ -44,6 +47,21 @@ static const char *prio_names[] = { "head", "lightweight", "annotated", }; +static inline unsigned int hash_sha1(const unsigned char *sha1) +{ + unsigned int hash; + memcpy(&hash, sha1, sizeof(hash)); + return hash; +} + +static inline struct commit_name *find_commit_name(const unsigned char *peeled) +{ + struct commit_name *n = lookup_hash(hash_sha1(peeled), &names); + while (n && !!hashcmp(peeled, n->peeled)) + n = n->next; + return n; +} + static int replace_name(struct commit_name *e, int prio, const unsigned char *sha1, @@ -82,12 +100,22 @@ static void add_to_known_names(const char *path, int prio, const unsigned char *sha1) { - struct commit_name *e = commit->util; + const unsigned char *peeled = commit->object.sha1; + struct commit_name *e = find_commit_name(peeled); struct tag *tag = NULL; if (replace_name(e, prio, sha1, &tag)) { if (!e) { + void **pos; e = xmalloc(sizeof(struct commit_name)); commit->util = e; + hashcpy(e->peeled, peeled); + pos = insert_hash(hash_sha1(peeled), e, &names); + if (pos) { + e->next = *pos; + *pos = e; + } else { + e->next = NULL; + } } e->tag = tag; e->prio = prio; @@ -95,7 +123,6 @@ static void add_to_known_names(const char *path, hashcpy(e->sha1, sha1); e->path = path; } - found_names = 1; } static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data) @@ -240,7 +267,7 @@ static void describe(const char *arg, int last_one) if (!cmit) die("%s is not a valid '%s' object", arg, commit_type); - n = cmit->util; + n = find_commit_name(cmit->object.sha1); if (n && (tags || all || n->prio == 2)) { /* * Exact match to an existing ref. @@ -418,8 +445,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix) return cmd_name_rev(i + argc, args, prefix); } + init_hash(&names); for_each_rawref(get_name, NULL); - if (!found_names && !always) + if (!names.nr && !always) die("No names found, cannot describe anything."); if (argc == 0) { -- cgit v1.2.3 From d1645d02defe43fa5b43140050ba265fcc49fa70 Mon Sep 17 00:00:00 2001 From: Anders Kaseorg Date: Thu, 9 Dec 2010 01:47:29 -0500 Subject: describe: Delay looking up commits until searching for an inexact match Now that struct commit.util is not used until after we've checked that the argument doesn't exactly match a tag, we can wait until then to look up the commits for each tag. This avoids a lot of I/O on --exact-match queries in repositories with many tags. For example, 'git describe --exact-match HEAD' becomes about 12 times faster on a cold cache (3.2s instead of 39s) in a linux-2.6 repository with 2000 packed tags. That is a huge win for the interactivity of the __git_ps1 shell prompt helper when on a detached HEAD. Signed-off-by: Anders Kaseorg Signed-off-by: Junio C Hamano --- builtin/describe.c | 37 ++++++++++++++++++++++--------------- 1 file changed, 22 insertions(+), 15 deletions(-) diff --git a/builtin/describe.c b/builtin/describe.c index 8149233059..a0f52c1b72 100644 --- a/builtin/describe.c +++ b/builtin/describe.c @@ -24,6 +24,7 @@ static int longformat; static int abbrev = DEFAULT_ABBREV; static int max_candidates = 10; static struct hash_table names; +static int have_util; static const char *pattern; static int always; static const char *dirty; @@ -62,6 +63,17 @@ static inline struct commit_name *find_commit_name(const unsigned char *peeled) return n; } +static int set_util(void *chain) +{ + struct commit_name *n; + for (n = chain; n; n = n->next) { + struct commit *c = lookup_commit_reference_gently(n->peeled, 1); + if (c) + c->util = n; + } + return 0; +} + static int replace_name(struct commit_name *e, int prio, const unsigned char *sha1, @@ -96,18 +108,16 @@ static int replace_name(struct commit_name *e, } static void add_to_known_names(const char *path, - struct commit *commit, + const unsigned char *peeled, int prio, const unsigned char *sha1) { - const unsigned char *peeled = commit->object.sha1; struct commit_name *e = find_commit_name(peeled); struct tag *tag = NULL; if (replace_name(e, prio, sha1, &tag)) { if (!e) { void **pos; e = xmalloc(sizeof(struct commit_name)); - commit->util = e; hashcpy(e->peeled, peeled); pos = insert_hash(hash_sha1(peeled), e, &names); if (pos) { @@ -128,8 +138,6 @@ static void add_to_known_names(const char *path, static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data) { int might_be_tag = !prefixcmp(path, "refs/tags/"); - struct commit *commit; - struct object *object; unsigned char peeled[20]; int is_tag, prio; @@ -137,16 +145,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void return 0; if (!peel_ref(path, peeled) && !is_null_sha1(peeled)) { - commit = lookup_commit_reference_gently(peeled, 1); - if (!commit) - return 0; - is_tag = !!hashcmp(sha1, commit->object.sha1); + is_tag = !!hashcmp(sha1, peeled); } else { - commit = lookup_commit_reference_gently(sha1, 1); - object = parse_object(sha1); - if (!commit || !object) - return 0; - is_tag = object->type == OBJ_TAG; + hashcpy(peeled, sha1); + is_tag = 0; } /* If --all, then any refs are used. @@ -169,7 +171,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void if (!prio) return 0; } - add_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1); + add_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1); return 0; } @@ -286,6 +288,11 @@ static void describe(const char *arg, int last_one) if (debug) fprintf(stderr, "searching to describe %s\n", arg); + if (!have_util) { + for_each_hash(&names, set_util); + have_util = 1; + } + list = NULL; cmit->object.flags = SEEN; commit_list_insert(cmit, &list); -- cgit v1.2.3