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

From: René Scharfe <l.s.r@web.de>
Date: Oct 9, 2014, 20:06 UTC
Message-ID: <5436EAB5.2070809@web.de>
In-Reply-To: <xmqqd2a3g2mf.fsf@gitster.dls.corp.google.com>

Am 07.10.2014 um 20:23 schrieb Junio C Hamano:

Show 35 quoted lines

> René Scharfe <l.s.r@web.de> writes:
> 
>> @@ -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