Re: [PATCH] use skip_prefix() to avoid more magic numbers

René Scharfe [off-list ref] writes:

This certainly makes it easier to read.

I suspect that the original was done as a (possibly premature)
optimization to avoid having to do strlen(3) on a variable that
points at constant strings for each and every ref we iterate with
for_each_rawref(), and it is somewhat sad to see it lost because
skip_prefix() assumes that the caller never knows the length of the
prefix, though.

Thanks.

Am 07.10.2014 um 20:23 schrieb Junio C Hamano:

René Scharfe [off-list ref] writes:

quoted

@@ -335,20 +337,18 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,
  	static struct {
  		int kind;
  		const char *prefix;
-		int pfxlen;
  	} ref_kind[] = {
-		{ REF_LOCAL_BRANCH, "refs/heads/", 11 },
-		{ REF_REMOTE_BRANCH, "refs/remotes/", 13 },
+		{ REF_LOCAL_BRANCH, "refs/heads/" },
+		{ REF_REMOTE_BRANCH, "refs/remotes/" },
  	};
  
  	/* Detect kind */
  	for (i = 0; i < ARRAY_SIZE(ref_kind); i++) {
  		prefix = ref_kind[i].prefix;
-		if (strncmp(refname, prefix, ref_kind[i].pfxlen))
-			continue;
-		kind = ref_kind[i].kind;
-		refname += ref_kind[i].pfxlen;
-		break;
+		if (skip_prefix(refname, prefix, &refname)) {
+			kind = ref_kind[i].kind;
+			break;
+		}

This certainly makes it easier to read.

I suspect that the original was done as a (possibly premature)
optimization to avoid having to do strlen(3) on a variable that
points at constant strings for each and every ref we iterate with
for_each_rawref(), and it is somewhat sad to see it lost because
skip_prefix() assumes that the caller never knows the length of the
prefix, though.

I didn't think much about the performance implications.  skip_prefix()
doesn't call strlen(3), though.  Your reply made me curious.  The
synthetic test program below can be used to call the old and the new
code numerous times.  I called it like this:

    for a in strncmp skip_prefix
    do
        for b in refs/heads/x refs/remotes/y refs/of/the/third/kind
        do
            time ./test-prefix $a $b
        done
    done

And got the following results:

100000000x strncmp for refs/heads/x, which is a local branch

real    0m2.423s
user    0m2.420s
sys     0m0.000s
100000000x strncmp for refs/remotes/y, which is a remote branch

real    0m4.331s
user    0m4.328s
sys     0m0.000s
100000000x strncmp for refs/of/the/third/kind, which is no branch

real    0m3.878s
user    0m3.872s
sys     0m0.000s
100000000x skip_prefix for refs/heads/x, which is a local branch

real    0m0.891s
user    0m0.888s
sys     0m0.000s
100000000x skip_prefix for refs/remotes/y, which is a remote branch

real    0m1.345s
user    0m1.340s
sys     0m0.000s
100000000x skip_prefix for refs/of/the/third/kind, which is no branch

real    0m1.080s
user    0m1.076s
sys     0m0.000s


The code handles millions of ref strings per second before and after
the change, and with the change it's faster.  I hope the results are
reproducible and make it easier to say goodbye to pfxlen. :)

René

---
 .gitignore    |  1 +
 Makefile      |  1 +
 test-prefix.c | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 89 insertions(+)
 create mode 100644 test-prefix.c

diff --git a/.gitignore b/.gitignore
index 5bfb234..8416c5e 100644
--- a/.gitignore
+++ b/.gitignore

@@ -193,6 +193,7 @@
 /test-mktemp
 /test-parse-options
 /test-path-utils
+/test-prefix
 /test-prio-queue
 /test-read-cache
 /test-regex

diff --git a/Makefile b/Makefile
index f34a2d4..c09b59e 100644
--- a/Makefile
+++ b/Makefile

@@ -561,6 +561,7 @@ TEST_PROGRAMS_NEED_X += test-mergesort
 TEST_PROGRAMS_NEED_X += test-mktemp
 TEST_PROGRAMS_NEED_X += test-parse-options
 TEST_PROGRAMS_NEED_X += test-path-utils
+TEST_PROGRAMS_NEED_X += test-prefix
 TEST_PROGRAMS_NEED_X += test-prio-queue
 TEST_PROGRAMS_NEED_X += test-read-cache
 TEST_PROGRAMS_NEED_X += test-regex

diff --git a/test-prefix.c b/test-prefix.c
new file mode 100644
index 0000000..ddc63af
--- /dev/null
+++ b/test-prefix.c

@@ -0,0 +1,87 @@
+#include "cache.h"
+
+#define ROUNDS 100000000
+
+#define REF_LOCAL_BRANCH    0x01
+#define REF_REMOTE_BRANCH   0x02
+
+static int test_skip_prefix(const char *refname)
+{
+	int kind, i;
+	const char *prefix;
+	static struct {
+		int kind;
+		const char *prefix;
+	} ref_kind[] = {
+		{ REF_LOCAL_BRANCH, "refs/heads/" },
+		{ REF_REMOTE_BRANCH, "refs/remotes/" },
+	};
+
+	for (i = 0; i < ARRAY_SIZE(ref_kind); i++) {
+		prefix = ref_kind[i].prefix;
+		if (skip_prefix(refname, prefix, &refname)) {
+			kind = ref_kind[i].kind;
+			break;
+		}
+	}
+	if (ARRAY_SIZE(ref_kind) <= i)
+		return 0;
+	return kind;
+}
+
+static int test_strncmp(const char *refname)
+{
+	int kind, i;
+	const char *prefix;
+	static struct {
+		int kind;
+		const char *prefix;
+		int pfxlen;
+	} ref_kind[] = {
+		{ REF_LOCAL_BRANCH, "refs/heads/", 11 },
+		{ REF_REMOTE_BRANCH, "refs/remotes/", 13 },
+	};
+
+	for (i = 0; i < ARRAY_SIZE(ref_kind); i++) {
+		prefix = ref_kind[i].prefix;
+		if (strncmp(refname, prefix, ref_kind[i].pfxlen))
+			continue;
+		kind = ref_kind[i].kind;
+		refname += ref_kind[i].pfxlen;
+		break;
+	}
+	if (ARRAY_SIZE(ref_kind) <= i)
+		return 0;
+	return kind;
+}
+
+int main(int argc, char **argv)
+{
+	if (argc == 3) {
+		int (*fn)(const char *) = NULL;
+		printf("%dx %s for %s, which is ", ROUNDS, argv[1], argv[2]);
+		if (!strcmp(argv[1], "skip_prefix"))
+			fn = test_skip_prefix;
+		if (!strcmp(argv[1], "strncmp"))
+			fn = test_strncmp;
+		if (fn) {
+			int i, kind = 0;
+			for (i = 0; i < ROUNDS; i++)
+				kind |= fn(argv[2]);
+			switch (kind) {
+			case 0:
+				puts("no branch");
+				break;
+			case REF_LOCAL_BRANCH:
+				puts("a local branch");
+				break;
+			case REF_REMOTE_BRANCH:
+				puts("a remote branch");
+				break;
+			default:
+				puts("invalid");
+			}
+		}
+	}
+	return 0;
+}

-- 
2.1.2