Re: xor as a lazy comparison

Re: xor as a lazy comparison

[Clayton Weaver]

Is not xor (^) typically compiled to a
one cycle instruction regardless of
requested optimization level? (May not
always have been the case on every
target architecture for != equality
tests.)
Clayton Weaver
cgweav at fastmail dot fm

PS:
Anyone know where I can get
a waterproof, battery powered gps that will fit inside the handle of a Fenwick?

Re: xor as a lazy comparison

[linux-os (Dick Johnson)]

On Wed, 27 Jul 2005, Clayton Weaver wrote:

> Is not xor (^) typically compiled to a
> one cycle instruction regardless of
> requested optimization level? (May not
> always have been the case on every
> target architecture for != equality
> tests.)
> Clayton Weaver
> cgweav at fastmail dot fm
>

I think the XOR thread was started by somebody as a ruse or
a joke. XOR will always destroy the value of an operand. This
means that it needs to be loaded and perhaps reloaded. A 'TEST'
instruction or a 'CMP' instruction never destroys anything and
only affects the flags. TEST is an AND in which the result is
not saved, only the flags get changed. A CMP is a subtract in
which the result is not saved, only the flags. These are
ix86 instructions, but similar instructions exist for other
CPUs.

All these instructions in their simplest form (using registers)
are two-byte instructions!

Disassembly of section .text:

00000000 <.text>:
    0:	39 c3                	cmp    %eax,%ebx
    2:	31 c3                	xor    %eax,%ebx
    4:	85 d8                	test   %ebx,%eax

Instructions that access memory use more bytes...

Cheers,
Dick Johnson
Penguin : Linux version 2.6.12 on an i686 machine (5537.79 BogoMips).
Warning : 98.36% of all statistics are fiction.
.
I apologize for the following. I tried to kill it with the above dot :

****************************************************************
The information transmitted in this message is confidential and may be privileged.  Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited.  If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to DeliveryErrors@analogic.com - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

Re: xor as a lazy comparison

[Grant Coady]

On Wed, 27 Jul 2005 15:58:48 -0400, "linux-os \(Dick Johnson\)" <linux-os@analogic.com> wrote:
>
>I think the XOR thread was started by somebody as a ruse or
>a joke. XOR will always destroy the value of an operand. 

You missed the part where somebody checked assembler output and
found compiler optimised xor to cmp as nothing referenced the result.

Grant.

xor as a lazy comparison

[Jan Engelhardt]

Hi list,


I have seen this in kernel/signal.c:check_kill_permission()

            && (current->euid ^ t->suid) && (current->euid ^ t->uid)

If current->euid and t->suid are the same, the xor returns 0, so these 
statements are effectively the same as a !=

	current->euid != t->suid ...

Why ^ ?


Jan Engelhardt
-- 

Re: xor as a lazy comparison

[Grant Coady]

On Sun, 24 Jul 2005 18:40:25 +0200 (MEST), Jan Engelhardt <jengelh@linux01.gwdg.de> wrote:
>
>I have seen this in kernel/signal.c:check_kill_permission()
>
>            && (current->euid ^ t->suid) && (current->euid ^ t->uid)
>
>If current->euid and t->suid are the same, the xor returns 0, so these 
>statements are effectively the same as a !=
>
>	current->euid != t->suid ...
>
>Why ^ ?
To confuse you, coders with assembly or hardware background throw in 
equivalent bit operations to succinctly describe their visualisation 
of solution space...  Perhaps the writer _wanted_ you to pause and 
think?  Maybe the compiler produces better code?  Try it and see.

Grant.

Re: xor as a lazy comparison

[Jan Engelhardt]

>To confuse you, coders with assembly or hardware background throw in 

I doubt that. I'm good enough assembly to see this :)

>equivalent bit operations to succinctly describe their visualisation 
>of solution space...  Perhaps the writer _wanted_ you to pause and 
>think?  Maybe the compiler produces better code?  Try it and see.

It produces a simple CMP. Should not be inefficient, though.


Jan Engelhardt
-- 

Re: xor as a lazy comparison

[Puneet Vyas]

Jan Engelhardt wrote:

>>To confuse you, coders with assembly or hardware background throw in 
>>    
>>
>
>I doubt that. I'm good enough assembly to see this :)
>
>  
>
>>equivalent bit operations to succinctly describe their visualisation 
>>of solution space...  Perhaps the writer _wanted_ you to pause and 
>>think?  Maybe the compiler produces better code?  Try it and see.
>>    
>>
>
>It produces a simple CMP. Should not be inefficient, though.
>
>
>Jan Engelhardt
>  
>
I just compiled two identical program , one with "!=" and other with 
"^". The assembly output is identical.

Re: xor as a lazy comparison

[Bernd Petrovitsch]

On Sun, 2005-07-24 at 18:15 -0400, Puneet Vyas wrote:
[...]
> I just compiled two identical program , one with "!=" and other with 
> "^". The assembly output is identical.

Hmm, which compiler and which version?
You might want to try much older and other compilers.

	Bernd
-- 
Firmix Software GmbH                   http://www.firmix.at/
mobil: +43 664 4416156                 fax: +43 1 7890849-55
          Embedded Linux Development and Services

Re: xor as a lazy comparison

[Steven Rostedt]

On Mon, 2005-07-25 at 10:57 +0200, Bernd Petrovitsch wrote:
> On Sun, 2005-07-24 at 18:15 -0400, Puneet Vyas wrote:
> [...]
> > I just compiled two identical program , one with "!=" and other with 
> > "^". The assembly output is identical.
> 
> Hmm, which compiler and which version?
> You might want to try much older and other compilers.
> 

Doesn't matter. The cycles saved for old compilers is not rational to
have obfuscated code.

Here's the patch to make the code more readable.

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

--- linux-2.6.13-rc3/kernel/signal.c.orig	2005-07-25 13:50:20.000000000 -0400
+++ linux-2.6.13-rc3/kernel/signal.c	2005-07-25 13:50:51.000000000 -0400
@@ -665,8 +665,8 @@ static int check_kill_permission(int sig
 			(unsigned long)info != 2 && SI_FROMUSER(info)))
 	    && ((sig != SIGCONT) ||
 		(current->signal->session != t->signal->session))
-	    && (current->euid ^ t->suid) && (current->euid ^ t->uid)
-	    && (current->uid ^ t->suid) && (current->uid ^ t->uid)
+	    && (current->euid != t->suid) && (current->euid != t->uid)
+	    && (current->uid != t->suid) && (current->uid != t->uid)
 	    && !capable(CAP_KILL))
 		return error;
 

Re: xor as a lazy comparison

[Lee Revell]

On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> Doesn't matter. The cycles saved for old compilers is not rational to
> have obfuscated code.

Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
well?

Lee

Re: xor as a lazy comparison

[Philippe Troin]

Lee Revell <rlrevell@joe-job.com> writes:

> On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> > Doesn't matter. The cycles saved for old compilers is not rational to
> > have obfuscated code.
> 
> Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> well?

Depends if you want to multiply by 2 or 4 :-)

Phil.

Re: xor as a lazy comparison

[Lee Revell]

On Mon, 2005-07-25 at 12:16 -0700, Philippe Troin wrote:
> Lee Revell <rlrevell@joe-job.com> writes:
> 
> > On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> > > Doesn't matter. The cycles saved for old compilers is not rational to
> > > have obfuscated code.
> > 
> > Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> > well?
> 
> Depends if you want to multiply by 2 or 4 :-)

I guess I just answered my own question ;-)

Lee

Re: xor as a lazy comparison

[Jan Engelhardt]

>> > Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
>> > well?
>> 
>> Depends if you want to multiply by 2 or 4 :-)
>
>I guess I just answered my own question ;-)

To answer for x *= 2 vs x <<= 1:

Use * when you would logically want to do a multiplication,
<< if you're working on a bitfield. It's just for keeping the code clean 
enough so that others may understand it.

In the longshot, it does not matter, as gcc will optimize out multiplication 
with powers of two to bitops.



Jan Engelhardt
-- 
| Alphagate Systems, http://alphagate.hopto.org/

Re: xor as a lazy comparison

[Bernd Petrovitsch]

On Tue, 2005-07-26 at 08:07 +0200, Jan Engelhardt wrote:
[...]
> To answer for x *= 2 vs x <<= 1:
and x += x

> Use * when you would logically want to do a multiplication,
> << if you're working on a bitfield. It's just for keeping the code clean 
> enough so that others may understand it.
> 
> In the longshot, it does not matter, as gcc will optimize out multiplication 
                                          ^^^ the C compiler
> with powers of two to bitops.

And if the C compiler is not doing this properly, such tunings are
probably in 100%-\eps cases worthless anyway.

	Bernd
-- 
Firmix Software GmbH                   http://www.firmix.at/
mobil: +43 664 4416156                 fax: +43 1 7890849-55
          Embedded Linux Development and Services

Re: xor as a lazy comparison

[Steven Rostedt]

On Mon, 2005-07-25 at 12:16 -0700, Philippe Troin wrote:
> Lee Revell <rlrevell@joe-job.com> writes:
> 
> > On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> > > Doesn't matter. The cycles saved for old compilers is not rational to
> > > have obfuscated code.
> > 
> > Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> > well?
> 
> Depends if you want to multiply by 2 or 4 :-)

I guess this proves my point :-)

But lets look at the signal.c code as well:

        if ((!info || ((unsigned long)info != 1 &&
                        (unsigned long)info != 2 && SI_FROMUSER(info)))
            && ((sig != SIGCONT) ||
                (current->signal->session != t->signal->session))
            && (current->euid ^ t->suid) && (current->euid ^ t->uid)
            && (current->uid ^ t->suid) && (current->uid ^ t->uid)
            && !capable(CAP_KILL))
                return error;

Why did they do the (current->signal->session != t->signal->session) and
not also do (current->signal->session ^ t->signal->session)?

Bit shifting for doubling (or quadrupling) may or may not be confusing,
(I don't mind that), but using xor for non-equal is IMO past that line.
Since, I usually use xor for bit masks. Looking at the above code,
especially since it is not always used, I would think that euid, uid,
and suid are all bitmasks.

-- Steve

Re: xor as a lazy comparison

[Lee Revell]

On Mon, 2005-07-25 at 12:16 -0700, Philippe Troin wrote:
> Lee Revell <rlrevell@joe-job.com> writes:
> 
> > On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> > > Doesn't matter. The cycles saved for old compilers is not rational to
> > > have obfuscated code.
> > 
> > Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> > well?
> 
> Depends if you want to multiply by 2 or 4 :-)

Ah, this explains why my drivers never worked...

Lee

Re: xor as a lazy comparison

[Paulo Marques]

Lee Revell wrote:
> On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> 
>>Doesn't matter. The cycles saved for old compilers is not rational to
>>have obfuscated code.
> 
> Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> well?

I guess this depends on what you logically want to do. If the problem 
requires you to shift some value N bits, then you should use a shift 
operation.

If what you want is to multiply a value by a certain ammount, you should 
just use a multiplication.

Using a shift to perform the multiplication should be left to the 
compiler IMHO.

The proof that the shift is not so clear is that even you got the shift 
wrong in your own example ;)

-- 
Paulo Marques - www.grupopie.com

It is a mistake to think you can solve any major problems
just with potatoes.
Douglas Adams

Re: xor as a lazy comparison

[Lee Revell]

On Mon, 2005-07-25 at 20:23 +0100, Paulo Marques wrote:
> Lee Revell wrote:
> > On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> > 
> >>Doesn't matter. The cycles saved for old compilers is not rational to
> >>have obfuscated code.
> > 
> > Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> > well?
> 
> I guess this depends on what you logically want to do. If the problem 
> requires you to shift some value N bits, then you should use a shift 
> operation.
> 
> If what you want is to multiply a value by a certain ammount, you should 
> just use a multiplication.
> 
> Using a shift to perform the multiplication should be left to the 
> compiler IMHO.
> 
> The proof that the shift is not so clear is that even you got the shift 
> wrong in your own example ;)
> 

Yeah, that was going to be my point, but I made it inadvertently before
I even got that far...

Lee

Re: xor as a lazy comparison

[Bill Davidsen]

Lee Revell wrote:
> On Mon, 2005-07-25 at 13:55 -0400, Steven Rostedt wrote: 
> 
>>Doesn't matter. The cycles saved for old compilers is not rational to
>>have obfuscated code.
> 
> 
> Where do we draw the line with this?  Is x *= 2 preferable to x <<= 2 as
> well?

In addition to the obvious error, let's not use x += x as well. If you 
want to multiple by two, do it.

Wasn't there a CPU where multiple was faster than add? Doesn't matter, 
let the compiler make the optimizations so you don't have to.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me