commit 8be88dfa934d602d1cf29ba3e33162511f08b748
from: Stefan Sperling <stsp@stsp.name>
date: Wed Oct 21 21:57:37 2020 UTC

cache kd_buf in struct diff_state to avoid repeated allocation + free

commit - 41f13ea5f1c5014b2868a2d6165f377fb3df8ce1
commit + 8be88dfa934d602d1cf29ba3e33162511f08b748
blob - e4d0d0f911a91395f8dd56ae7de181ff081cfbdf
blob + 94ef28c472ae1b07dee34bf8618414ded3037d74
--- lib/diff_internal.h
+++ lib/diff_internal.h
@@ -212,6 +212,10 @@ struct diff_state {
 	/* Remaining chunks from one diff algorithm pass, if any solved == false
 	 * chunks came up. */
 	diff_chunk_arraylist_t temp_result;
+
+ 	/* State buffer used by Myers algorithm. */
+	int *kd_buf;
+	size_t kd_buf_size; /* in units of sizeof(int), not bytes */
 };
 
 struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
blob - 9657150c85b801843b050722f1f56a5374458564
blob + 5491daca7ddd634de43ca8d3f1030e4115db3f35
--- lib/diff_main.c
+++ lib/diff_main.c
@@ -517,6 +517,8 @@ diff_run_algo(const struct diff_algo_config *algo_conf
 		struct diff_state inner_state = {
 			.result = state->result,
 			.recursion_depth_left = state->recursion_depth_left - 1,
+			.kd_buf = state->kd_buf,
+			.kd_buf_size = state->kd_buf_size,
 		};
 		diff_data_init_subsection(&inner_state.left, &state->left,
 					  c->left_start, c->left_count);
@@ -524,7 +526,8 @@ diff_run_algo(const struct diff_algo_config *algo_conf
 					  c->right_start, c->right_count);
 
 		rc = diff_run_algo(algo_config->inner_algo, &inner_state);
-
+		state->kd_buf = inner_state.kd_buf;
+		state->kd_buf_size = inner_state.kd_buf_size;
 		if (rc != DIFF_RC_OK)
 			goto return_rc;
 	}
@@ -564,6 +567,8 @@ diff_main(const struct diff_config *config,
 	struct diff_state state = {
 		.result = result,
 		.recursion_depth_left = config->max_recursion_depth ? : 32,
+		.kd_buf = NULL,
+		.kd_buf_size = 0,
 	};
 	diff_data_init_subsection(&state.left, &result->left,
 				  result->left.atoms.head,
@@ -573,6 +578,7 @@ diff_main(const struct diff_config *config,
 				  result->right.atoms.len);
 
 	result->rc = diff_run_algo(config->algo, &state);
+	free(state.kd_buf);
 
 	return result;
 }
blob - bb8138766878fb94ca61dd3150b7dd4986f79033
blob + 5eaebfacda33fd3b4931e4077bfad705adb4803c
--- lib/diff_myers.c
+++ lib/diff_myers.c
@@ -819,6 +819,7 @@ diff_algo_myers_divide(const struct diff_algo_config *
 	int rc = ENOMEM;
 	struct diff_data *left = &state->left;
 	struct diff_data *right = &state->right;
+	int *kd_buf;
 
 	debug("\n** %s\n", __func__);
 	debug("left:\n");
@@ -832,9 +833,16 @@ diff_algo_myers_divide(const struct diff_algo_config *
 	unsigned int max = left->atoms.len + right->atoms.len;
 	size_t kd_len = max + 1;
 	size_t kd_buf_size = kd_len << 1;
-	int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
-	if (!kd_buf)
-		return ENOMEM;
+
+	if (state->kd_buf_size < kd_buf_size) {
+		kd_buf = reallocarray(state->kd_buf, kd_buf_size,
+		    sizeof(int));
+		if (!kd_buf)
+			return ENOMEM;
+		state->kd_buf = kd_buf;
+		state->kd_buf_size = kd_buf_size;
+	} else
+		kd_buf = state->kd_buf;
 	int i;
 	for (i = 0; i < kd_buf_size; i++)
 		kd_buf[i] = -1;
@@ -1079,7 +1087,6 @@ diff_algo_myers_divide(const struct diff_algo_config *
 	rc = DIFF_RC_OK;
 
 return_rc:
-	free(kd_buf);
 	debug("** END %s\n", __func__);
 	return rc;
 }
@@ -1097,6 +1104,7 @@ diff_algo_myers(const struct diff_algo_config *algo_co
 	int rc = ENOMEM;
 	struct diff_data *left = &state->left;
 	struct diff_data *right = &state->right;
+	int *kd_buf;
 
 	debug("\n** %s\n", __func__);
 	debug("left:\n");
@@ -1119,9 +1127,16 @@ diff_algo_myers(const struct diff_algo_config *algo_co
 		return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
 	}
 
-	int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
-	if (!kd_buf)
-		return ENOMEM;
+	if (state->kd_buf_size < kd_buf_size) {
+		kd_buf = reallocarray(state->kd_buf, kd_buf_size,
+		    sizeof(int));
+		if (!kd_buf)
+			return ENOMEM;
+		state->kd_buf = kd_buf;
+		state->kd_buf_size = kd_buf_size;
+	} else
+		kd_buf = state->kd_buf;
+
 	int i;
 	for (i = 0; i < kd_buf_size; i++)
 		kd_buf[i] = -1;
@@ -1439,7 +1454,6 @@ diff_algo_myers(const struct diff_algo_config *algo_co
 	rc = DIFF_RC_OK;
 
 return_rc:
-	free(kd_buf);
 	debug("** END %s rc=%d\n", __func__, rc);
 	return rc;
 }