evaluate a generic swap function

[Stanley Rice]

Hello all

I wrote a "generic" swap function, which can swap some type, such as
int, double, long. But I don't know how to evaluate this function, and
don't know whether it's a good idea to use such a function. I hope you
can give me some suggestions.

void swap(void *left, void *right, size_t siz)
{
char *buf;

buf = (char *)malloc(sizeof(*buf) * siz);

memcpy(buf, left, siz);
memcpy(left, right, siz);
memcpy(right, buf, siz);

free(buf);
}

call this function in the following ways:
int a = 5;
int b = 4;
swap(&a, &b, sizeof(a));

Thanks.

 

[jacob navia]

Le 20/09/11 15:51, Stanley Rice a écrit :
in standard C:

void swap(void *left, void *right, size_t siz)
{
char buf[siz];

memcpy(buf, left, siz);
memcpy(left, right, siz);
memcpy(right, buf, siz);
}

 

[Jens Thoms Toerring]

Le 20/09/11 15:51, Stanley Rice a écrit :
in standard C:

void swap(void *left, void *right, size_t siz)
{
char buf[siz];

memcpy(buf, left, siz);
memcpy(left, right, siz);
memcpy(right, buf, siz);
}

One word of caution: this is standard C according to the 1999
standard, variable length arrays weren't part of the 1989 C
standard. If you want to cater also for C89 compiler, i.e.
use your original code, I would drop the cast from this line

buf = (char *)malloc(sizeof(*buf) * siz);

buf = malloc( sizeof *buf * siz );

will do nicely unless you forgot to include <stdlib.h>.
(Note also that you don't need the parentheses around
'*buf' after 'sizeof', they are only needed if you take
the size of a type.)

You also might consider testing if malloc() suceeded by
checking that 'buf' has't been set to NULL. Of course,
the question then is on how to proceed. The way it's
written now the program would crash the program. You
could instead give the function a return value and re-
turn something indicating an error. Or you could use a
slower method for the swapping where you copy only smal-
ler parts of the data with a fixed size buffer in a loop.
Depends on how "bullet-proof" you need this function to
be.
Regards Jens

 

[Malcolm McLean]

Hello all

I wrote a "generic" swap function, which can swap some type, such as
int, double, long. But I don't know how to evaluate this function, and
don't know whether it's a good idea to use such a function. I hope you
can give me some suggestions.

The function calls malloc to allocate a temporary buffer. This means
that it's vulnerable to failure. It's also likely to be inefficient.

You can write swap() as a byte swapping loop, which avoids the need
for a malloc(). The problem is that most calls will be to arrays of
ints or other larger types. You can probably get a 4x speed up if you
know that data is a multiple of four and aligned.
What this means is that swap() is really a function, like memcpy, best
implemented by the compiler, which can apply patches to speed up
common cases. E.g. swapping two basic types, which is an obvious use
for the function, can be turned into a sequence of three
instructions, or even sometimes eliminated altogether.

 

[ImpalerCore]

The function calls malloc to allocate a temporary buffer. This means
that it's vulnerable to failure. It's also likely to be inefficient.

You can write swap() as a byte swapping loop, which avoids the need
for a malloc(). The problem is that most calls will be to arrays of
ints or other larger types. You can probably get a 4x speed up if you
know that data is a multiple of four and aligned.
What this means is that swap() is really a function, like memcpy, best
implemented by the compiler, which can apply patches to speed up
common cases. E.g. swapping two basic types, which is an obvious use
for the function,  can be turned into a sequence of three
instructions, or even sometimes eliminated altogether.

One method to consider is to write macros to declare the function
prototype and definition of a swap specialized to the type.

\code snippet
#define C_SWAP_PROTO( NAME, TYPE ) void c_swap_##NAME( TYPE* left,
TYPE* right )

#define C_SWAP_IMPL( NAME, TYPE ) \
void c_swap_##NAME( TYPE* left, TYPE* right ) \
{ \
TYPE tmp; \
\
tmp = *left; \
*left = *right; \
*right = tmp; \
}
\endcode

Then, if one wants to swap a particular type, they declare the
prototype and definition where needed and use the generated function
name to swap the objects. The advantage is that in a library setting,
one can create a generic template for a swap without the need to
maintain an arbitrary list of swap functions, like c_swap_int,
c_swap_long, c_swap_my_struct, etc.

The reason for the 'NAME' attribute is that types with spaces in them
obviously cause problems in the function prototypes. You could use
them like the following.

\code snippet
#include <stdio.h>
#include <stdlib.h>

C_SWAP_PROTO( uint, unsigned int );

int main( void )
{
unsigned int u1 = 10;
unsigned int u2 = 20;

c_swap_uint( &u1, &u2 );

printf( "[u1,u2] = [%u,%u]\n", u1, u2 );

return EXIT_SUCCESS;
}

/* Important to *not* add the semicolon after the IMPL macro */
C_SWAP_IMPL( uint, unsigned int )
\endcode

I fully acknowledge that some may consider this "function template" a
coding horror. But at the same time, I have found this kind of setup
very convenient from a maintenance perspective.

Best regards,
John D.

 

[jacob navia]

Le 20/09/11 16:29, Jens Thoms Toerring a écrit :

Le 20/09/11 15:51, Stanley Rice a écrit :
in standard C:

void swap(void *left, void *right, size_t siz)
{
char buf[siz];

memcpy(buf, left, siz);
memcpy(left, right, siz);
memcpy(right, buf, siz);
}

One word of caution: this is standard C according to the 1999
standard, variable length arrays weren't part of the 1989 C
standard.

That one is not standard anymore, it has been obsoleted by the
committee. And if Microsoft doesn't follow it it doesn't matter
really, it is their problem.

Microsoft is the only major vendor that refuses C99.

 

[Jens Thoms Toerring]

Le 20/09/11 16:29, Jens Thoms Toerring a écrit :

Le 20/09/11 15:51, Stanley Rice a écrit :
in standard C:

void swap(void *left, void *right, size_t siz)
{
char buf[siz];

memcpy(buf, left, siz);
memcpy(left, right, siz);
memcpy(right, buf, siz);
}

One word of caution: this is standard C according to the 1999
standard, variable length arrays weren't part of the 1989 C
standard.

That one is not standard anymore, it has been obsoleted by the
committee. And if Microsoft doesn't follow it it doesn't matter
really, it is their problem.

Ok, let me rephrase that to "VLAs weren't part of the pre-
vious C standard from 1989";-) And I think it might matter
to the OP if he should be using a Microsoft compiler. And
then there also seem to be a few other compilers out there
in the wild without support for VLA's - at least I got a
bug report from someone just a few days ago about the "aCC:
HP C/aC++" compiler (from 2009) under HP-UX also not accep-
ting VLAs...
Regards, Jens

 

[BartC]

I wrote a "generic" swap function, which can swap some type, such as
int, double, long. But I don't know how to evaluate this function, and
don't know whether it's a good idea to use such a function. I hope you
can give me some suggestions.

void swap(void *left, void *right, size_t siz)
{
char *buf;

buf = (char *)malloc(sizeof(*buf) * siz);

memcpy(buf, left, siz);
memcpy(left, right, siz);
memcpy(right, buf, siz);

free(buf);
}

call this function in the following ways:
int a = 5;
int b = 4;
swap(&a, &b, sizeof(a));

What are the most common things to swap? If they are basic types such as
ints or chars, then your function will be inefficient, if you're planning to
do a lot of swapping. You also have to consider than malloc() calls are
costly, and subject to failure.

Since you will usually know what types of being swapped, it wouldn't be
difficult to add a few streamlined versions of swap(): swap_int(),
swap_double(), etc.

Or the size can be tested inside swap(), and values such as 4 or 8 can be
identified and deal with quickly without any allocations.

Also, if the size of the type is often going to be small, you might want to
just use a fixed-size buffer, such as:

char buf_fixed[256];

and use that, without any memory management, if the size happens to be <=
256, otherwise you'd need malloc(). (VLAs which someone suggested using are
also viable, if the size is not going to be so huge that you get stack
overflows.)

 

[jacob navia]

Le 20/09/11 23:20, BartC a écrit :

What are the most common things to swap? If they are basic types such as
ints or chars, then your function will be inefficient, if you're
planning to
do a lot of swapping. You also have to consider than malloc() calls are
costly, and subject to failure.

Happily the malloc calls are not needed in standard C.

 

[Ben Bacarisse]

Le 20/09/11 23:20, BartC a écrit :

Happily the malloc calls are not needed in standard C.

You don't need them in C90 either:

#define CHUNK_SIZE 512

void swap(void *vp1, void *vp2, size_t size)
{
char *cp1 = vp1, *cp2 = vp2;
do {
char tmp[CHUNK_SIZE];
size_t csz = size > CHUNK_SIZE ? CHUNK_SIZE : size;
memcpy(tmp, cp1, csz);
memcpy(cp1, cp2, csz);
memcpy(cp2, tmp, csz);
dst += csz;
src += csz;
} while (size -= csz);
}

(untested).

 

[Keith Thompson]

Ok, let me rephrase that to "VLAs weren't part of the pre-
vious C standard from 1989";-) And I think it might matter
to the OP if he should be using a Microsoft compiler. And
then there also seem to be a few other compilers out there
in the wild without support for VLA's - at least I got a
bug report from someone just a few days ago about the "aCC:
HP C/aC++" compiler (from 2009) under HP-UX also not accep-
ting VLAs...

VLAs are part of the *current* standard, C99.

In the latest draft of the *next* standard (which as yet has
no official status), VLAs are still part of the language, but
support for them is optional; an implementation may define the
macro __STDC_NO_VLA__ to indicate that it doesn't support them.

And of course the previous standard, C90, is still of considerable
significance; ISO says it's obsolete, but not everyone listens
to ISO.

 

[Eric Sosman]

Hello all

I wrote a "generic" swap function, which can swap some type, such as
int, double, long. But I don't know how to evaluate this function, and
don't know whether it's a good idea to use such a function. I hope you
can give me some suggestions.

void swap(void *left, void *right, size_t siz)
{
char *buf;

buf = (char *)malloc(sizeof(*buf) * siz);

The cast is harmless but unnecessary. And since you're already
assuming that `siz' is a byte count, the multiplication by unity is
also unnecessary, although harmless. Just saying.

memcpy(buf, left, siz);

If malloc() fails to deliver the requested amount of memory and
returns NULL, you'll be in trouble. You'd be in even worse trouble
using a C99 variable-length array instead of calling malloc(), because
malloc() can at least tell you when it fails, while a VLA cannot. Also,
malloc(0) is well-defined, while a VLA of zero elements is a constraint
violation. ("Swapping" two zero-length objects is something of a corner
case, it's true, but functions should behave nicely in the corners if
possible: consider the memxxx() functions with zero size.)

memcpy(left, right, siz);
memcpy(right, buf, siz);
free(buf);
}

call this function in the following ways:
int a = 5;
int b = 4;
swap(&a,&b, sizeof(a));

Although your function will work (if malloc() succeeds), I don't
think it's very attractive. An operation is worth encapsulating in
a utility function if it's difficult or tricky in some way, or if the
function can somehow perform the operation more cheaply or conveniently
than free-hand code. I doubt that this particular function scores on
either point: It encapsulates a simple operation, and probably uses
more time and memory than a simple implementation would.

 

[Gene]

Hello all

I wrote a "generic" swap function, which can swap some type, such as
int, double, long. But I don't know how to evaluate this function, and
don't know whether it's a good idea to use such a function. I hope you
can give me some suggestions.

 void swap(void *left, void *right, size_t siz)
{
    char *buf;

    buf = (char *)malloc(sizeof(*buf) * siz);

    memcpy(buf, left, siz);
    memcpy(left, right, siz);
    memcpy(right, buf, siz);

    free(buf);

}

call this function in the following ways:
    int a = 5;
    int b = 4;
    swap(&a, &b, sizeof(a));

Others have mentioned but not shown how you could implement this
without the potentially large and failure-prone buffer:

void swap(void *left, void *right, size_t siz)
{
char *p = left, *q = right;
while (siz--) {
char t = *p;
*p = *q;
*q = t;
p++; q++;
}
}

With a decent compiler (gcc included), this will be nicely optimized
to move as many bytes as possible with aligned word operations.

And if you say something like:

int a = 2, b = 1;
swap(&a, &b, sizeof a);

The generated code resulting from automatic inlining will be nearly
identical to what you'd get for

int a = 2, b = 1;
int t = a; a = b; b = t;

So back to your original question, it's fine to use a generic swap if
you avoid the malloc().

 

[Malcolm McLean]

An operation is worth encapsulating in
a utility function if it's difficult or tricky in some way, or if the
function can somehow perform the operation more cheaply or conveniently
than free-hand code. id

temp = a;
a = b;
b = temp;

or

swap(&a, &b, sizeof(int));

I think there's a case for the second. In reality it would be embedded
in some tedious logic which requires variables to be swapped, and
anything that makes such code more readable is a plus.

 

[Kenny McCormack]

And of course the previous standard, C90, is still of considerable
significance; ISO says it's obsolete, but not everyone listens
to ISO.

Hold the phone there, Kiki my boy!

If we admit that it is possible to not listen to ISO, then doesn't the whole
raison d'etre of this newsgroup fade away?

--
"The anti-regulation business ethos is based on the charmingly naive notion
that people will not do unspeakable things for money." - Dana Carpender

Quoted by Paul Ciszek (pciszek at panix dot com). But what I want to know
is why is this diet/low-carb food author doing making pithy political/economic
statements?

Nevertheless, the above quote is dead-on, because, the thing is - business
in one breath tells us they don't need to be regulated (which is to say:
that they can morally self-regulate), then in the next breath tells us that
corporations are amoral entities which have no obligations to anyone except
their officers and shareholders, then in the next breath they tell us they
don't need to be regulated (that they can morally self-regulate) ...

 

[Malcolm McLean]

If we admit that it is possible to not listen to ISO, then doesn't the whole
raison d'etre of this newsgroup fade away?

Not really. C90 C code will run pretty much anywhere. Code that is not
conforming might work in most places, or it might only be useful for
that particular platform. I got bitten by slash slash comments, I
thought that by now it was surely safe to assume they would be
accepted by any compiler. As it turned out, my very next compiler
wouldn't accept them.

I divide my code into four units; this program only, this platform
only, this platform only, many programs, this program only, any
platform, and many programs, many platforms. That helps with porting,
it helps with resusing code, and it helps with keeping the design
clean. Code in the second two sections should conform to ISO, code in
the first two doesn't have to. However if you want a GUI, then you
have to accept at least some code in the first two sections.

 

[jacob navia]

Le 21/09/11 17:45, Kenny McCormack a écrit :

Hold the phone there, Kiki my boy!

If we admit that it is possible to not listen to ISO, then doesn't the whole
raison d'etre of this newsgroup fade away?

Of course this is the same guy that always has the word
"the C standard exists for a reason"... to be held against
anybody that disagrees with him...

 

[Kenny McCormack]

Le 21/09/11 17:45, Kenny McCormack a écrit :

Of course this is the same guy that always has the word
"the C standard exists for a reason"... to be held against
anybody that disagrees with him...

Yup. Now, obviously, there are ways to weasel out of this and explain how
what he wrote isn't really a repudiation of everything he stands for, but
the fact remains that I think I was hardly alone in being shocked and amazed
to hear those words from his mouth (*).

(*) Metaphorically speaking, of course...

--
(This discussion group is about C, ...)

Wrong. It is only OCCASIONALLY a discussion group
about C; mostly, like most "discussion" groups, it is
off-topic Rorsharch [sic] revelations of the childhood
traumas of the participants...

 

[Jack Foot]

Yup. Now, obviously, there are ways to weasel out of this and explain
how what he wrote isn't really a repudiation of everything he stands
for, but the fact remains that I think I was hardly alone in being
shocked and amazed to hear those words from his mouth (*).

I sure reckon the difference this time is that Jacob was taking the part
of ISO. For some reason Keith seems to have a strange obsession with
Jacob, and he's obviously willing to abandon his principles if that lets
him get in a cheap attack on Jacob.

Sad...

 

[Seebs]

I wrote a "generic" swap function, which can swap some type, such as
int, double, long. But I don't know how to evaluate this function, and
don't know whether it's a good idea to use such a function. I hope you
can give me some suggestions.
Okay.

void swap(void *left, void *right, size_t siz)
{
char *buf;

buf = (char *)malloc(sizeof(*buf) * siz);

1. Don't cast the return of malloc in C.
2. I wouldn't do this. I'd just iterate through swapping the bytes
individually.

{
unsigned char u;
unsigned char *l = left;
unsigned char *r = right;
for (int i = 0; i < siz; ++i) {
u = *l;
*l = *r;
*r = u;
++l;
++r;
}
}

Slow? Maybe. But:

1. I don't have any data showing that I need to optimize this function
more.
2. malloc() is usually VERY expensive compared to most stuff I do.

-s