From patchwork Mon Feb 1 12:47:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12058955 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id DF9E9C433DB for ; Mon, 1 Feb 2021 12:48:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9DBF164EA2 for ; Mon, 1 Feb 2021 12:48:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231462AbhBAMsP (ORCPT ); Mon, 1 Feb 2021 07:48:15 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35096 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231145AbhBAMsL (ORCPT ); Mon, 1 Feb 2021 07:48:11 -0500 Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DE139C06174A for ; Mon, 1 Feb 2021 04:47:30 -0800 (PST) Received: by mail-wr1-x430.google.com with SMTP id l12so16446224wry.2 for ; Mon, 01 Feb 2021 04:47:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=D5QXzi/cbFOuguGsQb1Cl9Xqof6bgvqas9cgqXBJIbE=; b=gNvTB9NXTkQ87goJ38Yc4Sa5puLCjRECAbZ6kZXh2w9fR5/oTmIsuNJ30HAhUQB0Mg BibjMrdhpzRcob9QQY4S937RrjEjYvjS6JXdCOjM3cnPj78gva0sKJHaP7jA5weby4i1 H2C4azKEKUErUE14UuZanZpMy/VVOc35AAx+4ctgz/bZonaXiWb5Ld2Tihq6o1oo+Awb icFucZFVyUEjiz6jttqiObXVFhjJqqDdeuzUb7mQ+2SvGjRCZcVaO/Pqb2BENcuZqETu w2b/OZLFF0TGEmnQYEgN/URaDbV1PKegvMmmxjN+jHU93s/oMmI0mtKjadzsVIK4syi4 U7NA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=D5QXzi/cbFOuguGsQb1Cl9Xqof6bgvqas9cgqXBJIbE=; b=tBdBLUJg0WUZ5il7NiKhVz7VZ72TTXR51S79ccVJ5j9yxeQnurhUAlLV79IDaF3Q3E rNcJK1tURMrKf1siwLrRZh/WeH2QJ2nfT+PqexuTskiQ17LCa5wnY/8+BYH6RDH078Qr 7+t826lGObIuj0DqZMWyyfzzUQV2rcxvTWAXqo/pvdhfF36ylC2PWPYLU8gRYWsEijUs YMYPUIxdwWbfOE35frb4VMDW0tLjFLaqKOWfGHnw61OwIgEIfGAeAQKVHOP5rUKpfWBQ 9wrm3rIr3ER9diqNQyAoA2+4rowsTiNZxjIF+aqA6r+pe9+3WeHN0Tk/CJufKQnSNWGB 0qmA== X-Gm-Message-State: AOAM5300f/1v+AaQMhJvDpNbOvcBTt2lxsf0dz4oOLACJaASnXNRB6+E gW2kfwRV+vntjJv2ZotCiDKEUJJac2c= X-Google-Smtp-Source: ABdhPJymU7oiY2Tlo+yhsO011rbSXxXV4ijPI/DVaRHscdpPyXcBIkFJ/uTa7Q58w+RLh9DD4ri9qw== X-Received: by 2002:adf:a2ca:: with SMTP id t10mr17844805wra.370.1612183649518; Mon, 01 Feb 2021 04:47:29 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id r12sm26914534wrp.13.2021.02.01.04.47.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Feb 2021 04:47:29 -0800 (PST) Message-Id: <649f6799e6bfa0662ed5a4debf915053598fe142.1612183647.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 01 Feb 2021 12:47:23 +0000 Subject: [PATCH v2 1/5] commit-reach: reduce requirements for remove_redundant() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Michael Haggerty , me@ttaylorr.com, peff@peff.net, gitster@pobox.com, =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee Remove a comment at the beggining of remove_redundant() that mentions a reordering of the input array to have the initial segment be the independent commits and the final segment be the redundant commits. While this behavior is followed in remove_redundant(), no callers rely on that behavior. Remove the final loop that copies this final segment and update the comment to match the new behavior. Signed-off-by: Derrick Stolee --- commit-reach.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index e38771ca5a1..9af51fe7e07 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -160,9 +160,10 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt { /* * Some commit in the array may be an ancestor of - * another commit. Move such commit to the end of - * the array, and return the number of commits that - * are independent from each other. + * another commit. Move the independent commits to the + * beginning of 'array' and return their number. Callers + * should not rely upon the contents of 'array' after + * that number. */ struct commit **work; unsigned char *redundant; @@ -209,9 +210,6 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt for (i = filled = 0; i < cnt; i++) if (!redundant[i]) array[filled++] = work[i]; - for (j = filled, i = 0; i < cnt; i++) - if (redundant[i]) - array[j++] = work[i]; free(work); free(redundant); free(filled_index); From patchwork Mon Feb 1 12:47:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12058961 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1927BC433E6 for ; Mon, 1 Feb 2021 12:48:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C04B764EA5 for ; Mon, 1 Feb 2021 12:48:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231475AbhBAMsQ (ORCPT ); Mon, 1 Feb 2021 07:48:16 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35102 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231308AbhBAMsM (ORCPT ); Mon, 1 Feb 2021 07:48:12 -0500 Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 18128C061756 for ; Mon, 1 Feb 2021 04:47:32 -0800 (PST) Received: by mail-wr1-x429.google.com with SMTP id q7so16397925wre.13 for ; Mon, 01 Feb 2021 04:47:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=McEu39H+C/Qincvr1lZST/EZjVZrFbTYDM7C70uLiZE=; b=AWnZr0hpBDh1cJdoUJD7SMZjQJ3Noeg5HeoFhEBL78zPx50WgLk2JhFEQC1kCpGuCH MMiIP0JyZtqPr6pNPhjPpfD2+YlJiZAmDKLsPsKK21Xyuq28jSSx1BKxbbICiweT1Xdp VRRrHtaSZZ0/Bkkbw9F/kAwwyocSi/UAwBnm/38FF8iYrp9zqnEsFtq7wwNYjxQa25p1 TdLOtqPnWrq4hrZIHdBGlTDy2hBw/ZI2YzBZrs6Ef8ZIq/RFQJc9Q09yt1U8RTJT8drT X7fA8eyPwYULmQh2cq4M4/vwvJ7p9vGsE59l59Zf106EcIhkdxREFDjeEHSR2Zezxvir /ulQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=McEu39H+C/Qincvr1lZST/EZjVZrFbTYDM7C70uLiZE=; b=ECK2t2nKbYK0f3pIJiXPZn1AlbMWQwYaqVoBuLXcBy0x59oBjVQBUJxu22e2KlWj4p AlHM1EHLg3P1+xY1rDTupZeG23ymMn6M9JqSn970jBazxTArrAlQUMvf1Jw4MAMpTLyC ybI7ZgcmGgEQ5aQMyUxgBTj+Ryuoib7+txKp5U6GuVR104c5ua1Qc/bZGZBokgZruAQm cefb2UfDRkZYwHBDBB3Oz0gbh2/F/lEhXFNUOYaLljR0smRyLfVfffJKu1Lm6vjlZjxT pKFxlOlsY4DFegRJ316Z9PR8OTxZwCyM9Af75E06dTnnNo4TixI6ez1k3oPBZ2P3mSqR 73OQ== X-Gm-Message-State: AOAM533nxryqUbV8eb8DvU4upYd6bCij1Stpp0YUx3Ci3OgPWva36Jzt NMgEZn1h2s71qZIyXid8M/HjaTVYLkQ= X-Google-Smtp-Source: ABdhPJwdookc+TEStyQwt8cFz33yT+SiULKnGY3fzAdJTEKmZNvYkCZGI74URPzhgkSMZ7LwdFfaVw== X-Received: by 2002:adf:ee0d:: with SMTP id y13mr18111948wrn.228.1612183650540; Mon, 01 Feb 2021 04:47:30 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id m22sm27509884wrh.66.2021.02.01.04.47.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Feb 2021 04:47:29 -0800 (PST) Message-Id: <2f80ae5fcb00d9d5c1b0502af45921cb20ebdf94.1612183647.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 01 Feb 2021 12:47:24 +0000 Subject: [PATCH v2 2/5] commit-reach: use one walk in remove_redundant() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Michael Haggerty , me@ttaylorr.com, peff@peff.net, gitster@pobox.com, =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The current implementation of remove_redundant() uses several calls to paint_down_to_common() to determine that commits are independent of each other. This leads to quadratic behavior when many inputs are passed to commands such as 'git merge-base'. For example, in the Linux kernel repository, I tested the performance by passing all tags: git merge-base --independent $(git for-each-ref refs/tags --format="$(refname)") (Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do not point to commits.) Here is the performance improvement introduced by this change: Before: 16.4s After: 1.1s This performance improvement requires the commit-graph file to be present. We keep the old algorithm around as remove_redundant_no_gen() and use it when generation_numbers_enabled() is false. This is similar to other algorithms within commit-reach.c. The new algorithm is implemented in remove_redundant_with_gen(). The basic approach is to do one commit walk instead of many. First, scan all commits in the list and mark their _parents_ with the STALE flag. This flag will indicate commits that are reachable from one of the inputs, except not including themselves. Then, walk commits until covering all commits up to the minimum generation number pushing the STALE flag throughout. At the end, we need to clear the STALE bit from all of the commits we walked. We move the non-stale commits in 'array' to the beginning of the list, and this might overwrite stale commits. However, we store an array of commits that started the walk, and use clear_commit_marks() on each of those starting commits. That method will walk the reachable commits with the STALE bit and clear them all. This makes the algorithm safe for re-entry or for other uses of those commits after this walk. This logic is covered by tests in t6600-test-reach.sh, so the behavior does not change. This is tested both in the case with a commit-graph and without. Signed-off-by: Derrick Stolee --- commit-reach.c | 108 +++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 100 insertions(+), 8 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 9af51fe7e07..053676e51d0 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -156,15 +156,9 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in) return ret; } -static int remove_redundant(struct repository *r, struct commit **array, int cnt) +static int remove_redundant_no_gen(struct repository *r, + struct commit **array, int cnt) { - /* - * Some commit in the array may be an ancestor of - * another commit. Move the independent commits to the - * beginning of 'array' and return their number. Callers - * should not rely upon the contents of 'array' after - * that number. - */ struct commit **work; unsigned char *redundant; int *filled_index; @@ -210,12 +204,110 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt for (i = filled = 0; i < cnt; i++) if (!redundant[i]) array[filled++] = work[i]; + for (j = filled, i = 0; i < cnt; i++) + if (redundant[i]) + array[j++] = work[i]; free(work); free(redundant); free(filled_index); return filled; } +static int remove_redundant_with_gen(struct repository *r, + struct commit **array, int cnt) +{ + int i, count_non_stale = 0; + timestamp_t min_generation = GENERATION_NUMBER_INFINITY; + struct commit **walk_start; + size_t walk_start_nr = 0, walk_start_alloc = cnt; + struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; + + ALLOC_ARRAY(walk_start, walk_start_alloc); + + /* Mark all parents of the input as STALE */ + for (i = 0; i < cnt; i++) { + struct commit_list *parents; + timestamp_t generation; + + repo_parse_commit(r, array[i]); + parents = array[i]->parents; + + while (parents) { + repo_parse_commit(r, parents->item); + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc); + walk_start[walk_start_nr++] = parents->item; + prio_queue_put(&queue, parents->item); + } + parents = parents->next; + } + + generation = commit_graph_generation(array[i]); + + if (generation < min_generation) + min_generation = generation; + } + + /* push the STALE bits up to min generation */ + while (queue.nr) { + struct commit_list *parents; + struct commit *c = prio_queue_get(&queue); + + repo_parse_commit(r, c); + + if (commit_graph_generation(c) < min_generation) + continue; + + parents = c->parents; + while (parents) { + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + prio_queue_put(&queue, parents->item); + } + parents = parents->next; + } + } + + /* rearrange array */ + for (i = count_non_stale = 0; i < cnt; i++) { + if (!(array[i]->object.flags & STALE)) + array[count_non_stale++] = array[i]; + } + + /* clear marks */ + for (i = 0; i < walk_start_nr; i++) + clear_commit_marks(walk_start[i], STALE); + free(walk_start); + + return count_non_stale; +} + +static int remove_redundant(struct repository *r, struct commit **array, int cnt) +{ + /* + * Some commit in the array may be an ancestor of + * another commit. Move the independent commits to the + * beginning of 'array' and return their number. Callers + * should not rely upon the contents of 'array' after + * that number. + */ + if (generation_numbers_enabled(r)) { + int i; + + /* + * If we have a single commit with finite generation + * number, then the _with_gen algorithm is preferred. + */ + for (i = 0; i < cnt; i++) { + if (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY) + return remove_redundant_with_gen(r, array, cnt); + } + } + + return remove_redundant_no_gen(r, array, cnt); +} + static struct commit_list *get_merge_bases_many_0(struct repository *r, struct commit *one, int n, From patchwork Mon Feb 1 12:47:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12058959 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 31EC8C433E9 for ; Mon, 1 Feb 2021 12:48:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E5CF864D9E for ; Mon, 1 Feb 2021 12:48:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231486AbhBAMsS (ORCPT ); Mon, 1 Feb 2021 07:48:18 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35108 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231443AbhBAMsN (ORCPT ); Mon, 1 Feb 2021 07:48:13 -0500 Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 09D6FC0613D6 for ; Mon, 1 Feb 2021 04:47:33 -0800 (PST) Received: by mail-wr1-x430.google.com with SMTP id c12so16428217wrc.7 for ; Mon, 01 Feb 2021 04:47:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=UFgqZr9rawQ7Afq2fqGeJV+gn8BBK9vi8PqUK9wxD7Q=; b=raLvy1jxuiHcrRgowewubCvNmRYyndJbO5d5kx/lE1/uW+waqIsNeuBwI64EUj/5bc JThVMYEnqaxvYmJH53gAToduj0av8SJXKkoxCYMS2Z12uOmgLLMaoYsyvySuPmgEOYvT F24wxq1b+NM8b1TG+wxrp9FHE9QPFWyRnzAG92xIwJRKONr+pW7SxvpgaTizcYkbdwAc GoVyds870L8uVceZ0SMq619szjF3lpULfufMZRUA6lwuPVRcT1WgZ0Z/fL4QxZaq6ltv QsvqRHXIYVGx4Ep2aOyXyrb72mbcns+htR4jm7YBZenW2tStndVdD3VyGOsOWNzJNpWt reAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=UFgqZr9rawQ7Afq2fqGeJV+gn8BBK9vi8PqUK9wxD7Q=; b=q6hyDue/ZCPVOeBKW3WmkF3DiCElMyV5wl1JPhT1Fg/mzhmupSBHgjHAfwiSro1KRU 9DMoYMbpL8VNyyTJHiWSlr+LTpCMDIqqRamljjO6bxlZGwOZa7K3+W3NayKUV1VhM/Oa mJftubW1EpNQyaK69e8oGwE6NkvpWvUilLrV7Y2RdgDJoNf0Jh/RDVGQSmAJNPJOQal5 aL+rZ0ncShNNE2YfoG+wja/T+pXZsv+f7AsAcoR/u4BTuUrycCosBxv/WAr3BGAVgSPP TU9nHP999oD6ou6AZfz+EEFYgsJ/pOPqYMdQaIGYzaTy3VcbqmrdbP8HM0uw2xJL6eTM 6JCw== X-Gm-Message-State: AOAM530ctIJv7MB/gwK89nbJG95ZRJtp/7GU/pIotnRsQEG2jXLU7MB8 nZ42Sn5MXU32u/h+Gbyh5XKZL0Ng70o= X-Google-Smtp-Source: ABdhPJxRWVe74/ulerE4X7x4dJtboQWcPtfRc9o4bXArUb1ELn2QvO6YJKqxYnsUILugBE1xpqAF4w== X-Received: by 2002:a5d:4f87:: with SMTP id d7mr17682272wru.385.1612183651657; Mon, 01 Feb 2021 04:47:31 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i6sm27554257wrs.71.2021.02.01.04.47.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Feb 2021 04:47:31 -0800 (PST) Message-Id: <009f64b53c9567a94a52d1607e3ea0456776c9e1.1612183647.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 01 Feb 2021 12:47:25 +0000 Subject: [PATCH v2 3/5] commit-reach: move compare_commits_by_gen Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Michael Haggerty , me@ttaylorr.com, peff@peff.net, gitster@pobox.com, =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee Move this earlier in the file so it can be used by more methods. Signed-off-by: Derrick Stolee --- commit-reach.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 053676e51d0..7bf52e94429 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -17,6 +17,21 @@ static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT); +static int compare_commits_by_gen(const void *_a, const void *_b) +{ + const struct commit *a = *(const struct commit * const *)_a; + const struct commit *b = *(const struct commit * const *)_b; + + timestamp_t generation_a = commit_graph_generation(a); + timestamp_t generation_b = commit_graph_generation(b); + + if (generation_a < generation_b) + return -1; + if (generation_a > generation_b) + return 1; + return 0; +} + static int queue_has_nonstale(struct prio_queue *queue) { int i; @@ -651,21 +666,6 @@ int commit_contains(struct ref_filter *filter, struct commit *commit, return repo_is_descendant_of(the_repository, commit, list); } -static int compare_commits_by_gen(const void *_a, const void *_b) -{ - const struct commit *a = *(const struct commit * const *)_a; - const struct commit *b = *(const struct commit * const *)_b; - - timestamp_t generation_a = commit_graph_generation(a); - timestamp_t generation_b = commit_graph_generation(b); - - if (generation_a < generation_b) - return -1; - if (generation_a > generation_b) - return 1; - return 0; -} - int can_all_from_reach_with_flag(struct object_array *from, unsigned int with_flag, unsigned int assign_flag, From patchwork Mon Feb 1 12:47:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12058963 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id DD606C43381 for ; Mon, 1 Feb 2021 12:48:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B111664E9E for ; Mon, 1 Feb 2021 12:48:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231490AbhBAMs0 (ORCPT ); Mon, 1 Feb 2021 07:48:26 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35116 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231464AbhBAMsP (ORCPT ); Mon, 1 Feb 2021 07:48:15 -0500 Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B9357C0613ED for ; Mon, 1 Feb 2021 04:47:34 -0800 (PST) Received: by mail-wm1-x32d.google.com with SMTP id j18so12540905wmi.3 for ; Mon, 01 Feb 2021 04:47:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=TD3YqiwIGUfhzShNQFKZ9Adltf/LTAg7dpgLfajJDA4=; b=Y0cTRo6fyfjuwzMx4fLm1JyPO2N8r8IrdEBMtGAARW2c5M3utDC0IafDFpTaeQB3/A 66QEovnb8sF1BHOT/Dk4kTS+CKZuQFGNmqhxCdCposZFQuk5rTEL9rCJpXcD7rPEB/ru gmjW5crIFJMEPU94DpwfEeTz/O0iHMzQnKsaXl/OlbHwDct7XGpZ7KL1y1ZMOEM7gw5j MfchbjMcPg4JCapTWfC+YsZ/7BSK3bX1QjvgltG67qzfy755mHbkcLlhhX8iouZ3jLB+ GL3ZfMYuItF2n0iiKpjgt/vfOptH2W2kemiIqrnLwLNO1Q/oR7XaRVcaDGICAgX6SrXo uIWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=TD3YqiwIGUfhzShNQFKZ9Adltf/LTAg7dpgLfajJDA4=; b=NubnjFI+uyKSIxJR/4Ns42duA5MTh+Ny19Bc5P932Du9srCHbvCbToUrWHbw/nawMH jGGxl9FzAdh+DbunkXxso532W859kdpvnGcDZQ+gJc9aoRlnXBJsCV9+WmMutVlxho4Q //j6sA39O7AUGnlrt4Skd82VjOZxe55NxRnyeOV1YAPjq5bvwqSM6TbLAHZJVEfnoPcw fe0JIrJRojp0HrJZCs85Dua47t/df/gZDFh5KcMxX9VmhCLOKH1fqQaB1+PVR6Bh/+lS 4SL8Ckd3gnkR3rzjQgq2DN50qCuXTAqrf1h8zsSy0PbBo/hi5PPqO82nuYLAaQYNZC0u d25Q== X-Gm-Message-State: AOAM531QiETBe1EahzQQydyeLES3xOgrJ1sZBfgtaNYbt0k9AcZjvP4M 1t7+C9XGH9rZifLbrDFQ+0U2+9mVCvY= X-Google-Smtp-Source: ABdhPJxHnkW9MO6uTS8xs6LPShNpXqQAqP93cchGq6IAo7t6kldfQpIsLyNiZb5aN1hl5nnW4J+pRw== X-Received: by 2002:a1c:ba44:: with SMTP id k65mr5409936wmf.25.1612183652581; Mon, 01 Feb 2021 04:47:32 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id y67sm21716433wmg.47.2021.02.01.04.47.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Feb 2021 04:47:32 -0800 (PST) Message-Id: <83feabeebb5f035059758fba1ca5cf74f3a22c91.1612183647.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 01 Feb 2021 12:47:26 +0000 Subject: [PATCH v2 4/5] commit-reach: use heuristic in remove_redundant() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Michael Haggerty , me@ttaylorr.com, peff@peff.net, gitster@pobox.com, =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee Reachability algorithms in commit-reach.c frequently benefit from using the first-parent history as a heuristic for satisfying reachability queries. The most obvious example was implemented in 4fbcca4e (commit-reach: make can_all_from_reach... linear, 2018-07-20). Update the walk in remove_redundant() to use this same heuristic. Here, we are walking starting at the parents of the input commits. Sort those parents and walk from the highest generation to lower. Each time, use the heuristic of searching the first parent history before continuing to expand the walk. The order in which we explore the commits matters, so update compare_commits_by_gen to break generation number ties with commit date. This has no effect when the commits are in a commit-graph file with corrected commit dates computed, but it will assist when the commits are in the region "above" the commit-graph with "infinite" generation number. Note that we cannot shift to use compare_commits_by_gen_then_commit_date as the method prototype is different. We use compare_commits_by_gen for QSORT() as opposed to as a priority function. The important piece is to ensure we short-circuit the walk when we find that there is a single non-redundant commit. This happens frequently when looking for merge-bases or comparing several tags with 'git merge-base --independent'. Use a new count 'count_still_independent' and if that hits 1 we can stop walking. To update 'count_still_independent' properly, we add use of the RESULT flag on the input commits. Then we can detect when we reach one of these commits and decrease the count. We need to remove the RESULT flag at that moment because we might re-visit that commit when popping the stack. We use the STALE flag to mark parents that have been added to the new walk_start list, but we need to clear that flag before we start walking so those flags don't halt our depth-first-search walk. On my copy of the Linux kernel repository, the performance of 'git merge-base --independent ' goes from 1.1 seconds to 0.11 seconds. Signed-off-by: Derrick Stolee --- commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 56 insertions(+), 16 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 7bf52e94429..d3a6e2bdd04 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -29,6 +29,10 @@ static int compare_commits_by_gen(const void *_a, const void *_b) return -1; if (generation_a > generation_b) return 1; + if (a->date < b->date) + return -1; + if (a->date > b->date) + return 1; return 0; } @@ -231,11 +235,10 @@ static int remove_redundant_no_gen(struct repository *r, static int remove_redundant_with_gen(struct repository *r, struct commit **array, int cnt) { - int i, count_non_stale = 0; + int i, count_non_stale = 0, count_still_independent = cnt; timestamp_t min_generation = GENERATION_NUMBER_INFINITY; struct commit **walk_start; size_t walk_start_nr = 0, walk_start_alloc = cnt; - struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; ALLOC_ARRAY(walk_start, walk_start_alloc); @@ -245,6 +248,7 @@ static int remove_redundant_with_gen(struct repository *r, timestamp_t generation; repo_parse_commit(r, array[i]); + array[i]->object.flags |= RESULT; parents = array[i]->parents; while (parents) { @@ -253,7 +257,6 @@ static int remove_redundant_with_gen(struct repository *r, parents->item->object.flags |= STALE; ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc); walk_start[walk_start_nr++] = parents->item; - prio_queue_put(&queue, parents->item); } parents = parents->next; } @@ -264,26 +267,63 @@ static int remove_redundant_with_gen(struct repository *r, min_generation = generation; } - /* push the STALE bits up to min generation */ - while (queue.nr) { - struct commit_list *parents; - struct commit *c = prio_queue_get(&queue); + QSORT(walk_start, walk_start_nr, compare_commits_by_gen); - repo_parse_commit(r, c); + /* remove STALE bit for now to allow walking through parents */ + for (i = 0; i < walk_start_nr; i++) + walk_start[i]->object.flags &= ~STALE; - if (commit_graph_generation(c) < min_generation) - continue; + /* + * Start walking from the highest generation. Hopefully, it will + * find all other items during the first-parent walk, and we can + * terminate early. Otherwise, we will do the same amount of work + * as before. + */ + for (i = walk_start_nr - 1; i >= 0 && count_still_independent > 1; i--) { + /* push the STALE bits up to min generation */ + struct commit_list *stack = NULL; - parents = c->parents; - while (parents) { - if (!(parents->item->object.flags & STALE)) { - parents->item->object.flags |= STALE; - prio_queue_put(&queue, parents->item); + commit_list_insert(walk_start[i], &stack); + walk_start[i]->object.flags |= STALE; + + while (stack) { + struct commit_list *parents; + struct commit *c = stack->item; + + repo_parse_commit(r, c); + + if (c->object.flags & RESULT) { + c->object.flags &= ~RESULT; + if (--count_still_independent <= 1) + break; } - parents = parents->next; + + if (commit_graph_generation(c) < min_generation) { + pop_commit(&stack); + continue; + } + + parents = c->parents; + while (parents) { + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + commit_list_insert(parents->item, &stack); + break; + } + parents = parents->next; + } + + /* pop if all parents have been visited already */ + if (!parents) + pop_commit(&stack); } + free_commit_list(stack); } + /* clear result */ + for (i = 0; i < cnt; i++) + array[i]->object.flags &= ~RESULT; + /* rearrange array */ for (i = count_non_stale = 0; i < cnt; i++) { if (!(array[i]->object.flags & STALE)) From patchwork Mon Feb 1 12:47:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12058965 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C8191C433E0 for ; Mon, 1 Feb 2021 12:49:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 862C164E9C for ; Mon, 1 Feb 2021 12:49:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231284AbhBAMsz (ORCPT ); Mon, 1 Feb 2021 07:48:55 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35244 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231309AbhBAMsw (ORCPT ); Mon, 1 Feb 2021 07:48:52 -0500 Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B9D12C061786 for ; Mon, 1 Feb 2021 04:47:35 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id q7so16398128wre.13 for ; Mon, 01 Feb 2021 04:47:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=xm/UiSpbTXoKk2g5inAlTT9sD+QpBzXhqkyj6DUNqBY=; b=YA6vKY0xcGko+hut4mPgyiHFVDeejDyKprDxzokgkS7SAwOD1zGRqagiia6mVpNyS0 bpogd4SouCN9TaTCxvdMKz3q1b3E5YJEXnxZ6qN87weamPz9hwCUArwmkWd8Ayp70JZI gWIq41ESbmZDhZSmzshhkvCVyziMpH328ocPh/zrQ1VGcbbnFsf0pESFJzgbOUa6EPWc eYp5QS5VGFelHRhC7YtyxBI7zUJd1wjNivX2X/mdtNAoaIythpsIi9P2ztpJTbbohtas yGbYfjBYgBN7T5wW79HcrOkiddS6h6c+jP6626oUW6Kv0nlEkVB6PJPsju8pGZDZ+LIC BDZQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=xm/UiSpbTXoKk2g5inAlTT9sD+QpBzXhqkyj6DUNqBY=; b=czgg0HTtdiRYcI+1IKGrR1IBUpvyUyXdWtJEFHJzj9x84MNeHX4t4O5BV9uh86XZI+ ZX4sSlrL1+JWMyzPNUYgR8T6I1aR+EJ4iX2od911Oa1pnClNBSg4v5qHCxxeDKSK+8zK tD/W0nRkzZJ/3L1wcWr2XkvSsMJ4GqcapXUgtsE5uPlNRt4E7B+PiEfpkA13d3om3wG+ 1iCny1sGpTVGYmOkceq1Fr4nGPdyohAWVXFM5Tl/FMPT7GCxY/1bekHlMPCOhD3aeEXt 1RnUKDjYyeoXFFLXJ/cshITb7r74tgAnbKApBOCAlWtBl2OOKSNMZlyQGXfQ6TgWQN6j V18w== X-Gm-Message-State: AOAM5327gPVv1TkDP9Cg70DfjjKbwwaBIc8lmnlYiDfE9/LNkpgTQ6HI udPnIa6zVue2MbiFj6uhDFS/j1/nHpc= X-Google-Smtp-Source: ABdhPJzrhr2+l6uGKpNAGKKojn8G494nuxsr3Bi+tNHuQ5Xo1sAAwHaqXsbjJVVFVpjMuuo9jAO9pA== X-Received: by 2002:adf:f4c1:: with SMTP id h1mr18091723wrp.102.1612183654248; Mon, 01 Feb 2021 04:47:34 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i6sm27554404wrs.71.2021.02.01.04.47.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Feb 2021 04:47:33 -0800 (PST) Message-Id: <14f0974c987215bd36e91450c1a6ebc6d5732121.1612183647.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Mon, 01 Feb 2021 12:47:27 +0000 Subject: [PATCH v2 5/5] commit-reach: stale commits may prune generation further Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Michael Haggerty , me@ttaylorr.com, peff@peff.net, gitster@pobox.com, =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The remove_redundant_with_gen() algorithm performs a depth-first-search to find commits in the 'array' list, starting at the parents of each commit in 'array'. The result is that commits in 'array' are marked STALE when they are reachable from another commit in 'array'. This depth-first-search is fast when commits lie on or near the first-parent history of the higher commits. The search terminates early if all but one commit becomes marked STALE. However, it is possible that there are two independent commits with high generation number. In that case, the depth-first-search might languish by searching in lower generations due to the fixed min_generation used throughout the method. With the expectation that commits with lower generation are expected to become STALE more often, we can optimize further by increasing that min_generation boundary upon discovery of the commit with minimum generation. We must first sort the commits in 'array' by generation. We cannot sort 'array' itself since it must preserve relative order among the returned results (see revision.c:mark_redundant_parents() for an example). This simplifies the initialization of min_generation, but it also allows us to increase the new min_generation when we find the commit with smallest generation remaining. This requires more than two commits in order to test, so I used the Linux kernel repository with a few commits that are slightly off of the first-parent history. I timed the following command: git merge-base --independent 2ecedd756908 d2360a398f0b \ 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e The first two commits have similar generation and are near the v5.10 tag. Commit 160bab43419e is off of the first-parent history behind v5.5, while the others are scattered somewhere reachable from v5.9. This is designed to demonstrate the optimization, as that commit within v5.5 would normally cause a lot of extra commit walking. Since remove_redundant_with_alg() is called only when at least one of the input commits has a finite generation number, this algorithm is tested with a commit-graph generated starting at a number of different tags, the earliest being v5.5. commit-graph at v5.5: | Method | Time | |-----------------------+-------| | *_no_gen() | 864ms | | *_with_gen() (before) | 858ms | | *_with_gen() (after) | 810ms | commit-graph at v5.7: | Method | Time | |-----------------------+-------| | *_no_gen() | 625ms | | *_with_gen() (before) | 572ms | | *_with_gen() (after) | 517ms | commit-graph at v5.9: | Method | Time | |-----------------------+-------| | *_no_gen() | 268ms | | *_with_gen() (before) | 224ms | | *_with_gen() (after) | 202ms | commit-graph at v5.10: | Method | Time | |-----------------------+-------| | *_no_gen() | 72ms | | *_with_gen() (before) | 37ms | | *_with_gen() (after) | 9ms | Note that these are only modest improvements for the case where the two independent commits are not in the commit-graph (not until v5.10). All algorithms get faster as more commits are indexed, which is not a surprise. However, the cost of walking extra commits is more and more prevalent in relative terms as more commits are indexed. Finally, the last case allows us to jump to the minimum generation between the last two commits (that are actually independent) so we greatly reduce the cost in that case. Signed-off-by: Derrick Stolee --- commit-reach.c | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index d3a6e2bdd04..c2e0747fea4 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -237,15 +237,27 @@ static int remove_redundant_with_gen(struct repository *r, { int i, count_non_stale = 0, count_still_independent = cnt; timestamp_t min_generation = GENERATION_NUMBER_INFINITY; - struct commit **walk_start; + struct commit **walk_start, **sorted; size_t walk_start_nr = 0, walk_start_alloc = cnt; + int min_gen_pos = 0; + + /* + * Sort the input by generation number, ascending. This allows + * us to increase the "min_generation" limit when we discover + * the commit with lowest generation is STALE. The index + * min_gen_pos points to the current position within 'array' + * that is not yet known to be STALE. + */ + ALLOC_ARRAY(sorted, cnt); + COPY_ARRAY(sorted, array, cnt); + QSORT(sorted, cnt, compare_commits_by_gen); + min_generation = commit_graph_generation(sorted[0]); ALLOC_ARRAY(walk_start, walk_start_alloc); /* Mark all parents of the input as STALE */ for (i = 0; i < cnt; i++) { struct commit_list *parents; - timestamp_t generation; repo_parse_commit(r, array[i]); array[i]->object.flags |= RESULT; @@ -260,11 +272,6 @@ static int remove_redundant_with_gen(struct repository *r, } parents = parents->next; } - - generation = commit_graph_generation(array[i]); - - if (generation < min_generation) - min_generation = generation; } QSORT(walk_start, walk_start_nr, compare_commits_by_gen); @@ -296,6 +303,12 @@ static int remove_redundant_with_gen(struct repository *r, c->object.flags &= ~RESULT; if (--count_still_independent <= 1) break; + if (oideq(&c->object.oid, &sorted[min_gen_pos]->object.oid)) { + while (min_gen_pos < cnt - 1 && + (sorted[min_gen_pos]->object.flags & STALE)) + min_gen_pos++; + min_generation = commit_graph_generation(sorted[min_gen_pos]); + } } if (commit_graph_generation(c) < min_generation) { @@ -319,6 +332,7 @@ static int remove_redundant_with_gen(struct repository *r, } free_commit_list(stack); } + free(sorted); /* clear result */ for (i = 0; i < cnt; i++)