Big git diff speedup by avoiding x86 "fast string" memcmp

I was actually discussing this with Linus a while back, and finally got around to testing it out now that I have a modern CPU to measure it on! CCing linux-arch because it would be interesting to know whether your tuned functions do better than gcc or not (I would suspect not).

BTW. patch and numbers are on top of my scaling series, just for an idea of what it does, I just want to generate some interesting discussion.

If people are interested in running benchmarks, I'll be pushing out a new update soon, after some more testing and debugging here.

The standard memcmp function on a Westmere system shows up hot in profiles in the git diff workload (both parallel and single threaded), and it is likely due to the costs associated with trapping into microcode, and little opportunity to improve memory access (dentry name is not likely to take up more than a cacheline).

So replace it with an open-coded byte comparison. This increases code size by 24 bytes in the critical __d_lookup_rcu function, but the speedup is huge, averaging 10 runs of each:

git diff st   user   sys   elapsed  CPU
before        1.15   2.57  3.82      97.1
after         1.14   2.35  3.61      96.8

git diff mt   user   sys   elapsed  CPU
before        1.27   3.85  1.46     349
after         1.26   3.54  1.43     333

Elapsed time for single threaded git diff at 95.0% confidence:

        -0.21  +/- 0.01
        -5.45% +/- 0.24%

include/linux/dcache.h struct dentry_stat_t { · line 62

Quoted 13 lines · Nick Piggin

include/linux/dcache.h +13 -0

+static inline int dentry_memcmp(const unsigned char *cs,
+				const unsigned char *ct, size_t count)
+{
+	while (count) {
+		int ret = (*cs != *ct);
+		if (ret)
+			return ret;
+		cs++;
+		ct++;
+		count--;
+	}
+	return 0;
+}

we have a memcmp() in lib/string.c. Maybe reuse it from there?

include/linux/dcache.h struct dentry_stat_t { · line 62

Quoted 13 lines · Nick Piggin

include/linux/dcache.h +13 -0

+static inline int dentry_memcmp(const unsigned char *cs,
+				const unsigned char *ct, size_t count)
+{
+	while (count) {
+		int ret = (*cs != *ct);
+		if (ret)
+			return ret;
+		cs++;
+		ct++;
+		count--;
+	}
+	return 0;
+}

we have a memcmp() in lib/string.c. Maybe reuse it from there?

So replace it with an open-coded byte comparison. This increases code size by 24 bytes in the critical __d_lookup_rcu function, but the

speedup is huge, averaging 10 runs of each:

git diff st user sys elapsed CPU

git diff mt user sys elapsed CPU

The standard memcmp function on a Westmere system shows up hot in profiles in the git diff workload (both parallel and single threaded), and it is likely due to the costs associated with trapping into microcode, and little opportunity to improve memory access (dentry name is not likely to take up more than a cacheline).

Nick Piggin:

Quoted 5 lines

The standard memcmp function on a Westmere system shows up hot in profiles in the git diff workload (both parallel and single threaded), and it is likely due to the costs associated with trapping into microcode, and little opportunity to improve memory access (dentry name is not likely to take up more than a cacheline).

Let me make sure.
What you are pointing out is
- asm("repe; cmpsb") may grab CPU long time, and can be a hazard for scaling.
- by breaking it into pieces, the chances to scale will increase. Right?

Anyway this appraoch replacing smallest code by larger but faster code is interesting.
How about mixing 'unsigned char *' and 'unsigned long *' in referencing the given strings?
For example,

int f(const unsigned char *cs, const unsigned char *ct, size_t count)

{
	int ret;
	union {
		const unsigned long *l;
		const unsigned char *c;
	} s, t;

/* this macro is your dentry_memcmp() actually */

#define cmp(s, t, c, step)		      \
	do {				      \
		while ((c) >= (step)) {	      \
			ret = (*(s) != *(t)); \
			if (ret)	      \
				return ret;   \
			(s)++;		      \
			(t)++;		      \
			(c) -= (step);	      \
		}			      \
	} while (0)

	s.c = cs;
	t.c = ct;
	cmp(s.l, t.l, count, sizeof(*s.l));
	cmp(s.c, t.c, count, sizeof(*s.c));
	return 0;
}

What I am thinking here is,
- in load and compare, there is no difference between 'char*' and 'long*', probably.
- obviously 'step by sizeof(long)' will reduce the number of repeats.
- but I am not sure whether the length of string is generally longer than 4 (or 8) or not.

It's not scaling but just single threaded performance. gcc turns memcmp into rep cmp, which has quite a long latency, so it's not appripriate for short strings.

Nick Piggin:

Quoted 3 lines

It's not scaling but just single threaded performance. gcc turns memcmp into rep cmp, which has quite a long latency, so it's not appripriate for short strings.

Honestly speaking I doubt how this 'long *' approach is effective (Of course it never means that your result (by 'char *') is doubtful).

But is the "rep cmp has quite a long latency" issue generic for all x86 architecture, or Westmere system specific?

Well, let's see what turns up. We certainly can try the long * approach. I suspect on architectures where byte loads are very slow, gcc will block the loop into larger loads, so it should be no worse than a normal memcmp call, but if we do explicit padding we can avoid all the problems associated with tail handling.

In short, I think the change should be suitable for all x86 CPUs, but I would like to hear more opinions or see numbers for other cores.

Nick Piggin:

Quoted 6 lines

Well, let's see what turns up. We certainly can try the long * approach. I suspect on architectures where byte loads are very slow, gcc will block the loop into larger loads, so it should be no worse than a normal memcmp call, but if we do explicit padding we can avoid all the problems associated with tail handling.

Thank you for your reply.
But unfortunately I am afraid that I cannot understand what you wrote clearly due to my poor English. What I understood is,
- I suggested 'long *' approach
- You wrote "not bad and possible, but may not be worth"
- I agreed "the approach may not be effective"
And you gave deeper consideration, but the result is unchaged which means "'long *' approach may not be worth". Am I right?

Quoted 3 lines

In short, I think the change should be suitable for all x86 CPUs, but I would like to hear more opinions or see numbers for other cores.

I'd like to hear from other x86 experts too.
Also I noticed that memcmp for x86_32 is defined as __builtin_memcmp (for x86_64 is "rep cmp"). Why does x86_64 doesn't use __builtin_memcmp? Is it really worse?

J. R. Okajima

What I meant is that a "normal" memcmp that does long * memory operations is not a good idea, because it requires code and branches to handle the tail of the string. When average string lengths are less than 16 bytes, it hardly seems wothwhile. It will just get more mispredicts and bigger icache footprint.

However instead of a normal memcmp, we could actually pad dentry names out to sizeof(long) with zeros, and take advantage of that with a memcmp that does not have to handle tails -- it would operate entirely with longs.

That would avoid icache and branch regressions, and might speed up the operation on some architectures. I just doubted whether it would show an improvement to be worth doing at all. If it does, I'm all for it.

However instead of a normal memcmp, we could actually pad dentry names out to sizeof(long) with zeros, and take advantage of that with a memcmp that does not have to handle tails -- it would operate entirely with longs.

That would avoid icache and branch regressions, and might speed up the operation on some architectures. I just doubted whether it would show an improvement to be worth doing at all. If it does, I'm all for it.

I agree that the byte-compare or long-compare should give you very close results in modern pipeline CPUs. But surly 12 increments-and-test should show up against 3 (or even 2). I would say it must be a better plan.

From: Boaz Harrosh <[email protected]>
Date: Wed, 15 Dec 2010 15:15:09 +0200

Quoted 3 lines

I agree that the byte-compare or long-compare should give you very close results in modern pipeline CPUs. But surly 12 increments-and-test should show up against 3 (or even 2). I would say it must be a better plan.

For strings of these lengths the setup code necessary to initialize the inner loop and the tail code to handle the sub-word ending cases eliminate whatever gains there are.

I know this as I've been hacking on assembler optimized strcmp() and memcmp() in my spare time over the past year or so.

Quoted 11 lines · David Miller

From: Boaz Harrosh <[email protected]>
Date: Wed, 15 Dec 2010 15:15:09 +0200

Quoted 3 lines

I agree that the byte-compare or long-compare should give you very close results in modern pipeline CPUs. But surly 12 increments-and-test should show up against 3 (or even 2). I would say it must be a better plan.

For strings of these lengths the setup code necessary to initialize the inner loop and the tail code to handle the sub-word ending cases eliminate whatever gains there are.

You miss understood me. I'm saying that we know the beggining of the string is aligned and Nick offered to pad the last long, so surly a shift by 2 (or 3) + the reduction of the 12 dec-and-test to 3 should give you an optimization?

Quoted 13 lines · Boaz Harrosh

Quoted 11 lines · David Miller

From: Boaz Harrosh <[email protected]>
Date: Wed, 15 Dec 2010 15:15:09 +0200

Quoted 3 lines

I agree that the byte-compare or long-compare should give you very close results in modern pipeline CPUs. But surly 12 increments-and-test should show up against 3 (or even 2). I would say it must be a better plan.

For strings of these lengths the setup code necessary to initialize the inner loop and the tail code to handle the sub-word ending cases eliminate whatever gains there are.

Quoted 4 lines

You miss understood me. I'm saying that we know the beggining of the string is aligned and Nick offered to pad the last long, so surly a shift by 2 (or 3) + the reduction of the 12 dec-and-test to 3 should give you an optimization?

Masking is still going to take a bit more code, but perhaps. We're talking a handful of cycles here, so if you add a branch mispredict, or icache miss, you'll kill your savings.

This is what I've got at the moment, which adds only 8 bytes over the rep cmp variant, in the __d_lookup_rcu function.

static inline int dentry_memcmp(const unsigned char *cs,
const unsigned char *ct, size_t count)

{
       int ret;
       do {
               ret = (*cs != *ct);
               if (ret)
                       break;
               cs++;
               ct++;
               count--;
       } while (count);
       return ret;
}

Now if we pad and zero fill the dentry name, then we can compare with the path string, but we still have to mask that guy (unfortunately, I didn't consider that earlier) so it's not trivial and adds quite a bit of code size and branches:

static inline int dentry_memcmp_long(const unsigned char *cs,
const unsigned char *ct, ssize_t count)

{
        const unsigned long *ls = (const unsigned long *)cs;
        const unsigned long *lt = (const unsigned long *)ct;

       int ret;
       do {
                unsigned long t = *lt;
                unsigned long s = *ls;
                int shift = 0;

                if (count < 8)
                        shift = (8 - count) * 8;
                t = t & (0xffffffffffffffff >> shift);
               ret = (s != t);
               if (ret)
                       break;
               ls++;
               lt++;
               count-=8;
       } while (count > 0);
       return ret;
}

Something like this should work on little endian. You'd have to coax gcc to generate a cmov to get rid of that branch I think, because it won't be predictable for small string lengths. But then you have to think about icache...

On 12/16/2010 03:13 PM, Nick Piggin wrote:
static inline int dentry_memcmp_long(const unsigned char *cs, const unsigned char *ct, ssize_t count) {
       int ret;
       const unsigned long *ls = (const unsigned long *)cs; const unsigned long *lt = (const unsigned long *)ct;

       while (count > 8) {
               ret = (*cs != *ct);
               if (ret)
                       break;
               cs++;
               ct++;
               count-=8;
       }
       if (count) {
               unsigned long t = *ct & ((0xffffffffffffffff >> ((8 - count) * 8)) ret = (*cs != t)
       }

       return ret;
}

Same as yours but just to avoid the branch inside the loop and slightly smaller code.

BTW: On some ARCHs ++foo is faster than foo++
    and Also, is there a reason not to write the above loop as:

    while(c-- && (ret = (*cs++ != *ct++)))
               ;

You miss understood me. I'm saying that we know the beggining of the string is aligned and Nick offered to pad the last long, so surly a shift by 2 (or 3) + the reduction of the 12 dec-and-test to 3 should give you an optimization?

You miss understood me. I'm saying that we know the beggining of the string is aligned and Nick offered to pad the last long, so surly a shift by 2 (or 3) + the reduction of the 12 dec-and-test to 3 should give you an optimization?

Quoted 2 lines · J. R. Okajima

But is the "rep cmp has quite a long latency" issue generic for all x86 architecture, or Westmere system specific?

I don't believe it is Westmere specific. Intel and AMD have been improving these instructions in the past few years, so Westmere is probably as good or better than any.

That said, rep cmp may not be as heavily optimized as the set and copy string instructions.

In short, I think the change should be suitable for all x86 CPUs, but I would like to hear more opinions or see numbers for other cores.

Quoted 11 lines · Nick Piggin

Quoted 2 lines · J. R. Okajima

But is the "rep cmp has quite a long latency" issue generic for all x86 architecture, or Westmere system specific?

I don't believe it is Westmere specific. Intel and AMD have been improving these instructions in the past few years, so Westmere is probably as good or better than any.

That said, rep cmp may not be as heavily optimized as the set and copy string instructions.

Quoted 4 lines

In short, I think the change should be suitable for all x86 CPUs, but I would like to hear more opinions or see numbers for other cores.

How about other arch? If this is only for x86, shouldn't it be protected by CONFIG_X86?

That's what I would like to know, but I suspect that for very short strings we are dealing with, the custom loop will be fine for everybody.

include/linux/dcache.h struct dentry_stat_t { · line 62

Quoted 13 lines · Nick Piggin

include/linux/dcache.h +13 -0

+static inline int dentry_memcmp(const unsigned char *cs,
+                               const unsigned char *ct, size_t count)
+{
+       while (count) {
+               int ret = (*cs != *ct);
+               if (ret)
+                       return ret;
+               cs++;
+               ct++;
+               count--;
+       }
+       return 0;
+}

Since you are proposing a routine that only compares file names - I wonder whether it would be faster to start at the end and work backwards? If the filenames are the same, it makes no difference - you have to look at all the bytes. But if they are different you might bail out earlier. There are many applications that stick a common prefix onto the start of filenames (just look in "/lib" !), but I think it is less common to add a suffix (longer than "." single letter).