read-cache: speed up add_index_entry

From: Jeff Hostetler <[email protected]>

Signed-off-by Jeff Hostetler <[email protected]>

---
 t/perf/p0004-read-tree.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)
 create mode 100755 t/perf/p0004-read-tree.sh

t/perf/p0004-read-tree.sh new file +14 -0

new file mode 100755
index 0000000..5d8bbf5
@@ -0,0 +1,116 @@
+#!/bin/sh
+
+test_description="Tests performance of read-tree"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+test_checkout_worktree
+
+## usage: dir depth width files
+make_paths () {
+	for f in $(seq $4)
+	do
+		echo $1/file$f

Am 05.04.2017 um 19:38 schrieb [email protected]:

Quoted 28 lines

From: Jeff Hostetler <[email protected]>

Signed-off-by Jeff Hostetler <[email protected]>

---
 t/perf/p0004-read-tree.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)
 create mode 100755 t/perf/p0004-read-tree.sh

t/perf/p0004-read-tree.sh new file +14 -0

new file mode 100755
index 0000000..5d8bbf5
@@ -0,0 +1,116 @@
+#!/bin/sh
+
+test_description="Tests performance of read-tree"
+
+. ./perf-lib.sh
+
+test_perf_default_repo
+test_checkout_worktree
+
+## usage: dir depth width files
+make_paths () {
+	for f in $(seq $4)
+	do
+		echo $1/file$f

t/perf/p0004-read-tree.sh line 24

Quoted 10 lines

t/perf/p0004-read-tree.sh new file +10 -0

+	done;
+	if test $2 -gt 0;
+	then
+		for w in $(seq $3)
+		do
+			make_paths $1/dir$w $(($2 - 1)) $3 $4
+		done
+	fi
+	return 0
+}

"make_paths xxx_dir_xxx 5 10 9" takes more than a minute for me. Providing its results as a file would be quicker but less flexible. The following command prints the same result in less than a second.

	awk -v dir=xxx_dir_xxx -v depth=5 -v width=10 -v files=9 '
        	function make_paths(dir, depth, width, files,  i)
	        {
        	        for (i = 1; i <= files; i++) {
	                        print dir "/file" i
        	        }
	                if (depth > 0) {
        	                for (i = 1; i <= width; i++) {
	                                make_paths(dir "/dir" i, depth - 1, width, files)
        	                }
                	}
	        }
	        END {make_paths(dir, depth, width, files)}
	' </dev/null

It's faster because it avoids calling seq thousands of times.

t/perf/p0004-read-tree.sh line 28

Quoted 5 lines

t/perf/p0004-read-tree.sh new file +4 -0

+
+fill_index () {
+	make_paths $1 $2 $3 $4 |
+	sed "s/^/100644 $EMPTY_BLOB	/" |

You could add the prefix to the script above and avoid this sed call as well.

René

read-cache.c +15 -0

+ */
+int strcmp_offset(const char *s1_in, const char *s2_in, int *first_change)
+{
+	const unsigned char *s1 = (const unsigned char *)s1_in;
+	const unsigned char *s2 = (const unsigned char *)s2_in;
+	int diff = 0;
+	int k;
+
+	*first_change = 0;
+	for (k=0; s1[k]; k++)
+		if ((diff = (s1[k] - s2[k])))
+			goto found_it;
+	if (!s2[k])
+		return 0;
+	diff = -1;

Quoted 21 lines

Add strcmp_offset() function to also return the offset of the first change.

Signed-off-by Jeff Hostetler <[email protected]>

---
 cache.h      |  1 +
 read-cache.c | 29 +++++++++++++++++++++++++++++
 2 files changed, 30 insertions(+)

cache.h +1 -0

index 80b6372..4d82490 100644
@@ -574,6 +574,7 @@ extern int write_locked_index(struct index_state *, struct lock_file *lock, unsi
 extern int discard_index(struct index_state *);
 extern int unmerged_index(const struct index_state *);
 extern int verify_path(const char *path);
+extern int strcmp_offset(const char *s1_in, const char *s2_in, int *first_change);
 extern int index_dir_exists(struct index_state *istate, const char *name, int namelen);
 extern void adjust_dirname_case(struct index_state *istate, char *name);
 extern struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int igncase);

read-cache.c

Quoted 4 lines

read-cache.c +0 -0

index 9054369..b3fc77d 100644

read-cache.c is probably not the best place for such a general string utility function, though I'm not sure where its most apropriate place would be.

Quoted 5 lines

read-cache.c +0 -0

@@ -887,6 +887,35 @@ static int has_file_name(struct index_state *istate,
 	return retval;
 }
 

read-cache.c static int has_file_name(struct index_state *istate, · line 892

Quoted 3 lines

read-cache.c +3 -0

+
+/*
+ * Like strcmp(), but also return the offset of the first change.

This comment doesn't tell us what will happen with the offset parameter if it is NULL or if the two strings are equal. I don't really care about the safety check for NULL: a callsite not interested in the offset should just call strcmp() instead. I'm fine either way. However, setting it to 0 when the strings are equal doesn't seem quite right, does it.

Quoted 16 lines

read-cache.c +15 -0

+ */
+int strcmp_offset(const char *s1_in, const char *s2_in, int *first_change)
+{
+	const unsigned char *s1 = (const unsigned char *)s1_in;
+	const unsigned char *s2 = (const unsigned char *)s2_in;
+	int diff = 0;
+	int k;
+
+	*first_change = 0;
+	for (k=0; s1[k]; k++)
+		if ((diff = (s1[k] - s2[k])))
+			goto found_it;
+	if (!s2[k])
+		return 0;
+	diff = -1;

read-cache.c static int has_file_name(struct index_state *istate, · line 917

Quoted 10 lines

read-cache.c +10 -0

+
+found_it:
+	*first_change = k;
+	if (diff > 0)
+		return 1;
+	else if (diff < 0)
+		return -1;
+	else
+		return 0;
+}

The implementation seems to me a bit long-winded, with more conditional statements than necessary. How about something like this instead? Much shorter, no goto and only half the number of conditionals to reason about, leaves *first_change untouched when the two strings are equal, and deals with it being NULL.

int strcmp_offset(const char *s1, const char *s2, int *first_change)

{
	int k;

	for (k = 0; s1[k] == s2[k]; k++)
		if (s1[k] == '\0')
			return 0;

	if (first_change)
		*first_change = k;
	return ((unsigned char *)s1)[k] - ((unsigned char *)s2)[k];
}

Signed-off-by Jeff Hostetler <[email protected]>

---
 Makefile                      |  1 +
 t/helper/.gitignore           |  1 +
 t/helper/test-strcmp-offset.c | 64 +++++++++++++++++++++++++++++++++++++++++++
 t/t0065-strcmp-offset.sh      | 11 ++++++++
 4 files changed, 77 insertions(+)
 create mode 100644 t/helper/test-strcmp-offset.c
 create mode 100755 t/t0065-strcmp-offset.sh

I think this patch should be squashed into the previous commit; I don't see any reason why the tests should be added in a different commit than the function they are testing.

Quoted 5 lines

 t/helper/test-strcmp-offset.c | 64 +++++++++++++++++++++++++++++++++++++++++++
 t/t0065-strcmp-offset.sh      | 11 ++++++++
 4 files changed, 77 insertions(+)
 create mode 100644 t/helper/test-strcmp-offset.c
 create mode 100755 t/t0065-strcmp-offset.sh

Sure, tests are good, but I have to wonder how this would scale in the long term, when even such simple functions would get their own t/helper/test-func executable and t/tNNNN-func.sh script.

Hi Gábor,

Quoted 3 lines · SZEDER Gábor

I think this patch should be squashed into the previous commit; I don't see any reason why the tests should be added in a different commit than the function they are testing.

I am of two minds there. In some cases, the newly added test demonstrates the intended usage, and therefore makes for a nice documentation. In other cases, the new test is large enough to stand on its own, i.e. to merit a separate patch (also to make reviewing easier).

In this particular case, I tend to the latter: it is large enough a patch that it is easier to review as a separate patch.

Quoted 9 lines

Quoted 5 lines

 t/helper/test-strcmp-offset.c | 64 +++++++++++++++++++++++++++++++++++++++++++
 t/t0065-strcmp-offset.sh      | 11 ++++++++
 4 files changed, 77 insertions(+)
 create mode 100644 t/helper/test-strcmp-offset.c
 create mode 100755 t/t0065-strcmp-offset.sh

Sure, tests are good, but I have to wonder how this would scale in the long term, when even such simple functions would get their own t/helper/test-func executable and t/tNNNN-func.sh script.

True. The proliferation of executables in t/helper/ got a little out of hand.

But there is nothing preventing us from consolidating a few of them into a single executable, using our wonderful option parsing function with OPT_CMDMODE to switch between the different functions.

I could see, for example, how we could consolidate all string-related test helpers into a single one, say, test-strings:

t/helper/test-ctype.c
t/helper/test-regex.c
t/helper/test-strcmp-offset.c
t/helper/test-string-list.c
t/helper/test-line-buffer.c
t/helper/test-urlmatch-normalization.c
t/helper/test-wildmatch.c

Also, these helpers seem to be related to index handling and could go into a new test-index helper:

t/helper/test-dump-cache-tree.c
t/helper/test-dump-split-index.c
t/helper/test-dump-untracked-cache.c
t/helper/test-index-version.c
t/helper/test-scrap-cache-tree.c

t/helper/test-strcmp-offset.c new file +12 -0

new file mode 100644
index 0000000..fe01318
@@ -0,0 +1,64 @@
+#include "cache.h"
+
+struct test_data {
+	const char *s1;
+	const char *s2;
+	int first_change;
+};
+
+static struct test_data data[] = {
+	{ "abc", "abc", 0 },
+	{ "abc", "def", 0 },
+

Am 05.04.2017 um 19:38 schrieb [email protected]:

Quoted 23 lines

t/helper/test-strcmp-offset.c new file +16 -0

new file mode 100644
index 0000000..fe01318
@@ -0,0 +1,64 @@
+#include "cache.h"
+
+struct test_data {
+    const char *s1;
+    const char *s2;
+    int first_change;
+};
+
+static struct test_data data[] = {
+    { "abc", "abc", 0 },
+    { "abc", "def", 0 },
+
+    { "abc", "abz", 2 },
+
+    { "abc", "abcdef", 3 },
+

t/helper/test-strcmp-offset.c line 22

Quoted 6 lines

t/helper/test-strcmp-offset.c new file +6 -0

+    { "abc\xF0zzz", "abc\xFFzzz", 3 },
+
+    { NULL, NULL, 0 }
+};
+
+int try_pair(const char *sa, const char *sb, int first_change)

This should be static, right? Found with -Wmissing-prototypes.

t/helper/test-strcmp-offset.c line 29

Quoted 8 lines

t/helper/test-strcmp-offset.c new file +7 -0

+{
+    int failed = 0;
+    int offset, r_exp, r_tst;
+    int r_exp_sign, r_tst_sign;
+
+    /*
+     * Because differnt CRTs behave differently, only rely on signs

s/differnt/different/

René

Teach add_index_entry_with_check() and has_dir_name() to see if the path of the new item is greater than the last path in the index array before attempting to search for it.

During checkout, merge_working_tree() populates the new index in sorted order, so this change saves at least 2 lookups per file.

Signed-off-by Jeff Hostetler <[email protected]>

Quoted 8 lines

Teach add_index_entry_with_check() and has_dir_name() to see if the path of the new item is greater than the last path in the index array before attempting to search for it.

During checkout, merge_working_tree() populates the new index in sorted order, so this change saves at least 2 lookups per file.

I think the performance numbers from the cover letter should be included here, so they will be included in the history.