patch, 2 partssha1_name: try to use same abbrev length when core.abbrevguard is specified

If find_unique_abbrev() finds a ambiguous SHA1 name, it tries to find again with increased length. In this case, result hex strings could have different lengths even though the core.abbrevguard config option is specified. But if the option is specified and increased length (delta) is less than its value, the result could be adjusted to the same length.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 sha1_name.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

-u/--unique option will find and use minimum length of unique SHA-1 name. If -l option is specified also, it will have higher priority, IOW git blame will use full 40-length SHA-1 name.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 builtin/blame.c |   18 +++++++++++++++++-
 1 files changed, 17 insertions(+), 1 deletions(-)

Namhyung Kim <namhyung@gmail.com> writes:

The logic to determine and keep track of the longuest-unique looks correct, but I was hoping that we already have an easy optimization codepath to do this only once per commit, not for every blame-entry in the result. Doesn't the code have a similar optimization to figure out the necessary number of columns to show author names (I haven't read the code recently, though)?

Also we might find that the performance impact of doing this may be so miniscule that it is not worth wasting a short option name. If we were to use an option, I was actually hoping that the option would let the users specify a value different from the hardcoded 8 at the same time. E.g.

    git blame --abbrev=8 ;# current default with uniquefy applied
    git blame --abbrev=4 ;# equivalent to your "blame -u"

Can we have a benchmark of this feature in a largish and busy file in a project with a deep history?

2011-03-09 (수), 11:45 -0800, Junio C Hamano:

Right. METAINFO_SHOWN flag does that. I'll move the code under the block in next version.

Hmm... I thought about that too. But you mean that you only want --abbrev instead of -u, right?

My original intention was if user specified --abbrev explicitly, it should be honored regardless of the uniqueness. The guard will not be used in this situation because the user gave the exact length [s]he wants to see.

I gave it a try on a file in Linux kernel (with METAINFO_SHOWN optimization applied):

$ wc -l mm/page_alloc.c
5629 mm/page_alloc.c
$ git log --oneline mm/page_alloc.c | wc -l
566
$ perf record ../git/git blame -u mm/page_alloc.c > /dev/null
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.229 MB perf.data (~10014 samples) ]
$ perf report
# Events: 5K cycles
#
# Overhead  Command         Shared Object                         Symbol
# ........  .......  ....................  .............................
#
    21.11%      git  git                   [.] cmd_blame
    18.34%      git  git                   [.] get_origin
    18.32%      git  git                   [.] pass_blame
     3.99%      git  libz.so.1.2.3.3       [.] inflate
     3.14%      git  git                   [.] xdl_hash_record
     2.84%      git  libz.so.1.2.3.3       [.] inflate_table
     2.60%      git  libz.so.1.2.3.3       [.] inflate_fast
     2.23%      git  git                   [.] find_pack_entry_one
     1.84%      git  git                   [.] xdl_recmatch
     1.51%      git  libc-2.11.1.so        [.] memcpy
     1.49%      git  git                   [.] xdl_prepare_env
     1.36%      git  git                   [.] xdl_prepare_ctx
     1.13%      git  [kernel.kallsyms]     [k] __lock_acquire
     1.12%      git  git                   [.] xdi_diff
     1.09%      git  git                   [.] blame_chunk
     0.99%      git  libc-2.11.1.so        [.] _int_malloc
     0.79%      git  git                   [.] tree_entry_interesting
     0.77%      git  git                   [.] origin_decref
     0.67%      git  libz.so.1.2.3.3       [.] adler32
     0.42%      git  [kernel.kallsyms]     [k] sched_clock_local
     0.40%      git  git                   [.] decode_tree_entry
     0.38%      git  [kernel.kallsyms]     [k] clear_page_c
     0.35%      git  libc-2.11.1.so        [.] __GI___strncmp_ssse3
     0.32%      git  git                   [.] lookup_object
     0.31%      git  [kernel.kallsyms]     [k] lock_release
     0.29%      git  [kernel.kallsyms]     [k] hlock_class
     0.29%      git  [kernel.kallsyms]     [k] page_fault
     0.29%      git  git                   [.] patch_delta
     0.28%      git  [kernel.kallsyms]     [k] local_clock
     0.27%      git  [kernel.kallsyms]     [k] sched_clock
     0.25%      git  [kernel.kallsyms]     [k] delay_tsc
     0.25%      git  git                   [.] parse_commit_buffer
     0.25%      git  [kernel.kallsyms]     [k] look_up_lock_class
     0.23%      git  git                   [.] xdl_cha_alloc
     0.22%      git  libc-2.11.1.so        [.] _int_free
     0.22%      git  libc-2.11.1.so        [.] malloc_consolidate
     0.22%      git  [kernel.kallsyms]     [k] mark_lock
     0.21%      git  libc-2.11.1.so        [.] __malloc
     0.20%      git  git                   [.] nth_packed_object_offset

Looks like it doesn't have a performance impact IMHO. Hope this helps.

Thank you.

Namhyung Kim <namhyung@gmail.com> writes:

Yeah, if it can be shown that ensuring the uniqueness in addition to uniform length with negligible cost, I don't think there is any reason to have this as an option. So perhaps the minimum change would be to keep the current "8" as a hardwired constant to feed find-unique-abbrev with to find the longest unique prefix as your patch did and use that length when showing the output. Making "8" configurable would become a separate topic.

Hmm, like giving a ridiculously short --abbrev and forcing the output to be ambiguous yet hopefully they can be differenciated by other clues like author and date?

The reason I originally suggested to make the uniqueness an optional feature was primarily output performance, but that is linear with the number of lines in the file and is dwarfed by the history traversal cost, so it is a non-issue, so I then suggested that it doesn't need to be an option. But I think you may have a point--an option to decline uniqueness would also make sense, especially when you want a very short prefix that you know won't be unique and when you don't care about uniqueness.

As all the normal commands that use --abbrev would call f-u-a to ensure uniqueness, the current "cut at fixed length" behaviour is an oddball. It should become an optional behaviour.

The current behaviour, when we eventually have both options, would be:

	$ git blame --abbrev=8 --no-uniq $rev -- $path

and should be the default when neither --abbrev=$n nor --no-uniq is given for backward compatibility. Porcelains are _not_ supposed to be reading from blame output without giving it --porcelain option, but we know we cannot expect sanity from people who script around git.

When you want to give a very short width that wouldn't guarantee uniqueness, and you want to force that width, you would say:

	$ git blame --abbrev=4 --no-uniq $rev -- $path

Without --no-uniq, 

	$ git blame --abbrev=4 $rev -- $path

the command may use more hexdigits than 4 to ensure uniqueness, but all commit names are shown with the same width to ensure alignment as well.

I kind of like that. While I don't think "--no-uniq" is the best name for that option, I think --abbrev everywhere else implies uniqueness so it is not a good idea to require "-u" option for unique output and give ambiguous output without one. It would hurt consistency in the UI.

2011-03-10 (목), 01:43 -0800, Junio C Hamano:

OK. But I'm still wonder why the value is "8" instead of "7" (DEFAULT_ABBREV).

Right. But I'm not sure what the end result should be if the guard is set and/or --no-uniq is given. It might be related to the patch 1/2.

Say the unique length is 4 and the guard is 3. What do you expect from the following command?

	$ git blame --abbrev=5 -- $path
	$ git blame --abbrev=5 --no-uniq -- $path

I think it should be 8 and 5. But possible alternatives are (7, 5), (5, 5), (8, 8) and (7, 8).

Let me think of another example. In this case the unique length is 8, the guard is 4 and the commands are same.

I think it should be (9, 5). And corresponding alternatives are (12, 5), (8, 5), (12, 9) and (12, 9).

My logic can be described like:

	default output 	= max((c + g), u)
	no-uniq output 	= c

where 'l' is the caller-given length, 'g' is the guard length, and 'u' is the unique length.

Alternatives are:

(a)	default output = max((u + g), c)
	no-uniq output = c

(b)	default output = max(c, u)
	no-uniq output = c

(c)	default output = (c > u) ? (c + g) : (u + g)
	no-uniq output = c + g

(d)	default output = max((u + g), c)
	no-uniq output = c + g

Maybe we can make more combination if you want. What do you think?

How about "--fixed" ?

Thanks.

Namhyung Kim <namhyung@gmail.com> writes:

I am not sure if I can understand what problem you are trying to solve from the above description.

The function is given "len" from the caller to specify the minimum length of the output the caller expects (i.e. even if 4 hexdigits is enough to identify the given commit in a small project, the caller can say it wants to see at least 7 hexdigits). The loop without your patch finds the shortest prefix whose length is at least that given length that uniquely identifies the given object (or the shortest prefix that doesn't identify any existing object if the given sha1 does not exist in the repository). And then ensures the returned value is longer by the guard as an extra safety measure, so that later when the project grows, the disambiguation we find today has a better chance to survive.

With this patch, the loop decreases the length of the guard when "len" given by the caller is insufficient to ensure uniqueness, which does not sound right.

Suppose the given object has ambiguous other objects and you need 8 hexdigits at least to make it unique in today's history. The caller gives you len of 7, and the guard is set to 3.

With the original code, the loop starts with 7, finds that it is not long enough to disambiguate, increments and retries, finds that 8 is the shortest prefix, and then adds the guard and returns 11 hexdigits.

With your patch, the loop starts with 7 with extra set to 3, finds that 7 is not long enough and decrements extra to 2, finds that 8 is the shortest prefix, and then returns only 10 hexdigits.

Which feels like totally going against the reason why we added the guard.

What am I missing?

Junio C Hamano <gitster@pobox.com> writes:

I think what may be desirable is to honor the caller-supplied "len" a bit better. If an object is uniquely identifiable with only 4-hexdigit today, and if the caller gives 7 as len and the guard is set to 3, we return 10 hexdigits with the current code. We should instead return 7 hexdigits in such a case, as that is in line with the "use 3 extra to give the disambiguation we find today a better chance to survive".

Perhaps that was what you wanted to do, but I don't think that is what your code actually does.

Junio C Hamano <gitster@pobox.com> writes:

And here is an attempt to do so. I have to admit that I didn't give it too much thought, though, so please be careful when reviewing the logic.

-- >8 --
Subject: find_unique_abbrev(): honor caller-supplied "len" better

The caller of this function wants to ensure that the returned string is a unique abbreviation of the object name, and at least len characters long. When "len" is sufficiently short and we cannot ensure uniqueness with only "len" bytes, we returned minimally unique prefix (i.e. if you dropped the last character, there would be two or more objects that share that same prefix as their names in the repository).

An earlier change introduced core.abbrevguard configuration with a realization that a short prefix that is unique today may not stay unique forever, as new objects are added to the repository. When "len" is shorter than the length necessary to ensure uniqueness today, instead of returning a string that is only one character longer than the longest ambiguous prefix, we wanted to add that many extra characters to ensure uniqueness for longer time.

However, the code forgot that "len" may be sufficiently long. If an object is uniquely identifiable with only 4-hexdigit today, and if the caller gives 7 as len and the guard is set to 3, we returned 10 hexdigits, which was 3 characters longer than necessary. We should instead return 7 hexdigits in such a case, as that is in line with the original intention of using 3 extra hexdigits to give the disambiguation we find today a better chance to survive.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 sha1_name.c |   24 ++++++++++++++++++++++++
 1 files changed, 24 insertions(+), 0 deletions(-)

2011-03-10 (목), 01:19 -0800, Junio C Hamano:

What if the unique length is greater than or equal to the given length? For instance the unique length is 7 and the caller gives 7 and the guard is 3. What do you want to return, 7 or 10? How about the unique length of 8?

I think the meaning of the guard is somewhat vague. When this feature was considered in LKML at first, Linus just wanted to change the default length of commit abbreviation to 12 by making it user-configurable. [1] And this is the same situation what I tried to tell you in the previous email.

So I think it would be better to choose the output length using only caller-given length and the guard length if it guarantees the uniqueness today. It'll be simple, consistent and expected behavior IMHO.

Thanks.

Anyway, how about

	  if (len < MINIMUM_ABBREV)
		  len = MINIMUM_ABBREV;

2011-03-10 (목), 20:52 +0900, Namhyung Kim:

Oh, I missed the link. :)

[1] https://lkml.org/lkml/2010/10/28/264

Namhyung Kim <namhyung@gmail.com> writes:

Perhaps I didn't state it clearly enough.

Conceptually, f-u-a works in two stages. First find out what the shortest prefix that can be used to uniquely identify the given object _now_. Then make sure that the result it returns is at least "len" characters long. So if you code it naively, it would have looked like this:

	for (try = 0; try < 40; try++)
		if ("do first try characters name an object uniquely?")
			break; /* happy */
	if (try < len)
		return the first "len" characters;
	else
        	return the first "try" characters;

The original (before the abbrevguard patch) uses an obvious optimization to start the trial from "len" because it didn't matter if a prefix shorter than "len" is already unique---it will return "len" anyway.

The "guard" change was buggy. At the conceptual level, it should have changed the first phase of f-u-a, by dropping the "_now_" part. Given that we will be adding more and more objects, only one extra character to make things unique is not sufficient and having "guard" extra characters would keep the result unique hopefully a little longer. It should have done this:

	for (try = 0; try < 40; try++)
		if ("do first try characters name an object uniquely?")
			break; /* happy */
       +/* try has only one extra character to make it unique */
       +if (guard)
       +	try += (guard - 1); /* could be try += guard */
	if (try < len)
		return the first "len" characters;
	else
        	return the first "try" characters;

Back to your original question, if the object needs 7 characters (iow, its 6-character prefix is shared with another object) to make it unique, and if the caller gives you 7 as length, without guard, you would get 7 because you are saying 1 extra character is sufficiently unique by not setting the guard. If you set the guard to 3, you are saying that 1 extra character is not sufficient to guard it against future collisions and you want 3 extra instead, so you should be getting either 9 (if you define that "guard" overrides the default "1 more characters to make it minimally unique") or 10 (if you define that "guard" specifies how many extra characters to use to make it safer).

If the object needs 8 characters to make it minimally unique and you give 7 as "len", you should never get a 7-character string back. f-u-a is not "truncate to 'len'" function but its primary job is to ensure uniqueness. Without guard, you should get 8 (minimally unique), and with guard set to 3, you should get either 10 or 11 (again, depending on the definition of "guard").

Linus's "Let's make the default 12 for our project by adding a way to customize it" merely states "right now we know 7 is not enough and 12 is plenty for some time, and likely to be enough to give the same length". It does not mean he suddenly start favoring uniform length over uniqueness. Uniqueness requirement is a given.

And that discussion is all about what "len" to be given when calling f-u-a; it doesn't have anything to do with what the guard is about.

Setting "len" to 12 would make sure your output you get today would have at least 12 characters, but it doesn't have any effect on how long an abbreviated unique object name will stay unique in the future.

When you give the name of an object you have today to somebody else by shortening it with f-u-a, you can ensure that the object name has a better chance of staying unique a bit longer by setting the guard to a non-zero value even if you use shorter "len".

The "len" and "guard" are different concepts, have different purposes, and implemented as two different variables, of course.

Sorry, but I see nothing consistent nor expected about what you are saying. Perhaps it is "expected" if you don't understand what the guard is about. It is about the future viability of the output you produce today.

If you don't care about uniqueness tomorrow, you won't even need any guard. You just give an interface to specify "len" and be done with it.

2011-03-09 (수), 11:12 -0800, Junio C Hamano: 

That's probably because of my poor English. :(

What I was thinking is like below (from a user's point of view):

I knew git use 7 hexdigit to represent a commit object and it was not enough for my project. So I gave it 5 for the guard and expected to see 12 in everywhere - if 12 always guarantees uniqueness for the project now and probably, the near future. But sometimes git prints 13 even though 12 is long enough to represent the commit uniquely. Because 7 is not enough but 8 is, and simply add 5 (the guard) to it.

So I thought it would be natural to print 12 always in this case and thus, submitted the patch.

Thanks.