a ^= b ^= a ^= b ???
William Wendling
Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
t I heard someone say it doesn't.
--
Bill Wendling | GM/CS/S d@ H- s-: g+++ p? au+ a- w+ v->! C+++(++++)
wend...@uis.edu | U+>++++ P+ L++>+++ !3 E N+ K--- W--- M-- !V
Boom Shanka! | po--- Y++ t+++ 5- jx R+>++ G? tv+ b++>+++ D
| B+++ e+++(*) u*(++) h!(*) f+ !r(*) !n y?
Tanmoy Bhattacharya
Wendling) writes:
|> Sorry about this, guys, but...
You _should_ be very very sorry for posting this: This is one of the most
useless and most commonly occurring discussion in this newsgroup. Did you
realize there was something called the list of `Frequently Asked Questions'
or FAQs for short, which you are supposed to read _before_ you post and waste
everybody's time?
|>
|> Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
|> t I heard someone say it doesn't.
|>
Even though it looks like C, the statement is _not_ legal C. As a result it
can do whatever it wants. (C does not allow you to change the same object
twice within the same expression: the statement is slightly inaccurate and
read the FAQ for more info.)
And, programming is not about cute tricks: it is about expressing what you
mean clearly.
Cheers
Tanmoy
--
tan...@qcd.lanl.gov(128.165.23.46) DECNET: BETA::"tan...@lanl.gov"(1.218=1242)
Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87544-0285,USA H:#3,802,9 St,NM87545
Others see <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
<http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
fax: 1 (505) 665 3003 voice: 1 (505) 665 4733 [ Home: 1 (505) 662 5596 ]
hal...@caip.rutgers.edu
: ....
: And, programming is not about cute tricks:
: it is about expressing what you mean clearly.
billy the kid
>Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
>t I heard someone say it doesn't.
a ^= b;
b ^= a;
a ^= b;
may indeed work, but when you slap them all together without sequence
points (namely, a ';', or a non-function parameter list ',')... you don't
have any guarantees about what order operations occur. The order may change
by using different compiler switches on the same compiler, let alone across
different platforms or vendors. In general, is't an obfuscated method of
swapping variables. Who cares about a very small number (2-4 usually) of
extra bytes used by a program.
--
Billy the Kid
***************************************************************************
If they don't keep on exercising their lips, their brains start working.
-- Ford Prefect's theory on humans, Hitchhikers Guide to the Galaxy.
***************************************************************************
Steve E. Chapel
>Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
>t I heard someone say it doesn't.
I tried it, and it works, as long as a and b are the same size integer type.
It won't work for any other data type.
--
Steve Chapel sch...@cs.ucsb.edu | http://www.cs.ucsb.edu/~schapel
Senior in Computer Science at the | finger -l sch...@eci1.ucsb.edu
University of California, Santa Barbara | Finger me for my PGP public key
The Amorphous Mass
> Sorry about this, guys, but...
>
> Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
> t I heard someone say it doesn't.
Because a and b are being modified more than once between sequence points.
You can *not* depend on the order of evaluation being left-to-right.
This is in the FAQ (available by anon ftp from rtfm.mit.edu).
___________
Bushido, n.: the ancient art of keeping your | James Robinson
cool when a US President ralphs in your lap. | james-f-...@uiowa.edu
Tanmoy Bhattacharya
E. Chapel) writes:
|>
|> >Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
|> >t I heard someone say it doesn't.
|>
type.
|> It won't work for any other data type.
I am responding because of the dangerous attitude this expresses! Remember
the joke about the mathematician who would only agree that the visible
_side_ of the visible sheep on the mountain was black? Programming is very
like that: all you know is that it worked in the particular example you
tried. Assuming you have an ANSI compliant compiler, this means either
1) The program is correct on your implementation (which means it does not
violate what are called `constraints' and `syntax rules': and uses only those
undefined features which have been given meaning by your implementation
documentation.)
or
2) The program is incorrect in a way that is called `undefined' behaviour.
Note that neither of these is equivalent in spirit to the plain simple `it
works' which carries an implication that it works for others too: probably on
a different machine, and a different compiler.
A program which invokes undefined behaviour need not even work on your
compiler all the time: it may depend on what statements surround it (if you
have been programming any length of time, you must have heard about
heisenbugs: those that disappear when you put in a print statement somewhere?
Those are most often instances of undefined behaviour: the print statement
changed the behaviour of an unrelated part of the program!), it may depend on
what else is running on the machine, the time or place or the room
temperature :-)
In this particular case, it is very unlikely that a^=b^=a^=b belongs to the
class of implementation extensions. I am guessing, but in all probability it
is undefined behaviour even on your implementation (it is undefined by the
standard, and on most compilers I have seen), but if your compiler is not
very aggressive in optimization, it might just work for you in the vast
majority of the cases. If you are compiling code only for your machine, and
only on this specific revision of this specific compiler, and if you feel
lucky (or know how your compiler was coded), and if _my_ life does not depend
on your programming, please continue to use it :-)
Kevin D. Quitt
>wend...@eagle.uis.edu (William Wendling) writes:
>>Why won't a^=b^=a^=b work to swap a and b?
It may work, but it's by accident. The statement generates undefined
behaviour; one such behaviour is doing what you wanted to do (but
didn't express properly).
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91351-4454 96.37% of all statistics are made up
hal...@caip.rutgers.edu
: ....
: And, programming is not about cute tricks:
: it is about expressing what you mean clearly.
hal...@caip.rutgers.edu wrote:
>No, that is technical writing, and historie- and news-writing.
In article <1995Sep6.2...@llyene.jpl.nasa.gov>, k...@emoryi.jpl.nasa.gov (Kevin D. Quitt) writes:
> So you write ambiguous code?
That is impossible, unless it is sumthing that the compiler together with
the system that the compiler runs on and the system that the program runs
all relevant implementors call undefind. Such behavior is quite rare.
Kevin D. Quitt
>In article <42hnm4$4...@newshost.lanl.gov>, tan...@qcd.lanl.gov (Tanmoy Bhattacharya) writes
>: ....
>: And, programming is not about cute tricks:
>: it is about expressing what you mean clearly.
>No, that is technical writing, and historie- and news-writing.
So you write ambiguous code?
Steve Summit
>> Why won't a^=b^=a^=b work to swap a and b? I know it should, I thought
>> I heard someone say it doesn't.
>
Indeed.
Here's another little-known secret: the "return" keyword is optional!
This program correctly prints 123 on my computer:
main()
{
printf("%d\n", function(100, 20));
}
int function(a, b)
{
a + b + 3;
}
Also, it's more efficient.
Steve Summit
s...@eskimo.com
P.S. Anybody got a clean dictionary? Mine's smudged between
"Saratoga" and "sarcoma," and I can't read the word there.
John R MacMillan
|: it is about expressing what you mean clearly.
|
|>No, that is technical writing, and historie- and news-writing.
I disagree. Expressing your program ``clearly'' to a compiler is only
part of the task (and IMHO, the easier part of the task). Most
programs are read often by humans as well (whether they were intended
to be, or not) for maintenance, or extensions, or porting, and the
program's intent must be clear to them as well.
|> So you write ambiguous code?
|
|That is impossible, unless it is sumthing that the compiler together with
|the system that the compiler runs on and the system that the program runs
|all relevant implementors call undefind. Such behavior is quite rare.
Actually, it's quite common in this newsgroup (witness the current
thread, and the interminable "i = i++" questions), and not all that
uncommon in C, which has a fair bit of unspecified, undefined, and
implementation-defined behaviour. Even experienced programmers
sometimes trip over it; a recent version of a widely-used freely
available software program generated a bug report against the compiler
I maintain, and it turned out that the program was relying on
unspecified behaviour.
(For the curious, the program had a macro like:
#define FOO(n) ((temp = (n)), <expresion using temp>)
then used it twice in a function call:
func(FOO(value1), FOO(value2));
It's not immediately obvious that the result is unspecified, but a
valid ordering is:
assign value1 to temp
assign value2 to temp
eval <expression using temp>
eval <expression using temp>
call func with evaluated results
which is NOT was intended.)
Tanmoy Bhattacharya
E. Chapel) writes:
|> sch...@zonker.cs.ucsb.edu (Steve E. Chapel) writes:
|>
|> >wend...@eagle.uis.edu (William Wendling) writes:
|>
|> >>Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
|>
|> >I tried it, and it works, as long as a and b are the same size integer
type.
|> >It won't work for any other data type.
|>
|> the people who sent me this e-mail seriously misread my post.
The reason for that (_if_ rudeness can ever be justified) is that this issue
is discussed at quite a length in the list called FAQ which answers
frequently asked questions. In the interest of saving everybody's time, it is
considered polite to read it before posting. Your behaviour in posting this
shows that you have been impolite, and the rudeness you received was in
response to that fact.
This is not to say that the FAQ cannot be challenged, or that it is
infalliable. It however has been written by people, and checked by people,
who know a lot about C. Some people who have looked at it are regular
contributors to comp.std.c, and some of them, I am sure, are involved in the
standards work on C. To challenge it, you must quote it, and counter its
arguments rationally: not just ignore it.
|>
|> If someone makes a statement that something does not work, and it works
|> in only one situation, however bizarre that situation is, the original
|> statement that it does not work is incorrect. This is called "proof by
|> counterexample." The fact that it works with the compiler, OS, and
It is you who has misunderstood the original statement. `It does not work'
talking of a program construct does _not_ mean that it works under no
circumstance. It simply means that the construct either has the unintended
effect, or is meaningless drivel. The second is the case here, a^=b^=a^=b; is
absolutely meaningless as a C language construct.
|> processor that I have at my disposal is such a proof by counterexample
|> that a^=b^=a^=b can work to swap a and b.
|>
|> The statement that a^=b^=a^=b does not swap a and b is implicit in the
|> question. Since this statement is incorrect, the question is invalid.
This is wrong. a^=b^=a^=b; brings in `undefined' behaviour, and so it is not
a C language instruction to swap two variables. It may however have that
effect in one particular compiler.
This is analogous to the `English' statement "I went to came from there." It
is not an English sentence, but if you utter it in actual speech, some people
will say 'Uh?', some will assume you `came from' there, and some will assume
you `went to and came back from' there. All responses are valid, but is is
not _true_ that the original sentence is a way of expressing that last
meaning. In this analogy, you can see that one can correctly say that
"The statement does not mean that 'you went to and came back from there'",
and yet, there is at least one person here who interpreted my statement that
way.
So, what happened to the logical principle of proof by counterexample? Why
didn't a counterexample disprove the statement? Because, inherent in my
statement was an understood quantifier `There exists': i.e. There exists
English speakers, to whom the statement does not mean ... Similarly when one
says that a^=b^=a^=b does not swap variables, it only means that `There
exists C compilers where the expression does not swap variables'. This
statement can _not_ be contradicted by a counter example: the only way to
contradict it is by `reductio ad absurdum': To prove the statement false, you
have to show that a compiler which did not swap the variables in that context
was not a C compiler. The only way, this in turn could be true, is if the
expression swaps two variables purely according to the definition of the C
language.
Fortunately the C language is a well defined entity, defined by a document
publicly available, though not exactly cheap, and it is a obvious after even
a casual reading of the two passages that the standard refrains from making
any statements about this particular expression.
So, that is why the statement that the `expression does not swap variables'
cannot be disproved after all.
|>
|> To answer the question "why does a^=b^=a^=b not work under all possible
|> circumstances?" is much more involved; two cases that I pointed out are
|> when a and b are non-integral types, and when a and b are differently-sized
|> integers. I believe yet another case is when the code occurs in a macro
|> that takes two parameters, and you invoke the macro with only one variable,
|> or with expressions that cause side effects. There are undoubtedly many
|> situations in which this code will not work.
Yes, and one of those situations is `at the whim of the compiler'. In other
words, it certainly may swap the variables, and yet, it may as well terminate
your program or wipe your disk. This expression does not have _any_ meaning
in C, and asking what it does can only be answered at a much lower level.
Basically, the compiler generates some code and optimizes it under the
assumption that the same location will _not_ be modified twice in the same
expression (or between two sequence points to be exact). These optimizations
and the code generation strategies are required to be correct _only_ for that
case. So, when you violate that restriction, the machine code generated by
the compiler need not correspond to what the C expression seems to mean to
you.
Essentially, there is no reason why a smart compiler must generate the same
code for
a^=b; b^=a; a^=b;
and
a^=b^=a^=b;
The machine code in the former case _has_ to express the obvious because it
is valid C. Any possible `optimization' which would change the meaning is
obviously invalid, and the compiler will take special steps to avoid that.
The latter however is _not_ protected. The compiler can think it is
`optimizing' which however become invalid because the same variable changes
more than once.
|>
|> To answer the question "why is a^=b^=a^=b poor code for swapping two
|> variables?", the answer is that it the code is very opaque. Unless you
|> have seen this trick before, it will take you much longer to understand
|> what this code does than if you simply wrote what you meant.
No. It is true that the code is opaque, but it is also true that the code is
not C.
|>
|> But neither of these was the question that was asked, and therefore they
|> were not the questions that I answered.
Certainly. The questions is whether this code is C or not: and you wrongly
assert that it is C,
|>
|> If someone knows of any case in which this code segment does not work with
|> integeral types of the same size, not in a macro, where both of the variables
|> are modifiable and non-volitile, and so on ad nauseum, I'd like to know
|> about it because I don't understand why it wouldn't.
If you really want to know about C, please read the FAQ. It contains a lot of
valuable information.
Kevin D. Quitt
>In article <42hnm4$4...@newshost.lanl.gov>, tan...@qcd.lanl.gov (Tanmoy Bhattacharya) writes
>: ....
>: And, programming is not about cute tricks:
>: it is about expressing what you mean clearly.
>hal...@caip.rutgers.edu wrote:
>>No, that is technical writing, and historie- and news-writing.
>In article <1995Sep6.2...@llyene.jpl.nasa.gov>, k...@emoryi.jpl.nasa.gov (Kevin D. Quitt) writes:
>> So you write ambiguous code?
>That is impossible, unless it is sumthing that the compiler together with
>the system that the compiler runs on and the system that the program runs
>all relevant implementors call undefind. Such behavior is quite rare.
It's not only not impossible, it's why statements invoke undefined
behaviour. Since there's more than one possible "sensible" outcome,
the standard says the result is undefined, at which point it can be
*any* answer or behaviour.
Kevin D. Quitt
>integeral types of the same size, not in a macro, where both of the variables
>are modifiable and non-volitile, and so on ad nauseum, I'd like to know
>about it because I don't understand why it wouldn't.
You're modifying the variable a twice between sequence points. The actual
assignment to the variable can take place at any time, up to and including
the semi-colon. This means it's perfectly ok for the first assignment to
be delayed until after the second, so you could end up with a^b in a.
When we say "it doesn't work because it's undefined", you are not showing a
counter-example by saying "it works on my compiler". All that shows is
that your compiler (which has the right to format you disk or send nasty
email to your boss about your coding style) has chosen to generate code
that produces the code you expect. But that may change if you change
the parameters of the compilation, such as optimization.
Kevin D. Quitt
>> Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
>> t I heard someone say it doesn't.
This is right. (well, a is being modified twice.)
> You can *not* depend on the order of evaluation being left-to-right.
This is irrelevant. It's undefined only because of the previous statement.
Dr S.J. Harris
>
>>In article <42jki2$r...@zonker.cs.ucsb.edu>, sch...@zonker.cs.ucsb.edu
>>(Steve E. Chapel) writes:
>>> wend...@eagle.uis.edu (William Wendling) writes:
>>>> Why won't a^=b^=a^=b work to swap a and b? I know it should, I thought
>>>> I heard someone say it doesn't.
>>>
>
>>Indeed.
>
>>Here's another little-known secret: the "return" keyword is optional!
>>This program correctly prints 123 on my computer:
>
>> main()
>> {
>> printf("%d\n", function(100, 20));
>> }
>
>> int function(a, b)
>> {
>> a + b + 3;
>> }
>
>>Also, it's more efficient.
>
>
>Pretty stupid question, huh? It *does* work *sometimes*.
>
>All it has to do is work sometimes, and the quesiton "why doesn't it work?"
>becomes meaningless.
>
>This was my original point. No more. No less.
I bet any half decent optimiser would look at that a+b+3 line and think..
assignment ? nope,
functions calls? nope,
nah... I don't think I can be bothered to compile it.
Removing 'return' will only work if:
1. the temporary register used for calculations is the same as
the one used to pass back return values (very dodgy!)
2. the compiler does not optimise it out.
3...n. probably some more system/compiler specific features I
can't think of at the moment.
By the way - I just tried it on an SG Indy and an Indigo and it didn't
work. In fact, I just tried compiling it with two compilers and got
different
answers, neither of which was 123 (also, a C++ compiler told me I was
missing
a 'return').
ANSI C mode OFF:
From what I remember about Borland C, it may work on that
sometimes. Borland C usually uses AX for intermediate integer
results and passes integers back to a caller using AX too, so
the correct result returned is just a side effect of a calculation
which has not been optimised out.
ANSI C mode ON:
don't try this at home folks!
>--
>Steve Chapel sch...@cs.ucsb.edu | http://www.cs.ucsb.edu/~schapel
> Senior in Computer Science at the | finger -l sch...@eci1.ucsb.edu
>University of California, Santa Barbara | Finger me for my PGP public key
Just felt I had to put my oar in...
Simon
Peter Seebach
Steve E. Chapel <schapel@zonker> wrote:
>Here is the relavent portion of the FAQ:
>10.3: How can I write a generic macro to swap two values?
[snip]
>As you can see, it has to do with MACROS - the original question did
>not involve macros.
*sigh*. I suppose that, since the FAQ named the vars a and b, you
think that it would be legal were they named c and d?
Did you *read* the question it said to look at? And the answer to it?
IF YOU MODIFY THE SAME LVALUE TWICE BETWEEN SEQUENCE POINTS, OR REFER TO IT
AND MODIFY IT BETWEEN SEQUENCE POINTS[1], THE BEHAVIOR IS UNDEFINED.
[1] Unless that reference is solely to determine the new value, i.e.,
i = i + 1.
Now, which part do you not understand? The expression "a^=b^=a^=b"
is undefined. It is *because* this expression, *IN ANY CONTEXT
WHATSOEVER* is undefined, that a macro using it is undefined.
Once again, it is *meaningless*. It only means "swap a and b" *if* you assume
that all evaluation is left to right. It isn't.
*Please* try to think this through; would you really expect that several
experienced C programmers, many of whom are writing or have written books on
C, and who have checked their assertions with the ANSI committee, and who have
used *dozens* of compilers, would *all* be wrong? Of course you would; this
happens. But it's just as true that *you* are wrong some of the time. This
is one of those times.
The ASNI standard declares this behavior undefined. Meaning: It has no
defined effect. Meaning: A compiler is under no obligation to do what you
want with it.
-s
--
Peter Seebach - se...@solon.com || se...@intran.xerox.com --
C/Unix proto-wizard -- C/Unix questions? Send mail for help. No, really!
Copyright 1995 Peter Seebach. Like my work? Send donations!
The *other* C FAQ - ftp taniemarie.solon.com /pub/c/afq
John Woods
>> int function(a, b)
>> {
>> a + b + 3;
>> }
>>Also, it's more efficient.
>So why doesn't leaving out return it work?
>Pretty stupid question, huh? It *does* work *sometimes*.
>All it has to do is work sometimes, and the quesiton "why doesn't it work?"
>becomes meaningless.
"Sometimes" doesn't cut it in the real world. Running at doors full tilt
and smashing your face into them "sometimes" opens them, but for some odd
reason you just don't see this practiced very often.
>Steve Chapel sch...@cs.ucsb.edu | http://www.cs.ucsb.edu/~schapel
> Senior in Computer Science at the | finger -l sch...@eci1.ucsb.edu
God help your first employer.
The Amorphous Mass
> In comp.lang.c you write:
> >>
> >> Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
> >> t I heard someone say it doesn't.
>
> > Because a and b are being modified more than once between sequence points.
> > You can *not* depend on the order of evaluation being left-to-right.
>
> I haven't read the FAQ yet, but assignment associates Right-to-left.
>
I wasn't very clear. Assignment associates l-2-r, but the
*side-effects* of assignment can happen any time between sequence
points. That's why a[i] = i++, for example is undefined. The FAQ covers
this is some detail.
Thanks for responding, though.
M. J. Saltzman
>s...@eskimo.com (Steve Summit) writes:
>> <example of function with missing return that "works">
>>Also, it's more efficient.
>So why doesn't leaving out return it work?
>Pretty stupid question, huh? It *does* work *sometimes*.
>All it has to do is work sometimes, and the quesiton "why doesn't it work?"
>becomes meaningless.
>This was my original point. No more. No less.
There is actually a serious issue of semantics that is being flogged
here. In mathematics, computer science, and the sciences in general,
there is a conventional interpretation of the terms "true" and
"false", namely:
"True" means true always, i.e., for a theorem, in all
situations satisfying the premises, the conclusion holds
without fail.
"False" means not true, i.e., there is some situation in
which the premises of a proposition hold but the conclusion
does not.
To show that a proposition is false, it suffices to illustrate a
situation in which the premises hold but the conclusion does not, that
is, a counterexample. To show that a proposition is true requires a
proof, that is, a sound logical argument from sound principles
demonstrating that no counterexample can exist. It is not enough to
simply assert that after trying all the cases one could think of, one
has not found a counterexample, and it is certainly not enough to
simply illustrate an example (or even several examples) where the
assertion holds.
Consider the proposition, "All integers are even." Now we all know
that it is not the case that all integers are even, so we might say,
"Not all integers are even." Clearly, we do not consider it
acceptable to answer the claim, "Not all integers are even," by
saying, "But look, 2, 4, and 6 are even. So what's the problem?"
In computer science and programming, the (informal) terms "works" and
"doesn't work" (referring to algorithms or programs) are treated the
same as "true" and "false", namely:
"Works" means that whenever the initial conditions of the
algorithm are satisfied by the data, then the terminal
conditions are guaranteed to be satisfied.
"Doesn't work" means doesn't "work", i.e., there is some
set of data somewhere that satisfies the initial conditions,
but after running the algorithm, the data fails to satisfy
the ending conditions.
Consider the following proposed sorting algorithm:
Swap the first and last elements in the list, and stop.
We don't consider it acceptable to respond to the assertion, "This
algorithm doesn't work," by saying, "Look, if you put in the list
[5,2,3,4,1], the sorted list [1,2,3,4,5] is produced, so the algorithm
does work." If you claim that this algorithm "works", you are obliged
to demonstrate that there is no possible input list that remains
unsorted after applying the algorithm. The list [5,2,3,4,1] is not a
counterexample to the assertion that the algorithm "doesn't work", any
more than 2, 4, and 6 are counterexamples to the assertion that "not
all integers are even".
In comp.lang.c (and in programming in general), the convention is the
same: a piece of C code "works" only if it is guaranteed to produce
the expected result when compiled by any conceivable correct
compiler--not only ones that actually exist, but hypothetical
compilers that (for example) implement various exotic behaviors when
they encounter undefined language constructs. It is no more
acceptable in comp.lang.c to assert that a particular implementation
is a counterexample to the claim, "This construct doesn't work," than
it is to claim that a particular input list is a counterexample to the
claim that the above sorting algorithm "doesn't work".
If you claim that certain C code "works", you are obliged to provide a
sound logical argument that there can be no correct implementation of
C that will fail to compile it and produce the correct result when it
is executed. If you claim that the code "doesn't work", you need only
provide a hypothetical implementation that would fail to produce the
correct result. A convincing demonstration that the code relies on
"undefined behavior" is prima facie proof that the code "doesn't work",
since a hypothetical implementation could fail to produce the expected
result in a reasonable way or in an unreasonable way.
I would think that as a computer science student you would have
been exposed to this convention by now.
In another post, Chapel wrote:
+On Thu, 7 Sep 1995, Peter Seebach wrote:
+
+Here is the relavent portion of the FAQ:
+
+10.3: How can I write a generic macro to swap two values?
+
+A: There is no good answer to this question. If the values are
+ integers, a well-known trick using exclusive-OR could perhaps be
+ used, but it will not work for floating-point values or
+ pointers, or if the two values are the same variable
Here's the relevant portion of the relevant portion of the FAQ:
+ (and the
+ "obvious" supercompressed implementation for integral types
+ a^=b^=a^=b is illegal due to multiple side-effects; see question
+ 3.2).
This part has nothing whatsoever to do with macros.
+ [...rest of FAQ answer deleted...]
+
+As you can see, it has to do with MACROS - the original question did
+not involve macros.
--
Matthew Saltzman
Clemson University Math Sciences
m...@clemson.edu
billy the kid
Steve E. Chapel <sch...@zonker.cs.ucsb.edu> wrote:
>>>Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
>>>t I heard someone say it doesn't.
>If someone knows of any case in which this code segment does not work with
>integeral types of the same size, not in a macro, where both of the variables
>are modifiable and non-volitile, and so on ad nauseum, I'd like to know
>about it because I don't understand why it wouldn't.
You asked for it, watch closely:
"a" and "b" are 8-bit types (for demo purposes).
a contains 10100101
b contains 01100110
we do the "a ^= b ^= a ^= b" where we assume we have a stack-based system,
and it works like this (maybe not normal, but very possible, maybe desirable):
1) put all the values on the stack (right to left, so the operands show
up in the "right" order, we get this:
[2] 01100110
[1] 10100101
[tos] 01100110
2) take xor of a (10100101) and tos (01100110) and assign to a (11000011)
3) pop stack (we have this:)
[1] 01100110
[tos] 10100101
4) take xor of b (01100110) and tos (10100101) and assign to b (11000011)
5) pop stack (we have this:)
[tos] 01100110
6) take xor of a (11000011) and tos (01100110) and assign to a (10100101)
7) pop stack, and we are done.
a now contains 10100101 (was 10100101)
b now contains 11000011 (was 01100110)
see, something completely different happened, in a perfectly valid
implementation. This is the danger of assigning to a variable more than
once between sequence points.
--
Steve E. Chapel
>In article <42jki2$r...@zonker.cs.ucsb.edu>, sch...@zonker.cs.ucsb.edu
>(Steve E. Chapel) writes:
>> wend...@eagle.uis.edu (William Wendling) writes:
>>> Why won't a^=b^=a^=b work to swap a and b? I know it should, I thought
>>> I heard someone say it doesn't.
>>
>> I tried it, and it works...
>Indeed.
>Here's another little-known secret: the "return" keyword is optional!
>This program correctly prints 123 on my computer:
> main()
> {
> printf("%d\n", function(100, 20));
> }
> int function(a, b)
> {
> a + b + 3;
> }
>Also, it's more efficient.
So why doesn't leaving out return it work?
Pretty stupid question, huh? It *does* work *sometimes*.
All it has to do is work sometimes, and the quesiton "why doesn't it work?"
becomes meaningless.
This was my original point. No more. No less.
--
Steve Chapel sch...@cs.ucsb.edu | http://www.cs.ucsb.edu/~schapel
Senior in Computer Science at the | finger -l sch...@eci1.ucsb.edu
Steve E. Chapel
> Side effects cab be deferred.
>
> The implementation:
>
> Store a^b as temp1.
> Store b^a as temp2.
> Store a^b as temp3.
> Assign temp1 to a.
> Assign temp2 to b.
> Assign temp3 to a.
>
> Is legit. Please read the FAQ. Basically, the expression is ambiguous.
> Should the 2nd "a" evaluate as "a" before the expr. started, or as a ^ b?
>
> A compiler is entitled to ortimize the whole thing out.
Here is the relavent portion of the FAQ:
10.3: How can I write a generic macro to swap two values?
A: There is no good answer to this question. If the values are
integers, a well-known trick using exclusive-OR could perhaps be
used, but it will not work for floating-point values or
pointers, or if the two values are the same variable (and the
"obvious" supercompressed implementation for integral types
a^=b^=a^=b is illegal due to multiple side-effects; see question
3.2). If the macro is intended to be used on values of
arbitrary type (the usual goal), it cannot use a temporary,
since it does not know what type of temporary it needs (and
would have a hard time naming it if it did), and standard C does
not provide a typeof operator.
The best all-around solution is probably to forget about using a
macro, unless you're willing to pass in the type as a third
argument.
As you can see, it has to do with MACROS - the original question did
not involve macros.
Steve E. Chapel
>In article <42lotj$1...@zonker.cs.ucsb.edu>, sch...@zonker.cs.ucsb.edu (Steve
>E. Chapel) writes:
>|> sch...@zonker.cs.ucsb.edu (Steve E. Chapel) writes:
>|>
>|> >wend...@eagle.uis.edu (William Wendling) writes:
>|>
>|> >>Why won't a^=b^=a^=b work to swap a and b? I know it should, I though
>|> >>t I heard someone say it doesn't.
>|>
>|> >I tried it, and it works, as long as a and b are the same size integer
>type.
>|> >It won't work for any other data type.
>|>
>|> I received several rude e-mail messages for my followup. I believe that
>|> the people who sent me this e-mail seriously misread my post.
>It is you who has misunderstood the original statement. `It does not work'
>talking of a program construct does _not_ mean that it works under no
>circumstance. It simply means that the construct either has the unintended
>effect, or is meaningless drivel. The second is the case here, a^=b^=a^=b; is
>absolutely meaningless as a C language construct.
I disagree with you here. I wrote a fast table-driven CRC routine last week
and when I showed it to my boss he was quite pleased. We compiled the
routine and programmed a modem's EPROM with the compied code, and the
modem appeared to function perfectly in every way. I would have to say
that the code "works" in every sense of the word.
However, the code I wrote for that routine makes several assumptions:
that a short is the same size as two chars, and that the MSB of a short
is stored in the lower address. According to your definition of "works"
my code doesn't work.
I sure my boss would be quite amused to hear you say that my code doesn't
work. (And don't tell the modem - it might start spewing garbage in spite!:-)
Steve E. Chapel
>And, programming is not about cute tricks: it is about expressing what you
>mean clearly.
I disagree. Code clarity is only one of many programming issues.
Honestly, would you choose a clearly-written routine in time critical
code that does not meet the performance specifications you have been given
over an obscurely-written piece of code that meets specs? Surely
efficiency is another issue to be considered.
Steve E. Chapel
>sch...@zonker.cs.ucsb.edu (Steve E. Chapel) writes:
>>> int function(a, b)
>>> {
>>> a + b + 3;
>>> }
>>>Also, it's more efficient.
>>So why doesn't leaving out return it work?
>>Pretty stupid question, huh? It *does* work *sometimes*.
>>All it has to do is work sometimes, and the quesiton "why doesn't it work?"
>>becomes meaningless.
>"Sometimes" doesn't cut it in the real world. Running at doors full tilt
>and smashing your face into them "sometimes" opens them, but for some odd
>reason you just don't see this practiced very often.
>>Steve Chapel sch...@cs.ucsb.edu | http://www.cs.ucsb.edu/~schapel
>> Senior in Computer Science at the | finger -l sch...@eci1.ucsb.edu
>God help your first employer.
Hmmm. My current boss seems quite happy with my work. In case you missed
it I wrote little anecdote about some code that I wrote that works with
one of our compilers and does not work with another of our compilers. I've
showed that code to my boss and he is very happy with it, because it's very
efficient. He doesn't care if it's non-portable. It only has to work with
our embedded systems compiler. It seems like you're trying to say that
code that is not 100% portable is always bad code, but me and my boss
disagree with you.
I have no qualms about writing non-portable code if there is an advantage
to be gained from it. In my opinion, portability is just one issue out
of many that must be considered to determine whether code is "good" or
"bad". Other issues include maintainability, correctness, and efficiency.
I would have no hestitation it writing a^=b^=a^=b in my code under the
following conditions:
1) It needs to work with only one compiler
2) There is a large speed advantage gained by using this code
I don't even care if it's non-portable, or "illegal". As long as it
does what we what it to do, in my opinion it's good code.
billy the kid
previous post (did any one spot it :-)...
assignments bind right to left, instead of the normal left to right, so that
a = b = c = d = e = f = 0;
assigns 0 to everything correctly. The method I showed in my previous post
would have assigned b -> a, c -> b, etc... in that order, instead of the
correct way around... so, now I have corrected that error, and submit a
method of correctly doing something other than swapping...
In article <DEL2r...@ns1.nodak.edu>,
billy the kid <pepp...@badlands.NoDak.edu> wrote:
[ someone asking for a case where a ^= b ^= a ^= b; doesn't work ]
>You asked for it, watch closely:
(oops :-)
>"a" and "b" are 8-bit types (for demo purposes).
>
>a contains 10100101
>b contains 01100110
>
>we do the "a ^= b ^= a ^= b" where we assume we have a stack-based system,
>and it works like this (maybe not normal, but very possible, maybe desirable):
so far so good, the following has been corrected...
1) put all the values on the stack (left to right, so the operands show
up in the "right" order, we get this:
[2] 10100101 (a)
[1] 01100110 (b)
[tos] 10100101 (a)
2) take xor of b (01100110) and tos (10100101) and assign to a (11000011)
3) pop stack, we have this:
[1] 10100101 (a)
[tos] 01100110 (b)
4) take xor of a (11000011) and tos (01100110) and assign to b (10100101)
5) pop stack, we have this:
[tos] 10100101 (a)
6) take xor of b (10100101) and tos (10100101) and assign to a (00000000)
7) pop stack, and we are done.
a now contains 00000000 (was 10100101)
b now contains 10100101 (was 01100110)
This construct now becomes the "super-efficient" method of doing:
b = a;
a = 0;
or it could swap a and b, or it might even be able to do something else.
Tanmoy Bhattacharya
E. Chapel) writes:
<snip>
|> I would have no hestitation it writing a^=b^=a^=b in my code under the
|> following conditions:
|> 1) It needs to work with only one compiler
|> 2) There is a large speed advantage gained by using this code
Fine. This is not comp.lang.english, and I will not debate the merits of
your use of the term `working code'. Just do not confuse people by
claiming that that nonsense is `working C code'. (In comp.lang.c, `working
code' refers to `working C code') Every C compiler has to accept all valid C
code, but it in general also accepts a lot of garbage. That garbage `works'
by your definition, and (in fact the standard calls it `conforming C code':
which makes the definition of conformance useless to most people). It however
does not make it a `working C' program.
Now let us come to your preconditions one at a time:
1) It needs to work with only one compiler.
One has to realize that undefined code like this usually works on some
particular versions of some compilers in some optimization modes under some
conditions. There is no way to guarantee that it works, till the compiler has
completed the compilation, and then the resulting object code is either
examined to see that it got translated to the intended assembly code, or is
tested so thoroughly as to be sure of it. Most programmers do not like to
program in this way: they aim to write code which, unless there are bugs in
the compiler, is supposed to compile to a correct program (and out of all
possible ways of writing it _which are guaranteed to produce correct code_,
they choose the one that is fastest, or smallest or satisfy some other
criterion.) They do not like code whose meaning changes when they substitute
a different `conforming' compiler (this term has a much more precise meaning
than a `conforming program': which I noted above is a useless term to most
people), or a different (probably enhanced) version of the compiler, or add a
print statement somewhere in the code. a^=b^=a^=b fails all these
considerations.
I believe that most people who use comp.lang.c as a resource want to know
what is guaranteed, not what works on their particular version of their
particular compiler. It is little help to most people that there existed a
compiler somewhere sometime which accepted the code and produced the expected
behaviour.
2) There is a large speed advantage gained by using this code.
As I said, most people want to know _when they are coding_ that a fragment of
code will do what they expect it to do: only after that do they care if it is
faster. It also remains true that in the case at hand (and in most clearly
written code), good compilers do not make any distinction between the two
codes.
Look at this: I tried the following code on my compiler here:
#include <stdio.h>
int main(void)
{int a, b;
scanf("%d %d", &a, &b);
a^=b^=a^=b;
printf("%d %d\n",a,b);
return 0;
}
The portion which does the swapping (and caling printf) compiles to the
assembly code (LC1 is the address of the printf format string)
ld [%fp-12],%o1
sethi %hi(LC1),%o0
ld [%fp-16],%o2
or %o0,%lo(LC1),%o0
xor %o1,%o2,%o1
st %o1,[%fp-12]
xor %o1,%o2,%o2
st %o2,[%fp-16]
xor %o2,%o1,%o1
call _printf,0
st %o1,[%fp-12]
When I replace a^=b^=a^=b; with the obvious `a^=b; b^=a; a^=b;' I get
ld [%fp-12],%o1
sethi %hi(LC1),%o0
ld [%fp-16],%o2
or %o0,%lo(LC1),%o0
xor %o1,%o2,%o1
st %o1,[%fp-12]
xor %o2,%o1,%o2
st %o2,[%fp-16]
xor %o1,%o2,%o1
call _printf,0
st %o1,[%fp-12]
Which is identical in content.
(For those who want to know about why compilers do certain things (though
that is not proper discussion in comp.lang.c): why doesn't my compiler
eliminate the stores? I guess the reason is that it refrains from making
assumptions about the library routines: god knows why. It sees that a and b
addresses are being taken, and passed out of the routine (to scanf), and
_may_ have been stored in some global variable somewhere: so
before calling any other routine (e.g. printf), it has to implement the
sequence point by updating the _stored_ values of a and b. Why did it not
eliminate the first dead store into a? I have not the foggiest idea: maybe
some gcc developer will tell me someday if I have misanalyzed the problem.
So, to eliminate the stores, do as follows (this essentially allows c and d
to be `register variables')
...
{int a, b, c, d;
scanf("%d %d", &c, &d);
a = c; b = d;
a^=b^=a^=b;
...
Of course, making it correct by changing the line a^=b^=a^=b doesn't affect
anything whatsoever in this context at this optimization level on this
compiler!).
Lawrence Kirby
>P.S. Anybody got a clean dictionary? Mine's smudged between
>"Saratoga" and "sarcoma," and I can't read the word there.
sarcelle: Teal or similar duck.
(of the choices available I liked this one the best! :-) )
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Lawrence Kirby
sch...@zonker.cs.ucsb.edu "Steve E. Chapel" writes:
>I would have no hestitation it writing a^=b^=a^=b in my code under the
>following conditions:
> 1) It needs to work with only one compiler
> 2) There is a large speed advantage gained by using this code
>
>I don't even care if it's non-portable, or "illegal". As long as it
>does what we what it to do, in my opinion it's good code.
I agree. However you are forgetting that this is comp.lang.c which is
for discussing ANSI or generally portable code. What happens on your
particular compiler is not relevant here (unless you trying to determine
whether your compiler is working correctly or not). All that can be said
here about a^=b^=a^=b is that it has undefined behaviour. If you were
posting to a newsgroup relevant to your *particular* compiler the answer
may be different.
Steve E. Chapel
>In article <Pine.SUN.3.91.950908003725.7231A-100000@zonker>,
>Steve E. Chapel <schapel@zonker> wrote:
>>Here is the relavent portion of the FAQ:
>>10.3: How can I write a generic macro to swap two values?
>[snip]
>>As you can see, it has to do with MACROS - the original question did
>>not involve macros.
>*sigh*. I suppose that, since the FAQ named the vars a and b, you
>think that it would be legal were they named c and d?
>Did you *read* the question it said to look at? And the answer to it?
I thought I might have to explain why I thought it only had to do
with macros. In a macro such as:
#define swap(a, b) { int temp = a; a = b; b = temp; }
and you use it like this:
swap(c[i++], d[j++])
The macro will not work because of multiple side effects.
To see why, the macro expands to this:
{ int temp = c[i++]; c[i++] = d[j++]; d[j++] = temp; }
So the above macro to swap two values, which at first looks like
portable, well-defined code, will fail in some circumstances.
I thought this was what the FAQ was referring to when it talked about
the "multiple side effects" of a^=b^=a^=b in a macro.
Normally, I wouldn't have misunderstood, but I had just recently
written that this is one reason that a^=b^=a^=b might not work:
if it is in a macro and the macro is called with expressions that
cause side effects. I guess this predisposed me to think that this
was what the FAQ was saying. Of course now I see you are correct.
>IF YOU MODIFY THE SAME LVALUE TWICE BETWEEN SEQUENCE POINTS, OR REFER TO IT
>AND MODIFY IT BETWEEN SEQUENCE POINTS[1], THE BEHAVIOR IS UNDEFINED.
>[1] Unless that reference is solely to determine the new value, i.e.,
>i = i + 1.
>Now, which part do you not understand? The expression "a^=b^=a^=b"
>is undefined. It is *because* this expression, *IN ANY CONTEXT
>WHATSOEVER* is undefined, that a macro using it is undefined.
>Once again, it is *meaningless*. It only means "swap a and b" *if* you assume
>that all evaluation is left to right. It isn't.
I understand perfectly now. I never said that it wasn't undefined.
In my second post, I merely pointed out that I didn't understand
why it was undefined. Perhaps I should have referred to the FAQ,
but I was not asking a question or responding to one. I don't make
it a habit to memorize the FAQ of every newsgroup I post to, or to
refer to the FAQ every time I post. Is this what you expect me to do?
>*Please* try to think this through; would you really expect that several
>experienced C programmers, many of whom are writing or have written books on
>C, and who have checked their assertions with the ANSI committee, and who have
>used *dozens* of compilers, would *all* be wrong? Of course you would; this
>happens. But it's just as true that *you* are wrong some of the time. This
>is one of those times.
I never said that the result of a^=b^=a^=b was not undefined.
Try to calm down and not get so emotional when you post, because
you start making all kinds of simple mistakes, such as misquoting
people. In my opinion, it is this haste to post in an upset
emotional state that creates these long, torturuous threads.
billy the kid
>Honestly, would you choose a clearly-written routine in time critical
>code that does not meet the performance specifications you have been given
>over an obscurely-written piece of code that meets specs? Surely
>efficiency is another issue to be considered.
That is true, but you don't know if a clearly-written piece of code will
perform worse than an obscurely-written one, until you test it. Until
you are able to make a test to see if the clearly-written one is good
enough or not, it is better to stick with clearly-written code. Assumptions
about what is "faster" or "slower" are meaningless without a profiler to
tell you. I know people who will swear up and down that "i += 4" is faster
than "i = i + 4" or that "i <<= 4" is faster than "i *= 16", without bothering
to test to make sure. I know of CPU's where shift and multiplication take the
same amount of time, and I also know of compilers that will optimize "i *= 16"
into "i <<= 4" at compile time. So, until you test, all assumptions about
speed are irrelavent.
billy the kid
>that a short is the same size as two chars, and that the MSB of a short
>is stored in the lower address. According to your definition of "works"
>my code doesn't work.
But my modem, which expects that the MSB is stored at the higher address
(blech! :-) would choke. You are mis-interpreting the meaning of "does not
work". It when someone says something doesn't work in programming, (s)he
probably means that you can't plug that code in to a random program, and
expect the same result every time. Yesterday, code that made assumptions
about what order bytes are stored was generally acceptable, today, I'd say
that it is not, except for unusual circumstances (i.e. a program to produce
a lookup table for an embeded processor).
>I sure my boss would be quite amused to hear you say that my code doesn't
>work. (And don't tell the modem - it might start spewing garbage in spite!:-)
The code works in your situation, there is no guarantee it would work in
mine, (or anyone elses), therefore, the code might work, but until you are
reasonably sure it works for every circumstance, it doesn't. It might not
make any difference to you if it does or not (and it might be an
unjustafiable expense), but please don't say that it works in every sense of
the word, at least until you are reasonably sure that it does.
I bet if you were writing a program to work on a 68060 and an Pentium, you
boss wouldn't be happy with code that made assumptions about which order
the bytes are in a multi-byte object.
Steve Summit
(Steve E. Chapel) writes:
> I disagree with you here. I wrote a fast table-driven CRC routine last week
> and when I showed it to my boss he was quite pleased. We compiled the
> routine and programmed a modem's EPROM with the compied code, and the
> modem appeared to function perfectly in every way. I would have to say
>
> However, the code I wrote for that routine makes several assumptions:
> that a short is the same size as two chars, and that the MSB of a short
> is stored in the lower address. According to your definition of "works"
> my code doesn't work.
Time to haul down an old classic: The Psychology of Computer
Programming, by Gerald M. Weinberg (Van Nostrand Reinhold, 1971,
ISBN 0-442-29264-3; I believe a paperback or second edition has
recently been released).
(But first, Steve, let me say that I'm not trying to pick on you.
You've stepped up to the plate in a very old argument, and the
team you're batting for has ample representation and is not Wrong
in any strict logical sense. I, however, play for the other
team, and we're on defense.)
Anyway, here's what Weinberg has to say on pages 21-22, in
chapter 2, "What makes a good program?", talking about efficiency
and adaptability.
For a program to be efficient, it must take advantage of
the peculiarities of the problem and the machine on which
it is to be run. Programs that ignore the structure of
the machine do so at the risk of incurring heavy cost
penalties, and programmers who can exploit special
situations in a problem are the ones who can speed things
up and make them smaller. One peculiar example, not
entirely untypical, of this type of programming was an
assembly program that employed a special technique for
looking up operation codes to be translated. The
programmer had observed -- or figured out -- that there
was one number which, when used to multiply the operation
code bit pattern interpreted as numeric, yielded an
almost solid and completely unduplicated set of addresses.
Using this multiplier, he was able to effect a compact
and equally fast transformation from symbolic codes to
machine language.
The programmer was much congratulated for this ingenuity
-- the example was displayed to several generations of
programmers as a prototype of the kind of work they
should be doing. Sadly, however, this section of code
did not have a very long life, for, as so frequently
happens, the operation code repertoire of the machine was
expanded. When a dozen or so codes had been added to the
set, the old multiplier no longer had the same desirable
properties of compactness and uniqueness. In fact, no
multiplier could be found that would work in this way for
the new codes.
The outcome of attempts to find a new multiplier was to
abandon this special technique for a more general hash
table search -- one that allowed for the existence of
duplicates. Unhappily, the old technique was not
abandoned before a great deal of effort had been expended
on the attempt to adapt it to the changed circumstances.
This proved to be time wasted. In retrospect, the
savings in time of the specialized technique never paid
in its lifetime for the extra cost of fooling around when
the new codes were added. If a general hash table method
had been used in the first place, somewhat lower
efficiency would have been the result; but -- and this is
the "but" that makes the example -- the modification
would have been entirely trivial. In fact, essentially
no modification would have been required except the
addition of the new codes to the appropriate places in
the table.
This example could be supplemented with hundreds of
others, but the point would be the same. When we ask for
efficiency, we are often asking for "tight" coding that
will be difficult to modify. In terms of higher-level
languages, we often descend to the machine-language level
to make a program more efficient. This loses at least
one of the benefits of having the program in the
higher-level language -- that of transportability between
machines. In fact, it has the effect of freezing us to a
machine or implementation that we have admitted by our
very act is unsatisfactory.
However, the same managers who scream for efficiency are
the ones who tear their hair out when told the cost of
modifications. Conversely, the managers who ask for
generalized and easily modified programs are wont to
complain when they find out how slow and spacious these
programs turn out to be. We must be adult about such
matters: neither psychology nor magic is going to help us
to achieve contradictory goals simultaneously.
[Gerald R Weinberg, The Psychology of Computer
Programming, pp. 21-2.]
Nathan Sidwell
: tan...@qcd.lanl.gov (Tanmoy Bhattacharya) writes:
: >It is you who has misunderstood the original statement. `It does not work'
: >talking of a program construct does _not_ mean that it works under no
: >circumstance. It simply means that the construct either has the unintended
: >effect, or is meaningless drivel. The second is the case here, a^=b^=a^=b; is
: >absolutely meaningless as a C language construct.
: I disagree with you here. I wrote a fast table-driven CRC routine last week
: and when I showed it to my boss he was quite pleased. We compiled the
: routine and programmed a modem's EPROM with the compied code, and the
: modem appeared to function perfectly in every way. I would have to say
: that the code "works" in every sense of the word.
: However, the code I wrote for that routine makes several assumptions:
: that a short is the same size as two chars, and that the MSB of a short
: is stored in the lower address. According to your definition of "works"
: my code doesn't work.
Tanmoy, said
defined the problem to come with a specified set of assumption, If the
assumptions are violated, it doesn't work.
Your CRC routine works when the assumptions (sizeof(short)==2, bigendian
machine) are not violated. In your case that's correct so your algorithm
works. BUT your algorithm is one which calculates CRC for big endian
machines with 2 bye shorts. It is not one which calculates CRC on
all machines.
the original problam (a ^= b ^=a ^= b) _claimed_ to be a swap routine
for C. This it is not, there fore it doesn't work. If it claimed to
be a swap routine for ints on Steve's compiler with no optimizations,
then you could claim it worked, but it works for a pretty small
problem domain (ie not useful).
Secondly. No one has yet demonstrated a machine (architecture and
compiler combination) where the correct XOR swap trick results in
faster code than the more obvious use a temporary algorithm. The
XOR trick is faster on small register starved machines where you
want to swap the values in two registers and you don't have a spare
one. I first came across this programming Z80's in _ASSEMBLER_.
So I'll make an assertion (for which I offer no proof)
'There is no modern architecture where swapping by XOR can produce
faster code than swapping by using a temporary.'
Now actually I _can_ think of a pathelogical case where this is
incorrect but can you?
So I'll make the slightly weaker assertion,
'For modern architectures swap XOR trick nearly always results in
code which is no faster than using a temporary, and often results in
slower code.'
By modern architecture I mean anything released after 1980 but including
68K and i86 I don't include DSPs as they can be strange, and I bet
there's a counter example there.
nathan
--
Nathan Sidwell Holder of the Xmris home page
Chameleon Architecture Group at SGS-Thomson, formerly Inmos
http://www.pact.srf.ac.uk/~nathan/ Tel 0117 9707182
nat...@inmos.co.uk or nat...@bristol.st.com or nat...@pact.srf.ac.uk
John Woods
>>It is you who has misunderstood the original statement. `It does not work'
>>talking of a program construct does _not_ mean that it works under no
>>circumstance. It simply means that the construct either has the unintended
>>effect, or is meaningless drivel. The second is the case here, a^=b^=a^=b; is
>>absolutely meaningless as a C language construct.
>and when I showed it to my boss he was quite pleased. We compiled the
>routine and programmed a modem's EPROM with the compied code, and the
>modem appeared to function perfectly in every way. I would have to say
>that the code "works" in every sense of the word.
>However, the code I wrote for that routine makes several assumptions:
>that a short is the same size as two chars, and that the MSB of a short
>is stored in the lower address. According to your definition of "works"
>my code doesn't work.
Of course, if the company you work for comes out with a new, more powerful
modem that uses a different CPU, someone is going to need to remember to go
through and change this oh-so-carefully written nonsense. (And if this is
the same code you added "a^=b^=a^=b" to, disaster is as close as the next
upgrade to the compiler.) Or perhaps this company doesn't believe in
improving performance?
Could you possibly let us know which modem this is, so we may all avoid your
shoddy workmanship? (Especially since your boss is apparently likely to hire
someone equally inattentive when you leave.)
Michael Hartwig
sch...@zonker.cs.ucsb.edu (Steve E. Chapel) writes:
>j...@proteon.com (John Woods) writes:
[snip]
>>"Sometimes" doesn't cut it in the real world. Running at doors full tilt
>>and smashing your face into them "sometimes" opens them, but for some odd
>>reason you just don't see this practiced very often.
>>God help your first employer.
>Hmmm. My current boss seems quite happy with my work. In case you missed
>it I wrote little anecdote about some code that I wrote that works with
>one of our compilers and does not work with another of our compilers. I've
>showed that code to my boss and he is very happy with it, because it's very
>efficient. He doesn't care if it's non-portable. It only has to work with
>our embedded systems compiler. It seems like you're trying to say that
>code that is not 100% portable is always bad code, but me and my boss
>disagree with you.
IFF your current boss is an expert C programmer, his opinion might be useful
for this. I don't know (or care) if he is or not, but I've NEVER worked for
such an expert, so I don't tend to ask my managers' opinion about my coding
practices. My point: citing your manager's happiness with this kind of code
is irrelevant: you might as well cite your dog||cat||iguana as being happy with
your code.
>I have no qualms about writing non-portable code if there is an advantage
>to be gained from it. In my opinion, portability is just one issue out
>of many that must be considered to determine whether code is "good" or
>"bad". Other issues include maintainability, correctness, and efficiency.
Unfortunately, if your compiler ever changes (version, different company,
different compilation options), you've blown away maintainablility &
correctness. So now, out of 4 "goodness" issues, you've got 1 left:
efficiency. Even if you clearly comment the code with the conditions under
which it works, you've still created a maintainablility problem.
>I would have no hestitation it writing a^=b^=a^=b in my code under the
>following conditions:
> 1) It needs to work with only one compiler
> 2) There is a large speed advantage gained by using this code
1) How do you know? You have a crystal ball?
2) Your profiled EVERY POSSIBLE combination, including hand-written assembly
code? If you took all that time just to avoid {temp = a; a = b; b = temp;}
then I wonder how you ever finish any program.
>I don't even care if it's non-portable, or "illegal". As long as it
>does what we what it to do, in my opinion it's good code.
I repeat, with minor modification: God help your coworkers who have to modify
your code.
--
Michael Hartwig Loral Federal Systems - Owego, NY
har...@lfs.loral.com
John Woods
>>And, programming is not about cute tricks: it is about expressing what you
>>mean clearly.
>Honestly, would you choose a clearly-written routine in time critical
>code that does not meet the performance specifications you have been given
>over an obscurely-written piece of code that meets specs?
I would choose clearly-written assembler code for a time-critical routine,
frankly, over an obscurely-written piece of crap that will not work if the
compiler changes. Perhaps your boss should consider hiring someone who
knows how to use more than one tool well instead of someone who only knows
how to use one tool poorly?
Rich Miller
>
>>And, programming is not about cute tricks: it is about expressing what you
>>mean clearly.
>
>I disagree. Code clarity is only one of many programming issues.
>Honestly, would you choose a clearly-written routine in time critical
>code that does not meet the performance specifications you have been given
>efficiency is another issue to be considered.
It is rare indeed to find a piece of code that needs to be written
obscurely in order to meet performance specifications. And if (as
happens so often) the code needs to be modified, e.g. to fix a bug or
two, add a feature, or change an algorithm, the maintenance work is
greatly facilitated by having clearly-written code. Especially after
maintenance changes, obscurely-written code is more likely to have bugs.
Far too much attention is, IMHO, paid to "efficiency" tuning (at the
expense of clarity! :-) in low-level (and in this case, incorrect!)
code constructs like
a ^= b ^= a ^= b;
rather than concentrating on producing clear, correct code, and using
a profiler *when the code is finished* to locate and fix any areas that
are too slow.
-- Rich Miller (rmi...@wolfenet.com)
ron house
>In article <42qma8$a...@zonker.cs.ucsb.edu>
> sch...@zonker.cs.ucsb.edu "Steve E. Chapel" writes:
>>I would have no hestitation it writing a^=b^=a^=b in my code under the
>>following conditions:
>> 1) It needs to work with only one compiler
>> 2) There is a large speed advantage gained by using this code
>>
>>I don't even care if it's non-portable, or "illegal". As long as it
>>does what we what it to do, in my opinion it's good code.
>I agree.
I don't. You might get another version of this same compiler tomorrow
and suddenly find that hundreds of non-conforming hacks in your code
(because if you're dumb enough to do it once, you'll do it many times)
suddenly malfunction and you have the devil's job tracking them down
because they all depend on strange low-level properties. Or maybe,
unknown to you, your _EXACT SAME_ compiler might produce different,
non-functional code if some compiler switch is set differently. Maybe
the exact settings of all the compiler switches is needed to make it work.
(I see visions of you pounding away for hours trying to rediscover the
magic combination that gets your programs up and running.)
In short, what you propose is somewhat akin to making a building out
of substandard materials. Might work for a while, but some day the
whole lot caves in.
And finally, there almost never _is_ a "large speed advantage". In one
of my more stupid moments, I once rewrote a program to remove all fn
calls, put in numerous combined ops instead of my usual one-at-a-time
policy (but even then I didn't do nonstandard ones). And guesss what.
After all that, I couldn't measure the difference in speed.
--
Ron House. USQ | A nonviolent diet is the
(ho...@usq.edu.au) Toowoomba, Australia. | foundation for a nonviolent world.
Steve Summit
"Steve E. Chapel" <schapel@zonker> writes:
> Here is the relavent portion of the FAQ:
> As you can see, it has to do with MACROS - the original question did
> not involve macros.
Indeed. I've realized that since abusing the XOR trick is as
popular a sport as trying to write swap macros, I shall have to
add an explicit question about a^=b^=a^=b to the expressions
section, near the questions about i=i++ et al.
Steve Summit
s...@eskimo.com
Steve Summit
who therefore see it twice].
Someone whose name doesn't need to be dragged around any further wrote:
> I don't even care if it's non-portable, or "illegal". As long as it
> does what we what it to do, in my opinion it's good code.
This is an extremely popular, perhaps a majority, opinion. For
those of us who do not share it, though, it's always distressing
to see it expressed (especially so concisely), because we've seen
far too much truly bad code written in its wake. In particular,
such code either (a) did not even work perfectly in the first
place; or (b) was not significantly faster (or was actually
slower) than more portable code could have been; or (c) was
significantly harder for anyone (even the original author) to
understand or modify later; or, most importantly, (d) was not
restricted to that one compiler after all, i.e., it came to pass
that it had to be compiled under a different one, where it didn't
work; or (e) two or more or all of the above.
When some lovely little nonportable code truly is more efficient,
and when you're "absolutely sure" that it won't ever have to be
ported to a different compiler, processor, or operating system,
it's indeed tempting to use it. If you decide to, though, you
(and your boss) must realize that IF your assumption is wrong and
it ever does have to be compiled under any other compiler, after
all (even a later release of the one you're using now), it may
then fail. Furthermore, if for that or any other reason you find
yourself having to rewrite it later, it will cost you much more
time and effort than it would now, because you won't have all the
issues fresh in your mind. (It's also worth noting that the
eventual failure, under a later compiler or other changed
circumstance, may not always be discovered until after it has
caused significant damage.)
> ...In my opinion, portability is just one issue out
> of many that must be considered to determine whether code is "good" or
> "bad". Other issues include maintainability, correctness, and efficiency.
Indeed. Maintainability and correctness, in particular, are
rarely assigned enough importance.
Steve Summit
s...@eskimo.com
The Amorphous Mass
> I disagree with you here. I wrote a fast table-driven CRC routine last week
> and when I showed it to my boss he was quite pleased. We compiled the
> routine and programmed a modem's EPROM with the compied code, and the
> modem appeared to function perfectly in every way. I would have to say
> that the code "works" in every sense of the word.
Especially with the caveats I snipped below, it does *not* work in any
_portable_ way (and that is a significant way for code to "work!"). My
compiler (THINK C 5.0) sets short = 8 bits, and returns an arbitrary
value when confronted with a^=b^=a^=b, so don't ever try porting that
code to a Mac. On UNIX, gcc responds to #pragma directives (whose
parameters and behavior are implementation-defined) by launching the
video game rogue, so lord only knows what it does when confronted with
*UN*defined behavior.
> I sure my boss would be quite amused to hear you say that my code doesn't
> work. (And don't tell the modem - it might start spewing garbage in spite!:-)
If the student maintaining your code a year from now has to recompile
it your boss might not be amused. There is no reason to build your
castles on sand.
Brandon Wallace
=> In article <42hnm4$4...@newshost.lanl.gov>, tan...@qcd.lanl.gov (Tanmoy Bhattacharya) writes
=> : ....
=> : And, programming is not about cute tricks:
=> : it is about expressing what you mean clearly.
=>
=> hal...@caip.rutgers.edu wrote:
=> >No, that is technical writing, and historie- and news-writing.
=>
=> In article <1995Sep6.2...@llyene.jpl.nasa.gov>, k...@emoryi.jpl.nasa.gov (Kevin D. Quitt) writes:
=> > So you write ambiguous code?
=>
=> That is impossible, unless it is sumthing that the compiler together with
=> the system that the compiler runs on and the system that the program runs
=> all relevant implementors call undefind. Such behavior is quite rare.
Nonsense. The compiler may decide to do anything:
1) It may do what you probably want:
a ^= b;
b ^= a;
a ^= b;
2) It may put the values of a & b into registers:
r1 = a;
r2 = b;
a ^= r2;
b ^= r1;
a ^= r2;
3) It may do something else
Neither of those depend on what the system that the compiler runs on or
the system that the program runs on.
--
Brandon Wallace
Nicholas | Applegate Capital Management
mailto:bm...@criterion.com http://www.criterion.com/home-pages/brandon
"I live life face down in the fast lane."
Nathan Sidwell
: Look at this: I tried the following code on my compiler here:
: #include <stdio.h>
: int main(void)
: {int a, b;
: scanf("%d %d", &a, &b);
: a^=b^=a^=b;
: printf("%d %d\n",a,b);
: return 0;
: }
[elided]
: So, to eliminate the stores, do as follows (this essentially allows c and d
: to be `register variables')
: ...
: {int a, b, c, d;
: scanf("%d %d", &c, &d);
: a = c; b = d;
: a^=b^=a^=b;
: ...
: Of course, making it correct by changing the line a^=b^=a^=b doesn't affect
: anything whatsoever in this context at this optimization level on this
: compiler!).
Just to refer back to one of my posts about speed. Tanmoy will discover
that if he swapped by a temporary, then _NO_ instructions will be used,
as the compiler will just rename the live values of a and b.
Similarly for the version which loads and stores to memory, the xors
disappear and some memory operations go away too, leading
to better scheduled code.
Lawrence Kirby
>Lawrence Kirby <fr...@genesis.demon.co.uk> writes:
>
>>In article <42qma8$a...@zonker.cs.ucsb.edu>
>> sch...@zonker.cs.ucsb.edu "Steve E. Chapel" writes:
>
>>>I would have no hestitation it writing a^=b^=a^=b in my code under the
>>>following conditions:
>>> 1) It needs to work with only one compiler
>>> 2) There is a large speed advantage gained by using this code
>>>
>>>I don't even care if it's non-portable, or "illegal". As long as it
>>>does what we what it to do, in my opinion it's good code.
>
>>I agree.
>
>I don't. You might get another version of this same compiler tomorrow
>and suddenly find that hundreds of non-conforming hacks in your code
I guess the great majority of programs written are not strictly
conforming and hence are non-portable. There is nothing wrong with this
(except where a perfectly good portable alternative is available).
I would argue that the code is good in the framework of the stated
conditions if it meets them (that's what I agree to). The point however
is that the conditions themselves need to be examined carefully.
1) this can never really be certain. Say a major bug was found in the
compiler which meant it needed to be changed or at least upgraded.
All undefined constructs would need to be rechecked. Good coding
practice could encompass such constructs if they were deemed necessary,
clearly documented and reliably tracable in the code.
2) This is very unlikely. With decent optimisers that there are around
now the most efficient code is often the clearest. Where the intent
is clear to the reader it is often clearer to the compiler. Code
whose behaviour is undefined will be unclear for both. The only sure
way of verifying the behaviour of a particular compilation of undefined
code it to analyse the machine code/assembly it generates. You might
as well have written it in assembler in the first place.
So, as I say, if the code meets the conditions required it is good. However
the chances of it doing that are rather insignificant in this case. The
advisability of the conditions themselves can also be questioned. Condition
1 is not appropriate to comp.lang.c in particular or good programming
practice in general.
hgu...@freenet.vcu.edu
>t I heard someone say it doesn't.
It is a waste of time trying to figure out what this expression
does, because the behavior is undefined.
--
Harold Guller
hgu...@freenet.vcu.edu
Kevin D. Quitt
>On UNIX, gcc responds to #pragma directives (whose
>parameters and behavior are implementation-defined) by launching the
>video game rogue,
I agree with your sentiment, but gcc now has come pragmas, so the directive
itself is insufficient to launch rogue (nethack on my machine).
> so lord only knows what it does when confronted with
>*UN*defined behavior.
An unfamiliar pragma *does* cause undefined behaviour.
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91351-4454 96.37% of all statistics are made up
David Franklin
: following conditions:
: 1) It needs to work with only one compiler
: 2) There is a large speed advantage gained by using this code
Possibly a stupid question, but under what circumstances could you expect
a^=b^=a^=b; to run faster than {a^=b;b^=a;a^=b;} ?
Dave
Peter Seebach
David Franklin <kao...@tdc.dircon.co.uk> wrote:
>Possibly a stupid question, but under what circumstances could you expect
>a^=b^=a^=b; to run faster than {a^=b;b^=a;a^=b;} ?
A good optimizing compiler will elimitate the dead store to a, and
produce
b^=a;
a^=b;
... saving an xor and assignment.
-s
--
Peter Seebach - se...@solon.com || se...@intran.xerox.com --
C/Unix proto-wizard -- C/Unix questions? Send mail for help. No, really!
Copyright 1995 Peter Seebach. Like my work? Send donations!
The *other* C FAQ - ftp taniemarie.solon.com /pub/c/afq
Frank Hofmann
void main (void)
{
int a, b;
a = 123; b = 7654;
printf ("a = %d, b = %d\n", a, b);
a^=b^=a^=b;
printf ("a = %d, b = %d\n", a, b);
}
I've tested this on a variety of systems: HP/UX using HP cc / gcc with various
optimization settings, DEC/OSF 1 on Alpha AXP using DEC cc / gcc with various
optimitzation settings, IRIX 5.2 on SGI PowerChallenge using SGI cc / gcc with
various optimization settings, Linux 1.2.13/1.3.31 using gcc with various
optimization settings (The last one on i486, AMD486, Pentium with/out FPU bug)
I've not found another machine to try so far, but please feel free to do so -
No matter what compiler or what compiler version, optimization level,
operating system or processor architecture I've tried, it *worked*.
Of course, you might say - this is too primitive. But as all these compilers
do what the original poster said this code would do, I suspect there's some
logic behind all this.
Don't forget: All these machines have
- different compilers
- different bit/byte order
- different processor architectures
- different sizeof (int)
so it can't be that dependent on implementation details if it still works with
all of these.
Please post reports of machines/compilers which don't make the above code
print the following:
a = 123, b = 7654
a = 7654, b = 123
I'm really curious now.
Frank
Tanmoy Bhattacharya
cip...@wpax01.physik.uni-wuerzburg.de (Frank Hofmann) writes:
|> I found this thread very interesting so far. That's why I've tried it
myself:
|>
|> void main (void)
|> {
|> int a, b;
|>
|> a = 123; b = 7654;
|> printf ("a = %d, b = %d\n", a, b);
|> a^=b^=a^=b;
|> printf ("a = %d, b = %d\n", a, b);
|> }
|> I've not found another machine to try so far, but please feel free to do
so -
|> No matter what compiler or what compiler version, optimization level,
|> operating system or processor architecture I've tried, it *worked*.
|> do what the original poster said this code would do, I suspect there's some
|> logic behind all this.
Certainly there is some logic behind all this ... As any rationalist will
tell you, things don't happen without a reason. The point that people were
trying to make is that the reason happens to be something other than the fact
that the compilers were designed to do so.
When writing a compiler, the programmer tries to satisfy certain goals.
Typical among these (in the usual order of importance to most people)
1) It must have a mode to compile _all_ correct programs correctly.
2) It must have a mode to diagnose _all_ errors that the standard specifies
as _needing_ a diagnostic.
3) It must have a mode to support common extensions of the language.
4) It must have a mode to optimize most correct programs as far as possible.
5) It must have a mode to generate useful hints to the programmer about
questionable programming practices.
Only (1) and (2) are required by the standard of a C compiler.
Notice that it is usually _not_ a terribly important goal to make every wrong
program fail: in fact, such a goal cannot be satisfied in even a turing
machine. What remains true however is that if you do not follow the rules,
compiling your program correctly is not a goal of the compiler writer, and if
it is met, it is met only by accident.
Take your example: it violates the rules in three places: let us treat them
one at a time.
1) You declare main as returning void instead of int. Most implementations
today run on machines that have fast registers (this by the way is not
necessary at all: a totally stack based machine is certainly possible) and
function return values are returned in registers if they are elementary
types like int (this is not necessary either. Most compilers today do not
return structs for example in registers: here passing the address of the
struct in a register is more common -- I have heard that the obviously
more clever tricks may or may not violate patents. There is no reason why
ints cannot be passed back in the same way, except that on most machines
today it will violate goal 4 listed above.), and all bit patterns make
sense as an int (again this is not necessary: a one's complement machine
can decide that the bit pattern `all ones' in an int is to abort the
code.) So, now, when `void main' is compiled, the compiler does not set
the return register to anything: and the C startup code that calls main
uses this un-setup register as an int: and calls exit with it. You can see
that any of the scenarios listed above (totally stack based machine,
address of int instead of the int in a register, or possiblity of invalid
bit patterns) and possibly many others would have created trouble. None of
the compilers you tried it on however belonged to any of these scenarios:
so it `worked' (actually it didn't: the exit status was garbage.
Fortunately again, every value of the exit status is accepted by your exit
function: not a universal occurence either). That neither means it will
work on _every_ compiler, nor does it mean it will work on the common
compilers in the future.
2) You called printf without including <stdio.h>. On some machines it is
faster to call a function if the number of arguments are known beforehand
by both the caller and the callee. To take advantage of this, the standard
specifies that the caller can use the fast method _unless_ a prototype
explicitly shows that the function takes a varying number of arguments.
None of the compilers you tried make use of this (and also, K&R 1 C, which
allowed one to call printf without declaration is often treated as a
common extension): so it worked. As usual, you can draw your conclusions.
3) You modified the same variable twice between sequence points a^=b^=a^=b;
The prohibition against this is also to help compilers generate better
code. It is completely conceivable to write a compiler which will do
proper optimizations by interchanging the order of stores in your code on
machines where it matters. None of the compilers you used were that
agressive (or they were not on machines where such optimization would have
helped). This (i.e. the absence of advanced optimization techniques) is
the reason you were looking for.
Hope this helps
Dan Pop
>I found this thread very interesting so far. That's why I've tried it myself:
>
>void main (void)
>{
> int a, b;
>
> a = 123; b = 7654;
> printf ("a = %d, b = %d\n", a, b);
> a^=b^=a^=b;
> printf ("a = %d, b = %d\n", a, b);
>}
>
>
>I've tested this on a variety of systems: HP/UX using HP cc / gcc with various
>optimization settings, DEC/OSF 1 on Alpha AXP using DEC cc / gcc with various
>optimitzation settings, IRIX 5.2 on SGI PowerChallenge using SGI cc / gcc with
>various optimization settings, Linux 1.2.13/1.3.31 using gcc with various
>optimization settings (The last one on i486, AMD486, Pentium with/out FPU bug)
>I've not found another machine to try so far, but please feel free to do so -
>No matter what compiler or what compiler version, optimization level,
>operating system or processor architecture I've tried, it *worked*.
So what? This code invokes undefined behaviour in three different
ways: it declares main as void (you obviously couldn't be bothered to
read the FAQ before posting), it modifies an object twice between
sequence points (another version of i=i++) and it calls a variadic
function without a prototype in scope. The code is illegal and _any_
result is correct.
Whether all the known compilers produce the same results or not is
irrelevant as far as this newsgroup is concerned.
Dan
--
Dan Pop
CERN, CN Division
Email: Dan...@mail.cern.ch
Mail: CERN - PPE, Bat. 31 R-004, CH-1211 Geneve 23, Switzerland
Frank Hofmann
Tanmoy Bhattacharya (tan...@qcd.lanl.gov) wrote:
: In article <43k3bf$i...@winx03.informatik.uni-wuerzburg.de>,
: cip...@wpax01.physik.uni-wuerzburg.de (Frank Hofmann) writes:
: |> I found this thread very interesting so far. That's why I've tried it
: myself:
: |>
: |> void main (void)
: |> {
: |> int a, b;
: |>
: |> a = 123; b = 7654;
: |> printf ("a = %d, b = %d\n", a, b);
: |> a^=b^=a^=b;
: |> printf ("a = %d, b = %d\n", a, b);
[deleted]
: Take your example: it violates the rules in three places: let us treat them
: one at a time.
: 1) You declare main as returning void instead of int. Most implementations
[snip]
: 2) You called printf without including <stdio.h>. On some machines it is
[snip]
: 3) You modified the same variable twice between sequence points a^=b^=a^=b;
[snip]
: Hope this helps
: Cheers
: Tanmoy
To 1) and 2): Writing the program as
#include <stdio.h>
int main (void)
{
int a, b;
a = 123; b = 7654;
printf ("a = %d, b = %d\n", a, b);
a^=b^=a^=b;
printf ("a = %d, b = %d\n", a, b);
return 0;
}
does not change its behaviour on any of the tested systems. I know it
should be 'int main' and I know <stdio.h> is necessary before using
printf (), so please stop complaining on these two - it's not the point
here. Changing these two to the correct style still works.
So only the last point remains: Why does a^=b^=a^=b swap a and b ?
I'd like to know a system/compiler configuration where this does not work.
If the compilers I've tested are optimizing too 'less aggressive' for this
to fail, then show me a case where it fails.
I wonder why it works, as it's clearly against specifications (this I can
see myself), but it does, on a variety of systems.
Can someone do a test on more systems than those I've tested ? Would really
be interesting to find out which compilers reject this (i.e. which ones
generate code that doesn't swap a and b).
Bye.
Frank
John R MacMillan
|print the following:
|
| a = 123, b = 7654
| a = 7654, b = 123
|
|I'm really curious now.
As has already been pointed out, it doesn't really matter if no one
could find an implementation that did not give the above results, but
to satisfy your curiousity, the SCO Optimizing C compiler (icc) prints:
a = 123, b = 7654
a = 0, b = 123
Lawrence Kirby
cip...@wpax01.physik.uni-wuerzburg.de "Frank Hofmann" writes:
>I found this thread very interesting so far. That's why I've tried it myself:
>
>void main (void)
>{
> int a, b;
>
> a = 123; b = 7654;
> printf ("a = %d, b = %d\n", a, b);
> a^=b^=a^=b;
> printf ("a = %d, b = %d\n", a, b);
>}
>
>
>I've tested this on a variety of systems: HP/UX using HP cc / gcc with various
>optimization settings, DEC/OSF 1 on Alpha AXP using DEC cc / gcc with various
>optimitzation settings, IRIX 5.2 on SGI PowerChallenge using SGI cc / gcc with
>various optimization settings, Linux 1.2.13/1.3.31 using gcc with various
>optimization settings (The last one on i486, AMD486, Pentium with/out FPU bug)
>I've not found another machine to try so far, but please feel free to do so -
>No matter what compiler or what compiler version, optimization level,
>operating system or processor architecture I've tried, it *worked*.
This doesn't guarantee that it will continue to work with future compilers
that have better optimisers.
A more useful test would be to compare the code generated for a^=b^=a^=b;
against that for a^=b,b^=a,a^=b; and also against {int temp=a;a=b;b=temp;}
That might put this thread back into some perspective. Actually the
code this compiles to tends to trivially push constants as the arguments to
both printf's so you might improve it by, say, changing the initial
assignments to
a = rand(); b = rand();
to actually make it do something.
I suspect you'll find that the code for a^=b^=a^=b is (possibly equally)
least efficient or just plain wrong (in terms of the original requirement).
Martin Ambuhl
in <43mkjd$o...@winx03.informatik.uni-wuerzburg.de> writes:
[snip]
>#include <stdio.h>
>int main (void)
>{
> int a, b;
> a = 123; b = 7654;
> printf ("a = %d, b = %d\n", a, b);
> a^=b^=a^=b;
> printf ("a = %d, b = %d\n", a, b);
> return 0;
>}
[snip]
>So only the last point remains: Why does a^=b^=a^=b swap a and b ?
>I'd like to know a system/compiler configuration where this does not work.
>If the compilers I've tested are optimizing too 'less aggressive' for this
>to fail, then show me a case where it fails.
Maybe it _doesn't_ swap a and b, and you just think it does:
for djgpp/gcc -O1, -O2, or -O3 we get this code:
.file "tst.c"
gcc2_compiled.:
___gnu_compiled_c:
.text
LC0:
.ascii "a = %d, b = %d\12\0"
.align 2
.globl _main
_main:
pushl %ebp
movl %esp,%ebp
call ___main
pushl $7654
pushl $123
pushl $LC0
call _printf
pushl $123
pushl $7654
pushl $LC0
call _printf
xorl %eax,%eax
leave
ret
The only xor in sight is the one setting the return code.
It _seems_ to swap a and b because the compiler prints them in reverse
order. No xors, no swaps, not even an int variable to be seen. Just two
calls to printf() to output two int literals.
--
* Martin Ambuhl net: mam...@ripco.com
* Chicago, IL (USA)
Steve Summit
cip...@wpax01.physik.uni-wuerzburg.de (Frank Hofmann) writes:
> ...I know it
> should be 'int main' and I know <stdio.h> is necessary before using
> printf (), so please stop complaining on these two - it's not the point
> here.
Indeed. There is rather a bit too much carping on these points
here lately. (When you saunter into comp.lang.c with your trusty
followup key in hand and with the will to use it, your thought
should be: "How many people can I truly help today?", not
"How many void main() nits can I pick?".)
> So only the last point remains: Why does a^=b^=a^=b swap a and b ?
>...
> I wonder why it works, as it's clearly against specifications (this I can
> see myself), but it does, on a variety of systems.
The extended remix version of the comp.lang.c FAQ list (coming
soon to a bookstore near you) addresses this question, after a
fashion:
11.35: People keep saying that the behavior of i = i++ is undefined,
but I just tried it on an ANSI-conforming compiler, and got the
results I expected.
A: A compiler may do anything it likes when faced with undefined
behavior (and, within limits, with implementation-defined and
unspecified behavior), including doing what you expect. It's
unwise to depend on it, though.
Here is another way of looking at it, due to Roger Miller:
"Somebody told me that in basketball you can't
hold the ball and run. I got a basketball and
tried it and it worked just fine. He obviously
didn't understand basketball."
> Can someone do a test on more systems than those I've tested ? Would really
> be interesting to find out which compilers reject this (i.e. which ones
> generate code that doesn't swap a and b).
Someone posted one a day or two ago. (Perhaps you've seen it by
now, and perhaps the article of yours to which I'm replying is
older; the news feed in these parts has been particularly
turbulent of late.)
In any case (and I think this argument's been posted, too),
concrete examples aren't always the best way to prove these
things. The fact is that a ^= b ^= a ^= b is undefined; the
person who asks for an example of a machine for which it fails at
least *seems* to be claiming that if none are forthcoming it's
safe to assume that the code "works as expected." One hundred
examples of machines where it "works" do not prove the claim,
however, because it only takes one failing example (which has, in
fact, now been provided) to demolish it. (If Mark Brader happens
along, he can post one of his quotes which says something like,
"Sir, your composure baffles me. A single counterexample
invalidates your claim as certainly as ten.")
Steve Summit
s...@eskimo.com
Frederic STARK
>
> Tanmoy Bhattacharya (tan...@qcd.lanl.gov) wrote:
> : cip...@wpax01.physik.uni-wuerzburg.de (Frank Hofmann) writes:
> : |> I found this thread very interesting so far. That's why I've tried
it
> : myself:
> : |>
> : |> void main (void)
> : |> {
> : |> int a, b;
> : |>
> : |> a = 123; b = 7654;
> : |> printf ("a = %d, b = %d\n", a, b);
> : |> a^=b^=a^=b;
> : |> printf ("a = %d, b = %d\n", a, b);
> [deleted]
>
> : Take your example: it violates the rules in three places: let us treat
them
> : one at a time.
>
> I know it
> should be 'int main' and I know <stdio.h> is necessary before using
> printf (), so please stop complaining on these two - it's not the point
So why didn't you wrote it correctly the first time ?
> here. Changing these two to the correct style still works.
> So only the last point remains: Why does a^=b^=a^=b swap a and b ?
Why not ?
Why (rand()+rand())&1 is alway 1 on my system ?
> I'd like to know a system/compiler configuration where this does not
work.
> If the compilers I've tested are optimizing too 'less aggressive' for
this
> to fail, then show me a case where it fails.
>
> I wonder why it works, as it's clearly against specifications (this I
can
> see myself), but it does, on a variety of systems.
>
> Can someone do a test on more systems than those I've tested ? Would
really
> be interesting to find out which compilers reject this (i.e. which ones
> generate code that doesn't swap a and b).
Probably all the ones you tested, as all the compilers
should have optimized the code, so they dont 'generate code
that swap a and b', they 'generate code that print 123, 7654
and 7654, 123'...
The good answer to 'What compiler will generate bad code on
this input' could be 'The one you'll use next year to
compile the software you made this year...'
Cheers,
-- fred
-----------------------------------------------------------------
frederic stark -- fr...@improve.fdn.org
-----------------------------------------------------------------
The Amorphous Mass
> I found this thread very interesting so far. That's why I've tried it myself:
>
> void main (void)
> {
> int a, b;
>
> a = 123; b = 7654;
> printf ("a = %d, b = %d\n", a, b);
> a^=b^=a^=b;
> printf ("a = %d, b = %d\n", a, b);
> }
>
This code *crashes* my coworker's Toshiba laptop, not because of the ^=
bit, but because of the void main(void). We changed it to int main(void)
and it worked as you hope it works.
We were running under BC++ 4.5.
However, the fact that it works on every compiler on every platform
you can find means little. It works because the compilers are nice
enough to correctly guess what you want out of "a^=b^=a^=b," not because
it's correct or clear. The result of that expression is undefined; if
there are scads of compilers that guess the intended result, then there
are a lot of people getting away with sloppy programs.
As someone else has no doubt pointed out, the compiler is as free to
overwrite your hard drive as it is to swap the values of a and b in the
above program.
Just for the heck of it, I'll see what THINK C 5.0 makes of it.
Mike McCarty
Frank Hofmann <cip...@wpax01.physik.uni-wuerzburg.de> wrote:
[stuff cut]
)Of course, you might say - this is too primitive. But as all these compilers
)do what the original poster said this code would do, I suspect there's some
)logic behind all this.
)
)Don't forget: All these machines have
)
) - different compilers
) - different bit/byte order
) - different processor architectures
) - different sizeof (int)
)
)so it can't be that dependent on implementation details if it still works with
)all of these.
)
)Please post reports of machines/compilers which don't make the above code
)print the following:
)
) a = 123, b = 7654
) a = 7654, b = 123
)
)I'm really curious now.
)
)Frank
You remind me of one of my students back when I was teaching Calculus
over at the University of Texas at Dallas. He wanted me to dispense with
proofs. I asked him on what basis he would determine what actually could
be depended upon. He said "what works". I asked him how often. He said
he wasn't quite sure. So I asked him whether, if a formula worked 40
times in a row, he would decide that it worked. He said "yes". So I
tried this on him
2
N + 41N + 41
always generates primes. When N is 0, one gets 41, when N is 1, one gets
83, etc. This works 41 times up to N is 40. When N is 41, one does -not-
get a prime, as is obvious.
If the results are allowed to be implementation dependent, then they
=are= implementation dependent. There is no justification for the phrase
"that dependent". It either is, or it is not. Just like the formula.
Either it =always= generates primes, or there are circumstances in
which it might not.
Either the formula a ^= b ^= a =always= works, or there are
circumstances in which it might not.
No middle ground on this one. And no number of examples can prove otherwise.
Mike
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
I don't speak for DSC.
Mike McCarty
)|Please post reports of machines/compilers which don't make the above code
)|print the following:
)|
)| a = 123, b = 7654
)| a = 7654, b = 123
)|
)
)As has already been pointed out, it doesn't really matter if no one
)could find an implementation that did not give the above results, but
)to satisfy your curiousity, the SCO Optimizing C compiler (icc) prints:
)
)a = 123, b = 7654
)a = 0, b = 123
It sure doesn't. Because all there has to be is ONE (1) compiler which
generates code which does not do the exchange. And if one didn't exist,
it would very soon, because I could write it tonight, and would very
soon.
I already have source for a C compiler written in C, and all I have to
do is make it look for this construct and emit code to zero both
variables.
Kevin D. Quitt
>I already have source for a C compiler written in C, and all I have to
>do is make it look for this construct and emit code to zero both
>variables.
No! Set them both to 42. I think that should be the result for i=i++ as
well. In fact, it should be the result from *any* undefined code. (Unless,
of course, you really can make demons fly out his nose ;-)
Andre Charron temp123195
think of XOR as an addition operator. As such, you'll see this written as
a += b -= a = b - a
and remember order of precedence. + - left to right, higher than
=, += and -= which are right to left. Rewriting,
1) a = b-a
2) b = b-a = b - (b-a) = a => b = a
3) a = a+b = a + (b-a) = b => a = b
Here's a small C program to demonstrate:
#include <stdio.h>
/* Weird non-ANSI C compiler */
void NoTempSwap();
main()
{
int a, b;
a=1;
b=2;
printf("Before swap: a=%d b=%d \n", a,b);
NoTempSwap(&a, &b);
printf("After swap: a=%d b=%d \n", a,b);
}
void NoTempSwap(a, b)
int *a, *b;
{
*a = *b - *a;
*b = *b - *a;
*a = *a + *b;
}
Hope this helps.
Lawrence Kirby
tp00008 "Andre Charron temp123195" writes:
>void NoTempSwap(a, b)
>int *a, *b;
>{
> *a = *b - *a;
> *b = *b - *a;
> *a = *a + *b;
>}
>
>
>Hope this helps.
The problem with this is that it can result in signed integer overflow
the effects of which are implementation defined. You should also test
for the case where a == b. All of theis is academic since the version
using a temporary will be faster in most cases anyway.
Dan Pop
>In article <43vaa3$a...@theopolis.orl.mmc.com>
> tp00008 "Andre Charron temp123195" writes:
>
>>void NoTempSwap(a, b)
>>int *a, *b;
>>{
>> *a = *b - *a;
>> *b = *b - *a;
>> *a = *a + *b;
>>}
>>
>
>The problem with this is that it can result in signed integer overflow
>the effects of which are implementation defined.
It's even worse: undefined behaviour!
Mike McCarty
Andre Charron temp123195 <tp00008> wrote:
)Remember that adding two bits is performed using the XOR operation;
)think of XOR as an addition operator. As such, you'll see this written as
)
) a += b -= a = b - a
)
)and remember order of precedence. + - left to right, higher than
)=, += and -= which are right to left. Rewriting,
)
) 1) a = b-a
) 2) b = b-a = b - (b-a) = a => b = a
) 3) a = a+b = a + (b-a) = b => a = b
)
)Here's a small C program to demonstrate:
[cut]
Your program is not guaranteed to work. Precedence has nothing to do
with order of execution. This is an order of execution problem.