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

Re: [PATCH] Speedup recursive by flushing index only once for all entries

From
Junio C Hamano <junkio@cox.net>
Date
Jan 10, 2007, 19:28 UTC
Message-ID
<7vr6u2adgx.fsf@assigned-by-dhcp.cox.net>
In-Reply-To
<20070107163112.GA9336@steel.home>
This comes on top of yours.

I'm reproducing all the merges in linux-2.6 history to make sure the base one, yours and this produce the same result (the same clean merge, or the same unmerged index and the same diff from HEAD). So far it is looking good.

-- >8 --
From: Junio C Hamano <junkio@cox.net>
Date: Wed, 10 Jan 2007 11:20:58 -0800
Subject: [PATCH] merge-recursive: do not use on-file index when not needed.

This revamps the merge-recursive implementation following the outline in:

	Message-ID: <7v8xgileza.fsf@assigned-by-dhcp.cox.net>

There is no need to write out the index until the very end just once from merge-recursive. Also there is no need to write out the resulting tree object for the simple case of merging with a single merge base.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 merge-recursive.c |  169 ++++++++++++++--------------------------------------
 1 files changed, 46 insertions(+), 123 deletions(-)
diff --git a/merge-recursive.c b/merge-recursive.c
index aab4c34..5237021 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -110,35 +110,6 @@ static void output_commit_title(struct commit *commit)
 	}
 }
 
-static const char *current_index_file = NULL;
-static const char *original_index_file;
-static const char *temporary_index_file;
-static int cache_dirty = 0;
-
-static int flush_cache(void)
-{
-	/* flush temporary index */
-	struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
-	int fd = hold_lock_file_for_update(lock, current_index_file, 1);
-	if (write_cache(fd, active_cache, active_nr) ||
-			close(fd) || commit_lock_file(lock))
-		die ("unable to write %s", current_index_file);
-	discard_cache();
-	cache_dirty = 0;
-	return 0;
-}
-
-static void setup_index(int temp)
-{
-	current_index_file = temp ? temporary_index_file: original_index_file;
-	if (cache_dirty) {
-		discard_cache();
-		cache_dirty = 0;
-	}
-	unlink(temporary_index_file);
-	discard_cache();
-}
-
 static struct cache_entry *make_cache_entry(unsigned int mode,
 		const unsigned char *sha1, const char *path, int stage, int refresh)
 {
@@ -167,9 +138,6 @@ static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
 		const char *path, int stage, int refresh, int options)
 {
 	struct cache_entry *ce;
-	if (!cache_dirty)
-		read_cache_from(current_index_file);
-	cache_dirty++;
 	ce = make_cache_entry(mode, sha1 ? sha1 : null_sha1, path, stage, refresh);
 	if (!ce)
 		return error("cache_addinfo failed: %s", strerror(cache_errno));
@@ -187,26 +155,6 @@ static int add_cacheinfo(unsigned int mode, const unsigned char *sha1,
  */
 static int index_only = 0;
 
-static int git_read_tree(struct tree *tree)
-{
-	int rc;
-	struct object_list *trees = NULL;
-	struct unpack_trees_options opts;
-
-	if (cache_dirty)
-		die("read-tree with dirty cache");
-
-	memset(&opts, 0, sizeof(opts));
-	object_list_append(&tree->object, &trees);
-	rc = unpack_trees(trees, &opts);
-	cache_tree_free(&active_cache_tree);
-
-	if (rc == 0)
-		cache_dirty = 1;
-
-	return rc;
-}
-
 static int git_merge_trees(int index_only,
 			   struct tree *common,
 			   struct tree *head,
@@ -216,11 +164,6 @@ static int git_merge_trees(int index_only,
 	struct object_list *trees = NULL;
 	struct unpack_trees_options opts;
 
-	if (!cache_dirty) {
-		read_cache_from(current_index_file);
-		cache_dirty = 1;
-	}
-
 	memset(&opts, 0, sizeof(opts));
 	if (index_only)
 		opts.index_only = 1;
@@ -236,39 +179,37 @@ static int git_merge_trees(int index_only,
 
 	rc = unpack_trees(trees, &opts);
 	cache_tree_free(&active_cache_tree);
-
-	cache_dirty = 1;
-
 	return rc;
 }
 
+static int unmerged_index(void)
+{
+	int i;
+	for (i = 0; i < active_nr; i++) {
+		struct cache_entry *ce = active_cache[i];
+		if (ce_stage(ce))
+			return 1;
+	}
+	return 0;
+}
+
 static struct tree *git_write_tree(void)
 {
 	struct tree *result = NULL;
 
-	if (cache_dirty) {
-		unsigned i;
-		for (i = 0; i < active_nr; i++) {
-			struct cache_entry *ce = active_cache[i];
-			if (ce_stage(ce))
-				return NULL;
-		}
-	} else
-		read_cache_from(current_index_file);
+	if (unmerged_index())
+		return NULL;
 
 	if (!active_cache_tree)
 		active_cache_tree = cache_tree();
 
 	if (!cache_tree_fully_valid(active_cache_tree) &&
-			cache_tree_update(active_cache_tree,
-				active_cache, active_nr, 0, 0) < 0)
+	    cache_tree_update(active_cache_tree,
+			      active_cache, active_nr, 0, 0) < 0)
 		die("error building trees");
 
 	result = lookup_tree(active_cache_tree->sha1);
 
-	flush_cache();
-	cache_dirty = 0;
-
 	return result;
 }
 
@@ -331,10 +272,7 @@ static struct path_list *get_unmerged(void)
 	int i;
 
 	unmerged->strdup_paths = 1;
-	if (!cache_dirty) {
-		read_cache_from(current_index_file);
-		cache_dirty++;
-	}
+
 	for (i = 0; i < active_nr; i++) {
 		struct path_list_item *item;
 		struct stage_data *e;
@@ -469,9 +407,6 @@ static int remove_file(int clean, const char *path, int no_wd)
 	int update_working_directory = !index_only && !no_wd;
 
 	if (update_cache) {
-		if (!cache_dirty)
-			read_cache_from(current_index_file);
-		cache_dirty++;
 		if (remove_file_from_cache(path))
 			return -1;
 	}
@@ -1105,9 +1040,7 @@ static int merge_trees(struct tree *head,
 		    sha1_to_hex(head->object.sha1),
 		    sha1_to_hex(merge->object.sha1));
 
-	*result = git_write_tree();
-
-	if (!*result) {
+	if (unmerged_index()) {
 		struct path_list *entries, *re_head, *re_merge;
 		int i;
 		path_list_clear(&current_file_set, 1);
@@ -1128,17 +1061,11 @@ static int merge_trees(struct tree *head,
 			if (!process_entry(path, e, branch1, branch2))
 				clean = 0;
 		}
-		if (cache_dirty)
-			flush_cache();
 
 		path_list_clear(re_merge, 0);
 		path_list_clear(re_head, 0);
 		path_list_clear(entries, 1);
 
-		if (clean || index_only)
-			*result = git_write_tree();
-		else
-			*result = NULL;
 	} else {
 		clean = 1;
 		printf("merging of trees %s and %s resulted in %s\n",
@@ -1146,6 +1073,8 @@ static int merge_trees(struct tree *head,
 		       sha1_to_hex(merge->object.sha1),
 		       sha1_to_hex((*result)->object.sha1));
 	}
+	if (index_only)
+		*result = git_write_tree();
 
 	return clean;
 }
@@ -1170,10 +1099,10 @@ static int merge(struct commit *h1,
 		 const char *branch1,
 		 const char *branch2,
 		 int call_depth /* =0 */,
-		 struct commit *ancestor /* =None */,
+		 struct commit_list *ca,
 		 struct commit **result)
 {
-	struct commit_list *ca = NULL, *iter;
+	struct commit_list *iter;
 	struct commit *merged_common_ancestors;
 	struct tree *mrtree;
 	int clean;
@@ -1182,10 +1111,10 @@ static int merge(struct commit *h1,
 	output_commit_title(h1);
 	output_commit_title(h2);
 
-	if (ancestor)
-		commit_list_insert(ancestor, &ca);
-	else
-		ca = reverse_commit_list(get_merge_bases(h1, h2, 1));
+	if (!ca) {
+		ca = get_merge_bases(h1, h2, 1);
+		ca = reverse_commit_list(ca);
+	}
 
 	output("found %u common ancestor(s):", commit_list_count(ca));
 	for (iter = ca; iter; iter = iter->next)
@@ -1211,6 +1140,7 @@ static int merge(struct commit *h1,
 		 * merge_trees has always overwritten it: the commited
 		 * "conflicts" were already resolved.
 		 */
+		discard_cache();
 		merge(merged_common_ancestors, iter->item,
 		      "Temporary merge branch 1",
 		      "Temporary merge branch 2",
@@ -1223,25 +1153,21 @@ static int merge(struct commit *h1,
 			die("merge returned no commit");
 	}
 
+	discard_cache();
 	if (call_depth == 0) {
-		setup_index(0 /* $GIT_DIR/index */);
+		read_cache();
 		index_only = 0;
-	} else {
-		setup_index(1 /* temporary index */);
-		git_read_tree(h1->tree);
+	} else
 		index_only = 1;
-	}
 
 	clean = merge_trees(h1->tree, h2->tree, merged_common_ancestors->tree,
 			    branch1, branch2, &mrtree);
 
-	if (!ancestor && (clean || index_only)) {
+	if (index_only) {
 		*result = make_virtual_commit(mrtree, "merged tree");
 		commit_list_insert(h1, &(*result)->parents);
 		commit_list_insert(h2, &(*result)->parents->next);
-	} else
-		*result = NULL;
-
+	}
 	return clean;
 }
 
@@ -1277,19 +1203,16 @@ static struct commit *get_ref(const char *ref)
 
 int main(int argc, char *argv[])
 {
-	static const char *bases[2];
+	static const char *bases[20];
 	static unsigned bases_count = 0;
 	int i, clean;
 	const char *branch1, *branch2;
 	struct commit *result, *h1, *h2;
+	struct commit_list *ca = NULL;
+	struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
+	int index_fd;
 
 	git_config(git_default_config); /* core.filemode */
-	original_index_file = getenv(INDEX_ENVIRONMENT);
-
-	if (!original_index_file)
-		original_index_file = xstrdup(git_path("index"));
-
-	temporary_index_file = xstrdup(git_path("mrg-rcrsv-tmp-idx"));
 
 	if (argc < 4)
 		die("Usage: %s <base>... -- <head> <remote> ...\n", argv[0]);
@@ -1313,18 +1236,18 @@ int main(int argc, char *argv[])
 	branch2 = better_branch_name(branch2);
 	printf("Merging %s with %s\n", branch1, branch2);
 
-	if (bases_count == 1) {
-		struct commit *ancestor = get_ref(bases[0]);
-		clean = merge(h1, h2, branch1, branch2, 0, ancestor, &result);
-	} else
-		clean = merge(h1, h2, branch1, branch2, 0, NULL, &result);
+	index_fd = hold_lock_file_for_update(lock, get_index_file(), 1);
 
-	if (cache_dirty)
-		flush_cache();
+	for (i = 0; i < bases_count; i++) {
+		struct commit *ancestor = get_ref(bases[i]);
+		ca = commit_list_insert(ancestor, &ca);
+	}
+	clean = merge(h1, h2, branch1, branch2, 0, ca, &result);
+
+	if (active_cache_changed &&
+	    (write_cache(index_fd, active_cache, active_nr) ||
+	     close(index_fd) || commit_lock_file(lock)))
+			die ("unable to write %s", get_index_file());
 
 	return clean ? 0: 1;
 }
-
-/*
-vim: sw=8 noet
-*/

-- 
1.4.4.4.gc3d6
Previous: Junio C HamanoNext: Junio C Hamano
Message 8 of 40 in “Speedup recursive by flushing index only once for all entries”
  1. Speedup recursive by flushing index only once for all entriesAlex Riesen, Jan 4, 2007
  2. Johannes SchindelinJan 4, 2007
  3. Alex RiesenJan 4, 2007
  4. Junio C HamanoJan 4, 2007
  5. Alex RiesenJan 5, 2007
  6. Alex RiesenJan 7, 2007
  7. Junio C HamanoJan 10, 2007
  8. Junio C HamanoJan 10, 2007
  9. Junio C HamanoJan 10, 2007
  10. Alex RiesenJan 10, 2007
  11. Linus TorvaldsJan 10, 2007
  12. Johannes SchindelinJan 11, 2007
  13. Alex RiesenJan 11, 2007
  14. Alex RiesenJan 11, 2007
  15. Junio C HamanoJan 11, 2007
  16. Alex RiesenJan 11, 2007
  17. Linus TorvaldsJan 11, 2007
  18. Alex RiesenJan 11, 2007
  19. Linus TorvaldsJan 11, 2007
  20. Alex RiesenJan 11, 2007
  21. Junio C HamanoJan 11, 2007
  22. Alex RiesenJan 11, 2007
  23. Linus TorvaldsJan 11, 2007
  24. Junio C HamanoJan 11, 2007
  25. Alex RiesenJan 12, 2007
  26. Junio C HamanoJan 11, 2007
  27. Johannes SchindelinJan 11, 2007
  28. Sergey VlasovJan 12, 2007
  29. Alex RiesenJan 12, 2007
  30. Sergey VlasovJan 12, 2007
  31. Junio C HamanoJan 12, 2007
  32. merge-recursive: do not report the resulting tree object nameJunio C Hamano, Jan 12, 2007
  33. Johannes SchindelinJan 12, 2007
  34. Junio C HamanoJan 13, 2007
  35. Jakub NarebskiJan 13, 2007
  36. Johannes SchindelinJan 13, 2007
  37. Shawn O. PearceJan 13, 2007
  38. Junio C HamanoJan 13, 2007
  39. Alex RiesenJan 12, 2007
  40. Sergey VlasovJan 12, 2007

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.