git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
* [PATCH v1] diffcore-rename speedup
@ 2017-04-18 19:44 git
  2017-04-18 19:44 ` [PATCH v1] diffcore-rename: speed up register_rename_src git
  0 siblings, 1 reply; 2+ messages in thread
From: git @ 2017-04-18 19:44 UTC (permalink / raw)
  To: git; +Cc: gitster, peff, Jeff Hostetler

From: Jeff Hostetler <jeffhost@microsoft.com>

Here is another micro-optimization for very large repositories.
Speed up register_rename_src() in diffcore-rename.c

Jeff Hostetler (1):
  diffcore-rename: speed up register_rename_src

 diffcore-rename.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)

-- 
2.9.3


^ permalink raw reply	[flat|nested] 2+ messages in thread

* [PATCH v1] diffcore-rename: speed up register_rename_src
  2017-04-18 19:44 [PATCH v1] diffcore-rename speedup git
@ 2017-04-18 19:44 ` git
  0 siblings, 0 replies; 2+ messages in thread
From: git @ 2017-04-18 19:44 UTC (permalink / raw)
  To: git; +Cc: gitster, peff, Jeff Hostetler

From: Jeff Hostetler <jeffhost@microsoft.com>

Teach register_rename_src() to see if new file pair
can simply be appended to the rename_src[] array before
performing the binary search to find the proper insertion
point.

This is a performance optimization.  This routine is called
during run_diff_files in status and the caller is iterating
over the sorted index, so we should expect to be able to
append in the normal case.  The existing insert logic is
preserved so we don't have to assume that, but simply take
advantage of it if possible.

Using t/perf/p0005-status.h (from a parallel patch series),
we get the following improvement on a 4.2M file repo:

Test                                            HEAD~1               HEAD
0005.2: read-tree status br_ballast (4194305)   59.14(31.85+18.79)   55.48(28.52+20.71) -6.2%

On a 1M file repo:
Test                                            HEAD~1            HEAD
0005.2: read-tree status br_ballast (1000001)   8.20(4.82+3.35)   7.91(4.57+3.27) -3.5%

On a smaller repo, like linux.git (58K files), results are masked
by normal I/O variance.

Test                                          HEAD~1            HEAD
0005.2: read-tree status br_ballast (57994)   0.43(0.30+0.13)   0.42(0.31+0.12) -2.3%
0005.2: read-tree status br_ballast (57994)   0.42(0.32+0.09)   0.43(0.34+0.10) +2.4%
0005.2: read-tree status br_ballast (57994)   0.44(0.33+0.10)   0.42(0.26+0.16) -4.5%

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 diffcore-rename.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index f7444c8..543a409 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -81,6 +81,18 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
 
 	first = 0;
 	last = rename_src_nr;
+
+	if (last > 0) {
+		struct diff_rename_src *src = &(rename_src[last-1]);
+		int cmp = strcmp(one->path, src->p->one->path);
+		if (!cmp)
+			return src;
+		if (cmp > 0) {
+			first = last;
+			goto append_it;
+		}
+	}
+
 	while (last > first) {
 		int next = (last + first) >> 1;
 		struct diff_rename_src *src = &(rename_src[next]);
@@ -94,6 +106,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
 		first = next+1;
 	}
 
+append_it:
 	/* insert to make it at "first" */
 	ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
 	rename_src_nr++;
-- 
2.9.3


^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, back to index

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-04-18 19:44 [PATCH v1] diffcore-rename speedup git
2017-04-18 19:44 ` [PATCH v1] diffcore-rename: speed up register_rename_src git

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox