Emit generated runs in batches, not a write each

1 file changed, 33 insertions, 44 deletions

diff --git a/source/ui-ssdiff.c b/source/ui-ssdiff.c
index 7cea09e..e4472c4 100644
--- a/source/ui-ssdiff.c
+++ b/source/ui-ssdiff.c
@@ -18,14 +18,20 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
-static void create_or_reset_lcs_table(void)
+/*
+ * The table does not need clearing between calls. The fill below assigns
+ * every cell in [0,m] x [0,n] before anything reads it: a read only happens
+ * where both lines still have a character, so it never reaches past row m or
+ * column n, and the loops run downwards so the neighbour is always already
+ * written. Clearing the whole table on every changed line pair cost more than
+ * the comparison it was preparing for.
+ */
+static void create_lcs_table(void)
 {
 	int i;
 
-	if (L != NULL) {
-		memset(*L, 0, sizeof(int) * MAX_SSDIFF_SIZE);
+	if (L != NULL)
 		return;
-	}
 
 	// xcalloc will die if we ran out of memory;
 	// not very helpful for debugging
@@ -50,7 +56,7 @@ static char *longest_common_subsequence(char *A, char *B)
 	if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
 		return NULL;
 
-	create_or_reset_lcs_table();
+	create_lcs_table();
 
 	for (i = m; i >= 0; i--) {
 		for (j = n; j >= 0; j--) {
@@ -110,44 +116,20 @@ static int line_from_hunk(char *line, char type)
 
 static char *replace_tabs(char *line)
 {
-	char *prev_buf = line;
-	char *cur_buf;
-	size_t linelen = strlen(line);
-	int n_tabs = 0;
-	int i;
-	char *result;
-	size_t result_len;
-
-	if (linelen == 0) {
-		result = xmalloc(1);
-		result[0] = '\0';
-		return result;
-	}
+	struct strbuf out = STRBUF_INIT;
+	const char *p;
 
-	for (i = 0; i < linelen; i++) {
-		if (line[i] == '\t')
-			n_tabs += 1;
-	}
-	result_len = linelen + n_tabs * 8;
-	result = xmalloc(result_len + 1);
-	result[0] = '\0';
-
-	for (;;) {
-		cur_buf = strchr(prev_buf, '\t');
-		if (!cur_buf) {
-			linelen = strlen(result);
-			strlcpy(&result[linelen], prev_buf, result_len - linelen + 1);
-			break;
-		} else {
-			linelen = strlen(result);
-			strlcpy(&result[linelen], prev_buf, cur_buf - prev_buf + 1);
-			linelen = strlen(result);
-			memset(&result[linelen], ' ', 8 - (linelen % 8));
-			result[linelen + 8 - (linelen % 8)] = '\0';
-		}
-		prev_buf = cur_buf + 1;
+	// Each tab runs to the next eight-column stop. Walking the line once
+	// and appending replaces a loop that measured the result and rescanned
+	// the rest of the input at every tab, which made a tab-heavy line
+	// quadratic in its own length.
+	for (p = line; *p; p++) {
+		if (*p == '\t')
+			strbuf_addchars(&out, ' ', 8 - (out.len % 8));
+		else
+			strbuf_addch(&out, *p);
 	}
-	return result;
+	return strbuf_detach(&out, NULL);
 }
 
 static int calc_deferred_lines(struct deferred_lines *start)
@@ -210,28 +192,35 @@ static void print_part_with_lcs(const char *class, char *line, char *lcs)
 {
 	int line_len = strlen(line);
 	int i, j;
-	char c[2] = " ";
 	int same = 1;
+	struct strbuf run = STRBUF_INIT;
 
+	// Collect each stretch that is wholly inside or wholly outside the
+	// common subsequence and escape it in one go. Escaping a character at a
+	// time meant a write syscall per character of every changed line, which
+	// dominated this page.
 	j = 0;
 	for (i = 0; i < line_len; i++) {
-		c[0] = line[i];
 		if (same) {
 			if (line[i] == lcs[j])
 				j += 1;
 			else {
 				same = 0;
+				flush_run(&run);
 				htmlf("<span class='%s'>", class);
 			}
 		} else if (line[i] == lcs[j]) {
 			same = 1;
+			flush_run(&run);
 			html("</span>");
 			j += 1;
 		}
-		html_txt(c);
+		strbuf_addch(&run, line[i]);
 	}
+	flush_run(&run);
 	if (!same)
 		html("</span>");
+	strbuf_release(&run);
 }
 
 static void print_ssdiff_line(const char *class,