Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection

From

Junio C Hamano <gitster@pobox.com>

Date

Jan 28, 2014, 21:55 UTC

Message-ID

<xmqqbnyvlqki.fsf@gitster.dls.corp.google.com>

In-Reply-To

<b97e63128093f6c5f5cab854b9b9487c4e6b955a.1390234183.git.kirr@mns.spb.ru>

Kirill Smelkov <kirr@mns.spb.ru> writes:

> diff --git a/combine-diff.c b/combine-diff.c
> index 3b92c448..98c2562 100644
> --- a/combine-diff.c
> +++ b/combine-diff.c
> @@ -15,8 +15,8 @@
> ...
> +	while (1) {
> ...
> +		if (cmp < 0) {
> +			if (pprev)
> +				pprev->next = p->next;
> +			ptmp = p;
> +			p = p->next;
> +			free(ptmp);
> +			if (curr == ptmp)
> +				curr = p;
>  			continue;
> ...
> +		if (cmp > 0) {
> +			i++;
> +			continue;
>  		}
> ...
> +
> +		pprev = p;
> +		p = p->next;
> +		i++;
>  	}
>  	return curr;
>  }

Thanks. I very much like the approach.

  http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions

 combine-diff.c | 37 +++++++++++++++----------------------
 1 file changed, 15 insertions(+), 22 deletions(-)

diff --git a/combine-diff.c b/combine-diff.c
index 2d79312..0809e79 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -15,11 +15,10 @@
 static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)
 {
 	struct diff_queue_struct *q = &diff_queued_diff;
-	struct combine_diff_path *p, *pprev, *ptmp;
+	struct combine_diff_path *p, **tail = &curr;
 	int i, cmp;
 
 	if (!n) {
-		struct combine_diff_path *list = NULL, **tail = &list;
 		for (i = 0; i < q->nr; i++) {
 			int len;
 			const char *path;
@@ -43,35 +42,30 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,
 			*tail = p;
 			tail = &p->next;
 		}
-		return list;
+		return curr;
 	}
 
 	/*
-	 * NOTE paths are coming sorted here (= in tree order)
+	 * paths in curr (linked list) and q->queue[] (array) are
+	 * both sorted in the tree order.
 	 */
-
-	pprev = NULL;
-	p = curr;
 	i = 0;
+	while ((p = *tail) != NULL) {
+		cmp = ((i >= q->nr)
+		       ? -1 : strcmp(p->path, q->queue[i]->two->path));
 
-	while (1) {
-		if (!p)
-			break;
-
-		cmp = (i >= q->nr) ? -1
-				   : strcmp(p->path, q->queue[i]->two->path);
 		if (cmp < 0) {
-			if (pprev)
-				pprev->next = p->next;
-			ptmp = p;
-			p = p->next;
-			free(ptmp);
-			if (curr == ptmp)
-				curr = p;
+			/* p->path not in q->queue[]; drop it */
+			struct combine_diff_path *next = p->next;
+
+			if ((*tail = next) != NULL)
+				tail = &next->next;
+			free(p);
 			continue;
 		}
 
 		if (cmp > 0) {
+			/* q->queue[i] not in p->path; skip it */
 			i++;
 			continue;
 		}
@@ -80,8 +74,7 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,
 		p->parent[n].mode = q->queue[i]->one->mode;
 		p->parent[n].status = q->queue[i]->status;
 
-		pprev = p;
-		p = p->next;
+		tail = &p->next;
 		i++;
 	}
 	return curr;