Skip to contentSkip to conversation

kernel + gcc 4.1 = several problems

DISCUSSION Mikael Pettersson 16 participants 31 messages Jan 3, 2007 – Jan 7, 2007

lore
Share & tools
lore
#0 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 6 lines

The suggestions I've had so far which I have not yet tried:

(quoted diff) +0 -1
-	Select a different x86 CPU in the config.

- Unfortunately the C3-2 flags seem to simply tell GCC
to schedule for ppro (like i686) and enabled MMX and SSE
- Probably useless

Actually, try this one. Try using something that doesn't like "cmov". Maybe the C3-2 simply has some internal cmov bugginess.

That's a good suggestion. Earlier C3s didn't have cmov so it's not entirely unlikely that cmov in C3-2 is broken in some cases. Configuring for P5MMX or 486 should be good safe alternatives.

/Mikael

#1 lore raw
Quoted 11 lines · Mikael Pettersson
Quoted 9 lines · Linus Torvalds
Quoted 6 lines

The suggestions I've had so far which I have not yet tried:

(quoted diff) +0 -1
-	Select a different x86 CPU in the config.

- Unfortunately the C3-2 flags seem to simply tell GCC
to schedule for ppro (like i686) and enabled MMX and SSE
- Probably useless

Actually, try this one. Try using something that doesn't like "cmov". Maybe the C3-2 simply has some internal cmov bugginess.

Quoted 3 lines

That's a good suggestion. Earlier C3s didn't have cmov so it's not entirely unlikely that cmov in C3-2 is broken in some cases. Configuring for P5MMX or 486 should be good safe alternatives.

Or just C3 (not C3-2), which is what I've done.

I'll report back whether it crashes or not.

Signature · 5 lines
Cheers,
Alistair.

Final year Computer Science undergraduate.
1F2 55 South Clerk Street, Edinburgh, UK.
#2 lore raw
Quoted 12 lines · Alistair John Strachan
Quoted 11 lines · Mikael Pettersson
Quoted 9 lines · Linus Torvalds
Quoted 6 lines

The suggestions I've had so far which I have not yet tried:

(quoted diff) +0 -1
-	Select a different x86 CPU in the config.

- Unfortunately the C3-2 flags seem to simply tell GCC
to schedule for ppro (like i686) and enabled MMX and SSE
- Probably useless

Actually, try this one. Try using something that doesn't like "cmov". Maybe the C3-2 simply has some internal cmov bugginess.

Quoted 7 lines
Quoted 3 lines

That's a good suggestion. Earlier C3s didn't have cmov so it's not entirely unlikely that cmov in C3-2 is broken in some cases. Configuring for P5MMX or 486 should be good safe alternatives.

Or just C3 (not C3-2), which is what I've done.

I'll report back whether it crashes or not.

This didn't help. After about 14 hours, the machine crashed again.

cmov is not the culprit.

Signature · 5 lines
Cheers,
Alistair.

Final year Computer Science undergraduate.
1F2 55 South Clerk Street, Edinburgh, UK.
#3 lore raw
Quoted 4 lines · Alistair John Strachan

This didn't help. After about 14 hours, the machine crashed again.

cmov is not the culprit.

Ok. Have you ever tried to limit the drivers you have loaded? I notice you had the prism54 wireless thing in your modules list and the vt1211 hw monitoring thing. I'm wondering about the vt1211 thing - it probably isn't too common. But if you can use that machine without the wireless too, it might be good to try without either.

(The rest of your module list looked bog-standard, so if it's not hardware-specific, I don't think it's there)

Turning of the VIA sound driver just in case would be good too.

The reason I mention vt1211 in particular is that it does things like regulate fan activity etc. Is the problem perhaps heat-related?

Linus

#4 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 3 lines · Alistair John Strachan

This didn't help. After about 14 hours, the machine crashed again.

cmov is not the culprit.

Ok. Have you ever tried to limit the drivers you have loaded? I notice you had the prism54 wireless thing in your modules list and the vt1211 hw monitoring thing. I'm wondering about the vt1211 thing - it probably isn't too common.

Sure, and it only got added to 2.6.19 anyway (however GCC 3.4.6 really does seem to have no problem with it).

Quoted 2 lines

But if you can use that machine without the wireless too, it might be good to try without either.

Required, plus I've been running prism54 on three different machines with a huge number of compilers since the early 2.6 days with no problems.

Quoted 2 lines

(The rest of your module list looked bog-standard, so if it's not hardware-specific, I don't think it's there)

Agreed, the config is already _very_ minimal for this machine.

Quoted 1 line

Turning of the VIA sound driver just in case would be good too.

I'm not even really sure why that's enabled. I can do that.

Quoted 2 lines

The reason I mention vt1211 in particular is that it does things like regulate fan activity etc. Is the problem perhaps heat-related?

It definitely isn't heat related. This CPU puts out 7-10W, has a ridiculous 5000 RPM fan on it (that works) and the temp never exceeds 40C. If anything, the -O2, 3.4.6 kernel with CMOV ran the chip a little hotter.

As far as I can see, all the other components are either cool to touch or have stupidly big heatsinks on them.

(I realise with problems like these it's almost always some sort of obscure hardware problem, but I find that very difficult to believe when I can toggle from 3 years of stability to 6-18 hours crashing by switching compiler. I've also ran extensive stability test programs on the hardware with absolutely no negative results.)

Signature · 5 lines
Cheers,
Alistair.

Final year Computer Science undergraduate.
1F2 55 South Clerk Street, Edinburgh, UK.
#5 lore raw
Quoted 6 lines · Alistair John Strachan

(I realise with problems like these it's almost always some sort of obscure hardware problem, but I find that very difficult to believe when I can toggle from 3 years of stability to 6-18 hours crashing by switching compiler. I've also ran extensive stability test programs on the hardware with absolutely no negative results.)

The thing is, I agree with you - it does seem to be compiler-related. But at the same time, I'm almost positive that it's not in "pipe_poll()" itself, because that function is just too simple, and looking at the assembly code, I don't see how what you describe could happen in THAT function.

HOWEVER.

I can easily see an NMI coming in, or another interrupt, or something, and that one corrupting the stack under it because of a compiler bug (or a kernel bug that just needs a specific compiler to trigger). For example, we've had problems before with the compiler thinking it owns the stack frame for an "asmlinkage" function, and us having no way to tell the compiler to keep its hands off - so the compiler ended up touching registers that were actually in the "save area" of the interrupt or system call, and then returning with corrupted state.

Here's a stupid patch. It just adds more debugging to the oops message, and shows all the code pointers it can find on the WHOLE stack.

It also makes the raw stack dumping print out as much of the stack contents _under_ the stack pointer as it does above it too.

However, this patch is mostly useless if you have a separate stack for IRQ's (since if that happens, any interrupt will be taken on a different stack which we don't see any more), so you should NOT enable the 4KSTACKS config option if you try this out.

I'm not sure how enlightening any of the output might be, but it is probably worth trying.

Linus

---

arch/i386/kernel/traps.c +17 -1
index 0efad8a..2359eed 100644
@@ -243,6 +243,20 @@ void show_trace(struct task_struct *task, struct pt_regs *regs,
 	show_trace_log_lvl(task, regs, stack, "");
 }
 
+static void show_all_stack_addresses(unsigned long *esp)
+{
+	struct thread_info *tinfo = (void *) ((unsigned long)esp & (~(THREAD_SIZE - 1)));
+	unsigned long *stack = (unsigned long *)(tinfo+1);
+
+	printk("All stack code pointers:\n");
+	while (valid_stack_ptr(tinfo, stack)) {
+		unsigned long addr = *stack++;
+		if (__kernel_text_address(addr))
+			print_symbol(" %s", addr);
+	}
+	printk("\n");
+}
+
 static void show_stack_log_lvl(struct task_struct *task, struct pt_regs *regs,
 			       unsigned long *esp, char *log_lvl)
 {
@@ -256,8 +270,10 @@ static void show_stack_log_lvl(struct task_struct *task, struct pt_regs *regs,
 			esp = (unsigned long *)&esp;
 	}
 
+	show_all_stack_addresses(esp);
 	stack = esp;
-	for(i = 0; i < kstack_depth_to_print; i++) {
+	stack -= kstack_depth_to_print;
+	for(i = 0; i < 2*kstack_depth_to_print; i++) {
 		if (kstack_end(stack))
 			break;
 		if (i && ((i % 8) == 0))
#6 lore raw

Hi!

Quoted 26 lines
Quoted 5 lines

(I realise with problems like these it's almost always some sort of obscure hardware problem, but I find that very difficult to believe when I can toggle from 3 years of stability to 6-18 hours crashing by switching compiler. I've also ran extensive stability test programs on the hardware with absolutely no negative results.)

The thing is, I agree with you - it does seem to be compiler-related. But at the same time, I'm almost positive that it's not in "pipe_poll()" itself, because that function is just too simple, and looking at the assembly code, I don't see how what you describe could happen in THAT function.

HOWEVER.

I can easily see an NMI coming in, or another interrupt, or something, and that one corrupting the stack under it because of a compiler bug (or a kernel bug that just needs a specific compiler to trigger). For example, we've had problems before with the compiler thinking it owns the stack frame for an "asmlinkage" function, and us having no way to tell the compiler to keep its hands off - so the compiler ended up touching registers that were actually in the "save area" of the interrupt or system call, and then returning with corrupted state.

Here's a stupid patch. It just adds more debugging to the oops message, and shows all the code pointers it can find on the WHOLE stack.

Quoted 7 lines

It also makes the raw stack dumping print out as much of the stack contents _under_ the stack pointer as it does above it too.

However, this patch is mostly useless if you have a separate stack for IRQ's (since if that happens, any interrupt will be taken on a different stack which we don't see any more), so you should NOT enable the 4KSTACKS config option if you try this out.

stupid idea... perhaps gcc-4.1 generates bigger stackframe somewhere, and stack overflows?

that hw monitoring thingie... I'd turn it off. Its interactions with acpi are non-trivial and dangerous.
Pavel

Signature · 1 line
Thanks for all the (sleeping) penguins.
#7 lore raw

On Sunday 07 January 2007 00:36, Pavel Machek wrote:
[snip]

Quoted 7 lines
Quoted 4 lines

However, this patch is mostly useless if you have a separate stack for IRQ's (since if that happens, any interrupt will be taken on a different stack which we don't see any more), so you should NOT enable the 4KSTACKS config option if you try this out.

stupid idea... perhaps gcc-4.1 generates bigger stackframe somewhere, and stack overflows?

The primary reason it's not 4KSTACKS already is that I run multiple XFS partitions on top of an md RAID 1. LVM isn't involved, however, and I'm not using any other filesystem overlays like dm.

I'm fairly sceptical that it's a stack overflow, but I'll be sure to enable the debugging option on the next try.

Quoted 2 lines

that hw monitoring thingie... I'd turn it off. Its interactions with acpi are non-trivial and dangerous.

Well, GCC 3.4 kernels seem to run fine with it, but as I said to Linus I'll be sure to turn this and the sound drivers off in the next build.

Signature · 5 lines
Cheers,
Alistair.

Final year Computer Science undergraduate.
1F2 55 South Clerk Street, Edinburgh, UK.
#8 lore raw
In reply to Mikael Pettersson
Quoted 11 lines · Mikael Pettersson
Quoted 9 lines · Linus Torvalds
Quoted 6 lines

The suggestions I've had so far which I have not yet tried:

(quoted diff) +0 -1
-	Select a different x86 CPU in the config.

- Unfortunately the C3-2 flags seem to simply tell GCC
to schedule for ppro (like i686) and enabled MMX and SSE
- Probably useless

Actually, try this one. Try using something that doesn't like "cmov". Maybe the C3-2 simply has some internal cmov bugginess.

Quoted 2 lines

That's a good suggestion. Earlier C3s didn't have cmov so it's not entirely unlikely that cmov in C3-2 is broken in some cases.

Agreed! When I developped the cmov emulator, I used an early C3 for the tests (well, a "Samuel2" to be precise), because it did not report "cmov" in its flags. I first thought "wow, my emulator is amazingly fast!" because it took something like 50 cycles to do cmovne %eax,%ebx.

Then I realized that this processor performed cmov itself between registers, and only triggered the invalid opcode when one of the operand was a memory reference. And this time, for a hard-coded instruction, it was really slow...

For this reason, I would not be surprized at all that there would be some buggy behaviour in the cmov right there. Maybe a bug in the decoder unit making it skip a byte when the next instruction in the prefetch queue is a cmov affecting same registers... When vendors can do dirty things such as executing unsupported instructions, we can expect anything from them.

Quoted 1 line

Configuring for P5MMX or 486 should be good safe alternatives.

I generally use the P5MMX target for such processors.

Quoted 1 line

/Mikael

Regards,
Willy

#9 lore raw
In reply to Mikael Pettersson
Quoted 3 lines

That's a good suggestion. Earlier C3s didn't have cmov so it's not entirely unlikely that cmov in C3-2 is broken in some cases. Configuring for P5MMX or 486 should be good safe alternatives.

The proper fix for all of this mess is to fix the gcc compiler suite to actually generate i686 code when told to use i686. CMOV is an optional i686 extension which gcc uses without checking. In early PIV days it made sense but on modern processors CMOV is so pointless the bug should be fixed. At that point an i686 kernel would contain i686 instructions and actually run on all i686 processors ending all the i586 pain for most users and distributions.

Unfortunately the compiler people don't appear to care about their years old bug.

Alan

#10 lore raw
Quoted 7 lines · Alan

The proper fix for all of this mess is to fix the gcc compiler suite to actually generate i686 code when told to use i686. CMOV is an optional i686 extension which gcc uses without checking. In early PIV days it made sense but on modern processors CMOV is so pointless the bug should be fixed. At that point an i686 kernel would contain i686 instructions and actually run on all i686 processors ending all the i586 pain for most users and distributions.

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

Thanks,

Grzegorz Kulewski

#11 lore raw
Quoted 10 lines · Grzegorz Kulewski
Quoted 7 lines · Alan

The proper fix for all of this mess is to fix the gcc compiler suite to actually generate i686 code when told to use i686. CMOV is an optional i686 extension which gcc uses without checking. In early PIV days it made sense but on modern processors CMOV is so pointless the bug should be fixed. At that point an i686 kernel would contain i686 instructions and actually run on all i686 processors ending all the i586 pain for most users and distributions.

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

In theory modern processors should have no trouble converting a test/move sequence into the same uops generated by a cmov instruction, for one.

Jeff

#12 lore raw
In reply to Grzegorz Kulewski
Quoted 6 lines
Quoted 3 lines

fixed. At that point an i686 kernel would contain i686 instructions and actually run on all i686 processors ending all the i586 pain for most users and distributions.

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

Take a look at the recent ffmpeg bits on the mplayer list for one example I have to hand - P4 cmov is pretty slow. The crypto folks find the same things.

Alan

#13 lore raw
Quoted 10 lines · Alan
Quoted 6 lines
Quoted 3 lines

fixed. At that point an i686 kernel would contain i686 instructions and actually run on all i686 processors ending all the i586 pain for most users and distributions.

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

Take a look at the recent ffmpeg bits on the mplayer list for one example I have to hand - P4 cmov is pretty slow. The crypto folks find the same things.

cmov is effectively the same cost as a compare and jump, in both cases the cpu needs to do a prediction, and on a mispredict, restart.

the reason cmov can make sense is because it's smaller code...

Signature · 2 lines
if you want to mail me at work (you don't), use arjan (at) linux.intel.com
Test the interaction between Linux and your BIOS via http://www.linuxfirmwarekit.org
#14 lore raw
Quoted 8 lines · Arjan van de Ven
Quoted 7 lines · Alan
Quoted 6 lines
Quoted 3 lines

fixed. At that point an i686 kernel would contain i686 instructions and actually run on all i686 processors ending all the i586 pain for most users and distributions.

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

Quoted 8 lines
Quoted 3 lines

Take a look at the recent ffmpeg bits on the mplayer list for one example I have to hand - P4 cmov is pretty slow. The crypto folks find the same things.

cmov is effectively the same cost as a compare and jump, in both cases the cpu needs to do a prediction, and on a mispredict, restart.

the reason cmov can make sense is because it's smaller code...

BTW, from GCC POV availability of CMOV is the only difference between -march=i586 -mtune=something and -march=i686 -mtune=something. So this is just a naming thing, it could be called -march=i686cmov to make it more obvious but it is too late (and too unimportant) to change it now. Perhaps adding a note to info gcc/man gcc ought to be enough?
If you don't want CMOV being emitted, compile with -march=i586 -mtune=generic (or whatever other tuning you pick up), with -march=i686 -mtune=generic you tell GCC you have CMOV. Whether CMOV is actually used in generated code is another matter, which should be decided based on the selected -mtune. For -Os CMOV should be used whenever available, as that means usually smaller code, otherwise if on some particular chip CMOV is actually slower than compare, jump and assignment, then CMOV should not be selected for that particular tuning (say if Pentium4 has slower CMOV than compare+jump+assignment, -mtune=pentium4 should not emit CMOV, at least not often), if you have examples of that, please file a bug to
http://gcc.gnu.org/bugzilla/. -mtune=generic should emit resp. not emit CMOV depending on whether it is a win on the currently common CPUs.

Jakub

#15 lore raw
In reply to Arjan van de Ven
Quoted 2 lines

cmov is effectively the same cost as a compare and jump, in both cases the cpu needs to do a prediction, and on a mispredict, restart.

On a P4 it appears to be slower than compare/jump in most cases

#16 lore raw
Quoted 5 lines · Alan
Quoted 3 lines

cmov is effectively the same cost as a compare and jump, in both cases the cpu needs to do a prediction, and on a mispredict, restart.

On a P4 it appears to be slower than compare/jump in most cases

On just about EVERYTHING it's slower than compare/jump. See my other post on why, together with a (largely untested) test app.

Linus

#17 lore raw
In reply to Grzegorz Kulewski
Quoted 3 lines · Grzegorz Kulewski

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

CMOV (and, more generically, any "predicated instruction") tends to generally a bad idea on an aggressively out-of-order CPU. It doesn't always have to be horrible, but in practice it is seldom very nice, and (as usual) on the P4 it can be really quite bad.

On a P4, I think a cmov basically takes 10 cycles.

But even ignoring the usual P4 "I suck at things that aren't totally normal", cmov is actually not a great idea. You can always replace it by

		j<negated condition> forward
		mov ..., %reg
	forward:

and assuming the branch is AT ALL predictable (and 95+% of all branches are), the branch-over will actually be a LOT better for a CPU.

Why? Becuase branches can be predicted, and when they are predicted they basically go away. They go away on many levels, too. Not just the branch itself, but the _conditional_ for the branch goes away as far as the critical path of code is concerned: the CPU still has to calculate it and check it, but from a performance angle it "doesn't exist any more", because it's not holding anything else up (well, you want to do it in _some_ reasonable time, but the point stands..)

Similarly, whichever side of the branch wasn't taken goes away. Again, in an out-of-order machine with register renaming, this means that even if the branch isn't taken above, and you end up executing all the non-branch instructions, because you now UNCONDITIONALLY over-write the register, the old data in the register is now DEAD, so now all the OTHER writes to that register are off the critical path too!

So the end result is that with a conditional branch, ona good CPU, the _only_ part of the code that is actually performance-sensitive is the actual calculation of the value that gets used!

In contrast, if you use a predicated instruction, ALL of it is on the critical path. Calculating the conditional is on the critical path. Calculating the value that gets used is obviously ALSO on the critical path, but so is the calculation for the value that DOESN'T get used too. So the cmov - rather than speeding things up - actually slows things down, because it makes more code be dependent on each other.

So here's the basic rule:

- cmov is sometimes nice for code density. It's not a big win, but it certainly can be a win.

- if you KNOW the branch is totally unpredictable, cmov is often good for performance. But a compiler almost never knows that, and even if you train it with input data and profiling, remember that not very many branches _are_ totally unpredictable, so even if you were to know that something is unpredictable, it's going to be very rare.

- on a P4, branch mispredictions are expensive, but so is cmov, so all the above is to some degree exaggerated. On nicer microarchitectures (the Intel Core 2 in particular is something I have to say is very nice indeed), the difference will be a lot less noticeable. The loss from cmov isn't very big (it's not as sucky as P4), but neither is the win (branch misprediction isn't that expensive either).

Here's an example program that you can test and time yourself.

On my Core 2, I get

	[torvalds@woody ~]$ gcc -DCMOV -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000

	real    0m0.194s
	user    0m0.192s
	sys     0m0.000s

	[torvalds@woody ~]$ gcc -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000
	
	real    0m0.167s
	user    0m0.168s
	sys     0m0.000s

ie the cmov is quite a bit slower. Maybe I did something wrong. But note how cmov not only is slower, it's fundamnetally more limited too (ie the branch-over can actually do a lot of things cmov simply cannot do).

So don't use cmov. Except for non-performance-critical code, or if you really care about code-size, and it helps (which is actually fairly rare:
quite often cmov isn't even smaller than a conditional jump and a regular move, partly because a regular move can take arguments that a cmov cannot:
move to memory, move from an immediate etc etc, so depending on what you're moving, cmov simply isn't good even if it's _just_ a move).

(For me, the "cmov" version of the function ends up being three bytes shorter. So it's actually a good example of everything above)

Linus

(*) x86 only has "move to register" as a predicated instruction, but some other architectures have lots of them, potentially all instructions. I don't count conditional branches as "predicated", although some crazy people do. ARM has predicated instructions (but they are gone in Thumb, I think), and ia64 obviously has predicated instructions (but it will be gone in a few years ;)

#include <stdio.h>

/* How many iterations? */
#define ITERATIONS (100000000)

/* Which bit of the counter to test? */
#define BIT 1

#ifdef CMOV

#define choose(i, a, b) ({			\
	unsigned long result;			\
	asm("testl %1,%2 ; cmovne %3,%0"	\
		:"=r" (result)			\
		:"i" (BIT),			\
		 "g" (i),			\
		 "rm" (a),			\
		 "0" (b));			\
	result; })

#else

#define choose(i, a, b) ({			\
	unsigned long result;			\
	asm("testl %1,%2 ; je 1f ; mov %3,%0\n1:"	\
		:"=r" (result)			\
		:"i" (BIT),			\
		 "g" (i),			\
		 "g" (a),			\
		 "0" (b));			\
	result; })

#endif

int main(int argc, char **argv)

{
	int i;
	unsigned long sum = 0;

	for (i = 0; i < ITERATIONS; i++) {
		unsigned long a = 5, b = 7;
		sum += choose(i, a, b);
	}
	printf("%lu\n", sum);
	return 0;
}
#18 lore raw

Just to make clearer why I am so curious, this from X86_64 X2 3800+:

DarkStar:{venom}:/tmp> gcc -DCMOV -Wall -O2 t.c
DarkStar:{venom}:/tmp>time ./a.out
600000000

real    0m0.151s
user    0m0.150s
sys     0m0.000s

DarkStar:{venom}:/tmp> gcc -Wall -O2 t.c
DarkStar:{venom}:/tmp> time ./a.out
600000000

real    0m0.176s
user    0m0.180s
sys     0m0.000s

DarkStar:{venom}:/tmp>gcc -m32 -DCMOV -Wall -O2 t.c DarkStar:{venom}:/tmp>time ./a.out 600000000

real    0m0.152s
user    0m0.160s
sys     0m0.000s

DarkStar:{venom}:/tmp>gcc -m32 -Wall -O2 t.c
DarkStar:{venom}:/tmp>time ./a.out
600000000

real    0m0.200s
user    0m0.200s
sys     0m0.000s
#19 lore raw
In reply to Linus Torvalds

Just curious why on Opteron dual core 2600MHZ I get:

phoenix:{root}:/tmp> gcc -DCMOV -Wall -O2 t.c
phoenix:{root}:/tmp>time ./a.out
600000000

real    0m0.117s
user    0m0.120s
sys     0m0.000s

phoenix:{root}:/tmp>gcc -Wall -O2 t.c
phoenix:{root}:/tmp> time ./a.out
600000000

real    0m0.136s
user    0m0.130s
sys     0m0.010s

Regards

(I understand it is very different from P4)

Luigi Genoni

Quoted 121 lines · Linus Torvalds

Date: Wed, 3 Jan 2007 08:03:37 -0800 (PST)
From: Linus Torvalds <[email protected]>
To: Grzegorz Kulewski <[email protected]>
Cc: Alan <[email protected]>, Mikael Pettersson <[email protected]>,
[email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: kernel + gcc 4.1 = several problems
Resent-Date: Wed, 03 Jan 2007 17:16:00 +0100
Resent-From: <[email protected]>

Quoted 3 lines · Grzegorz Kulewski

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

CMOV (and, more generically, any "predicated instruction") tends to generally a bad idea on an aggressively out-of-order CPU. It doesn't always have to be horrible, but in practice it is seldom very nice, and (as usual) on the P4 it can be really quite bad.

On a P4, I think a cmov basically takes 10 cycles.

But even ignoring the usual P4 "I suck at things that aren't totally normal", cmov is actually not a great idea. You can always replace it by

		j<negated condition> forward
		mov ..., %reg
	forward:

and assuming the branch is AT ALL predictable (and 95+% of all branches are), the branch-over will actually be a LOT better for a CPU.

Why? Becuase branches can be predicted, and when they are predicted they basically go away. They go away on many levels, too. Not just the branch itself, but the _conditional_ for the branch goes away as far as the critical path of code is concerned: the CPU still has to calculate it and check it, but from a performance angle it "doesn't exist any more", because it's not holding anything else up (well, you want to do it in _some_ reasonable time, but the point stands..)

Similarly, whichever side of the branch wasn't taken goes away. Again, in an out-of-order machine with register renaming, this means that even if the branch isn't taken above, and you end up executing all the non-branch instructions, because you now UNCONDITIONALLY over-write the register, the old data in the register is now DEAD, so now all the OTHER writes to that register are off the critical path too!

So the end result is that with a conditional branch, ona good CPU, the _only_ part of the code that is actually performance-sensitive is the actual calculation of the value that gets used!

In contrast, if you use a predicated instruction, ALL of it is on the critical path. Calculating the conditional is on the critical path. Calculating the value that gets used is obviously ALSO on the critical path, but so is the calculation for the value that DOESN'T get used too. So the cmov - rather than speeding things up - actually slows things down, because it makes more code be dependent on each other.

So here's the basic rule:

- cmov is sometimes nice for code density. It's not a big win, but it certainly can be a win.

- if you KNOW the branch is totally unpredictable, cmov is often good for performance. But a compiler almost never knows that, and even if you train it with input data and profiling, remember that not very many branches _are_ totally unpredictable, so even if you were to know that something is unpredictable, it's going to be very rare.

- on a P4, branch mispredictions are expensive, but so is cmov, so all the above is to some degree exaggerated. On nicer microarchitectures (the Intel Core 2 in particular is something I have to say is very nice indeed), the difference will be a lot less noticeable. The loss from cmov isn't very big (it's not as sucky as P4), but neither is the win (branch misprediction isn't that expensive either).

Here's an example program that you can test and time yourself.

On my Core 2, I get

	[torvalds@woody ~]$ gcc -DCMOV -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000

	real    0m0.194s
	user    0m0.192s
	sys     0m0.000s

	[torvalds@woody ~]$ gcc -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000

	real    0m0.167s
	user    0m0.168s
	sys     0m0.000s

ie the cmov is quite a bit slower. Maybe I did something wrong. But note how cmov not only is slower, it's fundamnetally more limited too (ie the branch-over can actually do a lot of things cmov simply cannot do).

So don't use cmov. Except for non-performance-critical code, or if you really care about code-size, and it helps (which is actually fairly rare:
quite often cmov isn't even smaller than a conditional jump and a regular move, partly because a regular move can take arguments that a cmov cannot:
move to memory, move from an immediate etc etc, so depending on what you're moving, cmov simply isn't good even if it's _just_ a move).

(For me, the "cmov" version of the function ends up being three bytes shorter. So it's actually a good example of everything above)

Linus

(*) x86 only has "move to register" as a predicated instruction, but some other architectures have lots of them, potentially all instructions. I don't count conditional branches as "predicated", although some crazy people do. ARM has predicated instructions (but they are gone in Thumb, I think), and ia64 obviously has predicated instructions (but it will be gone in a few years ;)

#20 lore raw

Well, on a P4 (which is supposed to be soo bad) I get:

Quoted 4 lines

gcc -O2 t.c -o t
foreach x ( 1 2 3 4 5 )

Quoted 2 lines

time ./t > /dev/null
end

0.196u 0.004s 0:00.19 100.0%    0+0k 0+0io 0pf+0w
0.168u 0.004s 0:00.16 100.0%    0+0k 0+0io 0pf+0w
0.168u 0.000s 0:00.16 100.0%    0+0k 0+0io 0pf+0w
0.160u 0.000s 0:00.15 106.6%    0+0k 0+0io 0pf+0w
0.180u 0.000s 0:00.18 100.0%    0+0k 0+0io 0pf+0w
Quoted 4 lines

gcc -DCMOV -O2 t.c -o t
foreach x ( 1 2 3 4 5 )

Quoted 2 lines

time ./t > /dev/null
end

0.168u 0.000s 0:00.17 94.1%     0+0k 0+0io 0pf+0w
0.152u 0.000s 0:00.15 100.0%    0+0k 0+0io 0pf+0w
0.136u 0.004s 0:00.13 100.0%    0+0k 0+0io 0pf+0w
0.168u 0.000s 0:00.16 100.0%    0+0k 0+0io 0pf+0w
0.172u 0.000s 0:00.17 100.0%    0+0k 0+0io 0pf+0w

see?

#21 lore raw
Quoted 2 lines · Tim Schmielau

Well, on a P4 (which is supposed to be soo bad) I get:

Interesting. My P4 gets basically exactly the same timings for the cmov and branch cases. And my Core 2 is consistently faster (something like 15%) for the branch version.

Btw, the test-case should be the best possible one for cmov, since there are no data-dependencies except for ALU operations, and everything is totally independent (the actual values have no data dependencies at all, since they are constants). So the critical path issue never show up.

Linus

#22 lore raw
In reply to Linus Torvalds

Hello,

Quoted 4 lines

Here's an example program that you can test and time yourself.

On my Core 2, I get

Quoted 15 lines
	[torvalds@woody ~]$ gcc -DCMOV -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000

	real    0m0.194s
	user    0m0.192s
	sys     0m0.000s

	[torvalds@woody ~]$ gcc -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000
	
	real    0m0.167s
	user    0m0.168s
	sys     0m0.000s

Test was done on my laptop with gcc 4.1.1 and CPU:

processor : 0
vendor_id : GenuineIntel
cpu family : 15
model : 2
model name : Intel(R) Pentium(R) 4 CPU 2.40GHz
stepping : 9
cpu MHz : 2392.349
cache size : 512 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 2
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe cid xtpr
bogomips : 4786.36
clflush size : 64

I wrote a simple script that run each version of your code 100 times measuring the execution time. Then some simple gnuplot magic was applied. The result is attached (png file).

- cmovne was faster with almost stable execution time (~171ms)
- je-mov was slower and execution time varies

Interpretation is up to you ;-)

Signature · 3 lines
Regards,

	Mariusz Kozlowski
#23 lore raw
In reply to Linus Torvalds
Quoted 17 lines · Linus Torvalds
Quoted 2 lines · Grzegorz Kulewski

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

CMOV (and, more generically, any "predicated instruction") tends to generally a bad idea on an aggressively out-of-order CPU. It doesn't always have to be horrible, but in practice it is seldom very nice, and (as usual) on the P4 it can be really quite bad.

On a P4, I think a cmov basically takes 10 cycles.

But even ignoring the usual P4 "I suck at things that aren't totally normal", cmov is actually not a great idea. You can always replace it by

		j<negated condition> forward
		mov ..., %reg
	forward:

...
...

Quoted 6 lines

In contrast, if you use a predicated instruction, ALL of it is on the critical path. Calculating the conditional is on the critical path. Calculating the value that gets used is obviously ALSO on the critical path, but so is the calculation for the value that DOESN'T get used too. So the cmov - rather than speeding things up - actually slows things down, because it makes more code be dependent on each other.

Why CPU people do not internally convert cmov into jmp,mov pair? --
vda

#24 lore raw
Quoted 2 lines · Denis Vlasenko

Why CPU people do not internally convert cmov into jmp,mov pair?

Probably because

- it's not worth it. cmov's certainly _can_ be faster for unpredictable input. So expecially if you teach your compiler (by using profiling) to use cmov's mainly for unpredictable cases, turning it into a conditional jump internally would likely be a bad idea.

- the biggest reason to do it would likely be microarchitectural: if you have an ALU or a bypass network that just isn't suitable for bypassing the flags that way (because you designed your pipeline for a conditional branch), you might decide that it just simplifies things to turn the cmov internally into a branch+mov uop pair.

- cmov's simply aren't common enough to be worth worrying about, especially as it's not likely that the difference is all that big in the end. The limitations on cmov's means that the compiler can only use them under certain fairly limited circumstances anyway, so it's not like you'll make a huge difference by doing anything clever. So see above - it's simply a wash, and likely ends up just depending on other issues.

And don't get me wrong. cmov's can make a difference. You can use them to avoid polluting your branch prediction tables, you can use them to make code smaller, and you can use them when they simply just fit the problem really well. It's just _not_ the case that they are "obviously better". They simply aren't. Conditional branches aren't "evil". There are many MUCH worse things you can do, and other things you should avoid.

It really all boils down to: there's simply no real reason to use cmov. It's not horrible either, so go ahead and use it if you want to, but don't expect your code to really magically run any faster.

Linus

#25 lore raw
Quoted 4 lines · Linus Torvalds
Quoted 2 lines · Denis Vlasenko

Why CPU people do not internally convert cmov into jmp,mov pair?

...

Quoted 3 lines

It really all boils down to: there's simply no real reason to use cmov. It's not horrible either, so go ahead and use it if you want to, but don't expect your code to really magically run any faster.

IOW: yet another slot in instruction opcode matrix and thousands of transistors in instruction decoders are wasted because of this "clever invention", eh?
--
vda

#26 lore raw
Quoted 4 lines · Denis Vlasenko

IOW: yet another slot in instruction opcode matrix and thousands of transistors in instruction decoders are wasted because of this "clever invention", eh?

Well, in all fairness, it can probably help more on certain microarchitectures. Intel is fairly aggressively OoO, especially in Core 2, and predicted branches are not only free, they allow OoO to do a great job around them. But an in-order architecture doesn't have that, and cmov might show more of an advantage there.

Linus

#27 lore raw
In reply to Linus Torvalds
Quoted 2 lines · Linus Torvalds

and assuming the branch is AT ALL predictable (and 95+% of all branches are), the branch-over will actually be a LOT better for a CPU.

IF... Counterexample: Add-Compare-Select in a Viterbi Decoder. If the compare can be predicted, you botched the compression of the data (if you can predict the data, you could have compressed it better), or your noise is not white, i.e. you f*** up the whitening filter. So in any practical viterbi decoder, the compares cannot be predicted. I remember cmov made a big difference in Viterbi Decoder performance on a Cyrix 6x86. But granted, nowadays these things are usually done with SIMD and masks.

Tom

#28 lore raw
Quoted 2 lines · Thomas Sailer

IF... Counterexample: Add-Compare-Select in a Viterbi Decoder.

Yes. [De]compression stuff tends to be (a) totally unpredictable and (b) a situation where people care about performance. It's fairly rare in many other situations.

That said, any real performance these days is about avoiding cache misses. There cmov really can help more, if it results in denser code (fairly big if, though).

Linus

#29 lore raw
In reply to Linus Torvalds
Quoted 98 lines

-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of Linus Torvalds
Sent: 2007年1月4日 0:04
To: Grzegorz Kulewski
Cc: Alan; Mikael Pettersson; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Subject: Re: kernel + gcc 4.1 = several problems

Quoted 3 lines · Grzegorz Kulewski

Could you explain why CMOV is pointless now? Are there any benchmarks proving that?

CMOV (and, more generically, any "predicated instruction") tends to generally a bad idea on an aggressively out-of-order CPU. It doesn't always have to be horrible, but in practice it is seldom very nice, and (as usual) on the P4 it can be really quite bad.

On a P4, I think a cmov basically takes 10 cycles.

But even ignoring the usual P4 "I suck at things that aren't totally normal", cmov is actually not a great idea. You can always replace it by

		j<negated condition> forward
		mov ..., %reg
	forward:

and assuming the branch is AT ALL predictable (and 95+% of all branches are), the branch-over will actually be a LOT better for a CPU.

Why? Becuase branches can be predicted, and when they are predicted they basically go away. They go away on many levels, too. Not just the branch itself, but the _conditional_ for the branch goes away as far as the critical path of code is concerned: the CPU still has to calculate it and check it, but from a performance angle it "doesn't exist any more", because it's not holding anything else up (well, you want to do it in _some_ reasonable time, but the point stands..)

Similarly, whichever side of the branch wasn't taken goes away. Again, in an out-of-order machine with register renaming, this means that even if the branch isn't taken above, and you end up executing all the non-branch instructions, because you now UNCONDITIONALLY over-write the register, the old data in the register is now DEAD, so now all the OTHER writes to that register are off the critical path too!

So the end result is that with a conditional branch, ona good CPU, the _only_ part of the code that is actually performance-sensitive is the actual calculation of the value that gets used!

In contrast, if you use a predicated instruction, ALL of it is on the critical path. Calculating the conditional is on the critical path. Calculating the value that gets used is obviously ALSO on the critical path, but so is the calculation for the value that DOESN'T get used too. So the cmov - rather than speeding things up - actually slows things down, because it makes more code be dependent on each other.

So here's the basic rule:

- cmov is sometimes nice for code density. It's not a big win, but it certainly can be a win.

- if you KNOW the branch is totally unpredictable, cmov is often good for performance. But a compiler almost never knows that, and even if you train it with input data and profiling, remember that not very many branches _are_ totally unpredictable, so even if you were to know that something is unpredictable, it's going to be very rare.

- on a P4, branch mispredictions are expensive, but so is cmov, so all the above is to some degree exaggerated. On nicer microarchitectures (the Intel Core 2 in particular is something I have to say is very nice indeed), the difference will be a lot less noticeable. The loss from cmov isn't very big (it's not as sucky as P4), but neither is the win (branch misprediction isn't that expensive either).

Here's an example program that you can test and time yourself.

On my Core 2, I get

	[torvalds@woody ~]$ gcc -DCMOV -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000

	real    0m0.194s
	user    0m0.192s
	sys     0m0.000s

	[torvalds@woody ~]$ gcc -Wall -O2 t.c
	[torvalds@woody ~]$ time ./a.out
	600000000

	real    0m0.167s
	user    0m0.168s
	sys     0m0.000s
Quoted 3 lines

ie the cmov is quite a bit slower. Maybe I did something wrong. But note how cmov not only is slower, it's fundamnetally more limited too (ie the branch-over can actually do a lot of things cmov simply cannot do).

Hi,
cmov will stall on eflags in your test program.
I think you will see benefit of cmov if you can manage to put some instructions which does NOT modify eflags between testl and cmov.

Thanks
Zou Nan hai

#30 lore raw
Quoted 2 lines · Nanhai

cmov will stall on eflags in your test program.

And that is EXACTLY my point.

CMOV is a piece of CRAP for most things, exactly because it serializes three streams of data: the two inputs, and the conditional.

My test-case was actually _good_ for cmov, because there was just the one conditional (which was 100% ALU) thing that was serialized. In real life, the two data sources also come from memory, and _any_ of them being delayed ends up delaying the cmov, and screwing up your out-of-order pipeline because you now introduced a serialization point that was very possibly not necessary at all.

In contrast, a conditional branch-around serializes absolutely NOTHING, because branches get predicted.

Quoted 2 lines

I think you will see benefit of cmov if you can manage to put some instructions which does NOT modify eflags between testl and cmov.

A lot of the time, the conditional _is_ the critical path.

The whole point of this discussion was that cmov isn't really all that great. It has fundamental problems that a conditional branch that gets predicted simply does not have.

That's qiute apart from the fact that cmov has rather limited semantics, and that in 99% of all cases you have to use a conditional branch anyway.

Linus