Hash tags by commit SHA1 in git-describe.
A message that is not in the archive (sent off-list or not yet received): 8e29bab8b4b9f53cbdc85e6e783bf3b5d3787f0f.1168727248.git.spearce@spearce.org
PATCH 2/4 Hash tags by commit SHA1 in git-describe.
If a project has a very large number of tags then git-describe will spend a good part of its time looping over the tags testing them one at a time to determine if it matches a given commit. For 10 tags this is not a big deal, but for hundreds of tags the time could become considerable if we don't find an exact match for the input commit and we need to walk back along the history chain.
--- builtin-describe.c | 29 +++++++++++++++++------------ 1 files changed, 17 insertions(+), 12 deletions(-)
builtin-describe.c +17 -12
@@ -12,20 +12,20 @@ static const char describe_usage[] =static int all;/* Default to annotated tags only */ static int tags;/* But allow any tags if --tags is specified */ -static int abbrev =DEFAULT_ABBREV ; -static int names, allocs; +static unsigned int names[256 ], allocs[256 ];static struct commit_name {struct commit *commit;int prio;/* annotated tag = 2, tag = 1, head = 0 */ char path[FLEX_ARRAY ];/* more */ -} **name_array =NULL ; +} **name_array[256 ];static struct commit_name *match (struct commit *cmit) { -int i = names; -struct commit_name **p = name_array; +unsigned char m = cmit->object.sha1[0 ]; +unsigned int i = names[m]; +struct commit_name **p = name_array[m];while (i-- >0 ) {struct commit_name *n = *p++;
@@ -42,17 +42,19 @@ static void add_to_known_names(const char *path,int idx;int len =strlen (path)+1 ;struct commit_name *name =xmalloc (sizeof (struct commit_name ) + len); +unsigned char m = commit->object.sha1[0 ]; name->commit = commit; name->prio = prio;memcpy (name->path, path, len); - idx = names; -if (idx >= allocs) { - allocs = (idx +50 ) *3 /2 ; - name_array =xrealloc (name_array, allocs*sizeof (*name_array)); + idx = names[m]; +if (idx >= allocs[m]) { + allocs[m] = (idx +50 ) *3 /2 ; + name_array[m] =xrealloc (name_array[m], + allocs[m] *sizeof (*name_array)); } - name_array[idx] = name; - names = ++idx; + name_array[m][idx] = name; + names[m] = ++idx; }static int get_name (const char *path,const unsigned char *sha1,int flag,void *cb_data)
@@ -121,9 +123,12 @@ static void describe(const char *arg, int last_one)die ("%s is not a valid '%s' object" , arg, commit_type);if (!initialized) { +unsigned int m; initialized =1 ;for_each_ref (get_name,NULL ); -qsort (name_array, names,sizeof (*name_array), compare_names); +for (m =0 ; m <ARRAY_SIZE (name_array); m++) +qsort (name_array[m], names[m], +sizeof (*name_array[m]), compare_names); } n =match (cmit);
Signature · 1 line
1.5.0.rc1.g4494
Hi,
Quoted 3 lines · Shawn O. Pearce
If a project has a very large number of tags then git-describe will spend a good part of its time looping over the tags testing them one at a time to determine if it matches a given commit.
Why not just use object_refs? This also obviates the need for your patch 3/4, since you no longer have buckets to search binarily. Plus, it uses a hash map, which already turned out to beat (in terms of performance) the hell out of bucketed lists in git history.
Ciao,
Dscho
Quoted 10 lines · Johannes Schindelin
Quoted 3 lines · Shawn O. Pearce
If a project has a very large number of tags then git-describe will spend a good part of its time looping over the tags testing them one at a time to determine if it matches a given commit.
Why not just use
object_refs? This also obviates the need for your patch 3/4, since you no longer have buckets to search binarily. Plus, it uses a hash map, which already turned out to beat (in terms of performance) the hell out of bucketed lists in git history.
Very good point.
Quoted 8 lines · Junio C Hamano
Quoted 6 lines · Johannes Schindelin
Quoted 3 lines · Shawn O. Pearce
If a project has a very large number of tags then git-describe will spend a good part of its time looping over the tags testing them one at a time to determine if it matches a given commit.
Quoted 6 lines
Quoted 4 lines
Why not just use
object_refs? This also obviates the need for your patch 3/4, since you no longer have buckets to search binarily. Plus, it uses a hash map, which already turned out to beat (in terms of performance) the hell out of bucketed lists in git history.Very good point.
OK. I didn't realize we had a better system already implemented. Thanks for pointing it out.
I'll work up a patch to replace the crude hash/list arrangement with something based on object_refs instead.
Signature · 1 line
Shawn.
PATCH 3/4 Use binary searching on large buckets in git-describe.
In reply to a message not in the archiveIf a project has a really huge number of tags (such as several thousand tags) then we are likely to have nearly a hundred tags in some buckets. Scanning those buckets as linked lists could take a large amount of time if done repeatedly during history traversal.
Since we are searching for a unique commit SHA1 we can sort all tags by commit SHA1 and perform a binary search within the bucket. Once we identify a particular tag as matching this commit we walk backwards within the bucket matches to make sure we pick up the highest priority tag for that commit, as the binary search may have landed us in the middle of a set of tags which point at the same commit.
--- builtin-describe.c | 29 +++++++++++++++++++++-------- 1 files changed, 21 insertions(+), 8 deletions(-)
builtin-describe.c +21 -8
@@ -23,14 +23,24 @@ static struct commit_name {static struct commit_name *match (struct commit *cmit) { -unsigned char m = cmit->object.sha1[0 ]; -unsigned int i = names[m]; -struct commit_name **p = name_array[m]; - -while (i-- >0 ) { -struct commit_name *n = *p++; -if (n->commit == cmit) -return n; +unsigned char level0 = cmit->object.sha1[0 ]; +struct commit_name **p = name_array[level0]; +unsigned int hi = names[level0]; +unsigned int lo =0 ; + +while (lo < hi) { +unsigned int mi = (lo + hi) /2 ; +int cmp =hashcmp (p[mi]->commit->object.sha1, + cmit->object.sha1); +if (!cmp) { +while (mi && p[mi -1 ]->commit == cmit) + mi--; +return p[mi]; + } +if (cmp >0 ) + hi = mi; +else + lo = mi+1 ; }return NULL ; }
@@ -95,7 +105,10 @@ static int compare_names(const void *_a, const void *_b)struct commit_name *b = *(struct commit_name **)_b;unsigned long a_date = a->commit->date;unsigned long b_date = b->commit->date; +int cmp =hashcmp (a->commit->object.sha1, b->commit->object.sha1); +if (cmp) +return cmp;if (a->prio != b->prio)return b->prio - a->prio;return (a_date > b_date) ?-1 : (a_date == b_date) ?0 :1 ;
Signature · 1 line
1.5.0.rc1.g4494
Re: [PATCH 3/4] Use binary searching on large buckets in git-describe.
Quoted 4 lines · Shawn O. Pearce
If a project has a really huge number of tags (such as several thousand tags) then we are likely to have nearly a hundred tags in some buckets. Scanning those buckets as linked lists could take a large amount of time if done repeatedly during history traversal.
I think this is a good idea -- but would you still need the 256 buckets if you do this?
Re: [PATCH 3/4] Use binary searching on large buckets in git-describe.
Quoted 9 lines · Junio C Hamano
Quoted 4 lines · Shawn O. Pearce
If a project has a really huge number of tags (such as several thousand tags) then we are likely to have nearly a hundred tags in some buckets. Scanning those buckets as linked lists could take a large amount of time if done repeatedly during history traversal.
I think this is a good idea -- but would you still need the 256 buckets if you do this?
Well, yes and no. The binary search would make it O(log N) rather than O(N), which is clearly an improvement. But we're hashing by the commit SHA1 and since SHA1 does such a good job of distributing values around we get pretty even distribution among the buckets. This gets us a 1/256 reduction within each bucket, at the cost of just one array index operation.
Since the buckets are so small (1 pointer) and the match function is in the critical path of describe it would seem reasonable to take the small memory hit in return for better behavior on very large sets of tags. It certainly doesn't hurt on smaller tag sets (like git.git), we wind up with 1 tag per bucket and our lookups are constant time.
Signature · 1 line
Shawn.
PATCH 4/4 Improve git-describe performance by reducing revision listing.
In reply to a message not in the archiveMy prior version of git-describe ran very slowly on even reasonably sized projects like git.git and linux.git as it tended to identify a large number of possible tags and then needed to generate the revision list for each of those tags to sort them and select the best tag to describe the input commit.
All we really need is the number of commits in the input revision which are not in the tag. We can generate these counts during the revision walking and tag matching loop by assigning a color to each tag and coloring the commits as we walk them. This limits us to identifying no more than 26 possible tags, as there is limited space available within the flags field of struct commit.
The limitation of 26 possible tags is hopefully not going to be a problem in real usage, as most projects won't create 26 maintenance releases and merge them back into a development trunk after the development trunk was tagged with a release candidate tag. If that does occur git-describe will start to revert to its old behavior of using the newer maintenance release tag to describe the development trunk, rather than the development trunk's own tag. The suggested workaround would be to retag the development trunk's tip.
However since even 26 possible tags can take a while to generate a description for on some projects I'm defaulting the limit to 10 but offering the user --candidates to increase the number of possible matches if they need a more accurate result. I specifically chose 10 for the default as it seems unlikely projects will have more than 10 maintenance releases merged into a development trunk before retagging the development trunk, and it seems to perform about the same on linux.git as v1.4.4.4 git-describe.
A large amount of debugging information was also added during the development of this change, so I've left it in to be toggled on with --debug. It may be useful to the end user to help them understand why git-describe took one particular tag over another.
---
Quoted 4 lines · Junio C Hamano
This actually is QUITE bad.
With the tip of linux-2.6 repository, v1.4.4 series takes 0.03s while v1.5.0-rc1 takes about 3.6s. That is 100x fold, not just 4x.
This should restore git-describe to taking 0.03s on your system, yet get us 10 tag accuracy. It is running close to even with 1.4.4.4's git-describe on my system.
Documentation/git-describe.txt | 30 ++++++++++ builtin-describe.c | 125 ++++++++++++++++++++++++---------------- 2 files changed, 106 insertions(+), 49 deletions(-)
Documentation/git-describe.txt +30 -0
@@ -35,6 +35,16 @@ OPTIONS Instead of using the default 8 hexadecimal digits as the abbreviated object name, use <n> digits. +--candidates=<n>:: + Instead of considering only the 10 most recent tags as + candidates to describe the input committish consider + up to <n> candidates. Increasing <n> above 10 will take + slightly longer but may produce a more accurate result. + +--debug:: + Verbosely display information about the searching strategy + being employed to standard error. The tag name will still + be printed to standard out. EXAMPLES --------
@@ -63,6 +73,26 @@ the output shows the reference path as well: [torvalds@g5 git]$ git describe --all HEAD^ heads/lt/describe-g975b +SEARCH STRATEGY +--------------- + +For each committish supplied "git describe" will first look for +a tag which tags exactly that commit. Annotated tags will always +be preferred over lightweight tags, and tags with newer dates will +always be preferred over tags with older dates. If an exact match +is found, its name will be output and searching will stop. + +If an exact match was not found "git describe" will walk back +through the commit history to locate an ancestor commit which +has been tagged. The ancestor's tag will be output along with an +abbreviation of the input committish's SHA1. + +If multiple tags were found during the walk then the tag which +has the fewest commits different from the input committish will be +selected and output. Here fewest commits different is defined as +the number of commits which would be shown by "git log tag..input" +will be the smallest number of commits possible. + Author ------
builtin-describe.c +76 -49
195 lines not on this page · raw message
Signature · 1 line
1.5.0.rc1.g4494