From patchwork Tue May 21 13:14:38 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10953667 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 614BE912 for ; Tue, 21 May 2019 13:14:45 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4F79B28917 for ; Tue, 21 May 2019 13:14:45 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 434D22892E; Tue, 21 May 2019 13:14:45 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3279C28917 for ; Tue, 21 May 2019 13:14:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727976AbfEUNOn (ORCPT ); Tue, 21 May 2019 09:14:43 -0400 Received: from mail-qt1-f196.google.com ([209.85.160.196]:33442 "EHLO mail-qt1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726900AbfEUNOn (ORCPT ); Tue, 21 May 2019 09:14:43 -0400 Received: by mail-qt1-f196.google.com with SMTP id m32so20413821qtf.0 for ; Tue, 21 May 2019 06:14:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=bo6+nAk3HIYXNvpDEC1RBfLG4a5FXhdsvfem9qD1vrs=; b=Z8/hckITV3kDHgvGFotcfAb6rV9EYVMNzBI82yYoYeX2OeWgiggq0LExI+KNZE21Sx vPra+6j2C25jMOtyGojOimimIhm4/b8Z4sbvczbr7mIKhP73ELOav/hVANn6E096tmXU 667EiEN9Reetye3ZpsSLjN45eph1DMcSUMdyLAHmsm1Xyx73Yfrfv8vpyv1bwVlq3UoC GcYWHW3aSZvWeQzr9Dc8Nwm8beCKZvkr4LlkQ78fNchiZ8Jrf3mjyiaAU1h5l8pmZPTO BJ4wC0m9AaPny0ViSj91bnaIrczf6wcrOG560nKNwmRJD3aRfMAZDNBOvJADpg222teZ 9DNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=bo6+nAk3HIYXNvpDEC1RBfLG4a5FXhdsvfem9qD1vrs=; b=gfnVjbfgcjjQ0qfcvg+yjbwHB9IPp+UgWugHYPq38jaOS//tx9i7hLvSoFNSSXSion 8NJykW3dGqODnPTiPPf20hnAqEzSa4lTl5t1KwHIB/Q3urpdoHqBhNSdpaDgxCK7rRqw FTa1aYJSZ/aFhxLB0D/gF130qDvYIJeaVQ9hW4+QhHoqX6pQJdGYQtdB6pcamLc93c53 MqGoF/TcLC5EkOxFo1Zwwo7ntR1z0u2T6xnfD4Za6u7vgJofO7uLSmUDJ9s7OxwAH+3H Bat7BghWJ+4hIvo0UHthKwrKWvBmTEgPpXXLY3Tm9shbNoZ8qFKZgBIjELVrS1BzfkMI r3TA== X-Gm-Message-State: APjAAAWPs4WKNV6QbSHKGe+HiqcGwM1fT8pXbvgRLdTd4awn+t3FD/BW 5VmYDggodAB//J1U19F/J0jdxzlGTv4= X-Google-Smtp-Source: APXvYqwvjudRRr1KlfIJIvgoI9lOpegYHdiLdlyqPzrOfhWVecHeW3dUc758H/DhulTkWaz0M7WpCA== X-Received: by 2002:ac8:3316:: with SMTP id t22mr2341461qta.383.1558444481811; Tue, 21 May 2019 06:14:41 -0700 (PDT) Received: from stolee-gitdev.corp.microsoft.com ([2001:4898:a800:1012:223c:4c6c:142a:3ad0]) by smtp.gmail.com with ESMTPSA id j26sm13964812qtj.70.2019.05.21.06.14.40 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 21 May 2019 06:14:40 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: szeder.dev@gmail.com, jnareb@gmail.com, jrnieder@google.com, mh@glandium.org, Derrick Stolee Subject: [PATCH] revision: use generation for A..B --topo-order queries Date: Tue, 21 May 2019 09:14:38 -0400 Message-Id: <20190521131438.58394-1-dstolee@microsoft.com> X-Mailer: git-send-email 2.22.0.rc1 In-Reply-To: References: MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP If a commit-graph exists with computed generation numbers, then a 'git rev-list --topo-order -n ' query will use those generation numbers to reduce the number of commits walked before writing N commits. One caveat put in b454241 (revision.c: generation-based topo-order algorithm, 2018-11-01) was to not enable the new algorithm for queries with a revision range "A..B". The logic was placed to walk from "A" and mark those commits as uninteresting, but the performance was actually worse than the existing logic in some cases. The root cause of this performance degradation is that generation numbers _increase_ the number of commits we walk relative to the existing heuristic of walking by commit date. While generation numbers actually guarantee that the algorithm is correct, the existing logic is very rarely wrong and that added requirement is not worth the cost. This motivates the planned "corrected commit date" to replace generation numbers in a future version of Git. The current change enables the logic to use whatever reachability index is currently in the commit-graph (generation numbers or corrected commit date). The limited flag in struct rev_info forces a full walk of the commit history (after discovering the A..B range). Previosuly, it is enabled whenever we see an uninteresting commit. We prevent enabling the parameter when we are planning to use the reachability index for a topo-order. Signed-off-by: Derrick Stolee --- Mike, If you have the chance, then please apply this patch (on v2.22.0-rc1) and re-run your test. This will confirm if my thoughts on this matter are correct. Thanks, -Stolee revision.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/revision.c b/revision.c index d4aaf0ef25..be6ccf5786 100644 --- a/revision.c +++ b/revision.c @@ -436,7 +436,9 @@ static struct commit *handle_commit(struct rev_info *revs, die("unable to parse commit %s", name); if (flags & UNINTERESTING) { mark_parents_uninteresting(commit); - revs->limited = 1; + + if (!revs->topo_order || !generation_numbers_enabled(the_repository)) + revs->limited = 1; } if (revs->sources) { char **slot = revision_sources_at(revs->sources, commit); From patchwork Tue May 21 13:59:53 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 10953835 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 3F24813AD for ; Tue, 21 May 2019 14:00:00 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2E6DA285D1 for ; Tue, 21 May 2019 14:00:00 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 21B0428A4E; Tue, 21 May 2019 14:00:00 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AE419285D1 for ; Tue, 21 May 2019 13:59:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728104AbfEUN76 (ORCPT ); Tue, 21 May 2019 09:59:58 -0400 Received: from mail-qt1-f194.google.com ([209.85.160.194]:37171 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727624AbfEUN76 (ORCPT ); Tue, 21 May 2019 09:59:58 -0400 Received: by mail-qt1-f194.google.com with SMTP id o7so20591686qtp.4 for ; Tue, 21 May 2019 06:59:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=oHb7X4cWwIHpQUPeiijK/av/imXGErm757kJh/gLRdo=; b=ud5rqpFcyBIUikGqfu7wclSd6vl4k3f3lq5h/nWXOrVtpi0T74xbUhF5g4W49QwDQ3 PxKhgOc8zsUPhhf+Tque8QJC3a9VLZqpIqsnAN3DYzdo6meR2wAq5tr3sblMGYTWuyc7 ki0yxEpwlG9FOaPHYGog6rx3ZqDjewSgxajWP7Oygs3sjJ4vgrSRP4pLqKR7MhdoQ/H4 /N+S6vetdP8jdzRPbu4kTbSTSh377cLYRBK3Nw/SNlnu2fsrIH2t7+dTR8FSKhjyWUBE CKco9rwtqMzSKyz7LyUJ//SsRJl4O4Zg0WEtse22+oSv1mhIttnJ+97+Vydw4gliioUx wzIQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=oHb7X4cWwIHpQUPeiijK/av/imXGErm757kJh/gLRdo=; b=rZjZh4J9YbTekUfjfnvig/Aqj7nONQ77S0U/gvQ8sotNuV5oj8YYta1aGV9P4rpLG4 WLBLVL7NOjtFMvscZ7RIZAQpnImB9j20sjzLlse3HRujClW0nxz046HWjMWsTBekfQAK xgCuOTfWNegTzDJ5ntyo4phA8zOHA8EgYZ5OkaEmNJITdbez8UcPpUHek12s3llbmQBm vVCNgsNwWBIg6Jx7xaQbMrfPzLsJIIPJDa2juTbed2TBbj66cKQ7jj7wbrTVjD/U1ET2 AYldHg2G2rOIoZ6GL87g161oJdOdbsGYndkPsQiTSmsg6EQu7+JN4d6eS1ORrdWdhdpE 9TdA== X-Gm-Message-State: APjAAAWEPG/256OmZcnFU2OCJkUVQI4KzUZurYOWMT67XEuU/hk2LB3H uZvSVTUTFiLN8hLRqfUODdLzQNim6e4= X-Google-Smtp-Source: APXvYqzvOa0rZGAZYPNlL5VA7LYL2Ikk0HkBsWbTZ2wme8vahiEfhqcIpNEeYls1hGVWd0ZUUxknAw== X-Received: by 2002:aed:224e:: with SMTP id o14mr68681883qtc.271.1558447197269; Tue, 21 May 2019 06:59:57 -0700 (PDT) Received: from stolee-gitdev.corp.microsoft.com ([2001:4898:a800:1010:223e:4c6c:142a:3ad0]) by smtp.gmail.com with ESMTPSA id c32sm6837891qtd.61.2019.05.21.06.59.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 21 May 2019 06:59:56 -0700 (PDT) From: Derrick Stolee X-Google-Original-From: Derrick Stolee To: git@vger.kernel.org Cc: jnareb@gmail.com, jrnieder@google.com, szeder.dev@gmail.com, mh@glandium.org, Derrick Stolee Subject: [PATCH 2/2] revision: keep topo-walk free of unintersting commits Date: Tue, 21 May 2019 09:59:53 -0400 Message-Id: <20190521135953.214701-1-dstolee@microsoft.com> X-Mailer: git-send-email 2.22.0.rc1 In-Reply-To: <20190521131438.58394-1-dstolee@microsoft.com> References: <20190521131438.58394-1-dstolee@microsoft.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP When updating the topo-order walk in b454241 (revision.c: generation-based topo-order algorithm, 2018-11-01), the logic was a huge rewrite of the walk logic. In that massive change, we accidentally included the UNINTERESTING commits in expand_topo_walk(). This means that a simple query like git rev-list --topo-order HEAD~1..HEAD will expand the topo walk for all commits reachable from HEAD, and not just one commit. This change should speed up these cases, but there is still a need for corrected commit-date for some A..B queries. Signed-off-by: Derrick Stolee --- Sorry for the patch-spam, but I took a moment to check this command on the Git repo, and was able to reproduce the slowness. That didn't make sense to me, so I added some log messages to expand_topo_walk() and notices we were walking the UNINITERESTING commits. This is part of the reason the new logic is slower for A..B commands, but not the whole reason. You'll want this patch as well for a test. Thanks, -Stolee revision.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/revision.c b/revision.c index be6ccf5786..621feb9df7 100644 --- a/revision.c +++ b/revision.c @@ -3265,6 +3265,9 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit) struct commit *parent = p->item; int *pi; + if (parent->object.flags & UNINTERESTING) + continue; + if (parse_commit_gently(parent, 1) < 0) continue;