Re: Is there a Swap faster than using XOR!!!

From: Paul Hsieh (websnarf_at_gmail.com)
Date: 12/02/04 

Date: 1 Dec 2004 20:07:34 -0800

Keith Thompson <kst-u@mib.org> wrote:
> websnarf@gmail.com (Paul Hsieh) writes:
> [...]
> > An alternate solution (which sort of works for floating point as well)
> > includes: b += a; a = b - a; b -= a; . However as to whether or not
> > this is faster is also apparently off topic in c.l.c.
>
> If by "sort of works" you mean "doesn't work", I agree.

*Sigh* ...

> [...] Yes, it's
> mathematically sound if a and b are capable of representing actual
> real numbers, but C floating-point variables are not. Roundoff errors
> will cause errors in the results. In some cases, you may get the same
> values you started with; in others, you'll lose a lot of precision,
> especially if the initial values of a and b differ greatly in
> magnitude. If a and b are the same variable, you'll set it to zero (a
> problem shared with the xor kludge). And of course any of the
> operations can overflow if the operands are floating-point or signed
> integers.
>
> The way to swap two variables in C is to use a temporary variable:
> old_a = a;
> a = b;
> b = old_a;

Of course, I didn't have wait too long before you tripped yourself up.
 This *ALSO* has a numerical problem. For example, older x86
compilers would often put the x87 into 80 bit mode -- but being an x86
this means that running out of registers (or stack entries) was a
common problem. So the above operation would require an additional
storage which might be forced to go through memory -> but that memory
would be declared as 64 bits, so this action actually drops some
accuracy.

Look, *ALL* floating point usage is inherently numerically unstable
(unless the parameters are short shifted powers of two) -- which is
why I just said "sort of works". If you are using floating point at
all, either you work out how every single operation is numerically
characterized (and you may need to understand the underlying assembly
to really know), or you just assume that in general that every
calculation will always be off by some amount and maybe you test to
see by how much.

> Asking how to swap to variables without using a temporary is like
> asking how to drive a nail without using a hammer. The correct answer
> is not "use xor" or "use your forehead", it's "why do you want to do
> that?". If there's a valid answer to that, we can consider alternate
> solutions, but I have yet to see a case where it doesn't make more
> sense just to use a temporary.

Spoken like someone unjustifiably sure of themselves. Try
implementing an incremental fibonacci inner loop using an add, a swap
and a 3 variables. Then tell me which swap implementation is the most
appropriate for such an inner loop.

Every "clever swap implementation", that I know of has a scenario
where it is best to use them. For example, the 3 xors can be used on
graphics buffers, if your graphics device has limited memory, is too
slow either to swap on a pixel by pixel basis or to otherwise transfer
through system memory but nevertheless has an accelerated pixel-op
engine which includes xor. The sum, subtract method works well if the
surrounding operations can cancel out with those operations. And
finally the often useful "DONT DO THAT" operation -- i.e., rename the
registers in your algorithm, rather switching them at run time. These
are 3 cases where I would never recommend using the swap through a
temp solution.

Your problem is that you've got a hammer and a nail, but you didn't
bother to check if you are trying to penetrate glass or paper. 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: Heaps and Foreigners
    ... >> can ask for the memory and get a pointer to it. ... cause unfathomable deaths when swap space gets low or is exhausted. ... It's probably because there is some reserve memory to print out errors ... of RAM and disk space) and virtual swap (which is just a number managed ...
    (comp.lang.lisp)
  • Re: Is Greenspun enough?
    ... Most OSes memory map executables directly from the file system so code doesn't pollute the file cache or swap space. ...
    (comp.lang.lisp)
  • Re: [PATCH] io-controller: Add io group reference handling for request
    ... Find the io group bio belongs to. ... anonymous pages (swap) you still need the page tracking functionality ... so fair to charge the current task for the whole activity. ... is some other memory hungry application which is forcing these swap outs. ...
    (Linux-Kernel)
  • Re: Frontswap [PATCH 0/4] (was Transcendent Memory): overview
    ... instead of introducing a special purpose API. ... in memory and its enabled as highest priority swap. ... ramzswap needs a callback for every page and as ...
    (Linux-Kernel)
  • Re: [kde-linux] VM and Swap problems
    ... swap is half full the system starts removing swap until it is exactly ... Maybe one of your applications leak memory (I have a webpage ... to two times RAM. ... Unused memory will be used as disk buffers. ...
    (KDE)