Skip to contentSkip to conversation

Improved Swapping Method In sort.c

DISCUSSION Soumyadip Das Mahapatra 5 participants 6 messages Apr 30, 2008 – May 2, 2008

lore
Share & tools
lore
#0 lore raw

Hello everybody,
The swapping method (in function void u32_swap() line no.. 14 to 16) in lib/sort.c can be improved by using the following code *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a instead of the code given. This code
is not using third variable thus not consuming another memory. And I dont see any significance in
using *int size* argument. so the function should be
static void u32_swap(void *a, void *b)

{
    *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a;
}

Meet people who discuss and share your passions. Go to http://in.promos.yahoo.com/groups/bestofyahoo/

#1 lore raw
Quoted 3 lines · Soumyadip Das Mahapatra

Hello everybody, The swapping method (in function void u32_swap() line no.. 14 to 16) in lib/sort.c can be improved by using the following code *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a instead of the code given.

GCC is smart enough to optimize the current instructions into a bswap instruction or similar. While with xor, some are said to fail - and three xor operations are surely slower than a swap if there is a swap instruction.

Never heard of that?

#2 lore raw
In reply to Soumyadip Das Mahapatra
Quoted 9 lines · Soumyadip Das Mahapatra

Hello everybody,
The swapping method (in function void u32_swap() line no.. 14 to 16) in lib/sort.c can be improved by using the following code *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a instead of the code given. This code
is not using third variable thus not consuming another memory. And I dont see any significance in
using *int size* argument. so the function should be
static void u32_swap(void *a, void *b)

{
   *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a;
}

That proposal looks like buggy.

19:32 yaguchi:/dev/shm > cat ui.c
#include <stdint.h>
#include <stdio.h>

static void u32_swap(void *a, void *b)

{
        *(uint32_t *)b ^= *(uint32_t *)a 
                        ^= *(uint32_t *)b
                        ^= *(uint32_t *)a;
}

int main(void)

{
        uint32_t x = 5, y = 7;
        printf("%u %u\n", x, y);
        u32_swap(&x, &y);
        printf("%u %u\n", x, y);
}

19:32 yaguchi:/dev/shm > ./a.out
5 7
7 0

#3 lore raw
Quoted 33 lines · Jan Engelhardt
Quoted 9 lines · Soumyadip Das Mahapatra

Hello everybody,
The swapping method (in function void u32_swap() line no.. 14 to 16) in lib/sort.c can be improved by using the following code *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a instead of the code given. This code
is not using third variable thus not consuming another memory. And I dont see any significance in
using *int size* argument. so the function should be
static void u32_swap(void *a, void *b)

{
   *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a;
}

That proposal looks like buggy.

19:32 yaguchi:/dev/shm > cat ui.c
#include <stdint.h>
#include <stdio.h>

static void u32_swap(void *a, void *b)

{
        *(uint32_t *)b ^= *(uint32_t *)a 
                        ^= *(uint32_t *)b
                        ^= *(uint32_t *)a;
}

int main(void)

{
        uint32_t x = 5, y = 7;
        printf("%u %u\n", x, y);
        u32_swap(&x, &y);
        printf("%u %u\n", x, y);
}
Quoted 3 lines

19:32 yaguchi:/dev/shm > ./a.out
5 7
7 0

This happens because u32_swap has undefined behavior.

Try this instead:

static void u32_swap(void *a, void *b)

{
        *(uint32_t *)a ^= *(uint32_t *)b;
        *(uint32_t *)b ^= *(uint32_t *)a;
        *(uint32_t *)a ^= *(uint32_t *)b;
}

But still, this change to Linux is not necessary,
it actually generates worse code.

Signature · 1 line
Do what you love because life is too short for anything else.
#4 lore raw
In reply to Soumyadip Das Mahapatra
Quoted 5 lines · Soumyadip Das Mahapatra

static void u32_swap(void *a, void *b)

{
    *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a;
}

That was posted to comp.lang.c 20 years ago or more. It's not something that the compiler is likely to be able to optimize (unlike the normal swap, using a temporary variable.)

Another cute, temp-free swap, from the same era, is: b += a -= b; a = b - a.

#5 lore raw
In reply to Soumyadip Das Mahapatra
Quoted 10 lines · Soumyadip Das Mahapatra

Hello everybody,
The swapping method (in function void u32_swap() line no.. 14 to 16) in lib/sort.c can be improved by using the following code *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a instead of the code given. This code
is not using third variable thus not consuming another memory. And I dont see any significance in
using *int size* argument. so the function should be
static void u32_swap(void *a, void *b)

{
    *(u32 *)b ^= *(u32 *)a ^= *(u32 *)b ^= *(u32 *)a;
}

Not only is this invalid C, but it produces massively worse code.

-hpa