[PATCH 0/2] split index extra bits

[PATCH 0/2] split index extra bits

[Christian Couder]

This patch series contains 2 patches that have already been sent to
the list but have felt through the cracks. It would be nice if they
could be considered for v2.13.0.

Patch 1/2 (split-index: add and use unshare_split_index()) by Duy
fixes a memory leak when a new shared index file is created and memory
used by the old one should be freed.

Patch 2/2 (p3400: add perf tests for rebasing many changes) adds a
test in t/perf that can help see what performance improvements can be
gained by using the split index feature. For example using this patch
at one point I got the following results on a Linux machine on the Git
repository:

Test                                                            v2.10.0             v2.11.0                  v2.12.0                  origin/master         
------------------------------------------------------------------------------------------------------------------------------------------------------------
3400.2: rebase on top of a lot of unrelated changes             2.62(2.19+0.55)     2.54(2.15+0.49) -3.1%    2.59(2.19+0.49) -1.1%    2.66(2.27+0.52) +1.5% 
3400.4: rebase a lot of unrelated changes without split-index   14.08(10.12+3.92)   7.20(5.85+1.36) -48.9%   8.06(6.54+1.60) -42.8%   7.53(6.40+1.12) -46.5%
3400.6: rebase a lot of unrelated changes with split-index      14.10(10.11+3.94)   6.94(5.71+1.27) -50.8%   7.99(6.49+1.57) -43.3%   6.10(5.12+1.07) -56.7%

On bigger repositories results are likely to be better.

Christian Couder (1):
  p3400: add perf tests for rebasing many changes

Nguyễn Thái Ngọc Duy (1):
  split-index: add and use unshare_split_index()

 read-cache.c           | 10 ++-------
 split-index.c          | 57 ++++++++++++++++++++++++++++++++++++++------------
 split-index.h          |  1 +
 t/perf/p3400-rebase.sh | 22 ++++++++++++++++++-
 4 files changed, 68 insertions(+), 22 deletions(-)

-- 
2.13.0.rc1.83.g83955d3ecd.dirty

[PATCH 1/2] split-index: add and use unshare_split_index()

[Christian Couder]

From: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>

When split-index is being used, we have two cache_entry arrays in
index_state->cache[] and index_state->split_index->base->cache[].

index_state->cache[] may share the same entries with base->cache[] so
we can quickly determine what entries are shared. This makes memory
management tricky, we can't free base->cache[] until we know
index_state->cache[] does not point to any of those entries.

unshare_split_index() is added for this purpose, to find shared
entries and either duplicate them in index_state->cache[], or discard
them. Either way it should be safe to free base->cache[] after
unshare_split_index().

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 read-cache.c  | 10 ++--------
 split-index.c | 57 ++++++++++++++++++++++++++++++++++++++++++++-------------
 split-index.h |  1 +
 3 files changed, 47 insertions(+), 21 deletions(-)

diff --git a/read-cache.c b/read-cache.c
index 0d0081a11b..8da84ae2d1 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1877,15 +1877,9 @@ int discard_index(struct index_state *istate)
 {
 	int i;
 
-	for (i = 0; i < istate->cache_nr; i++) {
-		if (istate->cache[i]->index &&
-		    istate->split_index &&
-		    istate->split_index->base &&
-		    istate->cache[i]->index <= istate->split_index->base->cache_nr &&
-		    istate->cache[i] == istate->split_index->base->cache[istate->cache[i]->index - 1])
-			continue;
+	unshare_split_index(istate, 1);
+	for (i = 0; i < istate->cache_nr; i++)
 		free(istate->cache[i]);
-	}
 	resolve_undo_clear_index(istate);
 	istate->cache_nr = 0;
 	istate->cache_changed = 0;
diff --git a/split-index.c b/split-index.c
index f519e60f87..49bd197f71 100644
--- a/split-index.c
+++ b/split-index.c
@@ -73,10 +73,17 @@ void move_cache_to_base_index(struct index_state *istate)
 	int i;
 
 	/*
-	 * do not delete old si->base, its index entries may be shared
-	 * with istate->cache[]. Accept a bit of leaking here because
-	 * this code is only used by short-lived update-index.
+	 * If "si" is shared with another index_state (e.g. by
+	 * unpack-trees code), we will need to duplicate split_index
+	 * struct. It's not happening now though, luckily.
 	 */
+	assert(si->refcount <= 1);
+
+	unshare_split_index(istate, 0);
+	if (si->base) {
+		discard_index(si->base);
+		free(si->base);
+	}
 	si->base = xcalloc(1, sizeof(*si->base));
 	si->base->version = istate->version;
 	/* zero timestamp disables racy test in ce_write_index() */
@@ -275,11 +282,41 @@ void finish_writing_split_index(struct index_state *istate)
 	istate->cache_nr = si->saved_cache_nr;
 }
 
+void unshare_split_index(struct index_state *istate, int discard)
+{
+	struct split_index *si = istate->split_index;
+	int i;
+
+	if (!si || !si->base)
+		return;
+
+	for (i = 0; i < istate->cache_nr; i++) {
+		struct cache_entry *ce = istate->cache[i];
+		struct cache_entry *new = NULL;
+
+		if (!ce->index ||
+		    ce->index > si->base->cache_nr ||
+		    ce != si->base->cache[ce->index - 1])
+			continue;
+
+		if (!discard) {
+			int len = ce_namelen(ce);
+			new = xcalloc(1, cache_entry_size(len));
+			copy_cache_entry(new, ce);
+			memcpy(new->name, ce->name, len);
+			new->index = 0;
+		}
+		istate->cache[i] = new;
+	}
+}
+
+
 void discard_split_index(struct index_state *istate)
 {
 	struct split_index *si = istate->split_index;
 	if (!si)
 		return;
+	unshare_split_index(istate, 0);
 	istate->split_index = NULL;
 	si->refcount--;
 	if (si->refcount)
@@ -328,14 +365,8 @@ void add_split_index(struct index_state *istate)
 
 void remove_split_index(struct index_state *istate)
 {
-	if (istate->split_index) {
-		/*
-		 * can't discard_split_index(&the_index); because that
-		 * will destroy split_index->base->cache[], which may
-		 * be shared with the_index.cache[]. So yeah we're
-		 * leaking a bit here.
-		 */
-		istate->split_index = NULL;
-		istate->cache_changed |= SOMETHING_CHANGED;
-	}
+	if (!istate->split_index)
+		return;
+	discard_split_index(istate);
+	istate->cache_changed |= SOMETHING_CHANGED;
 }
diff --git a/split-index.h b/split-index.h
index df91c1bda8..65c0f09b2b 100644
--- a/split-index.h
+++ b/split-index.h
@@ -33,5 +33,6 @@ void finish_writing_split_index(struct index_state *istate);
 void discard_split_index(struct index_state *istate);
 void add_split_index(struct index_state *istate);
 void remove_split_index(struct index_state *istate);
+void unshare_split_index(struct index_state *istate, int discard);
 
 #endif
-- 
2.13.0.rc1.83.g83955d3ecd.dirty

[PATCH 2/2] p3400: add perf tests for rebasing many changes

[Christian Couder]

Rebasing onto many changes is interesting, but it's also
interesting to see what happens when rebasing many changes.

And while at it, let's also look at the impact of using a
split index.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 t/perf/p3400-rebase.sh | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/t/perf/p3400-rebase.sh b/t/perf/p3400-rebase.sh
index b3e7d525d2..ce271ca4c1 100755
--- a/t/perf/p3400-rebase.sh
+++ b/t/perf/p3400-rebase.sh
@@ -5,7 +5,7 @@ test_description='Tests rebase performance'
 
 test_perf_default_repo
 
-test_expect_success 'setup' '
+test_expect_success 'setup rebasing on top of a lot of changes' '
 	git checkout -f -b base &&
 	git checkout -b to-rebase &&
 	git checkout -b upstream &&
@@ -33,4 +33,24 @@ test_perf 'rebase on top of a lot of unrelated changes' '
 	git rebase --onto base HEAD^
 '
 
+test_expect_success 'setup rebasing many changes without split-index' '
+	git config core.splitIndex false &&
+	git checkout -b upstream2 to-rebase &&
+	git checkout -b to-rebase2 upstream
+'
+
+test_perf 'rebase a lot of unrelated changes without split-index' '
+	git rebase --onto upstream2 base &&
+	git rebase --onto base upstream2
+'
+
+test_expect_success 'setup rebasing many changes with split-index' '
+	git config core.splitIndex true
+'
+
+test_perf 'rebase a lot of unrelated changes with split-index' '
+	git rebase --onto upstream2 base &&
+	git rebase --onto base upstream2
+'
+
 test_done
-- 
2.13.0.rc1.83.g83955d3ecd.dirty

Re: [PATCH 0/2] split index extra bits

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

> This patch series contains 2 patches that have already been sent to
> the list but have felt through the cracks. It would be nice if they
> could be considered for v2.13.0.

There is no way for anything new to go to 2.13 without getting
reviewed and discussed at this point---it simply is way too late.

Re: [PATCH 0/2] split index extra bits

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Christian Couder <christian.couder@gmail.com> writes:
>
>> This patch series contains 2 patches that have already been sent to
>> the list but have felt through the cracks. It would be nice if they
>> could be considered for v2.13.0.
>
> There is no way for anything new to go to 2.13 without getting
> reviewed and discussed at this point---it simply is way too late.

I found that this is <20170419093314.4454-1-pclouds@gmail.com> in
mid April (please do not make readers dig the list archive when you
can).

I didn't see anybody (not even you, to whom the patch was apparently
addressed) commenting back then on the patch and that was why I
didn't touch it.  I've skimmed the change in 1/2 now, and although I
didn't see anything glaringly wrong, it would be good to have a test
if this fixes a reproducible crash.

Thanks.

Re: [PATCH 0/2] split index extra bits

[Christian Couder]

On Mon, May 8, 2017 at 3:49 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>> Christian Couder <christian.couder@gmail.com> writes:
>>
>>> This patch series contains 2 patches that have already been sent to
>>> the list but have felt through the cracks. It would be nice if they
>>> could be considered for v2.13.0.
>>
>> There is no way for anything new to go to 2.13 without getting
>> reviewed and discussed at this point---it simply is way too late.

Ok, sorry about resending too late.

> I found that this is <20170419093314.4454-1-pclouds@gmail.com> in
> mid April (please do not make readers dig the list archive when you
> can).
>
> I didn't see anybody (not even you, to whom the patch was apparently
> addressed) commenting back then on the patch and that was why I
> didn't touch it.  I've skimmed the change in 1/2 now, and although I
> didn't see anything glaringly wrong, it would be good to have a test
> if this fixes a reproducible crash.

It fixes a memory leak not a crash. And this should not be a big
problem as shared index files should not be changed often in the same
Git process.