From: Derrick Stolee Date: Mon, 02 Oct 2017 14:52:38 GMT Subject: Re: [PATCH v2 4/5] sha1_name: Parse less while finding common prefix Message-ID: In-Reply-To: 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 Stolee wrote: >> 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 disambiguation. Thanks, -Stolee