git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[RFC PATCH 10/10] linear-assignment.c: use "intmax_t" instead of "int"

From
Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Date
Dec 9, 2021, 19:19 UTC
Message-ID
<RFC-patch-10.10-46395080b64-20211209T191653Z-avarab@gmail.com>
In-Reply-To
<RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com>

Change the "int" type used by compute_assignment() to "intmax_t". On 64 bit systems this changes the overflow "die" added in the preceding commit (which before that was a segfault) to something that merely takes a very long time and a lot of memory to run.

On my relatively beefy system this completes:
    git -P range-diff --creation-factor=50 origin/master...git-for-windows/main

In around 300 seconds, with a reported max RSS of just under 18GB, but it does give you correct results for all ~50k commitsin that range.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 92 ++++++++++++++++++++++-----------------------
 linear-assignment.h |  8 +---
 range-diff.c        | 11 +++---
 3 files changed, 54 insertions(+), 57 deletions(-)
diff --git a/linear-assignment.c b/linear-assignment.c
index e45099d651a..ccd760520f8 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -7,14 +7,14 @@
 #include "linear-assignment.h"
 #include "compat/gnulib/intprops.h"
 
-static inline int cost_index(int *cost, int a, int b, int c)
+static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)
 {
-	int r;
+	intmax_t r;
 
 	if (INT_MULTIPLY_WRAPV(a, c, &r))
-		die(_("integer overflow in cost[%d + %d * %d] multiplication"), b, a, c);
+		die(_("integer overflow in cost[%"PRIuMAX" + %"PRIuMAX" * %"PRIuMAX"] multiplication"), b, a, c);
 	if (INT_ADD_WRAPV(b, r, &r))
-		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
+		die(_("integer overflow in cost[%"PRIuMAX" + ((%"PRIuMAX" * %"PRIuMAX") = %"PRIuMAX")] addition"), b, a, c, r);
 
 	return r;
 }
@@ -22,15 +22,15 @@ static inline int cost_index(int *cost, int a, int b, int c)
 #define COST(column, row) cost[cost_index(cost, column_count, column, row)]
 
 static void columns_reduction(size_t column_count, size_t row_count,
-			      int *cost,
-			      int *column2row, int *row2column,
-			      int *v)
+			      intmax_t *cost,
+			      intmax_t *column2row, intmax_t *row2column,
+			      intmax_t *v)
 {
-	int i, j;
+	intmax_t i, j;
 
 	/* column reduction */
 	for (j = column_count - 1; j >= 0; j--) {
-		int i1 = 0;
+		intmax_t i1 = 0;
 
 		for (i = 1; i < row_count; i++)
 			if (COST(j, i1) > COST(j, i))
@@ -49,22 +49,22 @@ static void columns_reduction(size_t column_count, size_t row_count,
 }
 
 static void reduction_transfer(size_t column_count, size_t row_count,
-			       int *cost,
-			       int *free_row, int *free_count,
-			       int *column2row, int *row2column,
-			       int *v)
+			       intmax_t *cost,
+			       intmax_t *free_row, intmax_t *free_count,
+			       intmax_t *column2row, intmax_t *row2column,
+			       intmax_t *v)
 {
-	int i, j;
+	intmax_t i, j;
 
 	/* reduction transfer */
 	for (i = 0; i < row_count; i++) {
-		int j1 = row2column[i];
+		intmax_t j1 = row2column[i];
 		if (j1 == -1)
 			free_row[(*free_count)++] = i;
 		else if (j1 < -1)
 			row2column[i] = -2 - j1;
 		else {
-			int min = COST(!j1, i) - v[!j1];
+			intmax_t min = COST(!j1, i) - v[!j1];
 			for (j = 1; j < column_count; j++)
 				if (j != j1 && min > COST(j, i) - v[j])
 					min = COST(j, i) - v[j];
@@ -74,31 +74,31 @@ static void reduction_transfer(size_t column_count, size_t row_count,
 }
 
 static void augmenting_row_reduction(size_t column_count,
-				     int *cost,
-				     int *column2row, int *row2column,
-				     int *free_row, int *free_count, int *saved_free_count,
-				     int *v)
+				     intmax_t *cost,
+				     intmax_t *column2row, intmax_t *row2column,
+				     intmax_t *free_row, intmax_t *free_count, intmax_t *saved_free_count,
+				     intmax_t *v)
 {
 	int phase;
 
 	/* augmenting row reduction */
 	for (phase = 0; phase < 2; phase++) {
-		int i;
-		int k = 0;
+		intmax_t i;
+		intmax_t k = 0;
 
 		*saved_free_count = *free_count;
 		*free_count = 0;
 		while (k < *saved_free_count) {
-			int j;
-			int u1, u2;
-			int j1 = 0, j2, i0;
+			intmax_t j;
+			intmax_t u1, u2;
+			intmax_t j1 = 0, j2, i0;
 
 			i = free_row[k++];
 			u1 = COST(j1, i) - v[j1];
 			j2 = -1;
-			u2 = INT_MAX;
+			u2 = INTMAX_MAX;
 			for (j = 1; j < column_count; j++) {
-				int c = COST(j, i) - v[j];
+				intmax_t c = COST(j, i) - v[j];
 				if (u2 > c) {
 					if (u1 < c) {
 						u2 = c;
@@ -137,15 +137,15 @@ static void augmenting_row_reduction(size_t column_count,
 }
 
 static void augmentation(size_t column_count,
-			 int *cost,
-			 int *column2row, int *row2column,
-			 int *free_row, int free_count,
-			 int *v)
+			 intmax_t *cost,
+			 intmax_t *column2row, intmax_t *row2column,
+			 intmax_t *free_row, intmax_t free_count,
+			 intmax_t *v)
 {
-	int i, j;
-	int *d;
-	int *pred, *col;
-	int saved_free_count;
+	intmax_t i, j;
+	intmax_t *d;
+	intmax_t *pred, *col;
+	intmax_t saved_free_count;
 
 	/* augmentation */
 	saved_free_count = free_count;
@@ -153,8 +153,8 @@ static void augmentation(size_t column_count,
 	ALLOC_ARRAY(pred, column_count);
 	ALLOC_ARRAY(col, column_count);
 	for (free_count = 0; free_count < saved_free_count; free_count++) {
-		int i1 = free_row[free_count], low = 0, up = 0, last, k;
-		int min, c, u1;
+		intmax_t i1 = free_row[free_count], low = 0, up = 0, last, k;
+		intmax_t min, c, u1;
 
 		for (j = 0; j < column_count; j++) {
 			d[j] = COST(j, i1) - v[j];
@@ -184,7 +184,7 @@ static void augmentation(size_t column_count,
 
 			/* scan a row */
 			do {
-				int j1 = col[low++];
+				intmax_t j1 = col[low++];
 
 				i = column2row[j1];
 				u1 = COST(j1, i) - v[j1] - min;
@@ -208,14 +208,14 @@ static void augmentation(size_t column_count,
 update:
 		/* updating of the column pieces */
 		for (k = 0; k < last; k++) {
-			int j1 = col[k];
+			intmax_t j1 = col[k];
 			v[j1] += d[j1] - min;
 		}
 
 		/* augmentation */
 		do {
 			if (j < 0)
-				BUG("negative j: %d", j);
+				BUG("negative j: %"PRIuMAX, j);
 			i = pred[j];
 			column2row[j] = i;
 			SWAP(j, row2column[i]);
@@ -232,15 +232,15 @@ static void augmentation(size_t column_count,
  * i is `cost[j + column_count * i].
  */
 void compute_assignment(size_t column_count, size_t row_count,
-			int *cost,
-			int *column2row, int *row2column)
+			intmax_t *cost,
+			intmax_t *column2row, intmax_t *row2column)
 {
-	int *v;
-	int *free_row, free_count = 0, saved_free_count;
+	intmax_t *v;
+	intmax_t *free_row, free_count = 0, saved_free_count;
 
 	assert(column_count > 1);
-	memset(column2row, -1, sizeof(int) * column_count);
-	memset(row2column, -1, sizeof(int) * row_count);
+	memset(column2row, -1, sizeof(intmax_t) * column_count);
+	memset(row2column, -1, sizeof(intmax_t) * row_count);
 	ALLOC_ARRAY(v, column_count);
 
 	columns_reduction(column_count, row_count, cost, column2row,
diff --git a/linear-assignment.h b/linear-assignment.h
index 9ff055baac1..ee2726a7c8b 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -14,10 +14,6 @@
  * row_count).
  */
 void compute_assignment(size_t column_count, size_t row_count,
-			int *cost,
-			int *column2row, int *row2column);
-
-/* The maximal cost in the cost matrix (to prevent integer overflows). */
-#define COST_MAX (1<<16)
-
+			intmax_t *cost,
+			intmax_t *column2row, intmax_t *row2column);
 #endif
diff --git a/range-diff.c b/range-diff.c
index b0ccb46ff4c..3442ebdd65c 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -302,20 +302,21 @@ static int diffsize(const char *a, const char *b)
 		return count;
 
 	error(_("failed to generate diff"));
-	return COST_MAX;
+	return INT_MAX;
 }
 
 static void get_correspondences(struct string_list *a, struct string_list *b,
 				int creation_factor)
 {
 	size_t n = st_add(a->nr, b->nr);
-	int *cost, c, *a2b, *b2a;
+	intmax_t *cost, c, *a2b, *b2a;
 	size_t i, j;
 
 	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;
 
@@ -327,12 +328,12 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 			else if (a_util->matching < 0 && b_util->matching < 0)
 				c = diffsize(a_util->diff, b_util->diff);
 			else
-				c = COST_MAX;
+				c = INT_MAX;
 			cost[i + n * j] = c;
 		}
 
 		c = a_util->matching < 0 ?
-			a_util->diffsize * creation_factor / 100 : COST_MAX;
+			a_util->diffsize * creation_factor / 100 : INT_MAX;
 		for (j = b->nr; j < n; j++)
 			cost[i + n * j] = c;
 	}
@@ -341,7 +342,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 		struct patch_util *util = b->items[j].util;
 
 		c = util->matching < 0 ?
-			util->diffsize * creation_factor / 100 : COST_MAX;
+			util->diffsize * creation_factor / 100 : INT_MAX;
 		for (i = a->nr; i < n; i++)
 			cost[i + n * j] = c;
 	}

-- 
2.34.1.930.g0f9292b224d
Previous: Ævar Arnfjörð BjarmasonNext: Jeff King
Message 23 of 44 in “range-diff: fix segfault due to integer overflow”
  1. 00/10 range-diff: fix segfault due to integer overflowÆvar Arnfjörð Bjarmason, Dec 9, 2021
  2. 01/10 string-list API: change "nr" and "alloc" to "size_t"Ævar Arnfjörð Bjarmason, Dec 9, 2021
  3. 02/10 range-diff.c: don't use st_mult() for signed "int"Ævar Arnfjörð Bjarmason, Dec 9, 2021
  4. Jeff KingDec 10, 2021
  5. Ævar Arnfjörð BjarmasonDec 10, 2021
  6. Jeff KingDec 10, 2021
  7. Ævar Arnfjörð BjarmasonDec 10, 2021
  8. Phillip WoodDec 10, 2021
  9. Jeff KingDec 14, 2021
  10. Johannes SchindelinDec 10, 2021
  11. Ævar Arnfjörð BjarmasonDec 10, 2021
  12. Johannes SchindelinDec 11, 2021
  13. Ævar Arnfjörð BjarmasonDec 12, 2021
  14. Jeff KingDec 14, 2021
  15. 03/10 range-diff.c: use "size_t" to refer to "struct string_list"'s "nr"Ævar Arnfjörð Bjarmason, Dec 9, 2021
  16. 05/10 linear-assignment.c: split up compute_assignment() functionÆvar Arnfjörð Bjarmason, Dec 9, 2021
  17. 04/10 range-diff: zero out elements in "cost" firstÆvar Arnfjörð Bjarmason, Dec 9, 2021
  18. 06/10 linear-assignment.c: take "size_t", not "int" for *_countÆvar Arnfjörð Bjarmason, Dec 9, 2021
  19. 07/10 linear-assignment.c: convert a macro to a "static inline" functionÆvar Arnfjörð Bjarmason, Dec 9, 2021
  20. 08/10 linear-assignment.c: detect signed add/mul on GCC and ClangÆvar Arnfjörð Bjarmason, Dec 9, 2021
  21. Jeff KingDec 10, 2021
  22. 09/10 linear-assignment.c: add and use intprops.h from GnulibÆvar Arnfjörð Bjarmason, Dec 9, 2021
  23. 10/10 linear-assignment.c: use "intmax_t" instead of "int"Ævar Arnfjörð Bjarmason, Dec 9, 2021
  24. Jeff KingDec 10, 2021
  25. 0/5 range-diff: fix segfault due to integer overflowÆvar Arnfjörð Bjarmason, Dec 10, 2021
  26. 1/5 range-diff: zero out elements in "cost" firstÆvar Arnfjörð Bjarmason, Dec 10, 2021
  27. Jeff KingDec 14, 2021
  28. 2/5 linear-assignment.c: split up compute_assignment() functionÆvar Arnfjörð Bjarmason, Dec 10, 2021
  29. Jeff KingDec 14, 2021
  30. 3/5 linear-assignment.c: take "size_t", not "int" for *_countÆvar Arnfjörð Bjarmason, Dec 10, 2021
  31. Jeff KingDec 14, 2021
  32. 4/5 range-diff.c: rename "n" to "column_count" in get_correspondences()Ævar Arnfjörð Bjarmason, Dec 10, 2021
  33. Jeff KingDec 14, 2021
  34. 5/5 range-diff: fix integer overflow & segfault on cost[i + n * j]Ævar Arnfjörð Bjarmason, Dec 10, 2021
  35. Jeff KingDec 14, 2021
  36. Johannes SchindelinDec 10, 2021
  37. Ævar Arnfjörð BjarmasonDec 10, 2021
  38. Philip OakleyDec 21, 2021
  39. Ævar Arnfjörð BjarmasonDec 21, 2021
  40. Johannes SchindelinDec 22, 2021
  41. Jeff KingDec 22, 2021
  42. Philip OakleyDec 24, 2021
  43. Ævar Arnfjörð BjarmasonDec 24, 2021
  44. Philip OakleyDec 24, 2021

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.