| Message ID | b3272f499e51cfc53345f9f09f8762db1a4cf0a6.1624858240.git.ps@pks.im (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Speed up connectivity checks via bitmaps | expand |
On Mon, Jun 28 2021, Patrick Steinhardt wrote: > [[PGP Signed Part:Undecided]] > In the case where git-receive-pack(1) receives only commands which > delete references, then per technical specification the client MUST NOT > send a packfile. As a result, we know that no new objects have been > received, which makes it a moot point to check whether all received > objects are fully connected. Is it just per specification, or do we also have assertions/tests for what happens in that case? > [...] > The following tests were executed on linux.git and back up above > expectation: > > Test origin/master HEAD > --------------------------------------------------------------------------------------------------------- > 5400.4: empty receive-pack updated:new 178.36(428.22+164.36) 177.62(421.33+164.48) -0.4% > 5400.7: clone receive-pack updated:new 0.10(0.08+0.02) 0.10(0.08+0.02) +0.0% > 5400.9: clone receive-pack updated:main 0.10(0.08+0.02) 0.11(0.08+0.02) +10.0% > 5400.11: clone receive-pack main~10:main 0.15(0.11+0.04) 0.15(0.10+0.05) +0.0% > 5400.13: clone receive-pack :main 0.01(0.00+0.01) 0.01(0.01+0.00) +0.0% > 5400.16: clone_bitmap receive-pack updated:new 0.10(0.07+0.02) 0.09(0.06+0.02) -10.0% > 5400.18: clone_bitmap receive-pack updated:main 0.10(0.07+0.02) 0.10(0.08+0.02) +0.0% > 5400.20: clone_bitmap receive-pack main~10:main 0.15(0.11+0.03) 0.15(0.12+0.03) +0.0% > 5400.22: clone_bitmap receive-pack :main 0.02(0.01+0.01) 0.01(0.00+0.00) -50.0% > 5400.25: extrarefs receive-pack updated:new 32.34(20.72+11.86) 32.56(20.82+11.95) +0.7% > 5400.27: extrarefs receive-pack updated:main 32.42(21.02+11.61) 32.52(20.64+12.10) +0.3% > 5400.29: extrarefs receive-pack main~10:main 32.53(20.74+12.01) 32.39(20.63+11.97) -0.4% > 5400.31: extrarefs receive-pack :main 7.13(3.53+3.59) 7.15(3.80+3.34) +0.3% > 5400.34: extrarefs_bitmap receive-pack updated:new 32.55(20.72+12.04) 32.65(20.68+12.18) +0.3% > 5400.36: extrarefs_bitmap receive-pack updated:main 32.50(20.90+11.86) 32.67(20.93+11.94) +0.5% > 5400.38: extrarefs_bitmap receive-pack main~10:main 32.43(20.88+11.75) 32.35(20.68+11.89) -0.2% > 5400.40: extrarefs_bitmap receive-pack :main 7.21(3.58+3.63) 7.18(3.61+3.57) -0.4% We're doing less work so I'd expect to te be faster, but do these tests really back that up? From eyeballing these I can't find a line where the confidence intervals don't overlap, e.g. the +10% regresison is a .10->.11 "regression" with a [+-] 0.02 (so within the error bars) etc, ditto for the -50% improvement. Perhaps the error bars will reduce with a high GIT_PERF_REPEAT_COUNT, or the re-arrangement for keeping things hotter in cache that I suggested in 1/3.
On Mon, Jun 28 2021, Ævar Arnfjörð Bjarmason wrote: > On Mon, Jun 28 2021, Patrick Steinhardt wrote: > >> [[PGP Signed Part:Undecided]] >> In the case where git-receive-pack(1) receives only commands which >> delete references, then per technical specification the client MUST NOT >> send a packfile. As a result, we know that no new objects have been >> received, which makes it a moot point to check whether all received >> objects are fully connected. > > Is it just per specification, or do we also have assertions/tests for > what happens in that case? > >> [...] >> The following tests were executed on linux.git and back up above >> expectation: >> >> Test origin/master HEAD >> --------------------------------------------------------------------------------------------------------- >> 5400.4: empty receive-pack updated:new 178.36(428.22+164.36) 177.62(421.33+164.48) -0.4% >> 5400.7: clone receive-pack updated:new 0.10(0.08+0.02) 0.10(0.08+0.02) +0.0% >> 5400.9: clone receive-pack updated:main 0.10(0.08+0.02) 0.11(0.08+0.02) +10.0% >> 5400.11: clone receive-pack main~10:main 0.15(0.11+0.04) 0.15(0.10+0.05) +0.0% >> 5400.13: clone receive-pack :main 0.01(0.00+0.01) 0.01(0.01+0.00) +0.0% >> 5400.16: clone_bitmap receive-pack updated:new 0.10(0.07+0.02) 0.09(0.06+0.02) -10.0% >> 5400.18: clone_bitmap receive-pack updated:main 0.10(0.07+0.02) 0.10(0.08+0.02) +0.0% >> 5400.20: clone_bitmap receive-pack main~10:main 0.15(0.11+0.03) 0.15(0.12+0.03) +0.0% >> 5400.22: clone_bitmap receive-pack :main 0.02(0.01+0.01) 0.01(0.00+0.00) -50.0% >> 5400.25: extrarefs receive-pack updated:new 32.34(20.72+11.86) 32.56(20.82+11.95) +0.7% >> 5400.27: extrarefs receive-pack updated:main 32.42(21.02+11.61) 32.52(20.64+12.10) +0.3% >> 5400.29: extrarefs receive-pack main~10:main 32.53(20.74+12.01) 32.39(20.63+11.97) -0.4% >> 5400.31: extrarefs receive-pack :main 7.13(3.53+3.59) 7.15(3.80+3.34) +0.3% >> 5400.34: extrarefs_bitmap receive-pack updated:new 32.55(20.72+12.04) 32.65(20.68+12.18) +0.3% >> 5400.36: extrarefs_bitmap receive-pack updated:main 32.50(20.90+11.86) 32.67(20.93+11.94) +0.5% >> 5400.38: extrarefs_bitmap receive-pack main~10:main 32.43(20.88+11.75) 32.35(20.68+11.89) -0.2% >> 5400.40: extrarefs_bitmap receive-pack :main 7.21(3.58+3.63) 7.18(3.61+3.57) -0.4% > > We're doing less work so I'd expect to te be faster, but do these tests > really back that up? From eyeballing these I can't find a line where the > confidence intervals don't overlap, e.g. the +10% regresison is a > .10->.11 "regression" with a [+-] 0.02 (so within the error bars) etc, > ditto for the -50% improvement. > > Perhaps the error bars will reduce with a high GIT_PERF_REPEAT_COUNT, or > the re-arrangement for keeping things hotter in cache that I suggested > in 1/3. Urgh, nevermind. Just after I sent this I re-read t/perf/README. I'd somehow recalled that we'd emit error bars from it, but that's Elapsed(User + System), not Time(.. + errorbar) as I thought, nevermind. Still, numbers are such that I wonder if the differences are getting lost in some noise...
On Mon, Jun 28, 2021 at 10:00:26AM +0200, Ævar Arnfjörð Bjarmason wrote: > > On Mon, Jun 28 2021, Patrick Steinhardt wrote: > > > [[PGP Signed Part:Undecided]] > > In the case where git-receive-pack(1) receives only commands which > > delete references, then per technical specification the client MUST NOT > > send a packfile. As a result, we know that no new objects have been > > received, which makes it a moot point to check whether all received > > objects are fully connected. > > Is it just per specification, or do we also have assertions/tests for > what happens in that case? I'm not sure whether we have any tests for this, but I've seen several hangs already in case the server did expect a packfile or errors in case the client sent one. In any case, the technical specification in Documentation/technical/pack-protocol.txt is quite clear on this: The packfile MUST NOT be sent if the only command used is 'delete'. > > [...] > > The following tests were executed on linux.git and back up above > > expectation: > > > > Test origin/master HEAD > > --------------------------------------------------------------------------------------------------------- > > 5400.4: empty receive-pack updated:new 178.36(428.22+164.36) 177.62(421.33+164.48) -0.4% > > 5400.7: clone receive-pack updated:new 0.10(0.08+0.02) 0.10(0.08+0.02) +0.0% > > 5400.9: clone receive-pack updated:main 0.10(0.08+0.02) 0.11(0.08+0.02) +10.0% > > 5400.11: clone receive-pack main~10:main 0.15(0.11+0.04) 0.15(0.10+0.05) +0.0% > > 5400.13: clone receive-pack :main 0.01(0.00+0.01) 0.01(0.01+0.00) +0.0% > > 5400.16: clone_bitmap receive-pack updated:new 0.10(0.07+0.02) 0.09(0.06+0.02) -10.0% > > 5400.18: clone_bitmap receive-pack updated:main 0.10(0.07+0.02) 0.10(0.08+0.02) +0.0% > > 5400.20: clone_bitmap receive-pack main~10:main 0.15(0.11+0.03) 0.15(0.12+0.03) +0.0% > > 5400.22: clone_bitmap receive-pack :main 0.02(0.01+0.01) 0.01(0.00+0.00) -50.0% > > 5400.25: extrarefs receive-pack updated:new 32.34(20.72+11.86) 32.56(20.82+11.95) +0.7% > > 5400.27: extrarefs receive-pack updated:main 32.42(21.02+11.61) 32.52(20.64+12.10) +0.3% > > 5400.29: extrarefs receive-pack main~10:main 32.53(20.74+12.01) 32.39(20.63+11.97) -0.4% > > 5400.31: extrarefs receive-pack :main 7.13(3.53+3.59) 7.15(3.80+3.34) +0.3% > > 5400.34: extrarefs_bitmap receive-pack updated:new 32.55(20.72+12.04) 32.65(20.68+12.18) +0.3% > > 5400.36: extrarefs_bitmap receive-pack updated:main 32.50(20.90+11.86) 32.67(20.93+11.94) +0.5% > > 5400.38: extrarefs_bitmap receive-pack main~10:main 32.43(20.88+11.75) 32.35(20.68+11.89) -0.2% > > 5400.40: extrarefs_bitmap receive-pack :main 7.21(3.58+3.63) 7.18(3.61+3.57) -0.4% > > We're doing less work so I'd expect to te be faster, but do these tests > really back that up? From eyeballing these I can't find a line where the > confidence intervals don't overlap, e.g. the +10% regresison is a > .10->.11 "regression" with a [+-] 0.02 (so within the error bars) etc, > ditto for the -50% improvement. > > Perhaps the error bars will reduce with a high GIT_PERF_REPEAT_COUNT, or > the re-arrangement for keeping things hotter in cache that I suggested > in 1/3. As I've layed out in the commit message, all we save now is spawning git-rev-list(1). The command list iterator which is used to feed data into git-rev-list(1) wouldn't provide any references given that it skips over all queued updates whose new OID is the null OID. So git-rev-list(1) doesn't receive any input except `--not --all` and thus can exit without doing a graph walk. Above numbers simply show that this saving is not significant and gets lost in the noise, at least on Linux. Windows may show slightly different numbers given that spawning of processes is slower there, but I don't expect it to matter much there, either. Patrick
On Mon, Jun 28, 2021 at 07:33:11AM +0200, Patrick Steinhardt wrote: > Fix this by not doing a connectivity check in case there were no pushed > objects. Given that git-rev-walk(1) with only negative references will > not do any graph walk, no performance improvements are to be expected. > Conceptionally, it is still the right thing to do though. Even though it's not producing any exciting results, I agree this is still a reasonable thing to do. I'm actually surprised it didn't help in your many-ref cases, just because I think the traversal machinery is pretty eager to parse tags and commits which are fed as tips. If I run "git rev-list --not --all --stdin </dev/null" in linux.git, it takes about 35ms. But if I make a ton of refs, like: git rev-list HEAD | perl -lpe 's{.*}{update refs/foo/commit$. $&}' | git update-ref --stdin git pack-refs --all --prune then it takes about 2000ms (if you don't pack it's even worse, as you might expect). So how come we don't see that improvement in your "extrarefs" cases? Looking at patch 1, they also seem to make one ref for every commit. I think the answer may be below... > + /* > + * If received commands only consist of deletions, then the client MUST > + * NOT send a packfile because there cannot be any new objects in the > + * first place. As a result, we do not set up a quarantine environment > + * because we know no new objects will be received. And that in turn > + * means that we can skip connectivity checks here. > + */ > + if (tmp_objdir) { I think this will work, but we're now making assumptions about how tmp_objdir will be initialized by the rest of the code. Could we make a more direct check of: skip calling rev-list if we have no positive tips to feed? If we call iterate_receive_command() and it returns end-of-list on the first call, then we know there is nothing to feed (and as a bonus, this catches some more noop cases around shallow repos; see iterate_receive_command). But that made me think that check_connected() could be doing this itself. And indeed, it seems to already. At the top of that function is: if (fn(cb_data, &oid)) { if (opt->err_fd) close(opt->err_fd); return err; } So before we even spawn rev-list, if there's nothing to feed it, we'll return right away ("err" will be "0" at this point). And I think that has been there since the beginning of the function (it is even in the old versions in builtin/fetch.c before it was factored out). And that explains why you didn't see any performance improvement. We're already doing this optimization. :) -Peff
On Tue, Jun 29, 2021 at 09:31:59PM -0400, Jeff King wrote: > If I run "git rev-list --not --all --stdin </dev/null" in linux.git, it > takes about 35ms. But if I make a ton of refs, like: The "--stdin" should be before "--not", of course, to mimic a real connectivity check. But it doesn't matter in this case because we're feeding an empty input. :) -Peff
On Tue, Jun 29, 2021 at 09:31:59PM -0400, Jeff King wrote: > On Mon, Jun 28, 2021 at 07:33:11AM +0200, Patrick Steinhardt wrote: > > > Fix this by not doing a connectivity check in case there were no pushed > > objects. Given that git-rev-walk(1) with only negative references will > > not do any graph walk, no performance improvements are to be expected. > > Conceptionally, it is still the right thing to do though. > > Even though it's not producing any exciting results, I agree this is > still a reasonable thing to do. > > I'm actually surprised it didn't help in your many-ref cases, just > because I think the traversal machinery is pretty eager to parse tags > and commits which are fed as tips. > > If I run "git rev-list --not --all --stdin </dev/null" in linux.git, it > takes about 35ms. But if I make a ton of refs, like: > > git rev-list HEAD | > perl -lpe 's{.*}{update refs/foo/commit$. $&}' | > git update-ref --stdin > git pack-refs --all --prune > > then it takes about 2000ms (if you don't pack it's even worse, as you > might expect). > > So how come we don't see that improvement in your "extrarefs" cases? > Looking at patch 1, they also seem to make one ref for every commit. > > I think the answer may be below... > > > + /* > > + * If received commands only consist of deletions, then the client MUST > > + * NOT send a packfile because there cannot be any new objects in the > > + * first place. As a result, we do not set up a quarantine environment > > + * because we know no new objects will be received. And that in turn > > + * means that we can skip connectivity checks here. > > + */ > > + if (tmp_objdir) { > > I think this will work, but we're now making assumptions about how > tmp_objdir will be initialized by the rest of the code. > > Could we make a more direct check of: skip calling rev-list if we have > no positive tips to feed? If we call iterate_receive_command() and it > returns end-of-list on the first call, then we know there is nothing to > feed (and as a bonus, this catches some more noop cases around shallow > repos; see iterate_receive_command). > > But that made me think that check_connected() could be doing this > itself. And indeed, it seems to already. At the top of that function is: > > if (fn(cb_data, &oid)) { > if (opt->err_fd) > close(opt->err_fd); > return err; > } > > So before we even spawn rev-list, if there's nothing to feed it, we'll > return right away ("err" will be "0" at this point). And I think that > has been there since the beginning of the function (it is even in the > old versions in builtin/fetch.c before it was factored out). > > And that explains why you didn't see any performance improvement. We're > already doing this optimization. :) > > -Peff Hah, thanks for solving this riddle. I always kind of wondered what this was supposed to do, where my assumption simply was "It's in case the callback returns an error". But your explanation is obviously correct and neatly explains what's going on. So yes, I'll drop this patch. Patrick
diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c index a34742513a..b9263cec15 100644 --- a/builtin/receive-pack.c +++ b/builtin/receive-pack.c @@ -1918,11 +1918,8 @@ static void execute_commands(struct command *commands, struct shallow_info *si, const struct string_list *push_options) { - struct check_connected_options opt = CHECK_CONNECTED_INIT; struct command *cmd; struct iterate_data data; - struct async muxer; - int err_fd = 0; int run_proc_receive = 0; if (unpacker_error) { @@ -1931,25 +1928,39 @@ static void execute_commands(struct command *commands, return; } - if (use_sideband) { - memset(&muxer, 0, sizeof(muxer)); - muxer.proc = copy_to_sideband; - muxer.in = -1; - if (!start_async(&muxer)) - err_fd = muxer.in; - /* ...else, continue without relaying sideband */ - } - data.cmds = commands; data.si = si; - opt.err_fd = err_fd; - opt.progress = err_fd && !quiet; - opt.env = tmp_objdir_env(tmp_objdir); - if (check_connected(iterate_receive_command_list, &data, &opt)) - set_connectivity_errors(commands, si); - if (use_sideband) - finish_async(&muxer); + /* + * If received commands only consist of deletions, then the client MUST + * NOT send a packfile because there cannot be any new objects in the + * first place. As a result, we do not set up a quarantine environment + * because we know no new objects will be received. And that in turn + * means that we can skip connectivity checks here. + */ + if (tmp_objdir) { + struct check_connected_options opt = CHECK_CONNECTED_INIT; + struct async muxer; + int err_fd = 0; + + if (use_sideband) { + memset(&muxer, 0, sizeof(muxer)); + muxer.proc = copy_to_sideband; + muxer.in = -1; + if (!start_async(&muxer)) + err_fd = muxer.in; + /* ...else, continue without relaying sideband */ + } + + opt.err_fd = err_fd; + opt.progress = err_fd && !quiet; + opt.env = tmp_objdir_env(tmp_objdir); + if (check_connected(iterate_receive_command_list, &data, &opt)) + set_connectivity_errors(commands, si); + + if (use_sideband) + finish_async(&muxer); + } reject_updates_to_hidden(commands);
In the case where git-receive-pack(1) receives only commands which delete references, then per technical specification the client MUST NOT send a packfile. As a result, we know that no new objects have been received, which makes it a moot point to check whether all received objects are fully connected. Fix this by not doing a connectivity check in case there were no pushed objects. Given that git-rev-walk(1) with only negative references will not do any graph walk, no performance improvements are to be expected. Conceptionally, it is still the right thing to do though. The following tests were executed on linux.git and back up above expectation: Test origin/master HEAD --------------------------------------------------------------------------------------------------------- 5400.4: empty receive-pack updated:new 178.36(428.22+164.36) 177.62(421.33+164.48) -0.4% 5400.7: clone receive-pack updated:new 0.10(0.08+0.02) 0.10(0.08+0.02) +0.0% 5400.9: clone receive-pack updated:main 0.10(0.08+0.02) 0.11(0.08+0.02) +10.0% 5400.11: clone receive-pack main~10:main 0.15(0.11+0.04) 0.15(0.10+0.05) +0.0% 5400.13: clone receive-pack :main 0.01(0.00+0.01) 0.01(0.01+0.00) +0.0% 5400.16: clone_bitmap receive-pack updated:new 0.10(0.07+0.02) 0.09(0.06+0.02) -10.0% 5400.18: clone_bitmap receive-pack updated:main 0.10(0.07+0.02) 0.10(0.08+0.02) +0.0% 5400.20: clone_bitmap receive-pack main~10:main 0.15(0.11+0.03) 0.15(0.12+0.03) +0.0% 5400.22: clone_bitmap receive-pack :main 0.02(0.01+0.01) 0.01(0.00+0.00) -50.0% 5400.25: extrarefs receive-pack updated:new 32.34(20.72+11.86) 32.56(20.82+11.95) +0.7% 5400.27: extrarefs receive-pack updated:main 32.42(21.02+11.61) 32.52(20.64+12.10) +0.3% 5400.29: extrarefs receive-pack main~10:main 32.53(20.74+12.01) 32.39(20.63+11.97) -0.4% 5400.31: extrarefs receive-pack :main 7.13(3.53+3.59) 7.15(3.80+3.34) +0.3% 5400.34: extrarefs_bitmap receive-pack updated:new 32.55(20.72+12.04) 32.65(20.68+12.18) +0.3% 5400.36: extrarefs_bitmap receive-pack updated:main 32.50(20.90+11.86) 32.67(20.93+11.94) +0.5% 5400.38: extrarefs_bitmap receive-pack main~10:main 32.43(20.88+11.75) 32.35(20.68+11.89) -0.2% 5400.40: extrarefs_bitmap receive-pack :main 7.21(3.58+3.63) 7.18(3.61+3.57) -0.4% Signed-off-by: Patrick Steinhardt <ps@pks.im> --- builtin/receive-pack.c | 49 ++++++++++++++++++++++++++---------------- 1 file changed, 30 insertions(+), 19 deletions(-)