Improve abbreviation disambiguation
v2 cover Improve abbreviation disambiguation
Thanks for the feedback on my v1 patch. Thanks also to Jeff Hostetler for helping me with this v2 patch, which includes an extra performance improvement in commit 5.
Changes since last version:
* Added helper program test-list-objects to construct a list of existing object ids.
* test-abbrev now disambiguates a list of OIDs from stdin.
* p0008-abbrev.sh now has two tests:
* 0008.1 tests 100,000 known OIDs
* 0008.2 tests 100,000 missing OIDs
* Added a third performance improvement that uses binary search within packfiles to inspect at most two object ids per packfile.
Thanks,
Stolee
---
When displaying object ids, we frequently want to see an abbreviation for easier typing. That abbreviation must be unambiguous among all object ids.
The current implementation of find_unique_abbrev() performs a loop checking if each abbreviation length is unambiguous until finding one that works. This causes multiple round-trips to the disk when starting with the default abbreviation length (usually 7) but needing up to 12 characters for an unambiguous short-sha. For very large repos, this effect is pronounced and causes issues with several commands, from obvious consumers status and log to less obvious commands such as fetch and push.
This patch improves performance by iterating over objects matching the short abbreviation only once, inspecting each object id, and reporting the minimum length of an unambiguous abbreviation.
A helper program test-list-objects outputs a sampling of object ids, which we reorder using sort -R before using them as input to a performance test.
A performance helper test-abbrev and performance test p0008-abbrev.sh are added to demonstrate performance improvements in this area.
I include performance test numbers in the commit messages for each change, but I also include the difference between the baseline and the final change here:
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.12 s | 0.05 s | -58.3% | | Git | 5 | 230162 | 0 | 0.25 s | 0.15 s | -40.0% | | Git | 4 | 154310 | 75852 | 0.18 s | 0.11 s | -38.9% | | Linux | 1 | 5606645 | 0 | 0.32 s | 0.10 s | -68.8% | | Linux | 24 | 5606645 | 0 | 2.77 s | 2.00 s | -27.8% | | Linux | 23 | 5283204 | 323441 | 2.86 s | 1.62 s | -43.4% | | VSTS | 1 | 4355923 | 0 | 0.27 s | 0.09 s | -66.7% | | VSTS | 32 | 4355923 | 0 | 2.41 s | 2.01 s | -16.6% | | VSTS | 31 | 4276829 | 79094 | 4.22 s | 3.02 s | -28.4% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 5.69 s
New Time: 4.09 s
Rel %: -28.1%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.61 s | 0.04 s | -93.4% | | Git | 5 | 230162 | 0 | 1.30 s | 0.15 s | -88.5% | | Git | 4 | 154310 | 75852 | 1.07 s | 0.12 s | -88.8% | | Linux | 1 | 5606645 | 0 | 0.65 s | 0.05 s | -92.3% | | Linux | 24 | 5606645 | 0 | 7.12 s | 1.28 s | -82.0% | | Linux | 23 | 5283204 | 323441 | 6.33 s | 0.96 s | -84.8% | | VSTS | 1 | 4355923 | 0 | 0.64 s | 0.05 s | -92.2% | | VSTS | 32 | 4355923 | 0 | 7.77 s | 1.36 s | -82.5% | | VSTS | 31 | 4276829 | 79094 | 7.76 s | 1.36 s | -82.5% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 38.9 s
New Time: 2.7 s
Rel %: -93.1%Derrick Stolee (5):
test-list-objects: List a subset of object ids p0008-abbrev.sh: Test find_unique_abbrev() perf
sha1_name: Unroll len loop in find_unique_abbrev_r
sha1_name: Parse less while finding common prefix
sha1_name: Minimize OID comparisons during disambiguation
Makefile | 2 + sha1_name.c | 128 ++++++++++++++++++++++++++++++++++++++----- t/helper/.gitignore | 2 + t/helper/test-abbrev.c | 19 +++++++ t/helper/test-list-objects.c | 85 ++++++++++++++++++++++++++++ t/perf/p0008-abbrev.sh | 22 ++++++++ 6 files changed, 243 insertions(+), 15 deletions(-) create mode 100644 t/helper/test-abbrev.c create mode 100644 t/helper/test-list-objects.c create mode 100755 t/perf/p0008-abbrev.sh
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
PATCH v2 1/5 test-list-objects: List a subset of object ids
Create test-list-objects helper program to output a random sample of OIDs present in the repo.
If no command line arguments are provided, all OIDs are output.
The first command line argument specifies how many samples to output. Samples are collected across the entire set of available OIDs to avoid clustering and therefore quite uniformly distributed.
If a second command line argument "--missing" is given, then a list of OIDs is generated without examining the repo.
--- Makefile | 1 + t/helper/.gitignore | 1 + t/helper/test-list-objects.c | 85 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 87 insertions(+) create mode 100644 t/helper/test-list-objects.c
Makefile +1 -0
@@ -647,6 +647,7 @@ TEST_PROGRAMS_NEED_X += test-hashmap TEST_PROGRAMS_NEED_X += test-index-version TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash TEST_PROGRAMS_NEED_X += test-line-buffer +TEST_PROGRAMS_NEED_X += test-list-objects TEST_PROGRAMS_NEED_X += test-match-trees TEST_PROGRAMS_NEED_X += test-mergesort TEST_PROGRAMS_NEED_X += test-mktemp
t/helper/.gitignore +1 -0
@@ -13,6 +13,7 @@ /test-index-version /test-lazy-init-name-hash /test-line-buffer +/test-list-objects /test-match-trees /test-mergesort /test-mktemp
t/helper/test-list-objects.c new file +85 -0
85 lines not on this page · raw message
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
t/helper/test-list-objects.c line 3
Quoted 9 lines · Derrick Stolee
t/helper/test-list-objects.c new file +3
-0@@ -0,0 +1,85 @@ +#include "cache.h" +#include "packfile.h" +#include <stdio.h>
If you include "cache.h", like the ordinary "git" program, you should not have to include any system headers like stdio.h yourself. The whole point of "git-compat-util.h must be the first to be included (indirectly including it via cache.h and friends is also OK)" rule is to make sure that system headers are included at the right place in the include sequence (e.g. defining feature macros before including certain headers, etc.).
t/helper/test-list-objects.c line 58
Quoted 6 lines
t/helper/test-list-objects.c new file +6
-0+int cmd_main (int ac,const char **av) +{ +unsigned int hash_delt =0xFDB97531 ; +unsigned int hash_base =0x01020304 ; +... +const int u_per_oid =sizeof (struct object_id ) /sizeof (unsigned int );
Because the above will not work as you expect, unless your uint is 32-bit, you would probably want to make hash_delt and hash_base explicitly uint32_t, I think.
Alternatively, because you assume that uint is at least 8-hex-digit wide in the output loop, you can keep "unsigned int" above, but change the divisor from sizeof(unsigned int) to a hardcoded 4.
Either would fix the issue.
t/helper/test-list-objects.c line 62
Quoted 3 lines
t/helper/test-list-objects.c new file +3
-0+ c.total =0 ; +if (ac >1 ) + n =atoi (av[1 ]);
Otherwise n will stay 0 as initialized. Not checking the result of atoi() is probably permissible, as this is merely a test helper and we can assume that the caller will not do anything silly, like passing "-3" in av[1]. But it certainly would be a good discipline to make sure av[1] is a reasonable number.
I am afraid that I may be misreading the code, but the following code seems to require that the caller must know roughly how many objects there are (so that a large-enough value can be passed to av[1] to force c.select_mod to 1) when it wants to show everything, as the "missing" loop will run 0 times showing nothing, and "listing" case will divide by zero.
"Not passing anything will show everything" the proposed log message promises is a better design than what the code actually seems to be doing.
t/helper/test-list-objects.c line 65
Quoted 3 lines
t/helper/test-list-objects.c new file +3
-0+ +if (ac >2 && !strcmp (av[2 ],"--missing" )) { +while (c.total++ < n) {
When n==0, this does nothing. I am not sure what the desired behaviour should be for "When no count is given, we show everything" in this codepath, though.
Also, doesn't "test-list-objects 5 --missing" look very wrong? Shouldn't it be more like "test-list-objects --missing 5"?
t/helper/test-list-objects.c line 78
Quoted 13 lines
t/helper/test-list-objects.c new file +13
-0+for (i =0 ; i < u_per_oid; i++) { +printf ("%08x" , hash_base); + hash_base += hash_delt; + } +printf ("\n" ); + } + }else { +setup_git_directory (); + +for_each_loose_object (count_loose, &c,0 ); +for_each_packed_object (count_packed, &c,0 ); + + c.select_mod =1 + c.total / n;
When n==0, this would divide by zero.
Perhaps
c.select_mod = n ? (1 + c.total / n) : 1;
or something to keep the promise of showing everything?
t/helper/test-list-objects.c line 85
Quoted 6 lines
t/helper/test-list-objects.c new file +6
-0+for_each_loose_object (output_loose, &c,0 ); +for_each_packed_object (output_packed, &c,0 ); + } + +exit (0 ); +}
Thanks.
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
In reply to Derrick StoleeQuoted 4 lines · Derrick Stolee
Create test-list-objects helper program to output a random sample of OIDs present in the repo.
If no command line arguments are provided, all OIDs are output.
This is weirdly specific. Can we accomplish the same thing with existing tools?
E.g., could:
git cat-file --batch-all-objects --batch-check='%(objectname)' | shuffle | head -n 100
do the same thing?
I know that "shuffle" isn't available everywhere, but I'd much rather see us fill in portability gaps in a general way, rather than introducing one-shot C code that needs to be maintained (and you wouldn't _think_ that t/helper programs need much maintenance, but try perusing "git log t/helper" output; they have to adapt to the same tree-wide changes as the rest of the code).
-Peff
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 9 lines · Jeff King
This is weirdly specific. Can we accomplish the same thing with existing tools?
E.g., could:
git cat-file --batch-all-objects --batch-check='%(objectname)' | shuffle | head -n 100
Quoted 8 lines
do the same thing?
I know that "shuffle" isn't available everywhere, but I'd much rather see us fill in portability gaps in a general way, rather than introducing one-shot C code that needs to be maintained (and you wouldn't _think_ that t/helper programs need much maintenance, but try perusing "git log t/helper" output; they have to adapt to the same tree-wide changes as the rest of the code).
I was thinking about this a bit more, and came to the conclusion that "sort -R" and "shuf" are wrong tools to use. We would want to measure with something close to real world workload. for example, letting
git rev-list --all --objects
produce the listof objects in traversal order (i.e. this is very similar to the order in which "git log -p" needs to access the objects) and chomping at the number of sample objects you need in your test would give you such a list.
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 25 lines · Junio C Hamano
Quoted 9 lines · Jeff King
This is weirdly specific. Can we accomplish the same thing with existing tools?
E.g., could:
git cat-file --batch-all-objects --batch-check='%(objectname)' | shuffle | head -n 100Quoted 8 lines
do the same thing?
I know that "shuffle" isn't available everywhere, but I'd much rather see us fill in portability gaps in a general way, rather than introducing one-shot C code that needs to be maintained (and you wouldn't _think_ that t/helper programs need much maintenance, but try perusing "git log t/helper" output; they have to adapt to the same tree-wide changes as the rest of the code).
I was thinking about this a bit more, and came to the conclusion that "sort -R" and "shuf" are wrong tools to use. We would want to measure with something close to real world workload. for example, letting
Quoted 6 lines
git rev-list --all --objectsproduce the listof objects in traversal order (i.e. this is very similar to the order in which "git log -p" needs to access the objects) and chomping at the number of sample objects you need in your test would give you such a list.
Actually, I'd just as soon see timings for "git log --format=%h" or "git log --raw", as opposed to patches 1 and 2.
You won't see a 90% speedup there, but you will see the actual improvement that real-world users are going to experience, which is way more important, IMHO.
-Peff
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 9 lines · Jeff King
Quoted 3 lines
Jeff King <[email protected]> writes:
Actually, I'd just as soon see timings for "git log --format=%h" or "git log --raw", as opposed to patches 1 and 2.
You won't see a 90% speedup there, but you will see the actual improvement that real-world users are going to experience, which is way more important, IMHO.
Yup, "log --raw -r" would really exercise the abbreviation machinery without spending time on the diff machinery, and it would be a good test.
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
In reply to Jeff KingQuoted 32 lines · Jeff King
Quoted 24 lines · Junio C Hamano
Quoted 9 lines · Jeff King
This is weirdly specific. Can we accomplish the same thing with existing tools?
E.g., could:
git cat-file --batch-all-objects --batch-check='%(objectname)' | shuffle | head -n 100Quoted 8 lines
do the same thing?
I know that "shuffle" isn't available everywhere, but I'd much rather see us fill in portability gaps in a general way, rather than introducing one-shot C code that needs to be maintained (and you wouldn't _think_ that t/helper programs need much maintenance, but try perusing "git log t/helper" output; they have to adapt to the same tree-wide changes as the rest of the code).
I was thinking about this a bit more, and came to the conclusion that "sort -R" and "shuf" are wrong tools to use. We would want to measure with something close to real world workload. for example, letting
Quoted 6 lines
git rev-list --all --objectsproduce the listof objects in traversal order (i.e. this is very similar to the order in which "git log -p" needs to access the objects) and chomping at the number of sample objects you need in your test would give you such a list.
Quoted 8 lines
Actually, I'd just as soon see timings for "git log --format=%h" or "git log --raw", as opposed to patches 1 and 2.
You won't see a 90% speedup there, but you will see the actual improvement that real-world users are going to experience, which is way more important, IMHO.
-Peff
Thanks for thinking hard about this.
For some real-user context: Some engineers using Git for the Windows repo were seeing extremely slow commands, such as 'fetch' or 'commit', and when we took a trace we saw most of the time spinning in this abbreviation code. Our workaround so far has been to set core.abbrev=40.
I'll run some perf numbers for these commands you recommend, and also see if I can replicate some of the pain points that triggered this change using the Linux repo.
Thanks,
-Stolee
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 7 lines · Derrick Stolee
Quoted 7 lines
Actually, I'd just as soon see timings for "git log --format=%h" or "git log --raw", as opposed to patches 1 and 2.
You won't see a 90% speedup there, but you will see the actual improvement that real-world users are going to experience, which is way more important, IMHO.
Quoted 5 lines
Thanks for thinking hard about this.
For some real-user context: Some engineers using Git for the Windows repo were seeing extremely slow commands, such as 'fetch' or 'commit', and when we took a trace we saw most of the time spinning in this abbreviation code.
That's surprising to me. I'd expect fetch to generate up to two abbreviations per fetched ref (for the status table). And for commit to generate only one for the summary. But maybe it was just so painfully slow on your repo that it was noticeable.
If there's a case where we're generating a bunch of abbreviated oids, that might be worth looking into. Do you happen to have a stack trace of one of the slow cases showing who is calling into the function?
Quoted 1 line
Our workaround so far has been to set core.abbrev=40.
I actually wondered about this. With the new auto-scaling, we'd typically jump straight to 12 or 13 hex-chars on a large repo, and that would be sufficient. So we'd really only need one iteration of the loop.
Quoted 3 lines
I'll run some perf numbers for these commands you recommend, and also see if I can replicate some of the pain points that triggered this change using the Linux repo.
Thanks!
-Peff
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 9 lines · Jeff King
Quoted 3 lines · Derrick Stolee
I'll run some perf numbers for these commands you recommend, and also see if I can replicate some of the pain points that triggered this change using the Linux repo.
Thanks!
-Peff
In my local copy, I added a test to p4211-line-log.sh that runs "git log --raw -r" and tested it on three copies of the Linux repo. In order, they have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles (~324,000 loose).
4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6% 4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1%
4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%
We have moderate performance gains for this command, despite the command doing many more things than just checking abbreviations.
I plan to re-roll my patch on Monday including the following feedback items:
* Remove test-list-objects and test-abbrev in favor of a new "git log" performance test.
* Fix binary search overflow error.
* Check response from open_pack_index(p) in find_abbrev_len_for_pack(). I plan to return without failure on non-zero result, which results in no failure on a bad pack and the abbreviation length will be the minimum required among all valid packs. (Thanks Stefan!)
I made note of a few things, but will not include them in my re-roll. I'll revisit them later if they are valuable:
- nth_packed_object_sha1() could be simplified in
find_abbrev_len_for_pack().
- Teach 'cat-file' to --batch-check='%(objectsize:short)'. (Peff already included a patch, perhaps that could be reviewed separately.)
- Ramsay caught my lack of "static" in test-list-objects.c, but that file will be removed in the next patch. I'll make sure to use "static" in the future.
I'm not re-rolling immediately to allow for some extra review over the weekend, if anyone is so inclined.
Thanks,
-Stolee
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 11 lines · Derrick Stolee
In my local copy, I added a test to
p4211-line-log.shthat runs "git log --raw -r" and tested it on three copies of the Linux repo. In order, they have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles (~324,000 loose).4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6% 4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1%4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%
We have moderate performance gains for this command, despite the command doing many more things than just checking abbreviations.
Yeah, while it's less exciting than seeing the 90% numbers for a micro-benchmark, I think this represents real-world gains (and 5-7% is nothing to sneeze at).
You might also try adding "--format=%h" or --oneline to your invocation, which would compute abbreviations for each commit (making your workload more abbrev-heavy and possibly showing off the difference more).
I also think "-r" isn't doing anything. Recursive diffs are the default for the "log" porcelain (even for --raw).
Quoted 11 lines
I plan to re-roll my patch on Monday including the following feedback items:
* Remove test-list-objects and test-abbrev in favor of a new "git log" performance test.
* Fix binary search overflow error.
* Check response from
open_pack_index(p)infind_abbrev_len_for_pack(). I plan to return without failure on non-zero result, which results in no failure on a bad pack and the abbreviation length will be the minimum required among all valid packs. (Thanks Stefan!)
That all sounds reasonable to me.
Quoted 2 lines
- Teach 'cat-file' to --batch-check='%(objectsize:short)'. (Peff already included a patch, perhaps that could be reviewed separately.)
I think I'll let it lie in the list archive for now unless somebody has a real use case for it (though I'm tempted to add it purely for completionism, since it's so easy).
-Peff
Re: [PATCH v2 1/5] test-list-objects: List a subset of object ids
Quoted 11 lines · Jeff King
Quoted 9 lines · Derrick Stolee
In my local copy, I added a test to
p4211-line-log.shthat runs "git log --raw -r" and tested it on three copies of the Linux repo. In order, they have 1 packfile (0 loose), 24 packfiles (0 loose), and 23 packfiles (~324,000 loose).4211.6: git log --raw -r 43.34(42.62+0.65) 40.47(40.16+0.27) -6.6% 4211.6: git log --raw -r 88.77(86.54+2.12) 82.44(81.87+0.52) -7.1%4211.6: git log --raw -r 108.86(103.97+4.81) 103.92(100.63+3.19) -4.5%
Quoted 6 lines
Quoted 2 lines
We have moderate performance gains for this command, despite the command doing many more things than just checking abbreviations.
Yeah, while it's less exciting than seeing the 90% numbers for a micro-benchmark, I think this represents real-world gains (and 5-7% is nothing to sneeze at).
Yes! I would even say 5-7% is much better than "nothing to sneeze at". We do prefer workload closer to the real-world usage over micro benchmarks, and consider changes that gain by a few percent as real improvements.
Quoted 3 lines
You might also try adding "--format=%h" or --oneline to your invocation, which would compute abbreviations for each commit (making your workload more abbrev-heavy and possibly showing off the difference more).
Again, agreed, and I would not consider it would be inflating the benchmark artificially in favor of the change. "log --oneline" is not something people use rarely---I'd think it would be quite a normal thing to do.
Quoted 2 lines
I also think "-r" isn't doing anything. Recursive diffs are the default for the "log" porcelain (even for --raw).
That's my fault writing "-r" ;-) Together with your "log --oneline" suggestion,
git log --oneline --raw
would be a reasonable thing to measure.
Thanks, both.
PATCH v2 2/5 p0008-abbrev.sh: Test find_unique_abbrev() perf
In reply to Derrick StoleeCreate helper program test-abbrev to compute the minimum length of a disambiguating short-sha for an input list of object ids.
Perf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For test 0008.1, these objects exist. For test 0008.2 these objects do not exist in the repo (with high probability). For each test, use sort -R to (deterministically) shuffle the sample of object ids to not check abbreviations in lexicographic order.
--- Makefile | 1 + t/helper/.gitignore | 1 + t/helper/test-abbrev.c | 19 +++++++++++++++++++ t/perf/p0008-abbrev.sh | 22 ++++++++++++++++++++++ 4 files changed, 43 insertions(+) create mode 100644 t/helper/test-abbrev.c create mode 100755 t/perf/p0008-abbrev.sh
Makefile +1 -0
@@ -633,6 +633,7 @@ X = PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS)) +TEST_PROGRAMS_NEED_X += test-abbrev TEST_PROGRAMS_NEED_X += test-chmtime TEST_PROGRAMS_NEED_X += test-ctype TEST_PROGRAMS_NEED_X += test-config
t/helper/.gitignore +1 -0
@@ -1,3 +1,4 @@ +/test-abbrev /test-chmtime /test-ctype /test-config
t/helper/test-abbrev.c new file +19 -0
@@ -0,0 +1,19 @@ +#include "cache.h" +#include <stdio.h> + +int cmd_main (int ac,const char **av) +{ +struct object_id oid; +char hex[GIT_MAX_HEXSZ +2 ]; +const char *end; + +setup_git_directory (); + +while (fgets (hex,GIT_MAX_HEXSZ +2 , stdin)) { + hex[GIT_MAX_HEXSZ ] =0 ; +if (!parse_oid_hex (hex, &oid, &end)) +find_unique_abbrev (oid.hash,MINIMUM_ABBREV ); + } + +exit (0 ); +}
t/perf/p0008-abbrev.sh new file +22 -0
@@ -0,0 +1,22 @@ +#!/bin/bash + +test_description='Test object disambiguation through abbreviations' +. ./perf-lib.sh + +test_perf_large_repo + +test-list-objects 100000 | sort -R > objs.txt + +test_perf 'find_unique_abbrev() for existing objects' ' + test-abbrev < objs.txt +' + +test-list-objects 100000 --missing | sort -R > objs.txt + +test_perf 'find_unique_abbrev() for missing objects' ' + test-abbrev < objs.txt +' + +rm objs.txt + +test_done
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf
t/helper/test-abbrev.c line 2
Quoted 8 lines · Derrick Stolee
t/helper/test-abbrev.c new file +2
-0@@ -0,0 +1,19 @@ +#include "cache.h" +#include <stdio.h>
Same comment on <stdio.h> as [1/5] applies.
t/helper/test-abbrev.c line 7
Quoted 5 lines
t/helper/test-abbrev.c new file +5
-0+ +int cmd_main (int ac,const char **av) +{ +struct object_id oid; +char hex[GIT_MAX_HEXSZ +2 ];
Why +2 (as opposed to +1)?
Quoted 18 lines
t/helper/test-abbrev.c new file +12
-0+const char *end; + +setup_git_directory (); + +while (fgets (hex,GIT_MAX_HEXSZ +2 , stdin)) { + hex[GIT_MAX_HEXSZ ] =0 ; +if (!parse_oid_hex (hex, &oid, &end)) +find_unique_abbrev (oid.hash,MINIMUM_ABBREV ); + } + +exit (0 ); +}t/perf/p0008-abbrev.sh new file +0
-0
t/perf/p0008-abbrev.sh line 8
Quoted 8 lines
t/perf/p0008-abbrev.sh new file +8
-0@@ -0,0 +1,22 @@ +#!/bin/bash + +test_description='Test object disambiguation through abbreviations' +. ./perf-lib.sh + +test_perf_large_repo + +test-list-objects 100000 | sort -R > objs.txt
I thought "sort randomly" was a GNUism. Does it work across platforms? I think not.
Quoted 14 lines
t/perf/p0008-abbrev.sh new file +14
-0+ +test_perf 'find_unique_abbrev() for existing objects' ' + test-abbrev < objs.txt +' + +test-list-objects 100000 --missing | sort -R > objs.txt + +test_perf 'find_unique_abbrev() for missing objects' ' + test-abbrev < objs.txt +' + +rm objs.txt + +test_done
Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf
In reply to Derrick StoleeQuoted 2 lines · Derrick Stolee
Create helper program test-abbrev to compute the minimum length of a disambiguating short-sha for an input list of object ids.
This seems like something that Git ought to be able to do via real commands.
Using "log --stdin --no-walk --format=%h" doesn't quite work, since it only handles commits. We ought to be able to ask "cat-file" for this, though. E.g., with the patch below you can do:
git cat-file --batch-check='%(objectsize:short)' <input
Or even just dispense with your earlier randomization helper and do:
git cat-file --batch-all-objects --batch-check='%(objectsize:short)'
to compute the abbreviation for every object.
Quoted 5 lines
Perf test
p0008-abbrev.shruns test-abbrev for 100,000 object ids. For test 0008.1, these objects exist. For test 0008.2 these objects do not exist in the repo (with high probability). For each test, usesort -Rto (deterministically) shuffle the sample of object ids to not check abbreviations in lexicographic order.
I know you're not the first to add a test like this, but I'm somewhat negative on these sorts of micro-benchmark perf tests. They're nice for showing off an improvement, but there's little indication of how they impact things that users actually do.
We know that this series makes finding abbreviations cheaper. But how much does it speed up "git log --oneline" on a real repository (including absurdly-sized ones)?
-Peff
Re: [PATCH v2 2/5] p0008-abbrev.sh: Test find_unique_abbrev() perf
Quoted 12 lines · Jeff King
Quoted 2 lines · Derrick Stolee
Create helper program test-abbrev to compute the minimum length of a disambiguating short-sha for an input list of object ids.
This seems like something that Git ought to be able to do via real commands.
Using "log --stdin --no-walk --format=%h" doesn't quite work, since it only handles commits. We ought to be able to ask "cat-file" for this, though. E.g., with the patch below you can do:
Quoted 7 lines
git cat-file --batch-check='%(objectsize:short)' <inputOr even just dispense with your earlier randomization helper and do:
git cat-file --batch-all-objects --batch-check='%(objectsize:short)'to compute the abbreviation for every object.
Of course it would help if I bothered to include the patch. Here it is.
builtin/cat-file.c +3 -0
@@ -225,6 +225,9 @@ static void expand_atom(struct strbuf *sb, const char *atom, int len,if (is_atom ("objectname" , atom, len)) {if (!data->mark_query)strbuf_addstr (sb,oid_to_hex (&data->oid)); + }else if (is_atom ("objectname:short" , atom, len)) { +if (!data->mark_query) +strbuf_add_unique_abbrev (sb, data->oid.hash,MINIMUM_ABBREV ); }else if (is_atom ("objecttype" , atom, len)) {if (data->mark_query) data->info.typep = &data->type;
-Peff
PATCH v2 3/5 sha1_name: Unroll len loop in find_unique_abbrev_r
In reply to Derrick StoleeUnroll the while loop inside find_unique_abbrev_r to avoid iterating through all loose objects and packfiles multiple times when the short name is longer than the predicted length.
Instead, inspect each object that collides with the estimated abbreviation to find the longest common prefix.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.12 s | 0.08 s | -33.3% | | Git | 5 | 230162 | 0 | 0.25 s | 0.17 s | -32.0% | | Git | 4 | 154310 | 75852 | 0.18 s | 0.14 s | -22.2% | | Linux | 1 | 5606645 | 0 | 0.32 s | 0.50 s | +56.2% | | Linux | 24 | 5606645 | 0 | 2.77 s | 2.41 s | -13.0% | | Linux | 23 | 5283204 | 323441 | 2.86 s | 1.99 s | -30.4% | | VSTS | 1 | 4355923 | 0 | 0.27 s | 0.40 s | +48.1% | | VSTS | 32 | 4355923 | 0 | 2.41 s | 2.09 s | -13.3% | | VSTS | 31 | 4276829 | 79094 | 4.22 s | 3.60 s | -14.7% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 5.69 s
New Time: 4.62 s
Rel %: -18.9%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.61 s | 0.06 s | -90.2% | | Git | 5 | 230162 | 0 | 1.30 s | 0.14 s | -89.2% | | Git | 4 | 154310 | 75852 | 1.07 s | 0.12 s | -88.8% | | Linux | 1 | 5606645 | 0 | 0.65 s | 0.40 s | -38.5% | | Linux | 24 | 5606645 | 0 | 7.12 s | 1.59 s | -77.7% | | Linux | 23 | 5283204 | 323441 | 6.33 s | 1.23 s | -80.6% | | VSTS | 1 | 4355923 | 0 | 0.64 s | 0.25 s | -60.9% | | VSTS | 32 | 4355923 | 0 | 7.77 s | 1.45 s | -81.3% | | VSTS | 31 | 4276829 | 79094 | 7.76 s | 1.59 s | -79.5% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 39.0 s
New Time: 3.9 s
Rel %: -90.0%--- sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 42 insertions(+), 15 deletions(-)
sha1_name.c +42 -15
@@ -474,10 +474,32 @@ static unsigned msb(unsigned long val)return r; } -int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) +struct min_abbrev_data { +unsigned int init_len; +unsigned int cur_len; +char *hex; +}; + +static int extend_abbrev_len (const struct object_id *oid,void *cb_data) { -int status, exists; +struct min_abbrev_data *mad = cb_data; + +char *hex =oid_to_hex (oid); +unsigned int i = mad->init_len; +while (mad->hex[i] && mad->hex[i] == hex[i]) + i++; + +if (i <GIT_MAX_RAWSZ && i >= mad->cur_len) + mad->cur_len = i +1 ; + +return 0 ; +} +int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) +{ +struct disambiguate_state ds; +struct min_abbrev_data mad; +struct object_id oid_ret;if (len <0 ) {unsigned long count =approximate_object_count ();/*
@@ -503,19 +525,24 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)sha1_to_hex_r (hex, sha1);if (len ==GIT_SHA1_HEXSZ || !len)return GIT_SHA1_HEXSZ ; - exists =has_sha1_file (sha1); -while (len <GIT_SHA1_HEXSZ ) { -struct object_id oid_ret; - status =get_short_oid (hex, len, &oid_ret,GET_OID_QUIETLY ); -if (exists - ? !status - : status ==SHORT_NAME_NOT_FOUND ) { - hex[len] =0 ; -return len; - } - len++; - } -return len; + +if (init_object_disambiguation (hex, len, &ds) <0 ) +return -1 ; + + mad.init_len = len; + mad.cur_len = len; + mad.hex = hex; + + ds.fn = extend_abbrev_len; + ds.always_call_fn =1 ; + ds.cb_data = (void *)&mad; + +find_short_object_filename (&ds); +find_short_packed_object (&ds); + (void )finish_object_disambiguation (&ds, &oid_ret); + + hex[mad.cur_len] =0 ; +return mad.cur_len; }const char *find_unique_abbrev (const unsigned char *sha1,int len)
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
PATCH v2 4/5 sha1_name: Parse less while finding common prefix
In reply to Derrick StoleeCreate get_hex_char_from_oid() to parse oids one hex character at a time. This prevents unnecessary copying of hex characters in extend_abbrev_len() when finding the length of a common prefix.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.08 s | 0.08 s | 0.0% | | Git | 5 | 230162 | 0 | 0.17 s | 0.16 s | - 5.9% | | Git | 4 | 154310 | 75852 | 0.14 s | 0.12 s | -14.3% | | Linux | 1 | 5606645 | 0 | 0.50 s | 0.25 s | -50.0% | | Linux | 24 | 5606645 | 0 | 2.41 s | 2.08 s | -13.7% | | Linux | 23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% | | VSTS | 1 | 4355923 | 0 | 0.40 s | 0.22 s | -45.0% | | VSTS | 32 | 4355923 | 0 | 2.09 s | 1.99 s | - 4.8% | | VSTS | 31 | 4276829 | 79094 | 3.60 s | 3.20 s | -11.1% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 4.61 s
New Time: 4.61 s
Rel %: 0.0%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% | | Git | 5 | 230162 | 0 | 0.14 s | 0.15 s | + 7.1% | | Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% | | Linux | 1 | 5606645 | 0 | 0.40 s | 0.17 s | -57.5% | | Linux | 24 | 5606645 | 0 | 1.59 s | 1.30 s | -18.2% | | Linux | 23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% | | VSTS | 1 | 4355923 | 0 | 0.25 s | 0.12 s | -52.0% | | VSTS | 32 | 4355923 | 0 | 1.45 s | 1.34 s | - 7.6% | | VSTS | 31 | 4276829 | 79094 | 1.59 s | 1.34 s | -15.7% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 3.91 s
New Time: 3.08 s
Rel %: -21.1%--- sha1_name.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-)
sha1_name.c +11 -2
@@ -480,13 +480,22 @@ struct min_abbrev_data {char *hex; }; +static inline char get_hex_char_from_oid (const struct object_id *oid,int i) +{ +static const char hex[] ="0123456789abcdef" ; + +if ((i &1 ) ==0 ) +return hex[oid->hash[i >>1 ] >>4 ]; +else +return hex[oid->hash[i >>1 ] &0xf ]; +} +static int extend_abbrev_len (const struct object_id *oid,void *cb_data) {struct min_abbrev_data *mad = cb_data; -char *hex =oid_to_hex (oid);unsigned int i = mad->init_len; -while (mad->hex[i] && mad->hex[i] == hex[i]) +while (mad->hex[i] && mad->hex[i] ==get_hex_char_from_oid (oid, i)) i++;if (i <GIT_MAX_RAWSZ && i >= mad->cur_len)
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix
Quoted 51 lines · Derrick Stolee
Create
get_hex_char_from_oid()to parse oids one hex character at a time. This prevents unnecessary copying of hex characters inextend_abbrev_len()when finding the length of a common prefix.p0008.1:
find_unique_abbrev()for existing objects
--------------------------------------------------For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.08 s | 0.08 s | 0.0% | | Git | 5 | 230162 | 0 | 0.17 s | 0.16 s | - 5.9% | | Git | 4 | 154310 | 75852 | 0.14 s | 0.12 s | -14.3% | | Linux | 1 | 5606645 | 0 | 0.50 s | 0.25 s | -50.0% | | Linux | 24 | 5606645 | 0 | 2.41 s | 2.08 s | -13.7% | | Linux | 23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% | | VSTS | 1 | 4355923 | 0 | 0.40 s | 0.22 s | -45.0% | | VSTS | 32 | 4355923 | 0 | 2.09 s | 1.99 s | - 4.8% | | VSTS | 31 | 4276829 | 79094 | 3.60 s | 3.20 s | -11.1% |For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492Base Time: 4.61 s New Time: 4.61 s Rel %: 0.0%p0008.2:
find_unique_abbrev()for missing objects
-------------------------------------------------For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% | | Git | 5 | 230162 | 0 | 0.14 s | 0.15 s | + 7.1% | | Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% | | Linux | 1 | 5606645 | 0 | 0.40 s | 0.17 s | -57.5% | | Linux | 24 | 5606645 | 0 | 1.59 s | 1.30 s | -18.2% | | Linux | 23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% | | VSTS | 1 | 4355923 | 0 | 0.25 s | 0.12 s | -52.0% | | VSTS | 32 | 4355923 | 0 | 1.45 s | 1.34 s | - 7.6% | | VSTS | 31 | 4276829 | 79094 | 1.59 s | 1.34 s | -15.7% |
Quoted 9 lines
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492Base Time: 3.91 s New Time: 3.08 s Rel %: -21.1%
These number look pretty cool!
Quoted 3 lines
Signed-off-by Derrick Stolee <[email protected]>Signed-off-by Derrick Stolee <[email protected]>
double signoff?
sha1_name.c struct min_abbrev_data { · line 483
Quoted 13 lines
--- sha1_name.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-)sha1_name.c +1
-0@@ -480,13 +480,22 @@ struct min_abbrev_data {char *hex; }; +static inline char get_hex_char_from_oid (const struct object_id *oid,int i)
'i' is not very descriptive, maybe add a comment? (I realize it is just walking through the char*s one by one)
Maybe this function (together with the change in the while below) could go into hex.c as "int progressively_cmp_oids" that returns the position at which the given oids differ?
sha1_name.c struct min_abbrev_data { · line 491
Quoted 8 lines
sha1_name.c +8
-0+{ +static const char hex[] ="0123456789abcdef" ; + +if ((i &1 ) ==0 ) +return hex[oid->hash[i >>1 ] >>4 ]; +else +return hex[oid->hash[i >>1 ] &0xf ]; +}
sha1_to_hex_r has very similar code, though it iterates less and covers both cases in the loop body.
That is the actual reason I propose moving this function (or a variant thereof) to hex.c as there we can share code.
Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix
My v3 patch is incoming, but I wanted to respond directly to this message.
Quoted 61 lines · Stefan Beller
Quoted 51 lines · Derrick Stolee
Create
get_hex_char_from_oid()to parse oids one hex character at a time. This prevents unnecessary copying of hex characters inextend_abbrev_len()when finding the length of a common prefix.p0008.1:
find_unique_abbrev()for existing objects
--------------------------------------------------For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.08 s | 0.08 s | 0.0% | | Git | 5 | 230162 | 0 | 0.17 s | 0.16 s | - 5.9% | | Git | 4 | 154310 | 75852 | 0.14 s | 0.12 s | -14.3% | | Linux | 1 | 5606645 | 0 | 0.50 s | 0.25 s | -50.0% | | Linux | 24 | 5606645 | 0 | 2.41 s | 2.08 s | -13.7% | | Linux | 23 | 5283204 | 323441 | 1.99 s | 1.69 s | -15.1% | | VSTS | 1 | 4355923 | 0 | 0.40 s | 0.22 s | -45.0% | | VSTS | 32 | 4355923 | 0 | 2.09 s | 1.99 s | - 4.8% | | VSTS | 31 | 4276829 | 79094 | 3.60 s | 3.20 s | -11.1% |For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492Base Time: 4.61 s New Time: 4.61 s Rel %: 0.0%p0008.2:
find_unique_abbrev()for missing objects
-------------------------------------------------For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% | | Git | 5 | 230162 | 0 | 0.14 s | 0.15 s | + 7.1% | | Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% | | Linux | 1 | 5606645 | 0 | 0.40 s | 0.17 s | -57.5% | | Linux | 24 | 5606645 | 0 | 1.59 s | 1.30 s | -18.2% | | Linux | 23 | 5283204 | 323441 | 1.23 s | 1.10 s | -10.6% | | VSTS | 1 | 4355923 | 0 | 0.25 s | 0.12 s | -52.0% | | VSTS | 32 | 4355923 | 0 | 1.45 s | 1.34 s | - 7.6% | | VSTS | 31 | 4276829 | 79094 | 1.59 s | 1.34 s | -15.7% |Quoted 9 lines
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492Base Time: 3.91 s New Time: 3.08 s Rel %: -21.1%
Quoted 6 lines
These number look pretty cool!
Quoted 3 lines
Signed-off-by Derrick Stolee <[email protected]>Signed-off-by Derrick Stolee <[email protected]>double signoff?
Oops! I'll be more careful with my format-patch in the future.
Quoted 13 lines
Quoted 13 lines
--- sha1_name.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-)sha1_name.c +0
-0@@ -480,13 +480,22 @@ struct min_abbrev_data {char *hex; };
Quoted 3 lines
sha1_name.c struct min_abbrev_data { · line 483
Quoted 1 line
sha1_name.c +1
-0+static inline char get_hex_char_from_oid (const struct object_id *oid,int i)'i' is not very descriptive, maybe add a comment? (I realize it is just walking through the char*s one by one)
I renamed 'i' to 'pos' in my v3.
Quoted 16 lines
Maybe this function (together with the change in the while below) could go into
hex.cas "intprogressively_cmp_oids" that returns the position at which the given oids differ?sha1_name.c struct min_abbrev_data { · line 491
Quoted 8 lines
sha1_name.c +8
-0+{ +static const char hex[] ="0123456789abcdef" ; + +if ((i &1 ) ==0 ) +return hex[oid->hash[i >>1 ] >>4 ]; +else +return hex[oid->hash[i >>1 ] &0xf ]; +}
sha1_to_hex_rhas very similar code, though it iterates less and covers both cases in the loop body.
Quoted 2 lines
That is the actual reason I propose moving this function (or a variant thereof) to
hex.cas there we can share code.
You're right that sha1_to_hex_r is similar, in fact I based my work on it. There are a few reasons I didn't combine the two implementations:
* I wanted to be sure my patch was only touching the code for disambiguating short-shas. Modifying code in hex.c would touch many more code paths.
* I realize that the extra branch in my version is slower than the branchless loop body in sha1_to_hex_r, so either I would slow that method or make the method call more complicated by returning two chars at a time.
* I wanted to strongly hint that the method should be inlined, but I'm not sure how to guarantee that happens across a linker boundary without doing strange things in header files.
I'm happy to revisit this after my patch is complete, since I think there are interesting trade-offs to consider here. I'd prefer to keep this discussion separate from the focus on disambiguation.
Thanks,
-Stolee
PATCH v2 5/5 sha1_name: Minimize OID comparisons during disambiguation
In reply to Derrick StoleeMinimize OID comparisons during disambiguatiosn of packfile OIDs.
Teach git to use binary search with the full OID to find the object's position (or insertion position, if not present) in the pack-index. The object before and immediately after (or the one at the insertion position) give the maximum common prefix. No subsequent linear search is required.
Take care of which two to inspect, in case the object id exists in the packfile.
If the input to find_unique_abbrev_r() is a partial prefix, then the OID used for the binary search is padded with zeroes so the object will not exist in the repo (with high probability) and the same logic applies.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.08 s | 0.05 s | -37.5% | | Git | 5 | 230162 | 0 | 0.16 s | 0.15 s | - 6.3% | | Git | 4 | 154310 | 75852 | 0.12 s | 0.11 s | - 8.3% | | Linux | 1 | 5606645 | 0 | 0.25 s | 0.10 s | -60.0% | | Linux | 24 | 5606645 | 0 | 2.08 s | 2.00 s | - 3.8% | | Linux | 23 | 5283204 | 323441 | 1.69 s | 1.62 s | - 4.1% | | VSTS | 1 | 4355923 | 0 | 0.22 s | 0.09 s | -59.1% | | VSTS | 32 | 4355923 | 0 | 1.99 s | 2.01 s | + 1.0% | | VSTS | 31 | 4276829 | 79094 | 3.20 s | 3.02 s | - 5.6% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 4.62 s
New Time: 4.09 s
Rel %: -11.5%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.05 s | 0.04 s | -20.0% | | Git | 5 | 230162 | 0 | 0.15 s | 0.15 s | 0.0% | | Git | 4 | 154310 | 75852 | 0.12 s | 0.12 s | 0.0% | | Linux | 1 | 5606645 | 0 | 0.17 s | 0.05 s | -70.6% | | Linux | 24 | 5606645 | 0 | 1.30 s | 1.28 s | - 1.5% | | Linux | 23 | 5283204 | 323441 | 1.10 s | 0.96 s | -12.7% | | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.05 s | -58.3% | | VSTS | 32 | 4355923 | 0 | 1.34 s | 1.36 s | + 1.5% | | VSTS | 31 | 4276829 | 79094 | 1.34 s | 1.36 s | + 1.5% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 3.08 s
New Time: 2.72 s
Rel %: -11.8--- sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 66 insertions(+), 4 deletions(-)
sha1_name.c +66 -4
@@ -478,6 +478,7 @@ struct min_abbrev_data {unsigned int init_len;unsigned int cur_len;char *hex; +const unsigned char *hash; };static inline char get_hex_char_from_oid (const struct object_id *oid,int i)
@@ -504,6 +505,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)return 0 ; } +static void find_abbrev_len_for_pack (struct packed_git *p, +struct min_abbrev_data *mad) +{ +int match =0 ; +uint32_t num, last, first =0 ; +struct object_id oid; + +open_pack_index (p); + num = p->num_objects; + last = num; +while (first < last) { +uint32_t mid = (first + last) /2 ; +const unsigned char *current; +int cmp; + + current =nth_packed_object_sha1 (p, mid); + cmp =hashcmp (mad->hash, current); +if (!cmp) { + match =1 ; + first = mid; +break ; + } +if (cmp >0 ) { + first = mid +1 ; +continue ; + } + last = mid; + } + +/* +* first is now the position in the packfile where we would insert +* mad->hash if it does not exist (or the position of mad->hash if +* it does exist). Hence, we consider a maximum of three objects +* nearby for the abbreviation length. +*/ + mad->init_len =0 ; +if (!match) { +nth_packed_object_oid (&oid, p, first); +extend_abbrev_len (&oid, mad); + }else if (first < num -1 ) { +nth_packed_object_oid (&oid, p, first +1 ); +extend_abbrev_len (&oid, mad); + } +if (first >0 ) { +nth_packed_object_oid (&oid, p, first -1 ); +extend_abbrev_len (&oid, mad); + } + mad->init_len = mad->cur_len; +} + +static void find_abbrev_len_packed (struct min_abbrev_data *mad) +{ +struct packed_git *p; + +prepare_packed_git (); +for (p = packed_git; p; p = p->next) +find_abbrev_len_for_pack (p, mad); +} +int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) {struct disambiguate_state ds;
@@ -535,19 +595,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)if (len ==GIT_SHA1_HEXSZ || !len)return GIT_SHA1_HEXSZ ; -if (init_object_disambiguation (hex, len, &ds) <0 ) -return -1 ; - mad.init_len = len; mad.cur_len = len; mad.hex = hex; + mad.hash = sha1; + +find_abbrev_len_packed (&mad); + +if (init_object_disambiguation (hex, mad.cur_len, &ds) <0 ) +return -1 ; ds.fn = extend_abbrev_len; ds.always_call_fn =1 ; ds.cb_data = (void *)&mad;find_short_object_filename (&ds); -find_short_packed_object (&ds); (void )finish_object_disambiguation (&ds, &oid_ret); hex[mad.cur_len] =0 ;
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
PATCH v3 1/5 test-list-objects: List a subset of object ids
In reply to Derrick StoleeCreate test-list-objects helper program to output a random sample of OIDs present in the repo.
If no command line arguments are provided, all OIDs are output.
The last command line argument specifies how many samples to output. Samples are collected across the entire set of available OIDs to avoid clustering and therefore quite uniformly distributed.
If a command line argument "--missing" is given before the sample count, then a list of OIDs is generated without examining the repo.
--- Makefile | 1 + t/helper/.gitignore | 1 + t/helper/test-list-objects.c | 87 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 89 insertions(+) create mode 100644 t/helper/test-list-objects.c
Makefile +1 -0
@@ -652,6 +652,7 @@ TEST_PROGRAMS_NEED_X += test-hashmap TEST_PROGRAMS_NEED_X += test-index-version TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash TEST_PROGRAMS_NEED_X += test-line-buffer +TEST_PROGRAMS_NEED_X += test-list-objects TEST_PROGRAMS_NEED_X += test-match-trees TEST_PROGRAMS_NEED_X += test-mergesort TEST_PROGRAMS_NEED_X += test-mktemp
t/helper/.gitignore +1 -0
@@ -13,6 +13,7 @@ /test-index-version /test-lazy-init-name-hash /test-line-buffer +/test-list-objects /test-match-trees /test-mergesort /test-mktemp
t/helper/test-list-objects.c new file +87 -0
87 lines not on this page · raw message
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v3 1/5] test-list-objects: List a subset of object ids
Quoted 1 line · Derrick Stolee
Subject: Re: [PATCH v3 1/5] test-list-objects: List a subset of object ids
Style nit: s/List/list/;
Quoted 2 lines
Signed-off-by Derrick Stolee <[email protected]>
This should stick to the left hand side.
No need to resend, only to fix these two, as I'll tweak them when queuing.
PATCH v3 2/5 p0008-abbrev.sh: Test find_unique_abbrev() perf
In reply to Derrick StoleeCreate helper program test-abbrev to compute the minimum length of a disambiguating short-sha for an input list of object ids.
Perf test p0008-abbrev.sh runs test-abbrev for 100,000 object ids. For test 0008.1, these objects exist. For test 0008.2 these objects do not exist in the repo (with high probability).
--- Makefile | 1 + t/helper/.gitignore | 1 + t/helper/test-abbrev.c | 18 ++++++++++++++++++ t/perf/p0008-abbrev.sh | 22 ++++++++++++++++++++++ 4 files changed, 42 insertions(+) create mode 100644 t/helper/test-abbrev.c create mode 100755 t/perf/p0008-abbrev.sh
Makefile +1 -0
@@ -638,6 +638,7 @@ X = PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS)) +TEST_PROGRAMS_NEED_X += test-abbrev TEST_PROGRAMS_NEED_X += test-chmtime TEST_PROGRAMS_NEED_X += test-ctype TEST_PROGRAMS_NEED_X += test-config
t/helper/.gitignore +1 -0
@@ -1,3 +1,4 @@ +/test-abbrev /test-chmtime /test-ctype /test-config
t/helper/test-abbrev.c new file +18 -0
@@ -0,0 +1,18 @@ +#include "cache.h" + +int cmd_main (int ac,const char **av) +{ +struct object_id oid; +char hex[GIT_MAX_HEXSZ +2 ]; +const char *end; + +setup_git_directory (); + +while (fgets (hex,GIT_MAX_HEXSZ +2 , stdin)) { + hex[GIT_MAX_HEXSZ ] =0 ; +if (!parse_oid_hex (hex, &oid, &end)) +find_unique_abbrev (oid.hash,MINIMUM_ABBREV ); + } + +exit (0 ); +}
t/perf/p0008-abbrev.sh new file +22 -0
@@ -0,0 +1,22 @@ +#!/bin/bash + +test_description='Test object disambiguation through abbreviations' +. ./perf-lib.sh + +test_perf_large_repo + +test-list-objects 100000 > objs.txt + +test_perf 'find_unique_abbrev() for existing objects' ' + test-abbrev < objs.txt +' + +test-list-objects --missing 100000 > objs.txt + +test_perf 'find_unique_abbrev() for missing objects' ' + test-abbrev < objs.txt +' + +rm objs.txt + +test_done
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
v3 cover Improve abbreviation disambituation
In reply to Derrick StoleeThanks for the feedback on my previous versions, and for patience with my inexperience on the mailing list. I tried to respond to all feedback, but decided to not apply one suggestion:
* Removed the "sort -R" from p0008-abbrev.sh, since it is a GNU- specific flag. The perf test now considers objects in "discovery" order, which improved performance all versions of the test as expected. New perf numbers are provided.
* get_hex_char_from_oid(): renamed i to pos. I did not unify the code in this method with that in hex.c:sha1_to_hex_r due to the extra branch in get_hex_char_from_oid and wanting to inline the method. If we want to make this method available for other callers, then I would be happy to submit a separate patch for this change after the current patch is accepted.
* Removed unecessary includes.
* Use uint32_t instead of unsigned int in test-list-objects.c
* Rearranged arguments in test-list-objects and fixed the n == 0 bug.
---
When displaying object ids, we frequently want to see an abbreviation for easier typing. That abbreviation must be unambiguous among all object ids.
The current implementation of find_unique_abbrev() performs a loop checking if each abbreviation length is unambiguous until finding one that works. This causes multiple round-trips to the disk when starting with the default abbreviation length (usually 7) but needing up to 12 characters for an unambiguous short-sha. For very large repos, this effect is pronounced and causes issues with several commands, from obvious consumers status and log to less obvious commands such as fetch and push.
This patch improves performance by iterating over objects matching the short abbreviation only once, inspecting each object id, and reporting the minimum length of an unambiguous abbreviation.
A helper program test-list-objects outputs a sampling of object ids, which we reorder using sort -R before using them as input to a performance test.
A performance helper test-abbrev and performance test p0008-abbrev.sh are added to demonstrate performance improvements in this area.
I include performance test numbers in the commit messages for each change, but I also include the difference between the baseline and the final change here:
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.09 s | 0.05 s | -44.4% | | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | -27.3% | | Git | 4 | 154310 | 75852 | 0.09 s | 0.06 s | -33.3% | | Linux | 1 | 5606645 | 0 | 0.13 s | 0.05 s | -61.5% | | Linux | 24 | 5606645 | 0 | 1.13 s | 0.88 s | -22.1% | | Linux | 23 | 5283204 | 323441 | 1.08 s | 0.80 s | -25.9% | | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.05 s | -58.3% | | VSTS | 32 | 4355923 | 0 | 1.02 s | 0.95 s | - 6.9% | | VSTS | 31 | 4276829 | 79094 | 2.25 s | 1.93 s | -14.2% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 5.69 s
New Time: 4.09 s
Rel %: -28.1%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.66 s | 0.07 s | -89.4% | | Git | 5 | 230162 | 0 | 0.90 s | 0.12 s | -86.7% | | Git | 4 | 154310 | 75852 | 0.79 s | 0.09 s | -88.6% | | Linux | 1 | 5606645 | 0 | 0.48 s | 0.04 s | -91.7% | | Linux | 24 | 5606645 | 0 | 4.41 s | 0.85 s | -80.7% | | Linux | 23 | 5283204 | 323441 | 4.11 s | 0.78 s | -81.0% | | VSTS | 1 | 4355923 | 0 | 0.46 s | 0.04 s | -91.3% | | VSTS | 32 | 4355923 | 0 | 5.40 s | 0.98 s | -81.9% | | VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.04 s | -82.3% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 38.9 s
New Time: 2.7 s
Rel %: -93.1%Derrick Stolee (5):
test-list-objects: List a subset of object ids p0008-abbrev.sh: Test find_unique_abbrev() perf
sha1_name: Unroll len loop in find_unique_abbrev_r
sha1_name: Parse less while finding common prefix
sha1_name: Minimize OID comparisons during disambiguation
Makefile | 2 + sha1_name.c | 129 ++++++++++++++++++++++++++++++++++++++----- t/helper/.gitignore | 2 + t/helper/test-abbrev.c | 18 ++++++ t/helper/test-list-objects.c | 87 +++++++++++++++++++++++++++++ t/perf/p0008-abbrev.sh | 22 ++++++++ 6 files changed, 245 insertions(+), 15 deletions(-) create mode 100644 t/helper/test-abbrev.c create mode 100644 t/helper/test-list-objects.c create mode 100755 t/perf/p0008-abbrev.sh
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v3 0/5] Improve abbreviation disambituation
Quoted 3 lines · Derrick Stolee
Thanks for the feedback on my previous versions, and for patience with my inexperience on the mailing list. I tried to respond to all feedback, but decided to not apply one suggestion:
For what it's worth, the optimizations here look sound overall. Like Junio, I was concerned at the loss of performance from patch 3 at first. After looking at your numbers, though, I think it really is just the cost of oid_to_hex() that is then eliminated in patch 4.
I had a few nits to pick on the perf-test setup, but I stupidly sent them in response to v2 (and so missed cc-ing several folks involved in review). I think they apply equally to v3, though.
-Peff
PATCH v3 3/5 sha1_name: Unroll len loop in find_unique_abbrev_r
In reply to Derrick StoleeUnroll the while loop inside find_unique_abbrev_r to avoid iterating through all loose objects and packfiles multiple times when the short name is longer than the predicted length.
Instead, inspect each object that collides with the estimated abbreviation to find the longest common prefix.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|---------| | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% | | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% | | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% | | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% | | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% | | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% | | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% | | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% | | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 5.69 s
New Time: 4.62 s
Rel %: -18.9%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.66 s | 0.08 s | -87.9% | | Git | 5 | 230162 | 0 | 0.90 s | 0.13 s | -85.6% | | Git | 4 | 154310 | 75852 | 0.79 s | 0.10 s | -87.3% | | Linux | 1 | 5606645 | 0 | 0.48 s | 0.32 s | -33.3% | | Linux | 24 | 5606645 | 0 | 4.41 s | 1.09 s | -75.3% | | Linux | 23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% | | VSTS | 1 | 4355923 | 0 | 0.46 s | 0.25 s | -45.7% | | VSTS | 32 | 4355923 | 0 | 5.40 s | 1.15 s | -78.7% | | VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.18 s | -79.9% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 39.0 s
New Time: 3.9 s
Rel %: -90.0%--- sha1_name.c | 57 ++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 42 insertions(+), 15 deletions(-)
sha1_name.c +42 -15
@@ -474,10 +474,32 @@ static unsigned msb(unsigned long val)return r; } -int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) +struct min_abbrev_data { +unsigned int init_len; +unsigned int cur_len; +char *hex; +}; + +static int extend_abbrev_len (const struct object_id *oid,void *cb_data) { -int status, exists; +struct min_abbrev_data *mad = cb_data; + +char *hex =oid_to_hex (oid); +unsigned int i = mad->init_len; +while (mad->hex[i] && mad->hex[i] == hex[i]) + i++; + +if (i <GIT_MAX_RAWSZ && i >= mad->cur_len) + mad->cur_len = i +1 ; + +return 0 ; +} +int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) +{ +struct disambiguate_state ds; +struct min_abbrev_data mad; +struct object_id oid_ret;if (len <0 ) {unsigned long count =approximate_object_count ();/*
@@ -503,19 +525,24 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)sha1_to_hex_r (hex, sha1);if (len ==GIT_SHA1_HEXSZ || !len)return GIT_SHA1_HEXSZ ; - exists =has_sha1_file (sha1); -while (len <GIT_SHA1_HEXSZ ) { -struct object_id oid_ret; - status =get_short_oid (hex, len, &oid_ret,GET_OID_QUIETLY ); -if (exists - ? !status - : status ==SHORT_NAME_NOT_FOUND ) { - hex[len] =0 ; -return len; - } - len++; - } -return len; + +if (init_object_disambiguation (hex, len, &ds) <0 ) +return -1 ; + + mad.init_len = len; + mad.cur_len = len; + mad.hex = hex; + + ds.fn = extend_abbrev_len; + ds.always_call_fn =1 ; + ds.cb_data = (void *)&mad; + +find_short_object_filename (&ds); +find_short_packed_object (&ds); + (void )finish_object_disambiguation (&ds, &oid_ret); + + hex[mad.cur_len] =0 ; +return mad.cur_len; }const char *find_unique_abbrev (const unsigned char *sha1,int len)
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 6 lines · Derrick Stolee
p0008.1:
find_unique_abbrev()for existing objects
--------------------------------------------------For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
Quoted 12 lines
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|---------| | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% | | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% | | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% | | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% | | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% | | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% | | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% | | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% | | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |
The above does not look so good, especially in cases where a repository is well maintained by packing into smaller number of packs, we get much worse result?
Quoted 6 lines
p0008.2:
find_unique_abbrev()for missing objects
-------------------------------------------------For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
Quoted 12 lines
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.66 s | 0.08 s | -87.9% | | Git | 5 | 230162 | 0 | 0.90 s | 0.13 s | -85.6% | | Git | 4 | 154310 | 75852 | 0.79 s | 0.10 s | -87.3% | | Linux | 1 | 5606645 | 0 | 0.48 s | 0.32 s | -33.3% | | Linux | 24 | 5606645 | 0 | 4.41 s | 1.09 s | -75.3% | | Linux | 23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% | | VSTS | 1 | 4355923 | 0 | 0.46 s | 0.25 s | -45.7% | | VSTS | 32 | 4355923 | 0 | 5.40 s | 1.15 s | -78.7% | | VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.18 s | -79.9% |
The question is if this is even measuring a relevant workload. How often would we have a full 40-hex object name for which we actually do not have the object, and ask its name to be abbreviated?
Compared to it, the result from p0008.1 feels a lot more important. We know we make tons of "abbreviate the object name for this object we have" and we see them every day in our "git log -p" output.
Seeing a lot more impressive result from p0008.2 than p0008.1 makes me unsure if this patch is optimizing for the right case.
I'll have to see the code a bit deeper before I can comment on it.
Thanks.
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 20 lines · Junio C Hamano
Quoted 6 lines · Derrick Stolee
p0008.1:
find_unique_abbrev()for existing objects
--------------------------------------------------For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
Quoted 12 lines
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|---------| | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% | | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% | | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% | | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% | | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% | | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% | | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% | | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% | | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |
Quoted 3 lines
The above does not look so good, especially in cases where a repository is well maintained by packing into smaller number of packs, we get much worse result?
I understand that this patch on its own does not have good numbers. I split the patches 3 and 4 specifically to highlight two distinct changes:
Patch 3: Unroll the len loop that may inspect all files multiple times. Patch 4: Parse less while disambiguating.
Patch 4 more than makes up for the performance hits in this patch.
Quoted 27 lines
Quoted 7 lines
p0008.2:
find_unique_abbrev()for missing objects
-------------------------------------------------For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
Quoted 12 lines
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.66 s | 0.08 s | -87.9% | | Git | 5 | 230162 | 0 | 0.90 s | 0.13 s | -85.6% | | Git | 4 | 154310 | 75852 | 0.79 s | 0.10 s | -87.3% | | Linux | 1 | 5606645 | 0 | 0.48 s | 0.32 s | -33.3% | | Linux | 24 | 5606645 | 0 | 4.41 s | 1.09 s | -75.3% | | Linux | 23 | 5283204 | 323441 | 4.11 s | 0.99 s | -75.9% | | VSTS | 1 | 4355923 | 0 | 0.46 s | 0.25 s | -45.7% | | VSTS | 32 | 4355923 | 0 | 5.40 s | 1.15 s | -78.7% | | VSTS | 31 | 4276829 | 79094 | 5.88 s | 1.18 s | -79.9% |The question is if this is even measuring a relevant workload. How often would we have a full 40-hex object name for which we actually do not have the object, and ask its name to be abbreviated?
Compared to it, the result from p0008.1 feels a lot more important. We know we make tons of "abbreviate the object name for this object we have" and we see them every day in our "git log -p" output.
Quoted 6 lines
Seeing a lot more impressive result from p0008.2 than p0008.1 makes me unsure if this patch is optimizing for the right case.
I'll have to see the code a bit deeper before I can comment on it.
Thanks.
I agree that p0008.1 is more important. p0008.2 covers an important case of the previous implementation. The line
exists = has_sha1_file(sha1);
will inspect all packfiles and scan the full loose-object directory that would contain the object. The only reason for this call is to determine how to inspect the result of get_short_oid(), but is a significant portion of the time that is gained here.
Thanks,
-Stolee
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 26 lines · Derrick Stolee
Quoted 21 lines · Junio C Hamano
Quoted 6 lines · Derrick Stolee
p0008.1:
find_unique_abbrev()for existing objects
--------------------------------------------------For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
Quoted 12 lines
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|---------| | Git | 1 | 230078 | 0 | 0.09 s | 0.06 s | - 33.3% | | Git | 5 | 230162 | 0 | 0.11 s | 0.08 s | - 27.3% | | Git | 4 | 154310 | 75852 | 0.09 s | 0.07 s | - 22.2% | | Linux | 1 | 5606645 | 0 | 0.12 s | 0.32 s | +146.2% | | Linux | 24 | 5606645 | 0 | 1.12 s | 1.12 s | - 0.9% | | Linux | 23 | 5283204 | 323441 | 1.08 s | 1.05 s | - 2.8% | | VSTS | 1 | 4355923 | 0 | 0.12 s | 0.23 s | + 91.7% | | VSTS | 32 | 4355923 | 0 | 1.02 s | 1.08 s | + 5.9% | | VSTS | 31 | 4276829 | 79094 | 2.25 s | 2.08 s | - 7.6% |Quoted 3 lines
The above does not look so good, especially in cases where a repository is well maintained by packing into smaller number of packs, we get much worse result?
Quoted 8 lines
I understand that this patch on its own does not have good numbers. I split the
patches 3 and 4 specifically to highlight two distinct changes:Patch 3: Unroll the len loop that may inspect all files multiple times. Patch 4: Parse less while disambiguating.
Patch 4 more than makes up for the performance hits in this patch.
Now you confused me even more. When we read the similar table that appears in [Patch 4/5], what does the "Base Time" column mean? Vanilla Git with [Patch 3/5] applied? Vanillay Git with [Patch 4/5] alone applied? Something else?
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 6 lines · Junio C Hamano
Derrick Stolee <[email protected]> writes:
...Quoted 4 lines
I understand that this patch on its own does not have good numbers. I split the
patches 3 and 4 specifically to highlight two distinct changes:
Quoted 8 lines
Quoted 4 lines
Patch 3: Unroll the len loop that may inspect all files multiple times. Patch 4: Parse less while disambiguating.
Patch 4 more than makes up for the performance hits in this patch.
Now you confused me even more. When we read the similar table that appears in [Patch 4/5], what does the "Base Time" column mean? Vanilla Git with [Patch 3/5] applied? Vanillay Git with [Patch 4/5] alone applied? Something else?
In PATCH 3, 4, and 5, I used the commit-by-commit diff for the perf numbers, so the "Base Time" for PATCH 4 is the time calculated when PATCH 3 is applied. The table in the [PATCH 0/5] message includes the relative change for all commits.
I recalculated the relative change for each patch related to the baseline (PATCH 2). Looking again, it appears I misspoke and PATCH 4 does include a +8% change for a fully-repacked Linux repo relative to PATCH 2. Since PATCH 5 includes an optimization targeted directly at large packfiles, the final performance gain is significant in the fully-packed cases.
It is also worth looking at the absolute times for these cases, since the fully-packed case is significantly faster than the multiple-packfile case, so the relative change impacts users less.
One final note: the improvement was clearer in test p0008.1 when the test included "sort -R" to shuffle the known OIDs. Providing OIDs in lexicographic order has had a significant effect on the performance, which does not reflect real-world usage. I removed the "sort -R" because it is a GNU-ism, but if there is a good cross-platform alternative I would be happy to replace it.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| Repo | Baseline | Patch 3 | Rel % | Patch 4 | Rel % | Patch 5 | Rel % | |-------|----------|---------|-------|---------|-------|---------|-------| | Git | 0.09 | 0.06 | -33% | 0.05 | -44% | 0.05 | -44% | | Git | 0.11 | 0.08 | -27% | 0.08 | -27% | 0.08 | -27% | | Git | 0.09 | 0.07 | -22% | 0.06 | -33% | 0.06 | -33% | | Linux | 0.13 | 0.32 | 146% | 0.14 | + 8% | 0.05 | -62% | | Linux | 1.13 | 1.12 | - 1% | 0.94 | -17% | 0.88 | -22% | | Linux | 1.08 | 1.05 | - 3% | 0.86 | -20% | 0.80 | -26% | | VSTS | 0.12 | 0.23 | +92% | 0.11 | - 8% | 0.05 | -58% | | VSTS | 1.02 | 1.08 | + 6% | 0.95 | - 7% | 0.95 | - 7% | | VSTS | 2.25 | 2.08 | - 8% | 1.82 | -19% | 1.93 | -14% |
(Each repo has three versions, in order: 1 packfile, multiple packfiles, and multiple packfiles and loose objects.)
Thanks,
-Stolee
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
In reply to Derrick StoleeQuoted 12 lines · Derrick Stolee
sha1_name.c +9
-2-int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) +struct min_abbrev_data { +unsigned int init_len; +unsigned int cur_len; +char *hex; +}; + +static int extend_abbrev_len (const struct object_id *oid,void *cb_data) { -int status, exists; +struct min_abbrev_data *mad = cb_data; +
sha1_name.c static unsigned msb(unsigned long val) · line 496
Quoted 10 lines
sha1_name.c +10
-0+char *hex =oid_to_hex (oid); +unsigned int i = mad->init_len; +while (mad->hex[i] && mad->hex[i] == hex[i]) + i++; + +if (i <GIT_MAX_RAWSZ && i >= mad->cur_len) + mad->cur_len = i +1 ; + +return 0 ; +}
The idea is to keep the target to be abbreviated in mad->hex[], and as the two functions find_short_{object_filename,packed_object} discover objects whose first 'len' letters of hexname are the same as the target, they'd call into the "always_call_fn" callback, which is this function, and it keeps track of the maximum of the common prefix it has seen. Which makes sense. Well, sort of.
sha1_name.c int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) · line 518
Quoted 13 lines
sha1_name.c +0
-13- exists =has_sha1_file (sha1); -while (len <GIT_SHA1_HEXSZ ) { -struct object_id oid_ret; - status =get_short_oid (hex, len, &oid_ret,GET_OID_QUIETLY ); -if (exists - ? !status - : status ==SHORT_NAME_NOT_FOUND ) { - hex[len] =0 ; -return len; - } - len++; - } -return len;
The "always_call_fn" thing is a big sledgehammer that overrides everything else in update_candidates(). It bypasses the careful machinery set up to avoid having to open ambiguous object to learn their types as much as possible. One narrow exception when it is OK to use is if we never limit our candidates with type.
And it might appear that the conversion is safe (if only because we do not see any type limitation in the get_short_oid() call above), but I think there is one case where this patch changes the
behaviour: what happens if core.disambiguate was set to anything other than "none"? The new code does not know anything about type based filtering, so it can end up reporting longer abbreviation than it was asked to produce. It may not be a problem in practice, though.
I am not sure if setting core.disambiguate is generally a good idea in the first place, and if it is OK to break find_unique_abbrev() with respect to the configuration variable like this patch does.
I'd feel safe if we get extra input from Peff, who introduced the feature in 5b33cb1f ("get_short_sha1: make default disambiguation configurable", 2016-09-27).
Quoted 21 lines
sha1_name.c +18
-0+ +if (init_object_disambiguation (hex, len, &ds) <0 ) +return -1 ; + + mad.init_len = len; + mad.cur_len = len; + mad.hex = hex; + + ds.fn = extend_abbrev_len; + ds.always_call_fn =1 ; + ds.cb_data = (void *)&mad; + +find_short_object_filename (&ds); +find_short_packed_object (&ds); + (void )finish_object_disambiguation (&ds, &oid_ret); + + hex[mad.cur_len] =0 ; +return mad.cur_len; }const char *find_unique_abbrev (const unsigned char *sha1,int len)
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 12 lines · Junio C Hamano
Quoted 10 lines · Derrick Stolee
sha1_name.c +0
-10- exists =has_sha1_file (sha1); -while (len <GIT_SHA1_HEXSZ ) { -struct object_id oid_ret; - status =get_short_oid (hex, len, &oid_ret,GET_OID_QUIETLY ); -if (exists - ? !status - : status ==SHORT_NAME_NOT_FOUND ) { - hex[len] =0 ; -return len; - }
Quoted 8 lines
sha1_name.c int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) · line 518
Quoted 3 lines
sha1_name.c +0
-3- len++; - } -return len;The "
always_call_fn" thing is a big sledgehammer that overrides everything else inupdate_candidates(). It bypasses the careful machinery set up to avoid having to open ambiguous object to learn their types as much as possible. One narrow exception when it is OK to use is if we never limit our candidates with type.
I do not modify get_short_oid, which uses these advanced options, depending on the flags given. find_unique_abbrev_r() does not use these advanced options.
Quoted 11 lines
And it might appear that the conversion is safe (if only because we do not see any type limitation in the
get_short_oid()call above), but I think there is one case where this patch changes the
behaviour: what happens if core.disambiguate was set to anything other than "none"? The new code does not know anything about type based filtering, so it can end up reporting longer abbreviation than it was asked to produce. It may not be a problem in practice, though.I am not sure if setting core.disambiguate is generally a good idea in the first place, and if it is OK to break
find_unique_abbrev()with respect to the configuration variable like this patch does.
I do not think that type-aware disambiguation goes through this code path, since it requires giving different parameters to get_short_oid(). Test t1512-rev-parse-disambituagion.sh has a test 'core.disambiguate config can prefer types' that verifies this behavior.
Quoted 3 lines
I'd feel safe if we get extra input from Peff, who introduced the feature in
5b33cb1f("get_short_sha1: make default disambiguation configurable", 2016-09-27).
I look forward to more feedback. Thanks for taking the time to look at my patch series.
Thanks,
-Stolee
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 22 lines · Derrick Stolee
Quoted 12 lines · Junio C Hamano
Quoted 10 lines · Derrick Stolee
sha1_name.c +0
-10- exists =has_sha1_file (sha1); -while (len <GIT_SHA1_HEXSZ ) { -struct object_id oid_ret; - status =get_short_oid (hex, len, &oid_ret,GET_OID_QUIETLY ); -if (exists - ? !status - : status ==SHORT_NAME_NOT_FOUND ) { - hex[len] =0 ; -return len; - }Quoted 8 lines
sha1_name.c int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) · line 518
Quoted 3 lines
sha1_name.c +0
-3- len++; - } -return len;The "
always_call_fn" thing is a big sledgehammer that overrides everything else inupdate_candidates(). It bypasses the careful machinery set up to avoid having to open ambiguous object to learn their types as much as possible. One narrow exception when it is OK to use is if we never limit our candidates with type.
Quoted 3 lines
I do not modify
get_short_oid, which uses these advanced options, depending on the flags given.find_unique_abbrev_r()does not use these advanced options.
It is true that the function no longer even calls get_short_oid().
When it called get_short_oid() before this patch, it not pass "I want to favor committish" in the old code, as we can see in the above removed code. In get_short_oid(), ds.fn would have been set to default_disambigutate_hint, and that would have been used in the update_candidates() function.
Now, unless the user has core.disambiguate configuration set, this "default" thing becomes NULL, so overriding ds.fn like this patch does and bypass major parts of update_candidates() is probably fine. After all, update_candidates() wouldn't have inspected the object types and made the candidate management anyway with ds.fn set to NULL.
But having the configuration set would mean that the user wants to set default_disambigutate_hint to some non-default value, e.g. telling us to find disambiguation only among committishes; the patch however overrides ds.fn and essentially makes the code ignore it altogether, no? That change in behaviour was what I was wondering about.
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
In reply to Junio C HamanoQuoted 28 lines · Junio C Hamano
sha1_name.c int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) · line 518
Quoted 13 lines
sha1_name.c +0
-13- exists =has_sha1_file (sha1); -while (len <GIT_SHA1_HEXSZ ) { -struct object_id oid_ret; - status =get_short_oid (hex, len, &oid_ret,GET_OID_QUIETLY ); -if (exists - ? !status - : status ==SHORT_NAME_NOT_FOUND ) { - hex[len] =0 ; -return len; - } - len++; - } -return len;The "
always_call_fn" thing is a big sledgehammer that overrides everything else inupdate_candidates(). It bypasses the careful machinery set up to avoid having to open ambiguous object to learn their types as much as possible. One narrow exception when it is OK to use is if we never limit our candidates with type.And it might appear that the conversion is safe (if only because we do not see any type limitation in the
get_short_oid()call above), but I think there is one case where this patch changes the
behaviour: what happens if core.disambiguate was set to anything other than "none"? The new code does not know anything about type based filtering, so it can end up reporting longer abbreviation than it was asked to produce. It may not be a problem in practice, though.
Quoted 7 lines
I am not sure if setting core.disambiguate is generally a good idea in the first place, and if it is OK to break
find_unique_abbrev()with respect to the configuration variable like this patch does.I'd feel safe if we get extra input from Peff, who introduced the feature in
5b33cb1f("get_short_sha1: make default disambiguation configurable", 2016-09-27).
Regarding core.disambiguate, I _do_ think it's reasonable to set it to "commit" or "committish". And in fact I have meant to revisit the idea of doing so by default (the reason it was made into config at all was to let people play around with it and gain experience).
That said, I think it's entirely reasonable for find_unique_abbrev() to ignore type-based disambiguation entirely.
The type disambiguation is really a property of the context in which we do a lookup. And that context is not necessarily known to the generating side. Even core.disambiguate is not universal, as command-specific context overrides it.
So I think on the generating side we are better off creating a slightly longer abbreviation that is unambiguous no matter what context it is used in. I.e., I'd argue that it's actually more _correct_ to ignore the disambiguation code entirely on the generating side.
And it should also be faster, because it turns the abbreviation search into a purely textual one that never has to look at extra objects. And that speed matters a lot more on the generating side, where we tend to output long lists of abbreviated sha1s in commands like "git log" (as opposed to the lookup side, where we're asked to find some particular item of interest).
-Peff
Re: [PATCH v3 3/5] sha1_name: Unroll len loop in find_unique_abbrev_r
Quoted 4 lines · Jeff King
So I think on the generating side we are better off creating a slightly longer abbreviation that is unambiguous no matter what context it is used in. I.e., I'd argue that it's actually more _correct_ to ignore the disambiguation code entirely on the generating side.
OK. Thanks for sanity checking.
PATCH v3 4/5 sha1_name: Parse less while finding common prefix
In reply to Derrick StoleeCreate get_hex_char_from_oid() to parse oids one hex character at a time. This prevents unnecessary copying of hex characters in extend_abbrev_len() when finding the length of a common prefix.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.06 s | 0.05 s | -16.7% | | Git | 5 | 230162 | 0 | 0.08 s | 0.08 s | 0.0% | | Git | 4 | 154310 | 75852 | 0.07 s | 0.06 s | -14.3% | | Linux | 1 | 5606645 | 0 | 0.32 s | 0.14 s | -56.3% | | Linux | 24 | 5606645 | 0 | 1.12 s | 0.94 s | -16.1% | | Linux | 23 | 5283204 | 323441 | 1.05 s | 0.86 s | -18.1% | | VSTS | 1 | 4355923 | 0 | 0.23 s | 0.11 s | -52.2% | | VSTS | 32 | 4355923 | 0 | 1.08 s | 0.95 s | -12.0% | | VSTS | 31 | 4276829 | 79094 | 2.08 s | 1.82 s | -12.5% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 4.61 s
New Time: 4.61 s
Rel %: 0.0%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.08 s | 0.07 s | -12.5% | | Git | 5 | 230162 | 0 | 0.13 s | 0.12 s | - 7.7% | | Git | 4 | 154310 | 75852 | 0.10 s | 0.09 s | -10.0% | | Linux | 1 | 5606645 | 0 | 0.32 s | 0.13 s | -59.4% | | Linux | 24 | 5606645 | 0 | 1.09 s | 0.89 s | -18.3% | | Linux | 23 | 5283204 | 323441 | 0.99 s | 0.83 s | -16.2% | | VSTS | 1 | 4355923 | 0 | 0.25 s | 0.11 s | -56.0% | | VSTS | 32 | 4355923 | 0 | 1.15 s | 0.99 s | -13.9% | | VSTS | 31 | 4276829 | 79094 | 1.18 s | 1.02 s | -13.6% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 3.91 s
New Time: 3.08 s
Rel %: -21.1%--- sha1_name.c | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-)
sha1_name.c +12 -2
@@ -480,13 +480,23 @@ struct min_abbrev_data {char *hex; }; +static inline char get_hex_char_from_oid (const struct object_id *oid, +int pos) +{ +static const char hex[] ="0123456789abcdef" ; + +if ((pos &1 ) ==0 ) +return hex[oid->hash[pos >>1 ] >>4 ]; +else +return hex[oid->hash[pos >>1 ] &0xf ]; +} +static int extend_abbrev_len (const struct object_id *oid,void *cb_data) {struct min_abbrev_data *mad = cb_data; -char *hex =oid_to_hex (oid);unsigned int i = mad->init_len; -while (mad->hex[i] && mad->hex[i] == hex[i]) +while (mad->hex[i] && mad->hex[i] ==get_hex_char_from_oid (oid, i)) i++;if (i <GIT_MAX_RAWSZ && i >= mad->cur_len)
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v3 4/5] sha1_name: Parse less while finding common prefix
Quoted 20 lines · Derrick Stolee
sha1_name.c +11
-0@@ -480,13 +480,23 @@ struct min_abbrev_data {char *hex; }; +static inline char get_hex_char_from_oid (const struct object_id *oid, +int pos) +{ +static const char hex[] ="0123456789abcdef" ; + +if ((pos &1 ) ==0 ) +return hex[oid->hash[pos >>1 ] >>4 ]; +else +return hex[oid->hash[pos >>1 ] &0xf ]; +} +
sha1_name.c struct min_abbrev_data { · line 502
Quoted 10 lines
sha1_name.c +1
-2static int extend_abbrev_len (const struct object_id *oid,void *cb_data) {struct min_abbrev_data *mad = cb_data; -char *hex =oid_to_hex (oid);unsigned int i = mad->init_len; -while (mad->hex[i] && mad->hex[i] == hex[i]) +while (mad->hex[i] && mad->hex[i] ==get_hex_char_from_oid (oid, i)) i++;
Assuming that [PATCH 3/5] makes sense, it is an obvious optimization to avoid writing the whole 20-byte out before comparing, and instead to grab hex digits as they become needed.
I assume that the "Base Time" in the log message was with whatever version of Git before [PATCH 3/5] and this one were applied (i.e. not comparing to "vanilla Git plus 3/5")?
Thanks.
PATCH v3 5/5 sha1_name: Minimize OID comparisons during disambiguation
In reply to Derrick StoleeMinimize OID comparisons during disambiguatiosn of packfile OIDs.
Teach git to use binary search with the full OID to find the object's position (or insertion position, if not present) in the pack-index. The object before and immediately after (or the one at the insertion position) give the maximum common prefix. No subsequent linear search is required.
Take care of which two to inspect, in case the object id exists in the packfile.
If the input to find_unique_abbrev_r() is a partial prefix, then the OID used for the binary search is padded with zeroes so the object will not exist in the repo (with high probability) and the same logic applies.
p0008.1: find_unique_abbrev() for existing objects
--------------------------------------------------
For 10 repeated tests, each checking 100,000 known objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.05 s | 0.05 s | 0.0% | | Git | 5 | 230162 | 0 | 0.08 s | 0.08 s | 0.0% | | Git | 4 | 154310 | 75852 | 0.06 s | 0.06 s | 0.0% | | Linux | 1 | 5606645 | 0 | 0.14 s | 0.05 s | -64.3% | | Linux | 24 | 5606645 | 0 | 0.94 s | 0.88 s | - 6.4% | | Linux | 23 | 5283204 | 323441 | 0.86 s | 0.80 s | - 7.0% | | VSTS | 1 | 4355923 | 0 | 0.11 s | 0.05 s | -54.5% | | VSTS | 32 | 4355923 | 0 | 0.95 s | 0.95 s | 0.0% | | VSTS | 31 | 4276829 | 79094 | 1.82 s | 1.93 s | + 6.0% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 4.62 s
New Time: 4.09 s
Rel %: -11.5%p0008.2: find_unique_abbrev() for missing objects
-------------------------------------------------
For 10 repeated tests, each checking 100,000 missing objects, we find the following results when running in a Linux VM:
| | Pack | Packed | Loose | Base | New | | | Repo | Files | Objects | Objects| Time | Time | Rel% | |-------|-------|---------|--------|--------|--------|--------| | Git | 1 | 230078 | 0 | 0.07 s | 0.07 s | 0.0% | | Git | 5 | 230162 | 0 | 0.12 s | 0.12 s | 0.0% | | Git | 4 | 154310 | 75852 | 0.09 s | 0.09 s | 0.0% | | Linux | 1 | 5606645 | 0 | 0.13 s | 0.04 s | -69.2% | | Linux | 24 | 5606645 | 0 | 0.89 s | 0.85 s | - 4.5% | | Linux | 23 | 5283204 | 323441 | 0.83 s | 0.78 s | - 6.0% | | VSTS | 1 | 4355923 | 0 | 0.11 s | 0.04 s | -63.6% | | VSTS | 32 | 4355923 | 0 | 0.99 s | 0.98 s | - 1.0% | | VSTS | 31 | 4276829 | 79094 | 1.02 s | 1.04 s | + 2.0% |
For the Windows repo running in Windows Subsystem for Linux:
Pack Files: 50
Packed Objects: 22,385,898
Loose Objects: 492
Base Time: 3.08 s
New Time: 2.72 s
Rel %: -11.8--- sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 66 insertions(+), 4 deletions(-)
sha1_name.c +66 -4
@@ -478,6 +478,7 @@ struct min_abbrev_data {unsigned int init_len;unsigned int cur_len;char *hex; +const unsigned char *hash; }; static inline char get_hex_char_from_oid(const struct object_id *oid,
@@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)return 0 ; } +static void find_abbrev_len_for_pack (struct packed_git *p, +struct min_abbrev_data *mad) +{ +int match =0 ; +uint32_t num, last, first =0 ; +struct object_id oid; + +open_pack_index (p); + num = p->num_objects; + last = num; +while (first < last) { +uint32_t mid = (first + last) /2 ; +const unsigned char *current; +int cmp; + + current =nth_packed_object_sha1 (p, mid); + cmp =hashcmp (mad->hash, current); +if (!cmp) { + match =1 ; + first = mid; +break ; + } +if (cmp >0 ) { + first = mid +1 ; +continue ; + } + last = mid; + } + +/* +* first is now the position in the packfile where we would insert +* mad->hash if it does not exist (or the position of mad->hash if +* it does exist). Hence, we consider a maximum of three objects +* nearby for the abbreviation length. +*/ + mad->init_len =0 ; +if (!match) { +nth_packed_object_oid (&oid, p, first); +extend_abbrev_len (&oid, mad); + }else if (first < num -1 ) { +nth_packed_object_oid (&oid, p, first +1 ); +extend_abbrev_len (&oid, mad); + } +if (first >0 ) { +nth_packed_object_oid (&oid, p, first -1 ); +extend_abbrev_len (&oid, mad); + } + mad->init_len = mad->cur_len; +} + +static void find_abbrev_len_packed (struct min_abbrev_data *mad) +{ +struct packed_git *p; + +prepare_packed_git (); +for (p = packed_git; p; p = p->next) +find_abbrev_len_for_pack (p, mad); +} +int find_unique_abbrev_r (char *hex,const unsigned char *sha1,int len) {struct disambiguate_state ds;
@@ -536,19 +596,21 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)if (len ==GIT_SHA1_HEXSZ || !len)return GIT_SHA1_HEXSZ ; -if (init_object_disambiguation (hex, len, &ds) <0 ) -return -1 ; - mad.init_len = len; mad.cur_len = len; mad.hex = hex; + mad.hash = sha1; + +find_abbrev_len_packed (&mad); + +if (init_object_disambiguation (hex, mad.cur_len, &ds) <0 ) +return -1 ; ds.fn = extend_abbrev_len; ds.always_call_fn =1 ; ds.cb_data = (void *)&mad;find_short_object_filename (&ds); -find_short_packed_object (&ds); (void )finish_object_disambiguation (&ds, &oid_ret); hex[mad.cur_len] =0 ;
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation
sha1_name.c static int extend_abbrev_len(const struct object_id *oid, void *cb_data) · line 516
Quoted 12 lines
sha1_name.c +8
-0@@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)return 0 ; } +static void find_abbrev_len_for_pack (struct packed_git *p, +struct min_abbrev_data *mad) +{ +int match =0 ; +uint32_t num, last, first =0 ; +struct object_id oid; + +open_pack_index (p);
coverity complained here with
Calling "open_pack_index" without checking return value (as is done elsewhere 13 out of 15 times).
I think the easiest way out is just a
if (open_pack_index(p))
die(_("Cannot open existing pack idx file for '%s'"), p);or is there another good approach?
Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation
Quoted 4 lines · Stefan Beller
Quoted 4 lines
sha1_name.c +0
-0@@ -505,6 +506,65 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)return 0 ; }
Quoted 11 lines
sha1_name.c static int extend_abbrev_len(const struct object_id *oid, void *cb_data) · line 516
Quoted 8 lines
sha1_name.c +8
-0+static void find_abbrev_len_for_pack (struct packed_git *p, +struct min_abbrev_data *mad) +{ +int match =0 ; +uint32_t num, last, first =0 ; +struct object_id oid; + +open_pack_index (p);coverity complained here with
Calling "open_pack_index" without checking return value (as is done elsewhere 13 out of 15 times).
Good catch! This same line is repeated in unique_in_pack() in this same file, so if this is worth fixing then we should probably fix it there, too.
Quoted 6 lines
I think the easiest way out is just a
if (open_pack_index(p)) die(_("Cannot open existing pack idx file for '%s'"), p);or is there another good approach?
You probably intended to have p->pack_name in the die();
Using cat *.c | grep -A 2 "if (open_pack_index(" and cat */*.c | grep -A 2 "if (open_pack_index(" I see a few places that return error codes or quietly fail. The cases that use die() are inside builtin/ so I don't think die() is the right choice here.
Since find_abbrev_len_for_pack() is intended to extend the abbreviation length when necessary, I think a silent return is best here:
if (open_pack_index(p))
return;
Thanks,
-Stolee
Re: [PATCH v3 5/5] sha1_name: Minimize OID comparisons during disambiguation
In reply to Derrick Stoleesha1_name.c static int extend_abbrev_len(const struct object_id *oid, void *cb_data) · line 520
Quoted 12 lines · Derrick Stolee
sha1_name.c +12
-0+static void find_abbrev_len_for_pack (struct packed_git *p, +struct min_abbrev_data *mad) +{ +int match =0 ; +uint32_t num, last, first =0 ; +struct object_id oid; + +open_pack_index (p); + num = p->num_objects; + last = num; +while (first < last) { +uint32_t mid = (first + last) /2 ;
This can overflow if we are looking past 2^31. Probably not very common (things seem to get pretty painful at hundreds of millions of objects). But it can be written as:
uint32_t mid = lo + (hi - lo) / 2;
Sadly, this overflow case seems to be present in many of our binary searches.
sha1_name.c static int extend_abbrev_len(const struct object_id *oid, void *cb_data) · line 524
Quoted 4 lines
sha1_name.c +4
-0+const unsigned char *current; +int cmp; + + current =nth_packed_object_sha1 (p, mid);
nth_packed_object_sha1() has to do some minor computation to come up with the correct pointer. The normal packfile lookup precomputes the initial offset and stride outside the loop. I have no idea if that micro-optimization is actually noticeable, but I thought I'd mention it as a possible avenue for investigation since you're obviously interested in squeezing out performance. ;)
-Peff
PATCH 1/1 cleanup: fix possible overflow errors in binary search
A common mistake when writing binary search is to allow possible integer overflow by using the simple average:
mid = (min + max) / 2;
Instead, use the overflow-safe version:
mid = min + (max - min) / 2;
The included changes were found using the following two greps:
grep "/ 2;" *.c grep "/ 2;" */*.c grep "/2;" */*.c
Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code.
--- builtin/index-pack.c | 4 ++-- builtin/pack-objects.c | 2 +- builtin/unpack-objects.c | 2 +- cache-tree.c | 2 +- packfile.c | 2 +- sha1-lookup.c | 2 +- sha1_name.c | 2 +- string-list.c | 2 +- utf8.c | 2 +- xdiff/xpatience.c | 2 +- 10 files changed, 11 insertions(+), 11 deletions(-)
builtin/index-pack.c +2 -2
@@ -633,7 +633,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)int first =0 , last = nr_ofs_deltas;while (first < last) { -int next = (first + last) /2 ; +int next = first + (last - first) /2 ;struct ofs_delta_entry *delta = &ofs_deltas[next];int cmp;
@@ -687,7 +687,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)int first =0 , last = nr_ref_deltas;while (first < last) { -int next = (first + last) /2 ; +int next = first + (last - first) /2 ;struct ref_delta_entry *delta = &ref_deltas[next];int cmp;
builtin/pack-objects.c +1 -1
@@ -1277,7 +1277,7 @@ static int done_pbase_path_pos(unsigned hash)int lo =0 ;int hi = done_pbase_paths_num;while (lo < hi) { -int mi = (hi + lo) /2 ; +int mi = lo + (hi - lo) /2 ;if (done_pbase_paths[mi] == hash)return mi;if (done_pbase_paths[mi] < hash)
builtin/unpack-objects.c +1 -1
@@ -394,7 +394,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size, lo =0 ; hi = nr;while (lo < hi) { - mid = (lo + hi)/2 ; + mid = lo + (hi - lo) /2 ;if (base_offset < obj_list[mid].offset) { hi = mid; }else if (base_offset > obj_list[mid].offset) {
cache-tree.c +1 -1
@@ -49,7 +49,7 @@ static int subtree_pos(struct cache_tree *it, const char *path, int pathlen) lo =0 ; hi = it->subtree_nr;while (lo < hi) { -int mi = (lo + hi) /2 ; +int mi = lo + (hi - lo) /2 ;struct cache_tree_sub *mdl = down[mi];int cmp =subtree_name_cmp (path, pathlen, mdl->name, mdl->namelen);
packfile.c +1 -1
@@ -1743,7 +1743,7 @@ off_t find_pack_entry_one(const unsigned char *sha1, sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);while (lo < hi) { -unsigned mi = (lo + hi) /2 ; +unsigned mi = lo + (hi - lo) /2 ;int cmp =hashcmp (index + mi * stride, sha1);if (debug_lookup)
sha1-lookup.c +1 -1
@@ -95,7 +95,7 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr, hi = mi; else lo = mi +1 ; - mi = (hi + lo) /2 ; + mi = lo + (hi - lo) /2 ; }while (lo < hi);return -lo-1 ; }
sha1_name.c +1 -1
@@ -157,7 +157,7 @@ static void unique_in_pack(struct packed_git *p, num = p->num_objects; last = num;while (first < last) { -uint32_t mid = (first + last) /2 ; +uint32_t mid = first + (last - first) /2 ;const unsigned char *current;int cmp;
string-list.c +1 -1
@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;while (left +1 < right) { -int middle = (left + right) /2 ; +int middle = left + (right - left) /2 ;int compare =cmp (string, list->items[middle].string);if (compare <0 ) right = middle;
utf8.c +1 -1
@@ -32,7 +32,7 @@ static int bisearch(ucs_char_t ucs, const struct interval *table, int max)if (ucs < table[0 ].first || ucs > table[max].last)return 0 ;while (max >= min) { - mid = (min + max) /2 ; + mid = min + (max - min) /2 ;if (ucs > table[mid].last) min = mid +1 ;else if (ucs < table[mid].first)
xdiff/xpatience.c +1 -1
@@ -166,7 +166,7 @@ static int binary_search(struct entry **sequence, int longest,int left =-1 , right = longest;while (left +1 < right) { -int middle = (left + right) /2 ; +int middle = left + (right - left) /2 ;/* by construction, no two entries can be equal */ if (sequence[middle]->line2 > entry->line2) right = middle;
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH] cleanup: fix possible overflow errors in binary search
Quoted 8 lines · Derrick Stolee
A common mistake when writing binary search is to allow possible integer overflow by using the simple average:
mid = (min + max) / 2;Instead, use the overflow-safe version:
mid = min + (max - min) / 2;
Great, thank you for picking this up!
Quoted 5 lines
The included changes were found using the following two greps:
grep "/ 2;" *.c grep "/ 2;" */*.c grep "/2;" */*.c
You can use[1]:
git grep '/ 2;' '*.c'
to have Git expand the wildcard. That catches a few extra cases in compat/regex/*.c. Even though it's imported code, it might be nice to cover those, too (since it's a possible bug, and also as a good example).
[1] I'd actually write:
git grep '/ *2;' '*.c'
to do it all in one grep. :)
Quoted 4 lines
--- builtin/index-pack.c | 4 ++-- builtin/pack-objects.c | 2 +- builtin/unpack-objects.c | 2 +-
Quoted 8 lines
cache-tree.c | 2 +- packfile.c | 2 +- sha1-lookup.c | 2 +- sha1_name.c | 2 +- string-list.c | 2 +- utf8.c | 2 +- xdiff/xpatience.c | 2 +- 10 files changed, 11 insertions(+), 11 deletions(-)
These all look good to me (really the only way the conversion could be bad is if "min" was higher than "max", and each case is just inside a loop condition which makes sure that is not the case).
-Peff
Re: [PATCH] cleanup: fix possible overflow errors in binary search
Quoted 26 lines · Jeff King
Quoted 8 lines · Derrick Stolee
A common mistake when writing binary search is to allow possible integer overflow by using the simple average:
mid = (min + max) / 2;Instead, use the overflow-safe version:
mid = min + (max - min) / 2;Great, thank you for picking this up!
Quoted 5 lines
The included changes were found using the following two greps:
grep "/ 2;" *.c grep "/ 2;" */*.c grep "/2;" */*.cYou can use[1]:
git grep '/ 2;' '*.c'to have Git expand the wildcard. That catches a few extra cases in compat/regex/*.c. Even though it's imported code, it might be nice to cover those, too (since it's a possible bug, and also as a good example).
Quoted 5 lines
[1] I'd actually write:
git grep '/ *2;' '*.c'
to do it all in one grep. :)
Thanks for the grep lesson! I knew there would be a simpler way to do what I wanted.
Quoted 12 lines
Quoted 4 lines
--- builtin/index-pack.c | 4 ++-- builtin/pack-objects.c | 2 +- builtin/unpack-objects.c | 2 +-Quoted 8 lines
cache-tree.c | 2 +- packfile.c | 2 +- sha1-lookup.c | 2 +- sha1_name.c | 2 +- string-list.c | 2 +- utf8.c | 2 +- xdiff/xpatience.c | 2 +- 10 files changed, 11 insertions(+), 11 deletions(-)
Quoted 5 lines
These all look good to me (really the only way the conversion could be bad is if "min" was higher than "max", and each case is just inside a loop condition which makes sure that is not the case).
-Peff
I thought this should be simple enough. When we are all happy with the idea of this cleanup, I'll re-roll with the missed examples.
Thanks,
-Stolee
PATCH v2 1/1 cleanup: fix possible overflow errors in binary search
A common mistake when writing binary search is to allow possible integer overflow by using the simple average:
mid = (min + max) / 2;
Instead, use the overflow-safe version:
mid = min + (max - min) / 2;
This translation is safe since the operation occurs inside a loop conditioned on "min < max". The included changes were found using the following git grep:
git grep '/ *2;' '*.c'
Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code.
--- builtin/index-pack.c | 4 ++-- builtin/pack-objects.c | 2 +- builtin/unpack-objects.c | 2 +- cache-tree.c | 2 +- compat/regex/regex_internal.c | 4 ++-- compat/regex/regexec.c | 2 +- packfile.c | 2 +- sha1-lookup.c | 4 ++-- sha1_name.c | 2 +- string-list.c | 2 +- utf8.c | 2 +- xdiff/xpatience.c | 2 +- 12 files changed, 15 insertions(+), 15 deletions(-)
builtin/index-pack.c +2 -2
@@ -633,7 +633,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)int first =0 , last = nr_ofs_deltas;while (first < last) { -int next = (first + last) /2 ; +int next = first + (last - first) /2 ;struct ofs_delta_entry *delta = &ofs_deltas[next];int cmp;
@@ -687,7 +687,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)int first =0 , last = nr_ref_deltas;while (first < last) { -int next = (first + last) /2 ; +int next = first + (last - first) /2 ;struct ref_delta_entry *delta = &ref_deltas[next];int cmp;
builtin/pack-objects.c +1 -1
@@ -1277,7 +1277,7 @@ static int done_pbase_path_pos(unsigned hash)int lo =0 ;int hi = done_pbase_paths_num;while (lo < hi) { -int mi = (hi + lo) /2 ; +int mi = lo + (hi - lo) /2 ;if (done_pbase_paths[mi] == hash)return mi;if (done_pbase_paths[mi] < hash)
builtin/unpack-objects.c +1 -1
@@ -394,7 +394,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size, lo =0 ; hi = nr;while (lo < hi) { - mid = (lo + hi)/2 ; + mid = lo + (hi - lo) /2 ;if (base_offset < obj_list[mid].offset) { hi = mid; }else if (base_offset > obj_list[mid].offset) {
cache-tree.c +1 -1
@@ -49,7 +49,7 @@ static int subtree_pos(struct cache_tree *it, const char *path, int pathlen) lo =0 ; hi = it->subtree_nr;while (lo < hi) { -int mi = (lo + hi) /2 ; +int mi = lo + (hi - lo) /2 ;struct cache_tree_sub *mdl = down[mi];int cmp =subtree_name_cmp (path, pathlen, mdl->name, mdl->namelen);
compat/regex/regex_internal.c +2 -2
@@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)int low =0 , high = pstr->valid_len, mid; do { - mid = (high + low) / 2; + mid = low + (high - low) / 2; if (pstr->offsets[mid] > offset) high = mid; else if (pstr->offsets[mid] < offset)
@@ -1394,7 +1394,7 @@ re_node_set_contains (const re_node_set *set, int elem) right = set->nelem -1 ;while (idx < right) { - mid = (idx + right) /2 ; + mid = idx + (right - idx) /2 ;if (set->elems[mid] < elem) idx = mid +1 ;else
compat/regex/regexec.c +1 -1
@@ -4284,7 +4284,7 @@ search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx) last = right = mctx->nbkref_ents;for (left =0 ; left < right;) { - mid = (left + right) /2 ; + mid = left + (right - left) /2 ;if (mctx->bkref_ents[mid].str_idx < str_idx) left = mid +1 ;else
packfile.c +1 -1
@@ -1743,7 +1743,7 @@ off_t find_pack_entry_one(const unsigned char *sha1, sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);while (lo < hi) { -unsigned mi = (lo + hi) /2 ; +unsigned mi = lo + (hi - lo) /2 ;int cmp =hashcmp (index + mi * stride, sha1);if (debug_lookup)
sha1-lookup.c +2 -2
@@ -10,7 +10,7 @@ static uint32_t take2(const unsigned char *sha1)* Conventional binary search loop looks like this: * * do { -* int mi = (lo + hi) / 2; +* int mi = lo + (hi - lo) / 2; * int cmp = "entry pointed at by mi" minus "target"; * if (!cmp) * return (mi is the wanted one)
@@ -95,7 +95,7 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr, hi = mi; else lo = mi +1 ; - mi = (hi + lo) /2 ; + mi = lo + (hi - lo) /2 ; }while (lo < hi);return -lo-1 ; }
sha1_name.c +1 -1
@@ -157,7 +157,7 @@ static void unique_in_pack(struct packed_git *p, num = p->num_objects; last = num;while (first < last) { -uint32_t mid = (first + last) /2 ; +uint32_t mid = first + (last - first) /2 ;const unsigned char *current;int cmp;
string-list.c +1 -1
@@ -16,7 +16,7 @@ static int get_entry_index(const struct string_list *list, const char *string,compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;while (left +1 < right) { -int middle = (left + right) /2 ; +int middle = left + (right - left) /2 ;int compare =cmp (string, list->items[middle].string);if (compare <0 ) right = middle;
utf8.c +1 -1
@@ -32,7 +32,7 @@ static int bisearch(ucs_char_t ucs, const struct interval *table, int max)if (ucs < table[0 ].first || ucs > table[max].last)return 0 ;while (max >= min) { - mid = (min + max) /2 ; + mid = min + (max - min) /2 ;if (ucs > table[mid].last) min = mid +1 ;else if (ucs < table[mid].first)
xdiff/xpatience.c +1 -1
@@ -166,7 +166,7 @@ static int binary_search(struct entry **sequence, int longest,int left =-1 , right = longest;while (left +1 < right) { -int middle = (left + right) /2 ; +int middle = left + (right - left) /2 ;/* by construction, no two entries can be equal */ if (sequence[middle]->line2 > entry->line2) right = middle;
Signature · 1 line
2.14.1.538.g56ec8fc98.dirty
Re: [PATCH v2] cleanup: fix possible overflow errors in binary search
Quoted 9 lines · Derrick Stolee
A common mistake when writing binary search is to allow possible integer overflow by using the simple average:
mid = (min + max) / 2;Instead, use the overflow-safe version:
mid = min + (max - min) / 2;
Quoted 8 lines
This translation is safe since the operation occurs inside a loop conditioned on "min < max". The included changes were found using the following git grep:
git grep '/ *2;' '*.c'Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code.
Thanks, this version looks good to me.
compat/regex/regex_internal.c re_string_reconstruct (re_string_t *pstr, int idx, int eflags) · line 619
Quoted 13 lines
compat/regex/regex_internal.c +1
-1@@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)int low =0 , high = pstr->valid_len, mid; do { - mid = (high + low) / 2; + mid = low + (high - low) / 2; if (pstr->offsets[mid] > offset) high = mid; else if (pstr->offsets[mid] < offset)
This one is a do-while, so it's less obvious that "high" is always more than "low" when entering the loop. But one assumes it is so, since the binary search wouldn't work otherwise.
-Peff