"Derrick Stolee via GitGitGadget" [off-list ref] writes:
+ /* 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;
+ 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;
+ }
+ }
So, the inner loop makes sure we won't revisit STALE parent, but
keep digging parents we haven't seen, and stop when the generation
is old enough. What happens when there is no generation number
computed yet, I wonder... We'll keep getting infinity and dig all
the way down to root?
+ /* rearrange array */
+ dup = xcalloc(cnt, sizeof(struct commit *));
+ COPY_ARRAY(dup, array, cnt);
+ for (i = 0; i < cnt; i++) {
+ if (dup[i]->object.flags & STALE) {
+ int insert = cnt - 1 - (i - count_non_stale);
+ array[insert] = dup[i];
+ } else {
+ array[count_non_stale] = dup[i];
+ count_non_stale++;
+ }
+ }
+ free(dup);
The "fill stale ones from the end, non-stale ones from the
beginning" in the loop looks unnecessarily complex to me. I wonder
if we can do only the "fill non-stale ones from the beginning" half,
i.e.
for (i = count_non_stale = 0; i < cnt; i++) {
if (dup[i] is not stale)
array[count_non_stale++] = dup[i];
}
without the "keep the stale one at the end of array[]", and clear
marks using what is in dup[] as starting points before discarding
dup[]?
Or do the callers still look at the entries beyond count_non_stale?
Other than that, nicely done.
+ /* clear marks */
+ for (i = 0; i < cnt; i++) {
+ struct commit_list *parents;
+ parents = array[i]->parents;
+
+ while (parents) {
+ clear_commit_marks(parents->item, STALE);
+ parents = parents->next;
}
- common = paint_down_to_common(r, array[i], filled,
- work, min_generation);
- if (array[i]->object.flags & PARENT2)
- redundant[i] = 1;
- for (j = 0; j < filled; j++)
- if (work[j]->object.flags & PARENT1)
- redundant[filled_index[j]] = 1;
- clear_commit_marks(array[i], all_flags);
- clear_commit_marks_many(filled, work, all_flags);
- free_commit_list(common);
}
- /* Now collect the result */
- COPY_ARRAY(work, array, 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;
+ return count_non_stale;
}
static struct commit_list *get_merge_bases_many_0(struct repository *r,
Am 28.01.21 um 21:51 schrieb Junio C Hamano:
"Derrick Stolee via GitGitGadget" [off-list ref] writes:
quoted
+ /* rearrange array */
+ dup = xcalloc(cnt, sizeof(struct commit *));
+ COPY_ARRAY(dup, array, cnt);
+ for (i = 0; i < cnt; i++) {
+ if (dup[i]->object.flags & STALE) {
+ int insert = cnt - 1 - (i - count_non_stale);
+ array[insert] = dup[i];
+ } else {
+ array[count_non_stale] = dup[i];
+ count_non_stale++;
+ }
+ }
+ free(dup);
The "fill stale ones from the end, non-stale ones from the
beginning" in the loop looks unnecessarily complex to me. I wonder
if we can do only the "fill non-stale ones from the beginning" half,
i.e.
for (i = count_non_stale = 0; i < cnt; i++) {
if (dup[i] is not stale)
array[count_non_stale++] = dup[i];
}
without the "keep the stale one at the end of array[]", and clear
marks using what is in dup[] as starting points before discarding
dup[]?
Or do the callers still look at the entries beyond count_non_stale?
Had the same reaction. Both callers ignore the stale entries.
Other than that, nicely done.
quoted
+ /* clear marks */
+ for (i = 0; i < cnt; i++) {
+ struct commit_list *parents;
+ parents = array[i]->parents;
+
+ while (parents) {
+ clear_commit_marks(parents->item, STALE);
+ parents = parents->next;
}
This loop clears STALE from the parents of both the non-stale and
stale entries. OK. Should it also clear it from the stale entries
themselves?
quoted
- common = paint_down_to_common(r, array[i], filled,
- work, min_generation);
- if (array[i]->object.flags & PARENT2)
- redundant[i] = 1;
- for (j = 0; j < filled; j++)
- if (work[j]->object.flags & PARENT1)
- redundant[filled_index[j]] = 1;
- clear_commit_marks(array[i], all_flags);
- clear_commit_marks_many(filled, work, all_flags);
- free_commit_list(common);
}
- /* Now collect the result */
- COPY_ARRAY(work, array, 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;
+ return count_non_stale;
}
static struct commit_list *get_merge_bases_many_0(struct repository *r,
On 1/29/2021 12:11 PM, René Scharfe wrote:
Am 28.01.21 um 21:51 schrieb Junio C Hamano:
quoted
"Derrick Stolee via GitGitGadget" [off-list ref] writes:
quoted
+ /* rearrange array */
+ dup = xcalloc(cnt, sizeof(struct commit *));
+ COPY_ARRAY(dup, array, cnt);
+ for (i = 0; i < cnt; i++) {
+ if (dup[i]->object.flags & STALE) {
+ int insert = cnt - 1 - (i - count_non_stale);
+ array[insert] = dup[i];
+ } else {
+ array[count_non_stale] = dup[i];
+ count_non_stale++;
+ }
+ }
+ free(dup);
The "fill stale ones from the end, non-stale ones from the
beginning" in the loop looks unnecessarily complex to me. I wonder
if we can do only the "fill non-stale ones from the beginning" half,
i.e.
for (i = count_non_stale = 0; i < cnt; i++) {
if (dup[i] is not stale)
array[count_non_stale++] = dup[i];
}
without the "keep the stale one at the end of array[]", and clear
marks using what is in dup[] as starting points before discarding
dup[]?
Or do the callers still look at the entries beyond count_non_stale?
Had the same reaction. Both callers ignore the stale entries.
Ok, I can update that logic accordingly. I wanted to keep consistent
with the comment at the start of the method:
/*
* 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.
*/
but if no caller actually needs that, then I can remove this
behavior. Anyone mind if it is a follow-up patch to change this
part of the behavior?
quoted
Other than that, nicely done.
quoted
+ /* clear marks */
+ for (i = 0; i < cnt; i++) {
+ struct commit_list *parents;
+ parents = array[i]->parents;
+
+ while (parents) {
+ clear_commit_marks(parents->item, STALE);
+ parents = parents->next;
}
This loop clears STALE from the parents of both the non-stale and
stale entries. OK. Should it also clear it from the stale entries
themselves?
clear_commit_marks() walks commits starting from the input commit
(parents->item in this case) and clears the STALE bit as long as
it is present. This way, the accumulated clear_commit_marks() will
walk each commit only once _and_ will visit any of the commits from
'array' that received the STALE bit during the above walk.
Thanks,
-Stolee
On 1/28/2021 3:51 PM, Junio C Hamano wrote:
"Derrick Stolee via GitGitGadget" [off-list ref] writes:
quoted
+ 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;
+ }
+ }
So, the inner loop makes sure we won't revisit STALE parent, but
keep digging parents we haven't seen, and stop when the generation
is old enough. What happens when there is no generation number
computed yet, I wonder... We'll keep getting infinity and dig all
the way down to root?
If we are on commits that have no generation number yet, then we
will walk until reaching commits in the commit-graph file that have
a computed generation (or in the heuristic case, when we have reached
all but one of the commits).
In the case of the commit-graph, all commits will have generation
number "infinity". In such a case, perhaps the old algorithm _is_
the best we can do, at least for now.
The trade-off is that we might walk more commits in unusual cases
with few input commits. That quadratic behavior will take over as
the input size grows, no matter if there is a commit-graph or not.
I can do a big more digging into these unusual cases, especially
when we cannot rely on commit-graphs being present.
One way to ensure we do not regress from the current behavior
would be to condition the new algorithm with
if (generation_numbers_enabled(the_repository))
new_algorithm();
else
old_algorithm();
much like in repo_is_descendant_of().
Is that a good plan?
Thanks,
-Stolee
On 1/30/2021 10:59 PM, Derrick Stolee wrote:
On 1/28/2021 3:51 PM, Junio C Hamano wrote:
quoted
"Derrick Stolee via GitGitGadget" [off-list ref] writes:
quoted
+ 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;
+ }
+ }
So, the inner loop makes sure we won't revisit STALE parent, but
keep digging parents we haven't seen, and stop when the generation
is old enough. What happens when there is no generation number
computed yet, I wonder... We'll keep getting infinity and dig all
the way down to root?
If we are on commits that have no generation number yet, then we
will walk until reaching commits in the commit-graph file that have
a computed generation (or in the heuristic case, when we have reached
all but one of the commits).
In the case of the commit-graph, all commits will have generation
number "infinity". In such a case, perhaps the old algorithm _is_
the best we can do, at least for now.
The trade-off is that we might walk more commits in unusual cases
with few input commits. That quadratic behavior will take over as
the input size grows, no matter if there is a commit-graph or not.
I can do a big more digging into these unusual cases, especially
when we cannot rely on commit-graphs being present.
Indeed, the old algorithm is better for cases where generation
numbers do not help and there are multiple independent commits.
For example, this command in the Linux kernel repo changes from
0.047s in the old algorithm to 6.6s with the new algorithm:
git -c core.commitGraph=false merge-base --independent 2ecedd756908 d2360a398f0b >/dev/null
One way to ensure we do not regress from the current behavior
would be to condition the new algorithm with
if (generation_numbers_enabled(the_repository))
new_algorithm();
else
old_algorithm();
much like in repo_is_descendant_of().
I will include this in a v2.
Thanks,
-Stolee