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. On 9/25/2017 7:42 PM, Stefan Beller wrote: On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stoleewrote: Create 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% These number look pretty cool! Signed-off-by: Derrick Stolee Signed-off-by: Derrick Stolee double signoff? Oops! I'll be more careful with my format-patch in the future. --- sha1_name.c | 13 +++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/sha1_name.c b/sha1_name.c index f2a1ebe49..bb47b6702 100644 --- a/sha1_name.c +++ b/sha1_name.c @@ -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) I renamed 'i' to 'pos' in my v3. 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? +{ + 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. 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
Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix
On Mon, Sep 25, 2017 at 2:54 AM, Derrick Stoleewrote: > Create 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% > These number look pretty cool! > Signed-off-by: Derrick Stolee > > Signed-off-by: Derrick Stolee double signoff? > --- > sha1_name.c | 13 +++-- > 1 file changed, 11 insertions(+), 2 deletions(-) > > diff --git a/sha1_name.c b/sha1_name.c > index f2a1ebe49..bb47b6702 100644 > --- a/sha1_name.c > +++ b/sha1_name.c > @@ -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? > +{ > + 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.
[PATCH v2 4/5] sha1_name: Parse less while finding common prefix
Create 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% Signed-off-by: Derrick StoleeSigned-off-by: Derrick Stolee --- sha1_name.c | 13 +++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/sha1_name.c b/sha1_name.c index f2a1ebe49..bb47b6702 100644 --- a/sha1_name.c +++ b/sha1_name.c @@ -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) -- 2.14.1.538.g56ec8fc98.dirty