Home > Archive > Java Help > July 2004 > Negation of boolean
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Negation of boolean
|
|
| Aki \Sus\ Laukkanen 2004-07-28, 9:09 pm |
|
Hi again :)
One of those "Can yuo do this?" -type questions again:
Anything wrong with:
boolean sequenceContinues = false;
if([condition]){
sequenceContinues = !sequenceContinues;
}
else{}
?
--
-Aki "Sus" Laukkanen
| |
| Christophe Vanfleteren 2004-07-28, 9:09 pm |
| Aki "Sus" Laukkanen wrote:
>
> Hi again :)
>
> One of those "Can yuo do this?" -type questions again:
> Anything wrong with:
>
> boolean sequenceContinues = false;
> if([condition]){
> sequenceContinues = !sequenceContinues;
> }
> else{}
>
> ?
Rewrite that as
boolean sequenceContinues = ([condition]);
--
Kind regards,
Christophe Vanfleteren
| |
| Tor Iver Wilhelmsen 2004-07-28, 9:09 pm |
| Christophe Vanfleteren <c.v4nfl3t3r3n@pandora.be> writes:
> boolean sequenceContinues = ([condition]);
No, that doesn't do the same thing.
| |
| Aki \Sus\ Laukkanen 2004-07-28, 9:09 pm |
| Christophe Vanfleteren wrote:
> Aki "Sus" Laukkanen wrote:
>
>
>
>
> Rewrite that as
>
> boolean sequenceContinues = ([condition]);
That wouldn't accomplish what I'm trying to do. sequenceContinues is
supposed to change from flase to true or vice versa...
I actually mis-quoted my code, the if-block should be inside a while-loop.
Sorry about the confusion.
--
-Aki "Sus" Laukkanen
"No Akia nyt on niin helppo raadella - senkun vaan raatelee."
| |
| Roedy Green 2004-07-28, 9:09 pm |
| On Wed, 28 Jul 2004 18:35:56 +0300, "Aki \"Sus\" Laukkanen"
<aki.laukkanenREMOVETHIS@helsinki.fi> wrote or quoted :
>One of those "Can yuo do this?" -type questions again:
>Anything wrong with:
>
>boolean sequenceContinues = false;
>if([condition]){
> sequenceContinues = !sequenceContinues;
>}
>else{}
Would it not be simpler to write:
boolean sequenceContinues = conditionexpression;
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Eric Sosman 2004-07-28, 9:09 pm |
| Aki "Sus" Laukkanen wrote:
>
> Hi again :)
>
> One of those "Can yuo do this?" -type questions again:
> Anything wrong with:
>
> boolean sequenceContinues = false;
> if([condition]){
> sequenceContinues = !sequenceContinues;
> }
> else{}
>
> ?
Nothing objectionable that I can see. You could optimiize
(or obfuscate) the inversion a little:
sequenceContinues ^= true;
--
Eric.Sosman@sun.com
| |
| Jean-Philippe Martin 2004-07-28, 9:09 pm |
|
> That wouldn't accomplish what I'm trying to do. sequenceContinues is
> supposed to change from flase to true or vice versa...
> I actually mis-quoted my code, the if-block should be inside a while-loop.
> Sorry about the confusion.
>
> --
> -Aki "Sus" Laukkanen
> "No Akia nyt on niin helppo raadella - senkun vaan raatelee."
>
You just want a loop that change the value of a boolean ??? Here is a simple
class with a main method which print the doSequence value and switch it 10
times.
public class SwitchVal {
public static void main(String[] args) {
boolean doSequence = false;
for (int i=0; i<10; i++){
System.out.println(doSequence);
doSequence = !doSequence;
}
}
}
| |
| Aki \Sus\ Laukkanen 2004-07-28, 9:09 pm |
| Jean-Philippe Martin wrote:
> You just want a loop that change the value of a boolean ??? Here is a simple
> class with a main method which print the doSequence value and switch it 10
> times.
Actually, I want it to change the value only if the "if" condition is
met (and do some other stuff as well, regardless of whether it changed
the value or not.) (That other stuff varies depending on the value of
the boolean.)
--
-Aki "Sus" Laukkanen
| |
| Jean-Philippe Martin 2004-07-28, 9:09 pm |
| "Aki "Sus" Laukkanen" <aki.laukkanenREMOVETHIS@helsinki.fi> a écrit dans le
message de news:ce8h4s$f6v$1@oravannahka.helsinki.fi...
>
> Hi again :)
>
> One of those "Can yuo do this?" -type questions again:
> Anything wrong with:
>
> boolean sequenceContinues = false;
> if([condition]){
> sequenceContinues = !sequenceContinues;
> }
> else{}
>
> ?
>
> --
> -Aki "Sus" Laukkanen
>
>
It appears that I've misunderstood the question... Can it be more clear?
Maybe may I help;
| |
|
|
"Aki "Sus" Laukkanen" <aki.laukkanenREMOVETHIS@helsinki.fi> wrote in message
news:ce8or2$irb$1@oravannahka.helsinki.fi...
> Jean-Philippe Martin wrote:
>
>
simple[color=darkred]
10[color=darkred]
>
> Actually, I want it to change the value only if the "if" condition is
> met (and do some other stuff as well, regardless of whether it changed
> the value or not.) (That other stuff varies depending on the value of
> the boolean.)
>
> --
> -Aki "Sus" Laukkanen
>
You could use:
sequenceContinues = sequenceContinues ^ condition;
Which is XORing the two items and will invert sequenceContinues if condition
is true. Slightly less code (and probably marginally faster), but not quite
as clear.
adam
| |
| Patrick 2004-07-28, 9:09 pm |
| On Wed, 28 Jul 2004 21:12:22 +0100, Adam <notreal@me.com> wrote:
>
> "Aki "Sus" Laukkanen" <aki.laukkanenREMOVETHIS@helsinki.fi> wrote in
> message
> news:ce8or2$irb$1@oravannahka.helsinki.fi...
> simple
> 10
>
> You could use:
> sequenceContinues = sequenceContinues ^ condition;
>
> Which is XORing the two items and will invert sequenceContinues if
> condition
> is true. Slightly less code (and probably marginally faster), but not
> quite
> as clear.
>
> adam
>
you can also use :
sequenceContinues= condition ? !sequenceContinues:sequencecontinues;
it's more clear than Adams option. and easier as the if statement.
| |
| Roedy Green 2004-07-28, 9:09 pm |
| On Wed, 28 Jul 2004 23:22:17 +0200, Patrick <tuin01@home.nl> wrote or
quoted :
>sequenceContinues= condition ? !sequenceContinues:sequencecontinues;
How many of you know what this code does without looking it up?
sequenceContinues ^= condition;
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Oscar kind 2004-07-28, 9:09 pm |
| "Aki \"Sus\" Laukkanen" <aki.laukkanenREMOVETHIS@helsinki.fi> wrote:
>
> One of those "Can yuo do this?" -type questions again:
> Anything wrong with:
>
> boolean sequenceContinues = false;
> if([condition]){
> sequenceContinues = !sequenceContinues;
> }
> else{}
If this is a complete code snippet, simplify it as other have already
pointed out.
Otherwise, there is nothing wrong with it. Combine it with other code and
maybe a comment or two on the use of the boolean flag; I'd say the result
would be code that's easy to understand and maintain (even by the lesser
mortals).
--
Oscar Kind http://home.hccnet.nl/okind/
Software Developer for contact information, see website
PGP Key fingerprint: 91F3 6C72 F465 5E98 C246 61D9 2C32 8E24 097B B4E2
| |
| Mark Haase 2004-07-29, 3:57 am |
| In article <hl6gg0ta5cfo099j3jf6o7tnf9f0mvlh5i@4ax.com>,
Roedy Green <look-on@mindprod.com.invalid> wrote:
> How many of you know what this code does without looking it up?
I use ?: all the time. It's my favorite ternary operator. <insert nerdy
snicker>
--
|\/| /| |2 |<
mehaase(at)sas(dot)upenn(dot)edu
| |
| Roedy Green 2004-07-29, 3:57 am |
| On Thu, 29 Jul 2004 00:44:07 -0400, Mark Haase <mehaase@earthlink.net>
wrote or quoted :
>How many of you know what this code does without looking it up?
>sequenceContinues ^= condition;
>I use ?: all the time. It's my favorite ternary operator. <insert nerdy
>snicker>
It is pronounced xor-equals.
It has the following truth table:
sequenceContinues condition -> sequenceContinues
false false -> false
false true -> true
true false -> true
true true -> false
You can think of it as like bitwise different
you can thing of it as like:
if ( condition ) sequence = !sequence;
Even if you think it is too fancy pants, it would not hurt to learn it
so that you will understand if someone else uses it.
xor is for toggling.
most of the time you just want something like this:
sequenceContinues = condition;
or
sequenceContinues = !condition;
rather than something long-winded like
if ( condition ) sequenceContinues = false;
else sequenceContinues = true;
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
|
| Mark Haase wrote:
> In article <hl6gg0ta5cfo099j3jf6o7tnf9f0mvlh5i@4ax.com>,
> Roedy Green <look-on@mindprod.com.invalid> wrote:
>
>
>
>
> I use ?: all the time. It's my favorite ternary operator. <insert nerdy
> snicker>
>
What's your second favourite? :-)
John
| |
| Grant Wagner 2004-07-29, 3:58 pm |
| Patrick wrote:
> On Wed, 28 Jul 2004 21:12:22 +0100, Adam <notreal@me.com> wrote:
>
> you can also use :
> sequenceContinues= condition ? !sequenceContinues:sequencecontinues;
>
> it's more clear than Adams option. and easier as the if statement.
And now you're assigning something to sequenceContinues all the time, instead
of only when condition is true.
sequenceContinues = sequenceContinues ^ condition; may be all l33t c0ding, but
it has to retrieve the value of sequenceContinues, xor it with condition
(which it has to evaluate) and assign it back to sequenceContinues every
single pass through the loop. I'm not sure it would be faster then:
if (condition) {
sequenceContinues = !sequenceContinues;
}
which needs to evaluate condition (which the xor solution is doing too) and
only retrieves the value of sequenceContinues, negates it and performs the
assignment when condition is true. And it's the clearest code that describes
what is going on. Performance may not be an issue here, but in this case, the
clearest syntax to describe what is occurring is also the most efficient code.
In attempting to "streamline" the code, you've made it more inefficient.
--
Grant Wagner <gwagner@agricoreunited.com>
| |
| Mark Haase 2004-07-29, 8:57 pm |
| In article <7p6hg0dhi08tsom2h87gnqjr5vt9a3o9eb@4ax.com>,
Roedy Green <look-on@mindprod.com.invalid> wrote:
> On Thu, 29 Jul 2004 00:44:07 -0400, Mark Haase <mehaase@earthlink.net>
> wrote or quoted :
>
>
>
>
> It is pronounced xor-equals.
>
> It has the following truth table:
Bad quoting..I didn't write the first two lines above, even though
you've attributed them to me, and my comment was obviously in reference
to ?: and not ^=, which isn't even a ternary operator.
The explanation of XOR is nice, but let me add this as well:
XOR stands for "eXclusive OR", which is the easy way to remember what it
does. It means "one OR the other, but not both" ie. exclusive.
XOR can be used for basic encryption. Say message = 01010110 (0x56) and
cipher = 10011100 (0x9C). Then message ^ cypher = 11001010 = encrypted
message. The magic here is that
encrypted message ^ cipher = original message
Do it yourself and see. XOR is also real handy on input monitoring
circuits where you're watching for a multiple bit input to change. Just
use an XOR network and feed it into an interrupt source. When you get
interrupted you know that something has changed, so you can read the
entire value.
XOR for flip-flopping a boolean?? Overkill.
Hope the OP is still reading the thread..
--
|\/| /| |2 |<
mehaase(at)sas(dot)upenn(dot)edu
| |
| Roedy Green 2004-07-29, 8:57 pm |
| On Thu, 29 Jul 2004 17:42:48 GMT, Grant Wagner
<gwagner@agricoreunited.com> wrote or quoted :
>
>if (condition) {
> sequenceContinues = !sequenceContinues;
>}
>
>which needs to evaluate condition (which the xor solution is doing too) and
>only retrieves the value of sequenceContinues, negates it and performs the
>assignment when condition is true. And it's the clearest code that describes
>what is going on.
I wrote this little program to test your assumptions:
import java.util.Random;
public class XorEff
{
/**
* test harness
*
* @param args not used
*/
public static void main ( String[] args )
{
Random wheel = new Random();
boolean toggle = false;
for ( int i=0; i<10; i++ )
{
int a = wheel.nextInt( 10 );
int b = wheel.nextInt( 10 );
if ( a < b )
{
toggle = !toggle;
}
// compiles to: 13 bytes
//38: if_icmpge 51
//41: iload_2
//42: ifne 49
//45: iconst_1
//46: goto 50
//49: iconst_0
//50: istore_2
//51:
System.out.println( a + " " + b + " " + toggle );
}
for ( int i=0; i<10; i++ )
{
int a = wheel.nextInt( 10 );
int b = wheel.nextInt( 10 );
// read this as "toggle value if the condition is true."
toggle ^= ( a < b );
//compiles to 10 bytes
//126: if_icmpge 133
//129: iconst_1
//130: goto 134
//133: iconst_0
//134: ixor
//135: istore_2
//136:
System.out.println( a + " " + b + " " + toggle );
}
}
}
Here are my discoveries:
^= is the tersest source code.
^= is the code most likely to baffle an average programmer.
^= generates the shortest JVM byte code.
! generates the fastest code in the case where the expression is false
by a considerable margin.
^= generates slightly faster code in the case where the expression is
true.
I don't know how to snapshot what machine language code finally gets
generated in Hotspot.
Here are my opinions.
^= The tersest code is usually the most readable by a knowledgeable
programmer. There are fewer symbols to absorb. So long as you are
dealing with idiomatic patterns, such as x ^= condition, there is no
problem grasping what that does in a gestalt.
^= is an operator in the Java language. If you don't know what a basic
operator does, you can't consider yourself a profession Java
programmer. Everyone who writes Java code for a living should know off
the bat what this means, or be capable of figuring it out is less than
a minute.
^ has fascinating properties. People should want to learn about them
just out of wonder.
^ should be more widely used than it is.
It is not wise to use ^ in a team project where you are likely to have
anything but first class programmers participating. They will play
helpless. They have no way of figuring it out since somebody else did
their homework for them when they were going through school. If you
do use it, you need commentary explaining what it does. Further, there
exists a quite serviceable more standard alternative.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Roedy Green 2004-07-29, 8:57 pm |
| On Thu, 29 Jul 2004 16:08:45 -0400, Mark Haase <mehaase@earthlink.net>
wrote or quoted :
>Bad quoting..I didn't write the first two lines above, even though
>you've attributed them to me, and my comment was obviously in reference
>to ?: and not ^=, which isn't even a ternary operator.
done deliberately. Go back and see why.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Patrick 2004-07-29, 8:57 pm |
| On Thu, 29 Jul 2004 20:23:41 GMT, Roedy Green
<look-on@mindprod.com.invalid> wrote:
> <snip>
>
> Here are my discoveries:
>
> ^= is the tersest source code.
>
> ^= is the code most likely to baffle an average programmer.
>
> ^= generates the shortest JVM byte code.
>
> ! generates the fastest code in the case where the expression is false
> by a considerable margin.
>
> ^= generates slightly faster code in the case where the expression is
> true.
>
> I don't know how to snapshot what machine language code finally gets
> generated in Hotspot.
>
> Here are my opinions.
>
> ^= The tersest code is usually the most readable by a knowledgeable
> programmer. There are fewer symbols to absorb. So long as you are
> dealing with idiomatic patterns, such as x ^= condition, there is no
> problem grasping what that does in a gestalt.
>
> ^= is an operator in the Java language. If you don't know what a basic
> operator does, you can't consider yourself a profession Java
> programmer. Everyone who writes Java code for a living should know off
> the bat what this means, or be capable of figuring it out is less than
> a minute.
>
> ^ has fascinating properties. People should want to learn about them
> just out of wonder.
>
> ^ should be more widely used than it is.
>
> It is not wise to use ^ in a team project where you are likely to have
> anything but first class programmers participating. They will play
> helpless. They have no way of figuring it out since somebody else did
> their homework for them when they were going through school. If you
> do use it, you need commentary explaining what it does. Further, there
> exists a quite serviceable more standard alternative.
>
>
Roedy,
I checked your assumtion and wrote a test myself.
Seems to me you're right
xor is fastest
if comes second
and ?: is last.
my code:
package toggletest;
public class Test1 {
public Test1() {
}
public static void main(String args[]) {
long start1, end1;
boolean b1 = false, b2=false;
start1 = System.currentTimeMillis();
for (int x = 0; x < 100000000; x++) {
b2 = !b2;
b1 ^= b2;
}
end1 = System.currentTimeMillis();
long start2, end2;
b2=false;
start2 = System.currentTimeMillis();
for (int x = 0; x < 100000000; x++) {
b2 = !b2;
b1 = b2 ? !b1 : b1;
}
end2 = System.currentTimeMillis();
long start3, end3;
b2=false;
start3 = System.currentTimeMillis();
for (int x = 0; x < 100000000; x++) {
b2 = !b2;
if (b2) {
b1 = !b1;
}
}
end3 = System.currentTimeMillis();
System.out.println("xor " + (end1 - start1));
System.out.println("?: " + (end2 - start2));
System.out.println("if " + (end3 - start3));
}
}
| |
| Roedy Green 2004-07-29, 8:57 pm |
| On Thu, 29 Jul 2004 23:44:39 +0200, Patrick <tuin01@home.nl> wrote or
quoted :
>xor is fastest
The reason is there is a single Pentium machine instruction for ^=,
XOR. It takes only 1 cycle for register-register ( which is what we
would likely have here), or 3 cycles for an xor to memory. It is
analogous to add to memory and takes the same time.
This is indirect evidence HotSpot has done a great job of optimising
that code.
Consider the code:
boolean bigger = ( a > b );
In the equivalent code in my own BBL compiler, I convert condition
codes to flags in a single cycle rather than using the clumsy jump to
select one of two constants the JVM uses. I trust Hotspot uses
similar optimisations to those that I use. Conditional jumps are
greatly to be avoided. They are bulky, and time consuming, and they
confound the internal lookahead pipelines and caches. On the PowerPC
unconditional jumps are cleverly handled, but not the old Pentiums.
Here are some of my favourite flag capturing tricks. Java uses 0 and 1
in binary. Forth uses 0 and -1, which makes more sense for bitwise
operations.
Saving carry
SBB AX,AX -- saves state of carry flag as 0 or -1
CMC
SBB AX,AX -- saves inverted state of carry flag
which on a 486 is better written:
SBB AX,AX -- save carry as 0 or -1
NOT -- invert
Saving Sign
ROL AX,1
SBB AX,AX -- save sign bit as 0 or -1
On the 486 ROL is slow, so that can be improved with:
ADD AX,AX
SBB AX,AX -- save sign bit as 0 or -1
Testing for Zero
NEG AX -- set carry for AX non zero
SBB AX,AX -- save -1 for AX non zero, 0 for AX zero.
CMP AX,1 -- set carry for AX zero
SBB AX,AX -- set -1 for AX zero, 0 for AX non zero
That optimization works even on the 8086. Thanks. The use of
NEG or CMP 1 to for zero/non-zero looks strange. A newcomer
could think of it this way. CMP is like subtracting 1.
Ordinary positive numbers are little disturbed by subtracting
one. Subtracting one from 0 is a big deal, because it flips
negative, which is what carry is designed to detect. Negative
numbers are already negative, so nothing much happens.
Max-Minus binary 10000000... flips around back to positive
again, generating a 0 carry bit, the same as if nothing had
happened.
NEG is like a NOT followed by a subtract 1, so you'd expect toú
get the complement answer, which you do.
I did a lot of optimising of Pentium sequences using Michael Abrash's
brute force optimiser that just tries all possibilities. It is
remarkable how much it pays to avoid a jmp. If you are curious, you
can download the source to my BBL compiler from
http://mindprod.com/products.html#BBL. The parts written in assembler
are full of notes about my discoveries.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Chris Smith 2004-07-29, 8:57 pm |
| Grant Wagner wrote:
> And now you're assigning something to sequenceContinues all the time, instead
> of only when condition is true.
>
> sequenceContinues = sequenceContinues ^ condition; may be all l33t c0ding, but
> it has to retrieve the value of sequenceContinues, xor it with condition
> (which it has to evaluate) and assign it back to sequenceContinues every
> single pass through the loop.
Just a warning: making these kinds of judgements from the source code
level is quite dangerous. Many changes happen between source level and
machine code, especially in Java where there are an infinite number of
possible machine code versions. Things like avoiding overwriting a
register with the value it already has are probably moot. That's
especially true of ?: versus if, but I'd give you 1:1 odds that a smart
compiler (Hotspot included) knows enough basics about the behavior of
exclusive-or on boolean variables that it can similarly recognize the
pattern in that case as well.
And all this is assuming that an assignment costs more than a branch
that may be mispredicted. Modern processor architectures say otherwise,
if you have decent register allocation. It may be (I'd almost say
likely is) the case that Hotspot is going out of its way to generate
code that *always* reassigns the variable, so as to avoid the penalty
from a possible failure of branch prediction, which would probably mean
flushing the pipeline and stalling for a relatively very long time,
compared to the 0.5 nanoseconds required for a register assignment.
On top of that, there are probably a zillion other factors that are not
being considered here. The point is, programmers are not good at
reasoning about micro-optimization performance off the top of their
heads. With high-level problems, there are guidelines -- we can figure
that an O(n) algorithm is likely to be better than O(n log n), and so
forth... but when you get down to microprocessor-level optimization, you
need exposure to real data to get to the bottom of things, and you
simply can't do that from reading Java source code.
--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.
Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
| |
|
|
----- Original Message -----
From: "Roedy Green" <look-on@mindprod.com.invalid>
Newsgroups: comp.lang.java.help
Sent: Thursday, July 29, 2004 9:23 PM
Subject: Re: Negation of boolean
>
> Here are my discoveries:
>
> ^= is the tersest source code.
>
> ^= is the code most likely to baffle an average programmer.
>
> ^= generates the shortest JVM byte code.
>
> ! generates the fastest code in the case where the expression is false
> by a considerable margin.
>
> ^= generates slightly faster code in the case where the expression is
> true.
>
> I don't know how to snapshot what machine language code finally gets
> generated in Hotspot.
>
> Here are my opinions.
>
> ^= The tersest code is usually the most readable by a knowledgeable
> programmer. There are fewer symbols to absorb. So long as you are
> dealing with idiomatic patterns, such as x ^= condition, there is no
> problem grasping what that does in a gestalt.
>
> ^= is an operator in the Java language. If you don't know what a basic
> operator does, you can't consider yourself a profession Java
> programmer. Everyone who writes Java code for a living should know off
> the bat what this means, or be capable of figuring it out is less than
> a minute.
>
> ^ has fascinating properties. People should want to learn about them
> just out of wonder.
>
> ^ should be more widely used than it is.
>
> It is not wise to use ^ in a team project where you are likely to have
> anything but first class programmers participating. They will play
> helpless. They have no way of figuring it out since somebody else did
> their homework for them when they were going through school. If you
> do use it, you need commentary explaining what it does. Further, there
> exists a quite serviceable more standard alternative.
>
It seems that the java compiler creates a conditional branch when negating a
boolean using !b, which is 3to4 steps, always including one branch:
to negate a boolean at the top of the stack in jvm instructions
0:iload_0
1:ifne 8
4:iconst_1
5:goto 9
8:iconst_0
9....
whereas b^true is just a load, load const1 and xor. which is always just 3
steps, with no branching
Using xor to negate a boolean seems to be a faster (40% on my machine) than
negating using !, is that always the case and if so, why doesn't the
compiler take advantage of this and always compile !b to b^true?
adam
| |
| Roedy Green 2004-07-29, 8:57 pm |
| On Thu, 29 Jul 2004 17:17:32 -0600, Chris Smith <cdsmith@twu.net>
wrote or quoted :
>And all this is assuming that an assignment costs more than a branch
>that may be mispredicted. Modern processor architectures say otherwise,
>if you have decent register allocation. It may be (I'd almost say
>likely is) the case that Hotspot is going out of its way to generate
>code that *always* reassigns the variable, so as to avoid the penalty
>from a possible failure of branch prediction, which would probably mean
>flushing the pipeline and stalling for a relatively very long time,
>compared to the 0.5 nanoseconds required for a register assignment.
Just to reemphasis what Chris and I said:
If you code assembler, and count cycles, you quickly learn that
avoiding doing "work" by doing things two different ways rarely pays.
For speed you want long strings of instructions without any branching.
It pays to do some very strange things to avoid branches even
unconditional ones. You also want to arrange your code so that you
fall through without branching whereever possible on a conditional
branch.
This is because there is so much lookahead going on in a modern CPU.
As soon as you branch, you disturb the lookahead; the instruction
cache has to be flushed; partially precalced instructions have to be
forgotten; the instruction cache has to be reloaded; the pipelines
reprimed... All this happens transparently in the chip hardware.
To predict what will happen to any piece of Java source code requires
knowledge of Javac, byte code, the Hotspot code generator, and the
hardware. Even then there are plenty of surprises. When it matters,
you pretty well have to measure. Measuring is complicated by the fact
Hotspot runs in interpretive mode, then flips unpredictably to
optimised. To measure the long term behaviour, you need a test that
discards the early results. You also need a long enough test so that
GC's average out, or short enough so that you can get a test without
one.
-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-
Knowing that ^= is terser, generates shorter code in the JVM and also
faster code in Hotspot, do you still want to pretend it is too
difficult an idiom to learn?
// conditional toggle:
toggle ^= condition;
It won't hurt to LEARN it, even if you never USE it.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Roedy Green 2004-07-30, 3:58 am |
| On Fri, 30 Jul 2004 01:14:55 +0100, "Adam" <notreal@me.com> wrote or
quoted :
>Using xor to negate a boolean seems to be a faster (40% on my machine) than
>negating using !, is that always the case and if so, why doesn't the
>compiler take advantage of this and always compile !b to b^true?
The problem is optimisation goes on twice, once in Javac and once in
hotspot or other JVM.
The catch is, if you get too fancy with optimisation in Javac, the
second stage optimisation fails to notice common patterns. Ironically
it turns out the more flat footed Javac is, the easier time the
subsequent compilers have.
For example, you will see in the Jet docs they brag that their super
optimisers are now less  by the optimisations of byte code
obfuscators.
I wish it were easier to have a look at the code generated by HotSpot
and Jet so that I could see where they missed a peephole optimisation
I know. I could then pass the trick onto them. As it is, I only know
in very general terms what sorts of optimistation they do.
at a machine level
x = !x;
where x is a boolean could be compiled with a single Pentium NOT
instruction if you changed the boolean representation for true from 1
to -1. Unfortunately the JVM designers were unaware of why Forth
changed true from 1 to -1, and made the same blunder the original
Forth designers did.
If you want really fast code, you have to start at the bottom level,
and make things efficient for that, e.g. choosing the correct boolean
true representation.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| thufir.hawat@mail.com 2004-07-30, 3:58 am |
| On Fri, 30 Jul 2004, Roedy Green wrote:
[..]
> If you want really fast code, you have to start at the bottom level,
> and make things efficient for that, e.g. choosing the correct boolean
> true representation.
[..]
I always thought "true==1" anything else is false. Anyhow, what would be
the correct true reprensentation, and conversely, false?
Thufir Hawat
<http://www.shaw.ca/members/hawat/source/>
| |
| Roedy Green 2004-07-30, 3:58 am |
| On Fri, 30 Jul 2004 04:13:05 GMT, thufir.hawat@mail.com wrote or
quoted :
>I always thought "true==1" anything else is false. Anyhow, what would be
>the correct true reprensentation, and conversely, false?
Java has the values true and false at the source code level. There is
officially no numeric equivalence. However, when you do a
DataOutputStream of a boolean you get the numbers 1 and 0, so at least
externally Java is constrained to represent true as 1 and false as 0.
Similarly for JNI and serialised objects.
In Forth 0 is false and non-zero is true, with a canonical true
represented as -1. This representation is the most efficient from the
point of view of bit and logical manipulations in assembler. You can
do simple booleans or word sized chunks of many bits at once with the
same operators.
A clever optimiser could use the Forth representation for a purely
local boolean. Then for example it could implement ! simply using the
Pentium NOT instruction, or by storing a boolean variable with inverse
logical sense if that turned out to be more convenient. A optimiser
can use deMorgan's laws to simplify your expressions.
Ironically, | is sometimes faster than || since you avoid the jump. A
smart optimiser would convert || to | for you when it would be faster
and the second computation being done would be harmless.
Java and C programmers tend to think of boolean assignment as less
than first class. They prefer to think with ifs and conditions.
Boolean assignment seems unnatural.
You will rarely see them using code like this:
boolean deletable = s.endsWith(".tmp") || s.startWith( "temp" );
You will see instead the boolean expression repeated, or the boolean
computed like this:
boolean deletable = false;
if ( s.endsWith(".tmp") ) deletable = true;
else if ( s.startsWith("temp") ) deletable = true;
Ever since my FORTRAN days, I have been trying to encourage my fellow
programmers to use boolean assignment more often. It usually generates
more readable code in my opinion.
It also lets you build up very complicated expressions from simpler
pieces.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Mark Haase 2004-07-30, 3:58 am |
| In article <MPG.1b733373b4e6dbb8989758@news.altopia.net>,
Chris Smith <cdsmith@twu.net> wrote:
> from a possible failure of branch prediction, which would probably mean
> flushing the pipeline and stalling for a relatively very long time,
> compared to the 0.5 nanoseconds required for a register assignment.
Interesting, I had never considered how Java might be optimized for one
platform. On the PPC, for instance, the pipelines are short and
paralelled, so a pipeline stall isn't as big of a deal. Is that why Java
seems so much faster on Intel iron?
--
|\/| /| |2 |<
mehaase(at)sas(dot)upenn(dot)edu
| |
| Mark Haase 2004-07-30, 3:58 am |
| In article <esqig09jt87mca1atl01981kn97nqggdkf@4ax.com>,
Roedy Green <look-on@mindprod.com.invalid> wrote:
> done deliberately. Go back and see why.
I see what you're talking about but still don't understand why you
misquoted...
--
|\/| /| |2 |<
mehaase(at)sas(dot)upenn(dot)edu
| |
| Roedy Green 2004-07-30, 8:56 pm |
| On Fri, 30 Jul 2004 03:27:31 -0400, Mark Haase <mehaase@earthlink.net>
wrote or quoted :
>On the PPC, for instance, the pipelines are short and
>paralelled, so a pipeline stall isn't as big of a deal. Is that why Java
>seems so much faster on Intel iron?
the PPC is much cleverer about jumps than the Pentium. Usually you get
unconditional jumps free. It tries much harder to predict which way
branches will go. It also has more registers. The Pentium is register
starved.
It is a painstaking business coding low level snippets many ways to
find the optimum. At the low level, suboptimisations are much more
costly. They affect everything everywhere. It is probably just that
Sun spent more time on the Intel optimiser. The Pentium is much more
difficult chip to generate code for. It has so many
non-orthogonalities. The Pentium was designed with hand-coded
assembler in mind. The Power PC was designed with high level languages
and compilers in mind. The advantage the Pentium has is more compact
code if you go with the Pentium flow and use the peculiar magic
instructions and magic register combinations. It is hard for a
compiler to arrange things to be in just the correct form to suit.
In hand coding, you can bend to the Pentium's will more easily.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Chris Smith 2004-07-30, 8:57 pm |
| Mark Haase wrote:
> Interesting, I had never considered how Java might be optimized for one
> platform. On the PPC, for instance, the pipelines are short and
> paralelled, so a pipeline stall isn't as big of a deal. Is that why Java
> seems so much faster on Intel iron?
I don't know. More likely, the reason Java seems faster on Intel is
that Sun has been throwing money at the machine code optimizer for Intel
in response to the "Java is slow" image problems that they've had. They
probably figure they'll get more mileage out of optimizing a more
commonly used processor, and have neglected others (though I'm sure
Solaris performs just fine, too!).
I wouldn't be qualified to comment on what optimizations are or aren't
implemented in any particular JVM for the PPC processor, though.
--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.
Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
| |
| Chris Smith 2004-07-30, 8:57 pm |
| Roedy Green wrote:
> Java has the values true and false at the source code level. There is
> officially no numeric equivalence. However, when you do a
> DataOutputStream of a boolean you get the numbers 1 and 0, so at least
> externally Java is constrained to represent true as 1 and false as 0.
>
> Similarly for JNI and serialised objects.
DataOutputStream should have no impact on the internal representation
for boolean variables used by the VM. JNI may, though even there you've
got some parameter massaging, and changing boolean values isn't too
awfully time-consuming compared to some of the other stuff that goes on
in the JNI boundary.
--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.
Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
| |
| Patrick 2004-07-30, 8:57 pm |
| On Fri, 30 Jul 2004 00:35:27 GMT, Roedy Green
<look-on@mindprod.com.invalid> wrote:
> On Thu, 29 Jul 2004 17:17:32 -0600, Chris Smith <cdsmith@twu.net>
> wrote or quoted :
>
> Just to reemphasis what Chris and I said:
>
> If you code assembler, and count cycles, you quickly learn that
> avoiding doing "work" by doing things two different ways rarely pays.
> For speed you want long strings of instructions without any branching.
> It pays to do some very strange things to avoid branches even
> unconditional ones. You also want to arrange your code so that you
> fall through without branching whereever possible on a conditional
> branch.
>
> This is because there is so much lookahead going on in a modern CPU.
> As soon as you branch, you disturb the lookahead; the instruction
> cache has to be flushed; partially precalced instructions have to be
> forgotten; the instruction cache has to be reloaded; the pipelines
> reprimed... All this happens transparently in the chip hardware.
>
> To predict what will happen to any piece of Java source code requires
> knowledge of Javac, byte code, the Hotspot code generator, and the
> hardware. Even then there are plenty of surprises. When it matters,
> you pretty well have to measure. Measuring is complicated by the fact
> Hotspot runs in interpretive mode, then flips unpredictably to
> optimised. To measure the long term behaviour, you need a test that
> discards the early results. You also need a long enough test so that
> GC's average out, or short enough so that you can get a test without
> one.
>
> -o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-
> Knowing that ^= is terser, generates shorter code in the JVM and also
> faster code in Hotspot, do you still want to pretend it is too
> difficult an idiom to learn?
>
> // conditional toggle:
> toggle ^= condition;
>
>
> It won't hurt to LEARN it, even if you never USE it.
>
I still don't believe it's the best code from the readability point of
view.
But with good comments I see no reason not to use it when appropriate.
I't may be one of the things you need to learn when you grow from beginner
to intermediate or experienced programmer.
It's definitely something I re-learned.
Patrick
| |
| Roedy Green 2004-07-30, 8:57 pm |
| On Fri, 30 Jul 2004 21:55:46 +0200, Patrick <tuin01@home.nl> wrote or
quoted :
>I still don't believe it's the best code from the readability point of
>view.
Nobody claimed it was. It is still unfamiliar to most programmers.
However, I think it is high time that changed. We should me educating
Java coders about useful parts of their language they take a perverse
delight in ignoring and feeling virtuous about it. It is similar to
the inverse pride people get from writing slow code because they have
no idea which ways of coding are faster.
Reminds me a bit of Scalia's defense of idiocy.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
| |
| Patrick 2004-07-30, 8:57 pm |
| On Fri, 30 Jul 2004 20:46:38 GMT, Roedy Green
<look-on@mindprod.com.invalid> wrote:
> On Fri, 30 Jul 2004 21:55:46 +0200, Patrick <tuin01@home.nl> wrote or
> quoted :
>
>
> Nobody claimed it was. It is still unfamiliar to most programmers.
> However, I think it is high time that changed. We should me educating
> Java coders about useful parts of their language they take a perverse
> delight in ignoring and feeling virtuous about it. It is similar to
> the inverse pride people get from writing slow code because they have
> no idea which ways of coding are faster.
We should tell M$
>
> Reminds me a bit of Scalia's defense of idiocy.
>
>
--
Patrick
| |
| Tony Morris 2004-07-31, 3:56 am |
| "Mark Haase" <mehaase@earthlink.net> wrote in message
news:mehaase-4DC9BB.00440729072004@netnews.upenn.edu...
> In article <hl6gg0ta5cfo099j3jf6o7tnf9f0mvlh5i@4ax.com>,
> Roedy Green <look-on@mindprod.com.invalid> wrote:
>
Any SCJP should be able to tell you about the XOR compound operator.
[color=darkred]
> I use ?: all the time. It's my favorite ternary operator. <insert nerdy
> snicker>
It's the only ternary operator.
--
Tony Morris
http://xdweb.net/~dibblego/
| |
| Tony Morris 2004-07-31, 3:56 am |
| > Any SCJP should be able to tell you about the XOR compound operator.
*XOR compound assignment operator
--
Tony Morris
http://xdweb.net/~dibblego/
|
|
|
|
|