From patchwork Fri Feb 19 12:34:06 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12095343 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.8 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 44DFDC433DB for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 129A064EBD for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230184AbhBSMe4 (ORCPT ); Fri, 19 Feb 2021 07:34:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46900 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229720AbhBSMey (ORCPT ); Fri, 19 Feb 2021 07:34:54 -0500 Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 126DCC061788 for ; Fri, 19 Feb 2021 04:34:14 -0800 (PST) Received: by mail-wm1-x335.google.com with SMTP id l17so6930289wmq.2 for ; Fri, 19 Feb 2021 04:34:13 -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=NUP8hAaHIZ4GEw7Bpetf6PthcaIyZ9T5XakdU0bHZE0=; b=sJuHkWjuffDEijiq5W4FdX0SpwD1+UyNp/em8m2CcG0OEpRSGFUJ/9rRtnMLOS/C+P FtL7v/MkUHI9QX/Yw9SIB4VMf5cgw/w50sgmoLkBLGi9j6iZ5yHHWpWHK3OoZMVNtqlu dlesdberQf63jDA6XTGBlGicdIS2ZIU0OlIOL7tNGSw5oQfT7IctESfMjZgZDQsoPqAD TsnxoghxSgIH3bEWL1YQiiJill50vu9hwHM6LGG4tCYzqvZGx1wf+RmpMvXh35E64guR MIPvJrVl79dT2hmtyOdnLxS5rQt2n+lLMv2vTbxjc0A9OgtGvu/c3V7+LbqyZZ1VhHJy SYcg== 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=NUP8hAaHIZ4GEw7Bpetf6PthcaIyZ9T5XakdU0bHZE0=; b=lRAqqizXrzkJXBRLSOynriBTgyh6CniZygjQ4U4/UO4vVaKz52u0CddW9i1Mae6AKA 1bkwsHtW5f8HnJPz2RtyH2z0zRuV9kg36FhsPb7y5BYI/CerCBNAl2SDlVNDAfu07FgS s+9Ywhs6P19GXX8bPZiy9TxUyOeHV/ldBWJ4wpuwGCtSmxtGeJLiQDtafyy12MVWRDKi esermqHpWlDS/DUXcnOFDUMpIV3fQBzNeui4V7CYBcuTpsNhK6V1pTGHNJWqjgDaJmmi TVVCRTaiDLMw4GEUPBggwJr5dVSF59pV6A1odGoSTwxThAl4wt65Ap1Ug/MCEzpi8opv ojzg== X-Gm-Message-State: AOAM532Am5dcfZJy1/OQHMQpoVh3KjE+EJRbFwJM7UAFSswTuCdNmrXM 1OvFIL5UyfvQBcDDG5cM8eYEh3Wh3RU= X-Google-Smtp-Source: ABdhPJy6RWcIjrc7wJAWxKVHFvQX3kmUDcMpC00dF343qW1mFyzJJiZ92EZgi+tP4HweRpFInHb2Gw== X-Received: by 2002:a05:600c:3550:: with SMTP id i16mr7011864wmq.170.1613738052785; Fri, 19 Feb 2021 04:34:12 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f7sm13439065wre.78.2021.02.19.04.34.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 19 Feb 2021 04:34:12 -0800 (PST) Message-Id: <649f6799e6bfa0662ed5a4debf915053598fe142.1613738051.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 19 Feb 2021 12:34:06 +0000 Subject: [PATCH v3 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 e38771ca5a1f..9af51fe7e078 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 Fri Feb 19 12:34:07 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12095353 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.8 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 64D52C433E6 for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 386E464EC0 for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230195AbhBSMe7 (ORCPT ); Fri, 19 Feb 2021 07:34:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46908 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229804AbhBSMez (ORCPT ); Fri, 19 Feb 2021 07:34:55 -0500 Received: from mail-wm1-x32e.google.com (mail-wm1-x32e.google.com [IPv6:2a00:1450:4864:20::32e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D05F7C06178A for ; Fri, 19 Feb 2021 04:34:14 -0800 (PST) Received: by mail-wm1-x32e.google.com with SMTP id v62so7485116wmg.4 for ; Fri, 19 Feb 2021 04:34:14 -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=xAt7oYKkKU6imCln9jYSjKatAsxBNkwtMhyYSMZ8sPw=; b=DNEqXPxEC35HV9J/wJm43VMruTyuXpNAEtHItblLaI1iWxxXXNzXnyEJbvcMCgMOxF lK4/iqdPGzSUn0BL8xs9FgWJln4r4DnLCDj5Y2hMtHYWSrPc9vKiEjx8yLWVQXhdenDW ynVCK2GnJ3u41iOYBcRbipW6XUnzTQECKf4s38iv8LfkUfGpOyQidXHnTYG/+6tK8e6z JIef2wmpc/yNS9xznUDywA62k+KseM6X7ZOlw195H4oxFLNoJnRAr3n1713dtFYhYBas qek6LAFCZ7s15btOAaRRoNs7LegGHu/BgQjVuafADIn/PSVBKC9cllpI+ulIin9EwrFI m0lw== 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=xAt7oYKkKU6imCln9jYSjKatAsxBNkwtMhyYSMZ8sPw=; b=cpV6SJZ0enwNWyjiTD8vL9KoURXRLPeCdiHBROSnOqJNSFhIdIM+0FfKJSTO+aYTXB VlzRElhb36iWhxCFNiEganFQBabL7n5aaa309kSpw8xPc6NGOvrOwQtcW4ZcblF72zx/ 3Pxu7v4u1hI35R3A56VqgF0SOxGOlSR5NCs4soQJpIryxA19ltmvEKxL+M4Rwl3uia4O yZNYqaKnJvEytHVwsYy6tHT18QN3opOjlo2t3CPaayLtQTC/vW2H/sQJB77JdX7nI0fI 5McKl1MKH2kBYpe6LKzZUeNVLYRl19vXVxlZ+0KW7RvsrzksWw4rZqfnQxGfKno6QpZG 237Q== X-Gm-Message-State: AOAM532N3DbXlzoobm1indNAT2L7+RKsq6B5FGrbh/lnL8fAupE/VliS 8DGpusQabLlyXcgIkVwBw4fC/9OmdOY= X-Google-Smtp-Source: ABdhPJzk+no6XVTkFJZSWkONeU1BLwzXFafKYtfpFNQ8YN8NSrZzbYEGvtwD5dEGiiPbR1kzxJ8HpQ== X-Received: by 2002:a1c:20c3:: with SMTP id g186mr8018617wmg.59.1613738053455; Fri, 19 Feb 2021 04:34:13 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f7sm13439105wre.78.2021.02.19.04.34.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 19 Feb 2021 04:34:13 -0800 (PST) Message-Id: In-Reply-To: References: Date: Fri, 19 Feb 2021 12:34:07 +0000 Subject: [PATCH v3 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 | 104 +++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 96 insertions(+), 8 deletions(-) diff --git a/commit-reach.c b/commit-reach.c index 9af51fe7e078..7a3a1eb1a26e 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; @@ -216,6 +210,100 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt 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 */ + clear_commit_marks_many(walk_start_nr, walk_start, 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 Fri Feb 19 12:34:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12095351 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.8 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 A5261C4332D for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 873AF64EBD for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230240AbhBSMfK (ORCPT ); Fri, 19 Feb 2021 07:35:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46930 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230200AbhBSMfG (ORCPT ); Fri, 19 Feb 2021 07:35:06 -0500 Received: from mail-wr1-x433.google.com (mail-wr1-x433.google.com [IPv6:2a00:1450:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 362A9C06178B for ; Fri, 19 Feb 2021 04:34:15 -0800 (PST) Received: by mail-wr1-x433.google.com with SMTP id l12so8250006wry.2 for ; Fri, 19 Feb 2021 04:34:15 -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=/VQnHejz3F4+Nb7sLVqUxe8wEvgRIjrbaqweMGJyjRI=; b=pEGzAL8h0QPtTww6MLlyMmMExxVeOD0Ws+3AR5KjrKysLRpxc/pRgV1Ch7MUSfitd9 POHrJPq3slOVQdLmgdwQ5ef6QfvFVzfsEos5JlntUDqInxp0pSzOG0UIvgJi2eaFOY/f lymiKnV+Rzgyp8aDY9WKycLyg8MpeeUO4uYRw9LUd9G8HN6PyYZM2QRtuVOajcWbTOGn F/5fDY3OC8zYakQ0gVs7IRmWOOfxE+7Wfaf6r8WzjlOosqXN+KMDDQ1CjZ5APkF3bkrd R4c+7jsBJ3kI9oec1dMcPT442Y7iPSxFAmk2x6SOQYOtQCBAxJ7lW3G+9hjzL/QIw+vV Bclw== 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=/VQnHejz3F4+Nb7sLVqUxe8wEvgRIjrbaqweMGJyjRI=; b=OGXckDT4pOxfAcXE5+QRKCTYKp7ukS9qZPimHXmzVN17UN82NzDZHzF8PbcmU2GIv/ GhdG86Y269cy2lfUGyKIhyba6FoR1lemqCz0ai/ds6sqEPwqVN2pF6iwlbabHayESbZL NypE/6Ryyyj42KW7T4ifEVwv3I6Qff7wdPrEnmDf4WgUow6V6pmLzCoaeZMnFK7m3JvQ paAfOb/5sr+o+6SCvU42Gb12W5Af4Ws5NTFUtZfXcNlsBGT8VGjP14Ykqmzq+geJegdC h41FU0SSvHVRqmeBnzVGH0BLuKVbVRTHpicMQFDiWHALXYSQ7E9cyWwTiyeR0NVt1EUj 0/Sw== X-Gm-Message-State: AOAM531wZvNedR2d2QI79L/39/zYp8LvDxE2U9zhCMbsDTKaCMW0YpKm ucrZnkIEOlZk+uOLnGsBH3yKL26D744= X-Google-Smtp-Source: ABdhPJx1p9dnOap2J/6uo+NCxZBAO9uqoGil2tBtfZkr3pBFEM+OCgVSLPKsVYdTp2sikgk6+oJhuQ== X-Received: by 2002:adf:e98d:: with SMTP id h13mr9116606wrm.246.1613738054031; Fri, 19 Feb 2021 04:34:14 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id o10sm7011514wrx.5.2021.02.19.04.34.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 19 Feb 2021 04:34:13 -0800 (PST) Message-Id: <1d3c5ebbb632b33c6623c3c5ad120f1ec9884756.1613738051.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 19 Feb 2021 12:34:08 +0000 Subject: [PATCH v3 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 7a3a1eb1a26e..a34c5ba09e81 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; @@ -647,21 +662,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 Fri Feb 19 12:34:09 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12095349 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.8 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 7B8ADC43381 for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5100664EBD for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230196AbhBSMfJ (ORCPT ); Fri, 19 Feb 2021 07:35:09 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46932 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230206AbhBSMfG (ORCPT ); Fri, 19 Feb 2021 07:35:06 -0500 Received: from mail-wm1-x32c.google.com (mail-wm1-x32c.google.com [IPv6:2a00:1450:4864:20::32c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D925DC06178C for ; Fri, 19 Feb 2021 04:34:15 -0800 (PST) Received: by mail-wm1-x32c.google.com with SMTP id a132so6978606wmc.0 for ; Fri, 19 Feb 2021 04:34:15 -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=GEli7f/VTIvi6C6ZQrLXi9shGIHrHW8b1qit8uLsWfo=; b=pJ4wp0mK3oxT29oNErBk1lOeAqLdlceYIwvZq9Pp/RzUcJfJ7GPPNJWA0RMpzrObZp DVyq3Rs0ojqbqRBoADjPH00jaN64m9Zbo9Pu9U93ELqh5pZjXEQ9hdVDhrnS1RqS8aDJ DtdVpxzg9H+Zr2WmNGUPihYJcPY6XctN1TpqMCPmoz3VcyuhpCKQctoTpb/U59UsgpqJ t9JFyKC0eHitqLLPjf6LCqZOG2tLYzK9UFzZ76cTi8IEhlW60D+60kHjKKxupHlb1lY1 MV+kExLHKrsszH6Y60dr2xG2gnj8qUL0zL4RWGuRZ/WDz/arhKEkgk2T2G75u08HcPTS QLXA== 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=GEli7f/VTIvi6C6ZQrLXi9shGIHrHW8b1qit8uLsWfo=; b=qweyE/ZHVJ5i5TWRatBSJ96Pra0CE3UM3sSKQLlfMEOJG4ypaDP8s0S++Uux3kewlV 2+MSgPTxsMXjqusidF74yDBth7YjLEkg7lIam/++vuchj8Pncf7pze7dxI7fSzS52lZW I8E23Jozl9sZNjlV2kB2TkRkCzLc+R1WO1murFY2UihRVXgm8qIKnf91SrNzuG2UOZjr 8KLCaAL9KXAXiw/xN/MNI2y1rWjKau3zlJqpG3EeCq6VD7jz7BClKouuHIXwsi4cbljK V9bHJWvrY1DUB58y1E1b2jLtmHj38uZl7qsn3Lm2dq9xmv8tjW+yoc1atNSirgcdQYK9 Hfkg== X-Gm-Message-State: AOAM531W7jTehFHB4xY2P0y4KYWIJ8dvQyJ7g5x68gRIqjX/r+di5CpF IR09IbzzzhfFddkhebh2OF2TbKaxaAc= X-Google-Smtp-Source: ABdhPJyOL8W1Wrx51XDjjU5vLhFbqAZhgiaPJ5Pbr0uRwo4COnH2He983FaUDXNglwUiv3sxTdm9NA== X-Received: by 2002:a05:600c:4e8a:: with SMTP id f10mr8010517wmq.15.1613738054575; Fri, 19 Feb 2021 04:34:14 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id l4sm12999662wrt.42.2021.02.19.04.34.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 19 Feb 2021 04:34:14 -0800 (PST) Message-Id: In-Reply-To: References: Date: Fri, 19 Feb 2021 12:34:09 +0000 Subject: [PATCH v3 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 a34c5ba09e81..399f2a8673e0 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; } @@ -228,11 +232,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); @@ -242,6 +245,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) { @@ -250,7 +254,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; } @@ -261,26 +264,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 Fri Feb 19 12:34:10 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12095347 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.8 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 8E963C433E9 for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6B8F564ECE for ; Fri, 19 Feb 2021 12:35:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230228AbhBSMfK (ORCPT ); Fri, 19 Feb 2021 07:35:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46936 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230219AbhBSMfG (ORCPT ); Fri, 19 Feb 2021 07:35:06 -0500 Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 661FBC061793 for ; Fri, 19 Feb 2021 04:34:16 -0800 (PST) Received: by mail-wr1-x42e.google.com with SMTP id n8so8192636wrm.10 for ; Fri, 19 Feb 2021 04:34:16 -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=6PMselJ1nnqE9QMGYtzvXEW1KONWHeFSLbt8y2FJrro=; b=WPCZ54myPfi2lv9omYFlVsARFqI9tRypv3lSx4eASPE8DFVPgQX6KmEzZsrZn0upCN HtzfDswcOHBFnuT05ZWtyyOT0lV09ymsvHI586L5Zzv6Qj4vsMPLzgqaT+GE3/gykmK2 kmnwNqRV8nur70m4IWKjpbBhBrVNawsVH5VMfJqK30wnRAqbwG74Z08liyoV8NUUZx7x etNTjcS9NBckqGapa0edEOtVwChkLAHtL70/suOXCvgRy6dWunXZHgOLNw9FTOa0tO3h EOMg8RTOKDXmSq4ZlrFYhHX4que7lz94ZynKrl/QmvlI05EhDQqzSHnqOCBQAldvL/An XYbA== 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=6PMselJ1nnqE9QMGYtzvXEW1KONWHeFSLbt8y2FJrro=; b=OKzerhwr3H7C7Xzx4N4upjWGcMD32D/uhR2eTGNwZ2zHufjFw71tL1oDYqpm8c/vRs 8q1xb46Rb0KavHe9HUhaYz7WvbUVZ3Baw4NKlMr6M+oIK+xG53ZmrnBz+87AtX32Gg/W klx9bZfUYuU7vf9QHzXZUi9YhKV0eMzSkhHy+1tQyEMGWmJDA4olE3lInYGSafjUwjxa wHirUiC2KPXwBm3yf44b64IHcDEK3YN9DdqhPH8M0MJeREKyCsyWeRV35Bnylhgfj+cu wuqNH/Bd/YRJVqUR9yU87m2tfWOJVe+NFY0U3iq6W6gw/Zcz3iuYuo3dR/cUf3BmfTUc Ta3g== X-Gm-Message-State: AOAM530bDCBQwKeuJZS0HjvarYjgDrDEqUyhzWtyl2qmmQdrWlWU0PW7 rScMoUP/rw01SQoLUwQTmmo+hybC+3g= X-Google-Smtp-Source: ABdhPJxkMNABo2gMzpiLW73S5Uhqt50BwX5pN3jxxq/c36RDEYD0TvtOeT3mr39E5aovCj+bVwJHrg== X-Received: by 2002:a5d:550c:: with SMTP id b12mr9362888wrv.200.1613738055116; Fri, 19 Feb 2021 04:34:15 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 7sm285018wmi.27.2021.02.19.04.34.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 19 Feb 2021 04:34:14 -0800 (PST) Message-Id: <539db83bd7355d8b3a474ed7b577f4112e3ce1e0.1613738051.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 19 Feb 2021 12:34:10 +0000 Subject: [PATCH v3 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 399f2a8673e0..2ea84d3dc074 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -234,15 +234,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; @@ -257,11 +269,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); @@ -293,6 +300,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) { @@ -316,6 +329,7 @@ static int remove_redundant_with_gen(struct repository *r, } free_commit_list(stack); } + free(sorted); /* clear result */ for (i = 0; i < cnt; i++)