Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #145807 > unrolled thread

in place swap of float types

Back to article view | Back to comp.lang.c

Contents

  in place swap of float types 3queens@shabbyroad.com - 2019-08-27 17:03 +0000
    Re: in place swap of float types Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-08-27 19:22 +0000
      Re: in place swap of float types Andrew Smallshaw <andrews@sdf.org> - 2019-09-02 15:25 +0000
        Re: in place swap of float types Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-09-02 19:37 +0000
          Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-09-03 06:37 -0700
            Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-03 16:13 +0200
              Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-03 16:54 +0100
                Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-04 11:19 +0200
                  Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-09-04 02:35 -0700
                    Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-04 12:31 +0200
                  Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-04 12:12 +0100
                    Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-04 15:53 +0200
                      Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-09-04 07:17 -0700
                        Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-05 15:12 +0200
                          Re: in place swap of float types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-09-05 21:11 +0100
                      Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-04 16:30 +0100
                        Re: in place swap of float types jadill33@gmail.com - 2019-09-04 10:26 -0700
                        Re: in place swap of float types Ike Naar <ike@iceland.freeshell.org> - 2019-09-05 06:00 +0000
                          Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-05 11:14 +0100
                        Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-05 14:54 +0200
                          Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-05 15:48 +0100
                            Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-06 10:35 +0200
                              Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-09-06 02:52 -0700
                                Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-06 13:18 +0200
                              Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-06 12:14 +0100
                                Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-06 15:08 +0200
                                  Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-09-06 06:23 -0700
                      Re: in place swap of float types Keith Thompson <kst-u@mib.org> - 2019-09-04 14:16 -0700
                        Re: in place swap of float types Bart <bc@freeuk.com> - 2019-09-04 22:42 +0100
                        Re: in place swap of float types Keith Thompson <kst-u@mib.org> - 2019-09-04 15:21 -0700
                        Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-05 15:15 +0200
                Re: in place swap of float types Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-04 08:05 -0600
                  Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-05 15:17 +0200
                    Re: in place swap of float types Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-05 20:28 -0600
                      Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-06 10:39 +0200
                        Re: in place swap of float types Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-06 08:11 -0600
                          Re: in place swap of float types scott@slp53.sl.home (Scott Lurndal) - 2019-09-06 18:31 +0000
            Re: in place swap of float types Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-09-04 19:02 +0000
        Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-02 22:16 +0200
    Re: in place swap of float types Robert Wessel <robertwessel2@yahoo.com> - 2019-08-27 17:59 -0500
      Re: in place swap of float types Richard Damon <Richard@Damon-Family.org> - 2019-08-27 17:45 -0700
      Re: in place swap of float types James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-27 20:48 -0400
        Re: in place swap of float types Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-09-03 06:17 -0700
      Re: in place swap of float types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-28 02:09 +0100
      Re: in place swap of float types Siri Cruise <chine.bleu@yahoo.com> - 2019-08-27 21:26 -0700
      Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-08-28 09:22 +0200
      Re: in place swap of float types Andrey Tarasevich <andreytarasevich@hotmail.com> - 2019-08-28 16:36 -0700
    Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-08-28 09:36 +0200
      Re: in place swap of float types Bart <bc@freeuk.com> - 2019-08-28 12:02 +0100
        Re: in place swap of float types James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-28 05:08 -0700
          Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-08-28 05:26 -0700
          Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-08-28 14:40 +0200
          Re: in place swap of float types Keith Thompson <kst-u@mib.org> - 2019-08-28 13:01 -0700
      Re: in place swap of float types Philipp Klaus Krause <pkk@spth.de> - 2019-09-04 11:18 +0200
        Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-04 12:57 +0200
          Re: in place swap of float types Philipp Klaus Krause <pkk@spth.de> - 2019-09-04 13:24 +0200
    Re: in place swap of float types Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-05 08:18 +0200
      Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-05 15:19 +0200
        Re: in place swap of float types Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-05 16:18 +0200
          Re: in place swap of float types Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-09-05 07:32 -0700
            Re: in place swap of float types Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-05 17:32 +0200
            Re: in place swap of float types David Brown <david.brown@hesbynett.no> - 2019-09-06 10:54 +0200
              Re: in place swap of float types Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-06 14:23 +0200

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#145816

On 8/27/19 3:59 PM, Robert Wessel wrote:
> On Tue, 27 Aug 2019 17:03:38 -0000 (UTC), 3queens@shabbyroad.com
> wrote:
> 
>> Some time ago, there was a thread concerning using "a^=b; b^=a; a^=b" 
>> to do an in place swap of two variables of the same size.  It was
>> pointed out that this can only be done with integer types.  I found a
>> way to do it with floating point types as well.
>>
>> Declare a union with the floating point variable and an equally long
>> integer variable.  Then use the integer member to do the exclusive-or
>> process.
>>
>> Naturally, this would not be efficient if the data had to be copied into
>> and out of the union, but if the variables were defined as unions to
>> begin with, this would work.
>>
>> Maybe not that useful, but if space is really tight, perhaps useful in
>> some situations.
> 
> 
> AFAIK, this invokes undefined behavior.  You cannot reliably read from
> a different member of a union than was written to.
> 
The standard says:

If the member used to read the contents of a union object is not the
same as the member last used to store a value in the object, the
appropriate part of the object representation of the value is
reinterpreted as an object representation in the new type as described
in 6.2.6 (a process sometimes called “type punning”). This might be a
trap representation.

(Foot Note 97 to 6.5.2.3 p3)

So, to the extent that the representations are defined, the behavior is
defined. If the integral type is an unsigned type with no padding bits,
and thus no trap representation, and of size at least as big as the
other type, then there can be no undefined behavior.

Note also, that having the union of the floating point type and the
unsigned type in scope does mean that some optimizations based on the
non-aliasing of those types can't be done, as the presence of the union
warns that such aliasing might legitimately exist.

[toc] | [prev] | [next] | [standalone]

#145818

On 8/27/19 6:59 PM, Robert Wessel wrote:
> On Tue, 27 Aug 2019 17:03:38 -0000 (UTC), 3queens@shabbyroad.com
> wrote:
> 
>> Some time ago, there was a thread concerning using "a^=b; b^=a; a^=b" 
>> to do an in place swap of two variables of the same size.  It was
>> pointed out that this can only be done with integer types.  I found a
>> way to do it with floating point types as well.
>>
>> Declare a union with the floating point variable and an equally long
>> integer variable.  Then use the integer member to do the exclusive-or
>> process.
>>
>> Naturally, this would not be efficient if the data had to be copied into
>> and out of the union, but if the variables were defined as unions to
>> begin with, this would work.
>>
>> Maybe not that useful, but if space is really tight, perhaps useful in
>> some situations.
> 
> 
> AFAIK, this invokes undefined behavior.  You cannot reliably read from
> a different member of a union than was written to.
> 

The behavior of such code was never undefined. In C89, it was
implementation-defined. In C99, a footnote was added saying: "If the
member used to read the contents of a union object is not the same as
the member last used to store a value in the object, the appropriate
part of the object representation of the value is reinterpreted as an
object representation in the new type as described in 6.2.6 (a process
sometimes called ‘‘type punning’’). This might be a trap representation."

Footnotes are non-normative, and are intended to merely summarize and
make clear the meaning of normative text. I can't find any normative
text that clearly specifies that such reinterpretation takes place - the
committee apparently feels otherwise, and some people on this group have
claimed that it's an obvious consequence of the referenced section, 6.2.6.

Whether or not there's actual normative text backing up that footnote,
it definitely reflects the intent of the committee, as well as
describing the way that virtually every implementation of C has ever
actually handled unions, and the way that a very large fraction of C
programmers have always expected C unions to behave. Therefore, I think
it's quite safe to assume that this footnote is correct, even if there
is in fact no normative text that clearly supports it.

The representation of types is almost entirely implementation-defined -
in most cases, so code that relies on this footnote is inherently
non-portable. But if you read the relevant sections of an
implementation's documentation, you should be able to figure out
precisely which values of one type have representations that, if
reinterpreted as a different type, are also valid representations of
that type; you should also be able to determine which values they
represent in the new type.

However, the ^= trick should work in a union with an integer type of the
required size on most implementations. It won't work if the integer type
has padding bits. The standard allows each signed type to have one bit
pattern that is a trap representation (6.2.6.2p2), which would also
cause problems for such code.

The unsigned exact-width integer types (7.20.1.1) are guaranteed to have
neither of those features, and that is also likely to be the case for
almost all integer types on almost all implementations. But the concepts
of "padding bits" and trap representations weren't invented just for the
fun of it - there are real implementations that have those features.

[toc] | [prev] | [next] | [standalone]

#145923

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> On 8/27/19 6:59 PM, Robert Wessel wrote:
>
>>> [using unions to effect type punning]
>>
>> AFAIK, this invokes undefined behavior.  You cannot reliably read
>> from a different member of a union than was written to.
>
> The behavior of such code was never undefined.  In C89, it was
> implementation-defined.  In C99, a footnote was added

In a TC to C99.

> saying:  "If the member used to read the contents of a union
> object is not the same as the member last used to store a value in
> the object, the appropriate part of the object representation of
> the value is reinterpreted as an object representation in the new
> type as described in 6.2.6 (a process sometimes called 'type
> punning').  This might be a trap representation."
>
> Footnotes are non-normative, and are intended to merely summarize
> and make clear the meaning of normative text.  I can't find any
> normative text that clearly specifies that such reinterpretation
> takes place - the committee apparently feels otherwise, and some
> people on this group have claimed that it's an obvious consequence
> of the referenced section, 6.2.6.

Have they?  I consider what the footnote says to follow from other,
normative text in the Standard, and have said so in past postings,
but I don't remember anyone saying that it's obvious.  I wouldn't.

[toc] | [prev] | [next] | [standalone]

#145819

Robert Wessel <robertwessel2@yahoo.com> writes:

> On Tue, 27 Aug 2019 17:03:38 -0000 (UTC), 3queens@shabbyroad.com
> wrote:
>
>>Some time ago, there was a thread concerning using "a^=b; b^=a; a^=b" 
>>to do an in place swap of two variables of the same size.  It was
>>pointed out that this can only be done with integer types.  I found a
>>way to do it with floating point types as well.
>>
>>Declare a union with the floating point variable and an equally long
>>integer variable.  Then use the integer member to do the exclusive-or
>>process.
>>
>>Naturally, this would not be efficient if the data had to be copied into
>>and out of the union, but if the variables were defined as unions to
>>begin with, this would work.
>>
>>Maybe not that useful, but if space is really tight, perhaps useful in
>>some situations.
>
>
> AFAIK, this invokes undefined behavior.  You cannot reliably read from
> a different member of a union than was written to.

A footnote in the standard reads:

  If the member used to read the contents of a union object is not the
  same as the member last used to store a value in the object, the
  appropriate part of the object representation of the value is
  reinterpreted as an object representation in the new type as described
  in 6.2.6 (a process sometimes called "type punning"). This might be
  a trap representation.

so if the type read has trap representations then the result could be
undefined but it's not UB simply as a result of reading a member that
not the last one written.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#145820

In article <9ddbme52b398c5lrr1c653lvdo2oe7qbv5@4ax.com>,
 Robert Wessel <robertwessel2@yahoo.com> wrote:

> On Tue, 27 Aug 2019 17:03:38 -0000 (UTC), 3queens@shabbyroad.com
> wrote:
> 
> >Some time ago, there was a thread concerning using "a^=b; b^=a; a^=b" 
> >to do an in place swap of two variables of the same size.  It was
> >pointed out that this can only be done with integer types.  I found a
> >way to do it with floating point types as well.
> >
> >Declare a union with the floating point variable and an equally long
> >integer variable.  Then use the integer member to do the exclusive-or
> >process.
> >
> >Naturally, this would not be efficient if the data had to be copied into
> >and out of the union, but if the variables were defined as unions to
> >begin with, this would work.
> >
> >Maybe not that useful, but if space is really tight, perhaps useful in
> >some situations.
> 
> 
> AFAIK, this invokes undefined behavior.  You cannot reliably read from
> a different member of a union than was written to.

If I really were to do this claiming efficiency, I would do it in assembly to 
ensure I maximise register use.


Then again I don't do assembly any more.

The compilers I use have GCC extensions so I would do
    #define swap(x,y) ({typeof(x) _t = x; x = y; y = t_; t_;})
and let the compiler try do what it can.

Two notes: compilers now do value numerberring so they would compile the above 
code that x=R1, y=R2 before the swap, and x=R2, y=R1 after the swap without 
issuing any actual instructions.

And if you need to load/store x or y to memory, the compiler would issue
    R1 = memory[x]; R2 = memory[y];
    memory[x] = R2; memory[y] = R1;

Neither of these would be likely be issued from a convoluted union and xor. I 
can't think of xor being useful on anything but single accumulator machines. Are 
there still any of those outside of computer museums?

-- 
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.    @
'I desire mercy, not sacrifice.'                                    /|\
The first law of discordiamism: The more energy   This post         / \
to make order is nore energy made into entropy.   insults Islam.  Mohammed

[toc] | [prev] | [next] | [standalone]

#145821

On 28/08/2019 00:59, Robert Wessel wrote:
> On Tue, 27 Aug 2019 17:03:38 -0000 (UTC), 3queens@shabbyroad.com
> wrote:
> 
>> Some time ago, there was a thread concerning using "a^=b; b^=a; a^=b" 
>> to do an in place swap of two variables of the same size.  It was
>> pointed out that this can only be done with integer types.  I found a
>> way to do it with floating point types as well.
>>
>> Declare a union with the floating point variable and an equally long
>> integer variable.  Then use the integer member to do the exclusive-or
>> process.
>>
>> Naturally, this would not be efficient if the data had to be copied into
>> and out of the union, but if the variables were defined as unions to
>> begin with, this would work.
>>
>> Maybe not that useful, but if space is really tight, perhaps useful in
>> some situations.
> 
> 
> AFAIK, this invokes undefined behavior.  You cannot reliably read from
> a different member of a union than was written to.
> 

Others have shown why this is not undefined behaviour in C (unless there
are traps, padding bits, etc.).  But I believe it is undefined behaviour
in C++, if that is what you were thinking of.

(And I hope I'll be corrected if I'm wrong here!)

[toc] | [prev] | [next] | [standalone]

#145833

On 8/27/2019 3:59 PM, Robert Wessel wrote:
> 
> AFAIK, this invokes undefined behavior.  You cannot reliably read from
> a different member of a union than was written to.
> 

The act of reading itself is legal in C since C99+TC3 (albeit one might 
argue that even the original C89/90 permitted it).

However, the above permission still does not protect you from trap 
representations. In general case a type-punned representation might 
easily end up being a trap one, thus still triggering UB. So, it all 
boils down to specific properties of the given implementation. If in 
yours type punning between float and integer types never produces traps, 
then you are perfectly safe.

-- 
Best regards,
Andrey Tarasevich

[toc] | [prev] | [next] | [standalone]

#145822

On 27/08/2019 19:03, 3queens@shabbyroad.com wrote:
> Some time ago, there was a thread concerning using "a^=b; b^=a; a^=b" 
> to do an in place swap of two variables of the same size.  It was
> pointed out that this can only be done with integer types.  I found a
> way to do it with floating point types as well.
> 
> Declare a union with the floating point variable and an equally long
> integer variable.  Then use the integer member to do the exclusive-or
> process.
> 
> Naturally, this would not be efficient if the data had to be copied into
> and out of the union, but if the variables were defined as unions to
> begin with, this would work.
> 
> Maybe not that useful, but if space is really tight, perhaps useful in
> some situations.
> 
> 

Such tricks are long outdated - by decades at least.  I'm not convinced
this one was ever useful.  There are not many processors have so few
registers that such a trick could be helpful - and those that exist are
usually accumulator based, so the xor has to pass through the
accumulator bottleneck anyway.  On any cpu beyond small
microcontrollers, pipelining and dependencies would mean such an xor
sequence would be many times slower than using a sequence of move
instructions.

Compilers (of any reasonable quality) will handle allocation of
variables to registers or stack slots, and movement, renaming and reuse
of these variables and slots.  There isn't any trick you can do in the C
code that will be better than the compiler will do itself.  Indeed,
modern compilers can be smart enough to see the sequence of xors here
and realise it is silly code to swap "a" and "b", and find a better way
of swapping them without using xor.


I challenge you to show a sequence of code, for whatever target
processor you like, where you think such an xor swap was ever a useful
trick.  Then we can see if it would be at all useful on any realistic
cpu and compiler now.


No, such tricks are not useful - if space is really tight, write clear
sensible code and work /with/ your compiler, rather than trying to
outsmart it.

[toc] | [prev] | [next] | [standalone]

#145824

On 28/08/2019 08:36, David Brown wrote:
> On 27/08/2019 19:03, 3queens@shabbyroad.com wrote:

>> Maybe not that useful, but if space is really tight, perhaps useful in
>> some situations.
>>
>>
> 
> Such tricks are long outdated - by decades at least.  I'm not convinced
> this one was ever useful.  There are not many processors have so few
> registers that such a trick could be helpful - and those that exist are
> usually accumulator based, so the xor has to pass through the
> accumulator bottleneck anyway.  On any cpu beyond small
> microcontrollers, pipelining and dependencies would mean such an xor
> sequence would be many times slower than using a sequence of move
> instructions.
> 
> Compilers (of any reasonable quality) will handle allocation of
> variables to registers or stack slots, and movement, renaming and reuse
> of these variables and slots.  There isn't any trick you can do in the C
> code that will be better than the compiler will do itself.  Indeed,
> modern compilers can be smart enough to see the sequence of xors here
> and realise it is silly code to swap "a" and "b", and find a better way
> of swapping them without using xor.
> 
> 
> I challenge you to show a sequence of code, for whatever target
> processor you like, where you think such an xor swap was ever a useful
> trick.  Then we can see if it would be at all useful on any realistic
> cpu and compiler now.
> 
> 
> No, such tricks are not useful - if space is really tight, write clear
> sensible code and work /with/ your compiler, rather than trying to
> outsmart it.

I don't understand why anyone would think this xor trick was any faster 
than using the conventional swap idiom using a temporary.

Some brief tests swapping A[j] and A[k] on non-optimising compilers 
showed xor to be slower than using a temp. gcc-O3 also made the xor code 
a little slower.

(On my bcc, which has memory-based variables, using temp generates 10 
instructions rather than 12, and it uses 3 memory writes rather than 3 
read-modify-write instructions.)

[toc] | [prev] | [next] | [standalone]

#145826

On Wednesday, August 28, 2019 at 7:03:05 AM UTC-4, Bart wrote:
> On 28/08/2019 08:36, David Brown wrote:
...
> > No, such tricks are not useful - if space is really tight, write clear
> > sensible code and work /with/ your compiler, rather than trying to
> > outsmart it.
> 
> I don't understand why anyone would think this xor trick was any faster 
> than using the conventional swap idiom using a temporary.

The xor trick has always been about minimizing memory usage (including
registers) - not minimizing execution time.

And as David pointed out, it's of doubtful usefulness, even for that
purpose, in high-level languages like C. The compiler generally knows
better than the programmer how to best use the available registers, and
languages like C don't provide the level of detailed control needed to
do a significantly better job. Only the best assembly language
programmers can do a significantly better job than the best compilers -
because the expertise of the best assembly language programmers has, to
the extent possible, been built into the best compilers.

[toc] | [prev] | [next] | [standalone]

#145827

On Wednesday, 28 August 2019 13:08:24 UTC+1, James Kuyper  wrote:
> On Wednesday, August 28, 2019 at 7:03:05 AM UTC-4, Bart wrote:
> > On 28/08/2019 08:36, David Brown wrote:
> ...
> > > No, such tricks are not useful - if space is really tight, write clear
> > > sensible code and work /with/ your compiler, rather than trying to
> > > outsmart it.
> > 
> > I don't understand why anyone would think this xor trick was any faster 
> > than using the conventional swap idiom using a temporary.
> 
> The xor trick has always been about minimizing memory usage (including
> registers) - not minimizing execution time.
> 
It's a computer studies course puzzle. Swap two variables without using
a temporary. Not obvious how to do it, but since the class is on logical
operations, that gives students a clue. 

[toc] | [prev] | [next] | [standalone]

#145828

On 28/08/2019 14:08, James Kuyper wrote:
> On Wednesday, August 28, 2019 at 7:03:05 AM UTC-4, Bart wrote:
>> On 28/08/2019 08:36, David Brown wrote:
> ...
>>> No, such tricks are not useful - if space is really tight, write clear
>>> sensible code and work /with/ your compiler, rather than trying to
>>> outsmart it.
>>
>> I don't understand why anyone would think this xor trick was any faster 
>> than using the conventional swap idiom using a temporary.
> 
> The xor trick has always been about minimizing memory usage (including
> registers) - not minimizing execution time.
> 
> And as David pointed out, it's of doubtful usefulness, even for that
> purpose, in high-level languages like C. 

I actually have always doubted its usefulness even for assembly
programming on minimal machines.  And I have experience of programming
in assembly for minimal systems (or where there are minimal free
resources) - I have had tasks where I knew how to implement a new
feature, but it took days of work to find two or three free bits of ram
or a dozen bytes of code space in order to implement the feature.  And I
have never seen a task for which this trick would have been remotely
helpful.

Some "bit hack" ideas have their uses.  This one - IME - does not.

> The compiler generally knows
> better than the programmer how to best use the available registers, and
> languages like C don't provide the level of detailed control needed to
> do a significantly better job. Only the best assembly language
> programmers can do a significantly better job than the best compilers -
> because the expertise of the best assembly language programmers has, to
> the extent possible, been built into the best compilers.
> 

[toc] | [prev] | [next] | [standalone]

#145829

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> On Wednesday, August 28, 2019 at 7:03:05 AM UTC-4, Bart wrote:
>> On 28/08/2019 08:36, David Brown wrote:
> ...
>> > No, such tricks are not useful - if space is really tight, write clear
>> > sensible code and work /with/ your compiler, rather than trying to
>> > outsmart it.
>> 
>> I don't understand why anyone would think this xor trick was any faster 
>> than using the conventional swap idiom using a temporary.
>
> The xor trick has always been about minimizing memory usage (including
> registers) - not minimizing execution time.
>
> And as David pointed out, it's of doubtful usefulness, even for that
> purpose, in high-level languages like C. The compiler generally knows
> better than the programmer how to best use the available registers, and
> languages like C don't provide the level of detailed control needed to
> do a significantly better job. Only the best assembly language
> programmers can do a significantly better job than the best compilers -
> because the expertise of the best assembly language programmers has, to
> the extent possible, been built into the best compilers.

Another problem that I don't think anyone has pointed out in this thread
is that it fails if you try to swap an object with itself -- for example
swapping *p and *q, where p and q are pointers to the same object, or
swapping arr[i] and arr[j] where i==j.

Most algorithms, if implemented correctly, won't try to swap an object
with itself, but it's something to consider.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#145968

Am 28.08.19 um 09:36 schrieb David Brown:

> I challenge you to show a sequence of code, for whatever target
> processor you like, where you think such an xor swap was ever a useful
> trick.  Then we can see if it would be at all useful on any realistic
> cpu and compiler now.

Couldn't resist doing a quick experiment swapping two global floats,
using three versions of the float swap:

1) temporary variable
2) loop over bytes
3) Manually unrolled loop

I used current SDCC from svn and compiled using -mpdk13 --stack-auto for
the pdk13 target (the architecture supports a maximum of 1 KW ROM (each
word is 13 bits) and 64 B RAM) as reentrant code.

Code sizes:
1) 42 W
2) 131 W
3) 84 W

Stack space used for local variables:

1) 4 B
2) 4 B
3) 0 B

Still, probably not a very realistic or useful use case.

But let's look at swapping to global unsigned long long (which might be
a more realistic example for such a tiny µC than float). There the
temporary solution uses 75 W code space and 8 B of stack space. But the
xor solution uses only 48 W and 0 B of stack space. That one looks
useful to me.

Philipp

Code used:

float:

float f1, f2;

void f_tmp(void)
{
	float tmp = f1;
	f1 = f2;
	f2 = tmp;
}

void f_xor(void)
{
	for(unsigned char i = 0; i < sizeof(float); i++)
	{
		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i);
		*((unsigned char*)(&f2) + i) ^= *((unsigned char*)(&f1) + i);
		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i);
	}
}

#define SWAPBYTE(f1, f2, i) \
	{ \
		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i); \
		*((unsigned char*)(&f2) + i) ^= *((unsigned char*)(&f1) + i); \
		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i); \
	}

void f_xor_macro(void)
{
	SWAPBYTE(f1, f2, 0);
	SWAPBYTE(f1, f2, 1);
	SWAPBYTE(f1, f2, 2);
	SWAPBYTE(f1, f2, 3);
}

unsigned long long:

unsigned long long f1, f2;

void f_tmp(void)
{
	unsigned long long tmp = f1;
	f1 = f2;
	f2 = tmp;
}

void f_xor(void)
{
	f1 ^= f2;
	f2 ^= f1;
	f1 ^= f2;
}

[toc] | [prev] | [next] | [standalone]

#145976

On 04/09/2019 11:18, Philipp Klaus Krause wrote:
> Am 28.08.19 um 09:36 schrieb David Brown:
> 
>> I challenge you to show a sequence of code, for whatever target
>> processor you like, where you think such an xor swap was ever a useful
>> trick.  Then we can see if it would be at all useful on any realistic
>> cpu and compiler now.
> 
> Couldn't resist doing a quick experiment swapping two global floats,
> using three versions of the float swap:
> 
> 1) temporary variable
> 2) loop over bytes
> 3) Manually unrolled loop
> 
> I used current SDCC from svn and compiled using -mpdk13 --stack-auto for
> the pdk13 target (the architecture supports a maximum of 1 KW ROM (each
> word is 13 bits) and 64 B RAM) as reentrant code.
> 
> Code sizes:
> 1) 42 W
> 2) 131 W
> 3) 84 W
> 
> Stack space used for local variables:
> 
> 1) 4 B
> 2) 4 B
> 3) 0 B
> 
> Still, probably not a very realistic or useful use case.
> 
> But let's look at swapping to global unsigned long long (which might be
> a more realistic example for such a tiny µC than float). There the
> temporary solution uses 75 W code space and 8 B of stack space. But the
> xor solution uses only 48 W and 0 B of stack space. That one looks
> useful to me.
> 

Those are interesting figures.  I'm curious about the code generated for
the solutions here.

I'm trying to guess the instructions here.  I'm assuming loads, stores
and ALU instructions all pass through the accumulator A, and you have an
extra register B.  For the byte copy solution, I'm guessing that each
byte needs instructions:

	A = f1[i];
	B = A;
	A = f2[i];
	f1[i] = A;
	A = B;
	f2[i] = A;

That is six instructions per byte.

With a temporary, you'd have an array t[] for the temporary space:

	A = f1[i];
	t[i] = A;
	A = f2[i];
	f1[i] = A;
	A = t[i];
	f2[i] = A;

Again, six instructions per byte (and they might be in different orders).

For xor, a direct translation would give:

	A = f1[i];
	A ^= f2[i];
	f1[i] = A;

	A = f2[i];
	A ^= f1[i];
	f2[i] = A;

	A = f1[i];
	A ^= f2[i];
	f1[i] = A;

A smarter translation would give:

	A = f1[i];
	A ^= f2[i];
	f1[i] = A;

	A ^= f2[i];
	f2[i] = A;

	A ^= f1[i];
	f1[i] = A;

That is seven instructions per byte (but you don't need to use a
temporary register).

What am I missing?

> Philipp
> 
> Code used:
> 
> float:
> 
> float f1, f2;
> 
> void f_tmp(void)
> {
> 	float tmp = f1;
> 	f1 = f2;
> 	f2 = tmp;
> }
> 
> void f_xor(void)
> {
> 	for(unsigned char i = 0; i < sizeof(float); i++)
> 	{
> 		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i);
> 		*((unsigned char*)(&f2) + i) ^= *((unsigned char*)(&f1) + i);
> 		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i);
> 	}
> }
> 
> #define SWAPBYTE(f1, f2, i) \
> 	{ \
> 		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i); \
> 		*((unsigned char*)(&f2) + i) ^= *((unsigned char*)(&f1) + i); \
> 		*((unsigned char*)(&f1) + i) ^= *((unsigned char*)(&f2) + i); \
> 	}
> 
> void f_xor_macro(void)
> {
> 	SWAPBYTE(f1, f2, 0);
> 	SWAPBYTE(f1, f2, 1);
> 	SWAPBYTE(f1, f2, 2);
> 	SWAPBYTE(f1, f2, 3);
> }
> 
> unsigned long long:
> 
> unsigned long long f1, f2;
> 
> void f_tmp(void)
> {
> 	unsigned long long tmp = f1;
> 	f1 = f2;
> 	f2 = tmp;
> }
> 
> void f_xor(void)
> {
> 	f1 ^= f2;
> 	f2 ^= f1;
> 	f1 ^= f2;
> }
> 

[toc] | [prev] | [next] | [standalone]

#145978

Am 04.09.19 um 12:57 schrieb David Brown:
> 
> Those are interesting figures.  I'm curious about the code generated for
> the solutions here.
> 
> I'm trying to guess the instructions here.  I'm assuming loads, stores
> and ALU instructions all pass through the accumulator A, and you have an
> extra register B.  For the byte copy solution, I'm guessing that each
> byte needs instructions:
> 
> […]
> 
> What am I missing?


The architecture has one 8-bit accumulator a. The compiler uses one
8-bit memory location as pseudo-register p. p can be used as an index
register. We are lacking a stack-pointer-relative addressing mode, and
are compiling the code as reentrant. So accesses to the temporary on the
stack are very expensive (we need to set up p by moving the stack
pointer into a, adding an offset there, then move to p, then do a read
or write using p as a pointer).

Philipp

[toc] | [prev] | [next] | [standalone]

#146005

> "a^=b; b^=a; a^=b" ...
Those operations are strictly serializing on a OoO-CPU.
But how does a t = a; a = b; b = t; perform on a OoO-CPU???

[toc] | [prev] | [next] | [standalone]

#146022

On 05/09/2019 08:18, Bonita Montero wrote:
>> "a^=b; b^=a; a^=b" ...
> Those operations are strictly serializing on a OoO-CPU.
> But how does a t = a; a = b; b = t; perform on a OoO-CPU???

On most modern processors, you have plenty of registers, and compilers
are likely to generate the same kind of code for both swaps:

	reg1 = a;
	reg2 = b;
	b = reg1;
	a = reg2;

[toc] | [prev] | [next] | [standalone]

#146027

>>> "a^=b; b^=a; a^=b" ...

>> Those operations are strictly serializing on a OoO-CPU.
>> But how does a t = a; a = b; b = t; perform on a OoO-CPU???

> On most modern processors, you have plenty of registers, and compilers
> are likely to generate the same kind of code for both swaps:
> 	reg1 = a;
> 	reg2 = b;
> 	b = reg1;
> 	a = reg2;

This isn't an answer to my question. I asked whats the order
of execution of the above three instructions on a OoO-CPU,
i.e. if f.e. the isntructions might adress the remapper in
the instruction-scheduler in a way, that all three instruc-
tions are executed in a single clock-cycle.

[toc] | [prev] | [next] | [standalone]

#146029

On Thursday, 5 September 2019 15:18:08 UTC+1, Bonita Montero  wrote:
> >>> "a^=b; b^=a; a^=b" ...
> 
> >> Those operations are strictly serializing on a OoO-CPU.
> >> But how does a t = a; a = b; b = t; perform on a OoO-CPU???
> 
> > On most modern processors, you have plenty of registers, and compilers
> > are likely to generate the same kind of code for both swaps:
> > 	reg1 = a;
> > 	reg2 = b;
> > 	b = reg1;
> > 	a = reg2;
> 
> This isn't an answer to my question. I asked whats the order
> of execution of the above three instructions on a OoO-CPU,
> i.e. if f.e. the isntructions might adress the remapper in
> the instruction-scheduler in a way, that all three instruc-
> tions are executed in a single clock-cycle.
>
I doubt that is possible. The registers would have to be both source
and target in the same cycle. Whilst I'm not too familiar with modern
pipelining architectures, that's quite an engieering challenge.

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web