memswap()

[Malcolm]

Why isn't

void memswap(void *ptr1, void *ptr2, size_t len)

part of the standard library?

The function is easy to write, but if it was part of the standard then you
could write code like

memswap(&x, &y, sizeof(double));

knowing that any half-decent compiler would optimise it to a few inlined
instructions.

[Thomas Matthews]

Malcolm wrote:

Why isn't

void memswap(void *ptr1, void *ptr2, size_t len)

part of the standard library?

The function is easy to write, but if it was part of the standard then you
could write code like

memswap(&x, &y, sizeof(double));

knowing that any half-decent compiler would optimise it to a few inlined
instructions.

Your memswap declaration allows the function to swap
any sized area of memory with another.

This leads to the issue of the implementation having
enough memory to swap the areas. What about something
like:
unsigned char * p;
unsigned char * q;
p = malloc(32 * 1024 * 1024);
q = malloc(32 * 1024 * 1024);
memswap(p, q, 32 * 1024 * 1024);

Also, what happens if the size is bigger than
the size of the first two arguments:
unsigned int i;
unsigned int j;
memswap(&i, &j, 2 * sizeof(int));

Some compilers may already have a "swap" function.

--
Thomas Matthews
Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html

[Brett Frankenberger]

In article <xX*********************@newssvr28.news.prodigy.co m>,
Thomas Matthews <Th**************************@sbcglobal.net> wrote:

Your memswap declaration allows the function to swap
any sized area of memory with another.

This leads to the issue of the implementation having
enough memory to swap the areas.
How much do you think it would need?
What about something like:
unsigned char * p;
unsigned char * q;
p = malloc(32 * 1024 * 1024);
q = malloc(32 * 1024 * 1024);
memswap(p, q, 32 * 1024 * 1024);
void memswap(void *p1, void *p2, size_t count)
{
char tmp, *c1, *c2;

c1 = p1;
c2 = p2;
while (count--) {
tmp = *c1;
*c2++ = c1;
*c1++ = tmp;
};
};

Or, if you really want to get fancy, make them unsigned chars and do:
*c2 ^= *c1;
*c1 ^= *c2;
*c2++ ^= *c1++;
and eliminate the temporary variable.
Also, what happens if the size is bigger than
the size of the first two arguments:
unsigned int i;
unsigned int j;
memswap(&i, &j, 2 * sizeof(int));

Presumably undefined behavior, just like if you use memcpy() to copy
beyond the end of an object.

-- Brett

[Ben Pfaff]

rb*@panix.com (Brett Frankenberger) writes:

Or, if you really want to get fancy, make them unsigned chars and do:
*c2 ^= *c1;
*c1 ^= *c2;
*c2++ ^= *c1++;
and eliminate the temporary variable.

And make swap(p, p, n) degenerate into memset(p, 0, n) in the
process, too.
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,0xaa9aa9f6,0x1f6},*p=
b,x,i=24;for(;p+=!*p;*p/=4)switch(x=*p&3)case 0:{return 0;for(p--;i--;i--)case
2:{i++;if(1)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}

[Derk Gwen]

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:
# Why isn't
#
# void memswap(void *ptr1, void *ptr2, size_t len)
#
# part of the standard library?

Because nobody compaigned hard enough to add it? Or it was even defined the
last time standards round?

# knowing that any half-decent compiler would optimise it to a few inlined
# instructions.

A compiler can add it and optimise it whether the standard mentions it or not.

Note that putting & in front of variable usually forces the variable into memory
and not permit it to live in a register. Perhaps the compiler can decide it doesn't
really need the address and allow register allocation, but this could also cost
far more than the possible optimisation of this one operation.

--
Derk Gwen http://derkgwen.250free.com/html/index.html
Title does not dictate behaviour.

[Ben Pfaff]

It's clear what should happen when swapping two buffers that
overlap completely; that is, nothing at all should happen. It is
not clear to me what should happen when swapping two buffers that
partially overlap. Any suggestions?
--
"The way I see it, an intelligent person who disagrees with me is
probably the most important person I'll interact with on any given
day."
--Billy Chambless

[Brett Frankenberger]

In article <87************@pfaff.Stanford.EDU>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:

It's clear what should happen when swapping two buffers that
overlap completely; that is, nothing at all should happen. It is
not clear to me what should happen when swapping two buffers that
partially overlap. Any suggestions?

Undefined behavior, just like memcpy(). (memcpy(), by the way, is
undefined if the areas overlap, even if they overlap completely.)

-- Brett

[Arthur J. O'Dwyer]

On Wed, 6 Aug 2003, bd wrote:

On Wed, 06 Aug 2003 22:04:52 +0000, Dave Vandervies wrote:

Brett Frankenberger <rb*@panix.com> wrote:

Or, if you really want to get fancy, make them unsigned chars and do:
*c2 ^= *c1;
*c1 ^= *c2;
*c2++ ^= *c1++;
and eliminate the temporary variable.

[And screw up the case where c1==c2]
Hm, the way I see it:
(on entry)
c1 = 1, c2 = 1
c2 ^= c1
c1 = 1, c2 = 0

You forgot the dereference operators. If c1==c2, then
*c1 and *c2 are the same object. From the step above:

*c2 ^= *c1
*c1 = 0, *c2 = 0

....and continue from there.
And yes,

memswap(p, p+1, 2*sizeof *p)

and similar overlaps should be undefined behavior, as there
is no one reasonable effect this function call could
produce. I think it's simple enough to define the null
case, though (swapping *p with itself is a no-op).

-Arthur

[Brett Frankenberger]

In article <pa****************************@bd-home-comp.no-ip.org>,
bd <bd*****@bd-home-comp.no-ip.org> wrote:

On Wed, 06 Aug 2003 22:04:52 +0000, Dave Vandervies wrote:

In article <bg**********@reader1.panix.com>,
Brett Frankenberger <rb*@panix.com> wrote:

Or, if you really want to get fancy, make them unsigned chars and do:
*c2 ^= *c1;
*c1 ^= *c2;
*c2++ ^= *c1++;
and eliminate the temporary variable.
If you're going to do this, you'll also need to do:
--------
if(c1==c2)
return;
--------
before you enter the loop. This removes the bug where you'll get zeroed
memory if the pointers are the same, and is also a nice cheap optimization
for the "input pointers refer to the same memory" case.

Hm, the way I see it:
(on entry)
c1 = 1, c2 = 1
c2 ^= c1

I didn't write that. I wrote
*c2 ^= *c1;
If c1 == c2, then this is equivalent to:
*c2 ^= *c2
and when you exclusive-or anything with itself, you get 0.
Did I miss something here?

Yes. You presented evidence that the "XOR" trick for swapping two
values without needing a temporary variable works even with both values
are identical. But no one was suggesting that wasn't the case.

The c1==c2 case isn't swapping two variables that happen to have equal
values (that woulbe the *c1==*c2 case). The c1==c2 cause is swapping
the same variable with itself. My code doesn't work in the overlapped
case; I'd argue that that's not a problem because, except for the
completely overlapping case, it would be difficult to say what the
result should be anyway.

-- Brett

[Paul Hsieh]

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

Why isn't

void memswap(void *ptr1, void *ptr2, size_t len)

part of the standard library?

The function is easy to write, but if it was part of the standard then you
could write code like

memswap(&x, &y, sizeof(double));

knowing that any half-decent compiler would optimise it to a few inlined
instructions.

Well, since nobody else will answer your question, I'll give it a
shot. For small sized types like this, this is how I deal with the
issue:

#define swapType (type, x, y) { \
type tmp_NAMESPACE_OBFUSCATION_XJgb75b6978t; \
tmp_NAMESPACE_OBFUSCATION_XJgb75b6978t = x; \
x = y; \
y = t; \
}

This allows the compiler to use type specific mechanisms to perform
the swap. This matters on processors like the Athlon which physically
seperates that FPU and INT portions of the CPU (if you use an opaque
mechanism for trying to move the data, you may incurr large
performance penalties because of this.)

I think the compiler can use FP registers in something like:

memswap(&x, &y, sizeof(double));

as you suggest, but the compilers ability to do this might be very
narrow. For example if you did this:

memswap(&t.x, &t.y, sizeof(double));

The vendor might conclude that it shouldn't do this if t is a union.
Using FP registers might *normalize* the value while swapping it,
which would make the integer images change in unexpected ways. While
the ANSI committee could write all sorts of irrelevant verbiage about
how something is undefined, or not, their rubber stamp will not
override the desire of vendors who wanted to both simplify the
implementation (and not perform the optimization you are hoping for)
and make sure it was bit preserving to follow the principle of least
surprise.

Using the macro I showed above, you could instead use the following
alternative:

swapType (double, x, y);

Which takes fewer keystrokes, is more flexible, doesn't take a
function call hit, etc, etc.

I discuss various ways of swapping on my website:

http://www.azillionmonkeys.com/qed/case3.html

--
Paul Hsieh
http://www.azillionmonkeys.com/qed/
http://www.sf.net/

[Richard Bos]

qe*@pobox.com (Paul Hsieh) wrote:

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

Why isn't

void memswap(void *ptr1, void *ptr2, size_t len)

part of the standard library?

Well, since nobody else will answer your question, I'll give it a
shot. For small sized types like this, this is how I deal with the
issue:

#define swapType (type, x, y) { \
type tmp_NAMESPACE_OBFUSCATION_XJgb75b6978t; \
tmp_NAMESPACE_OBFUSCATION_XJgb75b6978t = x; \
x = y; \
y = t; \
}

That deals with the wrong issue. I'd expect memswap to be used more
often like this:

memswap(buffer1, buffer2, amount_of_data * *buffer1);

That is, I'd expect it to be used to swap entire buffers, not single
objects, which is what your macro does (correctly).

Richard

[Kevin Easton]

Paul Hsieh <qe*@pobox.com> wrote:

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

Why isn't

void memswap(void *ptr1, void *ptr2, size_t len)

part of the standard library?

The function is easy to write, but if it was part of the standard then you
could write code like

memswap(&x, &y, sizeof(double));

knowing that any half-decent compiler would optimise it to a few inlined
instructions.

Well, since nobody else will answer your question, I'll give it a
shot. For small sized types like this, this is how I deal with the
issue:

#define swapType (type, x, y) { \
type tmp_NAMESPACE_OBFUSCATION_XJgb75b6978t; \
tmp_NAMESPACE_OBFUSCATION_XJgb75b6978t = x; \
x = y; \
y = t; \
}

Here's another (better?) way of getting a name that's not supposed to
clash with x or y:

#define swap(type, x, y) \
{ \
type tmp ## x ## y; \
tmp ## x ## y = x; \
x = y; \
y = tmp ## x ## y; \
}

It would be nice if the standard included the GNU C typeof keyword, wouldn't
it?

- Kevin.

[Eric Sosman]

Kevin Easton wrote:

Here's another (better?) way of getting a name that's not supposed to
clash with x or y:

#define swap(type, x, y) \
{ \
type tmp ## x ## y; \
tmp ## x ## y = x; \
x = y; \
y = tmp ## x ## y; \
}

Try it with `swap(sometype, array[i], array[j])' and
let us know what your compiler thinks ...

--
Er*********@sun.com

[Malcolm]

"Paul Hsieh" <qe*@pobox.com> wrote in message

"Malcolm" <ma*****@55bank.freeserve.co.uk> wrote:

Well, since nobody else will answer your question, I'll give it a
shot. For small sized types like this, this is how I deal with the
issue:
[ swap macro using type and temporary ]
None of these swap macros have caught on. One of the reasons I think is that
C people don't like to pass types to function-like macros (an exception is
the va_list macros). Another reason is that if you are swapping two
pointers, it isn't obvious whether you should swap the pointers or what they
point to. A first reason could be fixed, you should pass the address of a
variable to be changed to show that its value may have been altered.
I think the compiler can use FP registers in something like:

memswap(&x, &y, sizeof(double));

as you suggest, but the compilers ability to do this might be very
narrow. For example if you did this:

memswap(&t.x, &t.y, sizeof(double));

The vendor might conclude that it shouldn't do this if t is a union.
Time for some anti-union legislation. Seriously, unions aren't used often
enough for this to be a problem in itself, but it might make an optimising
compiler hard to write if it has to check for unions before doing the
optimisation.
Using the macro I showed above, you could instead use the following
alternative:

swapType (double, x, y);

Which takes fewer keystrokes, is more flexible, doesn't take a
function call hit, etc, etc.

I think that is a valid criticism of memswap() - it is rather too many
keystrokes when C++ has swap(x,y).

[Ben Pfaff]

rb*@panix.com (Brett Frankenberger) writes:

In article <87************@pfaff.Stanford.EDU>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:

It's clear what should happen when swapping two buffers that
overlap completely; that is, nothing at all should happen. It is
not clear to me what should happen when swapping two buffers that
partially overlap. Any suggestions?
Undefined behavior, just like memcpy().

Seems to me like it would be more useful if it could handle
overlap.
(memcpy(), by the way, is undefined if the areas overlap, even
if they overlap completely.)

But there is also memmove() that handles overlap properly.
--
"...Almost makes you wonder why Heisenberg didn't include postinc/dec operators
in the uncertainty principle. Which of course makes the above equivalent to
Schrodinger's pointer..."
--Anthony McDonald

[Brett Frankenberger]

In article <87************@pfaff.Stanford.EDU>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:

rb*@panix.com (Brett Frankenberger) writes:

In article <87************@pfaff.Stanford.EDU>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:

>It's clear what should happen when swapping two buffers that
>overlap completely; that is, nothing at all should happen. It is
>not clear to me what should happen when swapping two buffers that
>partially overlap. Any suggestions?

Undefined behavior, just like memcpy().

Seems to me like it would be more useful if it could handle
overlap.

Maybe just the degenerate case of complete overlap, which is easy to
take care of (if (c1==c2) return;).

(memcpy(), by the way, is undefined if the areas overlap, even
if they overlap completely.)

But there is also memmove() that handles overlap properly.

In the case of partial overlap, what would be the "proper" thing for
memswap() to do.

-- Brett

[Ben Pfaff]

rb*@panix.com (Brett Frankenberger) writes:

In article <87************@pfaff.Stanford.EDU>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:

rb*@panix.com (Brett Frankenberger) writes:

In article <87************@pfaff.Stanford.EDU>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:
>It's clear what should happen when swapping two buffers that
>overlap completely; that is, nothing at all should happen. It is
>not clear to me what should happen when swapping two buffers that
>partially overlap. Any suggestions?

Undefined behavior, just like memcpy().

Seems to me like it would be more useful if it could handle
overlap.

Maybe just the degenerate case of complete overlap, which is easy to
take care of (if (c1==c2) return;).

(memcpy(), by the way, is undefined if the areas overlap, even
if they overlap completely.)

But there is also memmove() that handles overlap properly.

In the case of partial overlap, what would be the "proper" thing for
memswap() to do.

Why are you asking me the same question that I originally asked?
We are going in circles.
--
"When in doubt, treat ``feature'' as a pejorative.
(Think of a hundred-bladed Swiss army knife.)"
--Kernighan and Plauger, _Software Tools_

[Arthur J. O'Dwyer]

On Thu, 7 Aug 2003, Ben Pfaff wrote:

rb*@panix.com (Brett Frankenberger) writes:

Ben Pfaff <bl*@cs.stanford.edu> wrote:

rb*@panix.com (Brett Frankenberger) writes:
> Ben Pfaff <bl*@cs.stanford.edu> wrote:
> >It's clear what should happen when swapping two buffers that
> >overlap completely; that is, nothing at all should happen. It is
> >not clear to me what should happen when swapping two buffers that
> >partially overlap. Any suggestions?
>
> Undefined behavior, just like memcpy().

Seems to me like it would be more useful if it could handle
overlap.

In the case of partial overlap, what would be the "proper" thing for
memswap() to do[?]

Why are you asking me the same question that I originally asked?
We are going in circles.

Probably as a rhetorical device. What *do* you expect the output
of memswap(p,q,10) to be, given
ABCDEFGHIJKLMNOPQRSTUVWXYZ
^ ^
p q

Since there's no reasonable answer, the answer must be "undefined
behavior."

-Arthur

[Eric Sosman]

"Arthur J. O'Dwyer" wrote:

[...]
Probably as a rhetorical device. What *do* you expect the output
of memswap(p,q,10) to be, given

ABCDEFGHIJKLMNOPQRSTUVWXYZ
^ ^
p q
AGHIJKLMNOPQRSTUVWXYZBCDEF
Since there's no reasonable answer, the answer must be "undefined
behavior."

Reasonability dwells with Beauty: in the eye of
the beholder.

--
Er*********@sun.com

[Kevin Bracey]

In message <vj************@corp.supernews.com>
Derk Gwen <de******@HotPOP.com> wrote:

Note that putting & in front of variable usually forces the variable into
memory and not permit it to live in a register. Perhaps the compiler can
decide it doesn't really need the address and allow register allocation,
but this could also cost far more than the possible optimisation of this
one operation.

I can't speak for any other compilers, but the Norcroft compiler I'm familiar
with does try very hard to prevent automatic variables having their
"address-taken" property set unnecessarily, because of the performance hit
that results from it.

This includes using CSE analysis to elide pointers and addresses, specific
elimination of pointers to local variables passed into inlined functions,
making sure array subscripting doesn't inherently address-take, and a final
rescan to check the "address" pseudo-instruction hasn't been optimised out of
the function altogether.

Any compiler that can strongly optimise non-address-taken variables would
benefit from such pains being taken; "&" in itself shouldn't push something
out of a register.

In our case it's worth worrying about structures as well as scalars, as if
the structure doesn't have its address taken, we can perform structure
splitting (treating the structure as multiple independent
register-allocatable variables).

--
Kevin Bracey, Principal Software Engineer
Tematic Ltd Tel: [phone]
182-190 Newmarket Road Fax: [phone]
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/

[Arthur J. O'Dwyer]

On Fri, 8 Aug 2003, Eric Sosman wrote:

"Arthur J. O'Dwyer" wrote:

[...]
Probably as a rhetorical device. What *do* you expect the output
of memswap(p,q,10) to be, given

ABCDEFGHIJKLMNOPQRSTUVWXYZ
^ ^
p q
AGHIJKLMNOPQRSTUVWXYZBCDEF

^ ^
p q
Reasonability dwells with Beauty: in the eye of
the beholder.

Agreed, but I assume you must be joking about the
"reasonableness" of the above answer. How did the
letter 'B' get moved from address (p+0) to address
(p+20), for example?

If you're not joking, you're gonna have to explain
your algorithm. :-)

-Arthur