[RFC PATCH 04/10] range-diff: zero out elements in "cost" first
- From
Ævar Arnfjörð Bjarmason <avarab@gmail.com>
- Date
- Dec 9, 2021, 19:19 UTC
- Message-ID
- <RFC-patch-04.10-fe9dcb2d453-20211209T191653Z-avarab@gmail.com>
- In-Reply-To
- <RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com>
Have the get_correspondences() function use CALLOC_ARRAY instead of looping over the newly allocated "cost" to zero out some of its elements.
The for-loop that zero'd out elements in "cost" wasn't the first loop in that function, nor did it cover all of its elements, but regardless of that this change doesn't affect its end-state. None of the for-loops touched the same items in the array, so we could have (and an earlier WIP version of this change did) moved the for-loop we're deleting to come first in get_correspondences().
This can be seen from a careful reading of this code added in in d9c66f0b5bf (range-diff: first rudimentary implementation, 2018-08-13) (as well as adding some printf-debugging) we'll set all elements in the in the "n * n" allocated array. That's "n = A+B" where "A" and "B" are the number of commits in our respective ranges.
So let's just allocate this with CALLOC_ARRAY(), and skip these two for-loops. Furthermore let's remove the early exit condition from compute_assignment() in favor of an assert that it must be called with "column_count > 1", then "get_correspondences()" can skip calling it when no further filling of the "a2b" and "b2a" arrays is needed.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com> --- linear-assignment.c | 7 +------ range-diff.c | 13 +++++-------- 2 files changed, 6 insertions(+), 14 deletions(-)
diff --git a/linear-assignment.c b/linear-assignment.c index ecffc09be6e..0c0786a63b6 100644 --- a/linear-assignment.c +++ b/linear-assignment.c @@ -19,12 +19,7 @@ void compute_assignment(int column_count, int row_count, int *cost, int *free_row, free_count = 0, saved_free_count, *pred, *col; int i, j, phase; - if (column_count < 2) { - memset(column2row, 0, sizeof(int) * column_count); - memset(row2column, 0, sizeof(int) * row_count); - return; - } - + assert(column_count > 1); memset(column2row, -1, sizeof(int) * column_count); memset(row2column, -1, sizeof(int) * row_count); ALLOC_ARRAY(v, column_count); diff --git a/range-diff.c b/range-diff.c index 41003033752..b0ccb46ff4c 100644 --- a/range-diff.c +++ b/range-diff.c @@ -312,9 +312,9 @@ static void get_correspondences(struct string_list *a, struct string_list *b, int *cost, c, *a2b, *b2a; size_t i, j; - ALLOC_ARRAY(cost, st_mult(n, n)); - ALLOC_ARRAY(a2b, n); - ALLOC_ARRAY(b2a, n); + CALLOC_ARRAY(cost, st_mult(n, n)); + CALLOC_ARRAY(a2b, n); + CALLOC_ARRAY(b2a, n); for (i = 0; i < a->nr; i++) { struct patch_util *a_util = a->items[i].util; @@ -346,11 +346,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b, cost[i + n * j] = c; } - for (i = a->nr; i < n; i++) - for (j = b->nr; j < n; j++) - cost[i + n * j] = 0; - - compute_assignment(n, n, cost, a2b, b2a); + if (n > 1) + compute_assignment(n, n, cost, a2b, b2a); for (i = 0; i < a->nr; i++) if (a2b[i] >= 0 && a2b[i] < b->nr) {
-- 2.34.1.930.g0f9292b224d