git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Jakub Narebski <jnareb@gmail.com>
To: Derrick Stolee <dstolee@microsoft.com>
Cc: git@vger.kernel.org, "Junio C Hamano" <gitster@pobox.com>,
	"Jeff King" <peff@peff.net>,
	"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
	"Derrick Stolee" <stolee@gmail.com>
Subject: Re: [PATCH v5 00/11] Compute and consume generation numbers
Date: Thu, 03 May 2018 13:18:24 +0200	[thread overview]
Message-ID: <86sh79yolb.fsf@gmail.com> (raw)
In-Reply-To: <20180501124652.155781-1-dstolee@microsoft.com> (Derrick Stolee's message of "Tue, 1 May 2018 12:47:03 +0000")

Derrick Stolee <dstolee@microsoft.com> writes:

> Most of the changes from v4 are cosmetic, but there is one new commit:
>
> 	commit: use generation number in remove_redundant()
>
> Other changes are non-functional, but do clarify things.

I wonder if out perf framework in t/perf could help here to show
performance gains for the whole series.  Though it may not include
operations that are most helped by this one.

For commit-graph feature if would be nice, if feasible, to see changes
in performance from before version, checking both state where feature is
enabled to see the gains, and state where feature is disabled to see if
there are no performance regressions.

>
> Inter-diff from v4:

O.K., now to commenting on inter-changes.

> diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt
> index d9f2713efa..e1a883eb46 100644
> --- a/Documentation/technical/commit-graph.txt
> +++ b/Documentation/technical/commit-graph.txt
> @@ -125,9 +125,10 @@ Future Work
>    walks aware of generation numbers to gain the performance benefits they
>    enable. This will mostly be accomplished by swapping a commit-date-ordered
>    priority queue with one ordered by generation number. The following
> -  operation is an important candidate:
> +  operations are important candidates:
>
>      - 'log --topo-order'
> +    - 'tag --merged'
>
>  - Currently, parse_commit_gently() requires filling in the root tree
>    object for a commit. This passes through lookup_tree() and consequently

O.K., this is about discussion in "branch --contains / tag --merged
inconsistency" thread:

  https://public-inbox.org/git/87fu3g67ry.fsf@lant.ki.iif.hu/t/#u

> diff --git a/commit-graph.c b/commit-graph.c
> index aebd242def..a8c337dd77 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -248,6 +248,7 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,
>  static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
>  {
>         const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
> +       item->graph_pos = pos;
>         item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
>  }
>

Minor bugfix.

> @@ -454,8 +455,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
>                 else
>                         packedDate[0] = 0;
>
> -               if ((*list)->generation != GENERATION_NUMBER_INFINITY)
> -                       packedDate[0] |= htonl((*list)->generation << 2);
> +               packedDate[0] |= htonl((*list)->generation << 2);
>
>                 packedDate[1] = htonl((*list)->date);
>                 hashwrite(f, packedDate, 8);

Minor bugfix.

> @@ -589,18 +589,17 @@ static void close_reachable(struct packed_oid_list *oids)
>         }
>  }
>
> -static void compute_generation_numbers(struct commit** commits,
> -                                      int nr_commits)
> +static void compute_generation_numbers(struct packed_commit_list* commits)
>  {
>         int i;
>         struct commit_list *list = NULL;
>
> -       for (i = 0; i < nr_commits; i++) {
> -               if (commits[i]->generation != GENERATION_NUMBER_INFINITY &&
> -                   commits[i]->generation != GENERATION_NUMBER_ZERO)
> +       for (i = 0; i < commits->nr; i++) {
> +               if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
> +                   commits->list[i]->generation != GENERATION_NUMBER_ZERO)
>                         continue;
>
> -               commit_list_insert(commits[i], &list);
> +               commit_list_insert(commits->list[i], &list);
>                 while (list) {
>                         struct commit *current = list->item;
>                         struct commit_list *parent;

Refactoring: signature change from pair of struct commit** + int to
struct packed_commit_list*.

I think that it makes code a bit uglier for no gain, but that is just my
personal opinion; it is a matter of taste.

> @@ -621,10 +620,10 @@ static void compute_generation_numbers(struct commit** commits,
>                         if (all_parents_computed) {
>                                 current->generation = max_generation + 1;
>                                 pop_commit(&list);
> -                       }
>
> -                       if (current->generation > GENERATION_NUMBER_MAX)
> -                               current->generation = GENERATION_NUMBER_MAX;
> +                               if (current->generation > GENERATION_NUMBER_MAX)
> +                                       current->generation = GENERATION_NUMBER_MAX;
> +                       }
>                 }
>         }
>  }

Bugfix (though it didn't result in wrong information writen out, just in
inconsistent state in the middle of computation).

> @@ -752,7 +751,7 @@ void write_commit_graph(const char *obj_dir,
>         if (commits.nr >= GRAPH_PARENT_MISSING)
>                 die(_("too many commits to write graph"));
>
> -       compute_generation_numbers(commits.list, commits.nr);
> +       compute_generation_numbers(&commits);
>
>         graph_name = get_commit_graph_filename(obj_dir);
>         fd = hold_lock_file_for_update(&lk, graph_name, 0);

The other side of signature change.

> diff --git a/commit.c b/commit.c
> index e2e16ea1a7..5064db4e61 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -835,7 +835,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,
>                 int flags;
>
>                 if (commit->generation > last_gen)
> -                       BUG("bad generation skip");
> +                       BUG("bad generation skip %8x > %8x at %s",
> +                           commit->generation, last_gen,
> +                           oid_to_hex(&commit->object.oid));
>                 last_gen = commit->generation;
>
>                 if (commit->generation < min_generation)

More detailed BUG() message, always nice to have.

> @@ -947,6 +949,7 @@ static int remove_redundant(struct commit **array, int cnt)
>                 parse_commit(array[i]);
>         for (i = 0; i < cnt; i++) {
>                 struct commit_list *common;
> +               uint32_t min_generation = GENERATION_NUMBER_INFINITY;
>
>                 if (redundant[i])
>                         continue;
> @@ -955,8 +958,12 @@ static int remove_redundant(struct commit **array, int cnt)
>                                 continue;
>                         filled_index[filled] = j;
>                         work[filled++] = array[j];
> +
> +                       if (array[j]->generation < min_generation)
> +                               min_generation = array[j]->generation;
>                 }
> -               common = paint_down_to_common(array[i], filled, work, 0);
> +               common = paint_down_to_common(array[i], filled, work,
> +                                             min_generation);
>                 if (array[i]->object.flags & PARENT2)
>                         redundant[i] = 1;
>                 for (j = 0; j < filled; j++)

New commit in series.  Change looks quite short, gives measurable
performance gains (in appropriate case).

> @@ -1073,7 +1080,7 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
>         for (i = 0; i < nr_reference; i++) {
>                 if (parse_commit(reference[i]))
>                         return ret;
> -               if (min_generation > reference[i]->generation)
> +               if (reference[i]->generation < min_generation)
>                         min_generation = reference[i]->generation;
>         }
>
>

Style change.

> -- >8 --
>
> Derrick Stolee (11):
>   ref-filter: fix outdated comment on in_commit_list
>   commit: add generation number to struct commmit
>   commit-graph: compute generation numbers
>   commit: use generations in paint_down_to_common()
>   commit-graph: always load commit-graph information
>   ref-filter: use generation number for --contains
>   commit: use generation numbers for in_merge_bases()
>   commit: add short-circuit to paint_down_to_common()
>   commit: use generation number in remove_redundant()
>   merge: check config before loading commits
>   commit-graph.txt: update design document

It looks like the series is maturing nicely.

Best,
-- 
Jakub Narębski

      parent reply	other threads:[~2018-05-03 11:18 UTC|newest]

Thread overview: 162+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-03 16:51 [PATCH 0/6] Compute and consume generation numbers Derrick Stolee
2018-04-03 16:51 ` [PATCH 1/6] object.c: parse commit in graph first Derrick Stolee
2018-04-03 18:21   ` Jonathan Tan
2018-04-03 18:28     ` Jeff King
2018-04-03 18:32       ` Derrick Stolee
2018-04-03 16:51 ` [PATCH 2/6] commit: add generation number to struct commmit Derrick Stolee
2018-04-03 18:05   ` Brandon Williams
2018-04-03 18:28     ` Jeff King
2018-04-03 18:31       ` Derrick Stolee
2018-04-03 18:32       ` Brandon Williams
2018-04-03 18:44       ` Stefan Beller
2018-04-03 23:17       ` Ramsay Jones
2018-04-03 23:19         ` Jeff King
2018-04-03 18:24   ` Jonathan Tan
2018-04-03 16:51 ` [PATCH 3/6] commit-graph: compute generation numbers Derrick Stolee
2018-04-03 18:30   ` Jonathan Tan
2018-04-03 18:49     ` Stefan Beller
2018-04-03 16:51 ` [PATCH 4/6] commit: use generations in paint_down_to_common() Derrick Stolee
2018-04-03 18:31   ` Stefan Beller
2018-04-03 18:31   ` Jonathan Tan
2018-04-03 16:51 ` [PATCH 5/6] commit.c: use generation to halt paint walk Derrick Stolee
2018-04-03 19:01   ` Jonathan Tan
2018-04-03 16:51 ` [PATCH 6/6] commit-graph.txt: update future work Derrick Stolee
2018-04-03 19:04   ` Jonathan Tan
2018-04-03 16:56 ` [PATCH 0/6] Compute and consume generation numbers Derrick Stolee
2018-04-03 18:03 ` Brandon Williams
2018-04-03 18:29   ` Derrick Stolee
2018-04-03 18:47     ` Jeff King
2018-04-03 19:05       ` Jeff King
2018-04-04 15:45         ` [PATCH 7/6] ref-filter: use generation number for --contains Derrick Stolee
2018-04-04 15:45           ` [PATCH 8/6] commit: use generation numbers for in_merge_bases() Derrick Stolee
2018-04-04 15:48             ` Derrick Stolee
2018-04-04 17:01               ` Brandon Williams
2018-04-04 18:24               ` Jeff King
2018-04-04 18:53                 ` Derrick Stolee
2018-04-04 18:59                   ` Jeff King
2018-04-04 18:22           ` [PATCH 7/6] ref-filter: use generation number for --contains Jeff King
2018-04-04 19:06             ` Derrick Stolee
2018-04-04 19:16               ` Jeff King
2018-04-04 19:22                 ` Derrick Stolee
2018-04-04 19:42                   ` Jeff King
2018-04-04 19:45                     ` Derrick Stolee
2018-04-04 19:46                       ` Jeff King
2018-04-07 17:09     ` [PATCH 0/6] Compute and consume generation numbers Jakub Narebski
2018-04-07 16:55 ` Jakub Narebski
2018-04-08  1:06   ` Derrick Stolee
2018-04-11 19:32     ` Jakub Narebski
2018-04-11 19:58       ` Derrick Stolee
2018-04-14 16:52         ` Jakub Narebski
2018-04-21 20:44           ` Jakub Narebski
2018-04-23 13:54             ` Derrick Stolee
2018-04-09 16:41 ` [PATCH v2 00/10] " Derrick Stolee
2018-04-09 16:41   ` [PATCH v2 01/10] object.c: parse commit in graph first Derrick Stolee
2018-04-09 16:41   ` [PATCH v2 02/10] merge: check config before loading commits Derrick Stolee
2018-04-11  2:12     ` Junio C Hamano
2018-04-11 12:49       ` Derrick Stolee
2018-04-09 16:42   ` [PATCH v2 03/10] commit: add generation number to struct commmit Derrick Stolee
2018-04-09 17:59     ` Stefan Beller
2018-04-11  2:31     ` Junio C Hamano
2018-04-11 12:57       ` Derrick Stolee
2018-04-11 23:28         ` Junio C Hamano
2018-04-09 16:42   ` [PATCH v2 04/10] commit-graph: compute generation numbers Derrick Stolee
2018-04-11  2:51     ` Junio C Hamano
2018-04-11 13:02       ` Derrick Stolee
2018-04-11 18:49         ` Stefan Beller
2018-04-11 19:26         ` Eric Sunshine
2018-04-09 16:42   ` [PATCH v2 05/10] commit: use generations in paint_down_to_common() Derrick Stolee
2018-04-09 16:42   ` [PATCH v2 06/10] commit.c: use generation to halt paint walk Derrick Stolee
2018-04-11  3:02     ` Junio C Hamano
2018-04-11 13:24       ` Derrick Stolee
2018-04-09 16:42   ` [PATCH v2 07/10] commit-graph.txt: update future work Derrick Stolee
2018-04-12  9:12     ` Junio C Hamano
2018-04-12 11:35       ` Derrick Stolee
2018-04-13  9:53         ` Jakub Narebski
2018-04-09 16:42   ` [PATCH v2 08/10] ref-filter: use generation number for --contains Derrick Stolee
2018-04-09 16:42   ` [PATCH v2 09/10] commit: use generation numbers for in_merge_bases() Derrick Stolee
2018-04-09 16:42   ` [PATCH v2 10/10] commit: add short-circuit to paint_down_to_common() Derrick Stolee
2018-04-17 17:00   ` [PATCH v3 0/9] Compute and consume generation numbers Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 1/9] commit: add generation number to struct commmit Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 2/9] commit-graph: compute generation numbers Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 3/9] commit: use generations in paint_down_to_common() Derrick Stolee
2018-04-18 14:31       ` Jakub Narebski
2018-04-18 14:46         ` Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 4/9] commit-graph.txt: update design document Derrick Stolee
2018-04-18 19:47       ` Jakub Narebski
2018-04-17 17:00     ` [PATCH v3 5/9] ref-filter: use generation number for --contains Derrick Stolee
2018-04-18 21:02       ` Jakub Narebski
2018-04-23 14:22         ` Derrick Stolee
2018-04-24 18:56           ` Jakub Narebski
2018-04-25 14:11             ` Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 6/9] commit: use generation numbers for in_merge_bases() Derrick Stolee
2018-04-18 22:15       ` Jakub Narebski
2018-04-23 14:31         ` Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 7/9] commit: add short-circuit to paint_down_to_common() Derrick Stolee
2018-04-18 23:19       ` Jakub Narebski
2018-04-23 14:40         ` Derrick Stolee
2018-04-23 21:38           ` Jakub Narebski
2018-04-24 12:31             ` Derrick Stolee
2018-04-19  8:32       ` Jakub Narebski
2018-04-17 17:00     ` [PATCH v3 8/9] commit-graph: always load commit-graph information Derrick Stolee
2018-04-17 17:50       ` Derrick Stolee
2018-04-19  0:02       ` Jakub Narebski
2018-04-23 14:49         ` Derrick Stolee
2018-04-17 17:00     ` [PATCH v3 9/9] merge: check config before loading commits Derrick Stolee
2018-04-19  0:04     ` [PATCH v3 0/9] Compute and consume generation numbers Jakub Narebski
2018-04-23 14:54       ` Derrick Stolee
2018-04-25 14:37     ` [PATCH v4 00/10] " Derrick Stolee
2018-04-25 14:37       ` [PATCH v4 01/10] ref-filter: fix outdated comment on in_commit_list Derrick Stolee
2018-04-28 17:54         ` Jakub Narebski
2018-04-25 14:37       ` [PATCH v4 02/10] commit: add generation number to struct commmit Derrick Stolee
2018-04-28 22:35         ` Jakub Narebski
2018-04-30 12:05           ` Derrick Stolee
2018-04-25 14:37       ` [PATCH v4 03/10] commit-graph: compute generation numbers Derrick Stolee
2018-04-26  2:35         ` Junio C Hamano
2018-04-26 12:58           ` Derrick Stolee
2018-04-26 13:49             ` Derrick Stolee
2018-04-29  9:08         ` Jakub Narebski
2018-05-01 12:10           ` Derrick Stolee
2018-05-02 16:15             ` Jakub Narebski
2018-04-25 14:37       ` [PATCH v4 04/10] commit: use generations in paint_down_to_common() Derrick Stolee
2018-04-26  3:22         ` Junio C Hamano
2018-04-26  9:02           ` Jakub Narebski
2018-04-28 14:38             ` Jakub Narebski
2018-04-29 15:40         ` Jakub Narebski
2018-04-25 14:37       ` [PATCH v4 06/10] ref-filter: use generation number for --contains Derrick Stolee
2018-04-30 16:34         ` Jakub Narebski
2018-04-25 14:37       ` [PATCH v4 05/10] commit-graph: always load commit-graph information Derrick Stolee
2018-04-29 22:14         ` Jakub Narebski
2018-05-01 12:19           ` Derrick Stolee
2018-04-29 22:18         ` Jakub Narebski
2018-04-25 14:37       ` [PATCH v4 07/10] commit: use generation numbers for in_merge_bases() Derrick Stolee
2018-04-30 17:05         ` Jakub Narebski
2018-04-25 14:38       ` [PATCH v4 08/10] commit: add short-circuit to paint_down_to_common() Derrick Stolee
2018-04-30 22:19         ` Jakub Narebski
2018-05-01 11:47           ` Derrick Stolee
2018-05-02 13:05             ` Jakub Narebski
2018-05-02 13:42               ` Derrick Stolee
2018-04-25 14:38       ` [PATCH v4 09/10] merge: check config before loading commits Derrick Stolee
2018-04-30 22:54         ` Jakub Narebski
2018-05-01 11:52           ` Derrick Stolee
2018-05-02 11:41             ` Jakub Narebski
2018-04-25 14:38       ` [PATCH v4 10/10] commit-graph.txt: update design document Derrick Stolee
2018-04-30 23:32         ` Jakub Narebski
2018-05-01 12:00           ` Derrick Stolee
2018-05-02  7:57             ` Jakub Narebski
2018-04-25 14:40       ` [PATCH v4 00/10] Compute and consume generation numbers Derrick Stolee
2018-04-28 17:28         ` Jakub Narebski
2018-05-01 12:47       ` [PATCH v5 00/11] " Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 01/11] ref-filter: fix outdated comment on in_commit_list Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 02/11] commit: add generation number to struct commmit Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 03/11] commit-graph: compute generation numbers Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 04/11] commit: use generations in paint_down_to_common() Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 05/11] commit-graph: always load commit-graph information Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 06/11] ref-filter: use generation number for --contains Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 07/11] commit: use generation numbers for in_merge_bases() Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 08/11] commit: add short-circuit to paint_down_to_common() Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 09/11] commit: use generation number in remove_redundant() Derrick Stolee
2018-05-01 15:37           ` Derrick Stolee
2018-05-03 18:45           ` Jakub Narebski
2018-05-01 12:47         ` [PATCH v5 10/11] merge: check config before loading commits Derrick Stolee
2018-05-01 12:47         ` [PATCH v5 11/11] commit-graph.txt: update design document Derrick Stolee
2018-05-03 11:18         ` Jakub Narebski [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=86sh79yolb.fsf@gmail.com \
    --to=jnareb@gmail.com \
    --cc=avarab@gmail.com \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=peff@peff.net \
    --cc=stolee@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).