Swap Byte

Hello,

Help needed to optimize following program.

Code:

	int num,i, byte =0;

	printf(" Enter the number\n");
	scanf("%d",&num);
	printf("Number is %x\n",num);
	
	i = 0;
	
	do
	{
		if (num%2)
		{
			byte = byte << 1;
			byte |= 0x01;
		}
		else
			byte = byte << 1;

		num = num>>1; 
		i++;
	} while(i&7);
	printf("Reversed number = %x and %d \n",byte, i);
}

Thanks,
Tiger

For simple optimization, you want to avoid division and mod. Both are considered slow.

I'm on the phone now, so I'll add a bit more later.

[edit]
Additionally, you want to unrole or avoid loops completely. They're also considered slower than non-loops.
[/edit]

Quzah.

What i am looking at is,

1. Loop takes 8 iterations, even if most significant bits are 0. Any logic that avoid unncessary iteration.

2. There are no division in above program. Any replcacement for mod is greately apppreciated.

Let me know.

tiger

Originally posted by Roaring_Tiger
2. There are no division in above program. Any replcacement for mod is greately apppreciated.

Yes there is. Look at your first check:

if (num%2)

Right there.

There are many ways to optimize this. You can just hard code the swaps. You can use a loop with simple bit shifting. You can create a union. Many differnt things.

Since this is fun, I'll show you the unionized method:

Code:

union byteu
{
    unsigned char byte;
    struct 
    {
        unsigned char u0:1;
        unsigned char u1:1;
        unsigned char u2:1;
        unsigned char u3:1;
        unsigned char u4:1;
        unsigned char u5:1;
        unsigned char u6:1;
        unsigned char u7:1;
    } sbyte;
};

union byteu abyte, bbyte;

abyte.byte = 123;

bbyte.sbyte.u7 = abyte.sbyte.u0;
bbyte.sbyte.u6 = abyte.sbyte.u1;
bbyte.sbyte.u5 = abyte.sbyte.u2;
bbyte.sbyte.u4 = abyte.sbyte.u3;
bbyte.sbyte.u3 = abyte.sbyte.u4;
bbyte.sbyte.u2 = abyte.sbyte.u5;
bbyte.sbyte.u1 = abyte.sbyte.u6;
bbyte.sbyte.u0 = abyte.sbyte.u7;

abyte.byte = bbyte.byte;

Vola. Swapped with 9 assignments.

Quzah.

Originally posted by Roaring_Tiger
1. Loop takes 8 iterations, even if most significant bits are 0. Any logic that avoid unncessary iteration.
2. There are no division in above program. Any replcacement for mod is greately apppreciated.

A lookup table and other techniques are suggested in the following thread. Addressing your two questions, is something like the following what you had in mind?

Code:

#include <stdio.h>
#include <limits.h>

unsigned char foo(unsigned char value)
{
    unsigned char mask = 1 << (CHAR_BIT - 1), result = 0;
    while(value) /* skip most significant bits that are zero */
    {
        if(value & 1) /* replace mod (machine dependency) */
        {
            result |= mask;
        }
        mask  >>= 1;
        value >>= 1;
    }
    return result;
}

int main(void)
{
    unsigned char value = 5;
    printf("value = %X, reversed = %X\n", value, foo(value));
    return 0;
}

/* my output
value = 5, reversed = A0
*/

Thanks

Originally posted by quzah
Yes there is. Look at your first check:

if (num%2)

Right there.

There are many ways to optimize this. You can just hard code the swaps. You can use a loop with simple bit shifting. You can create a union. Many differnt things.

Since this is fun, I'll show you the unionized method:

Code:

union byteu
{
    unsigned char byte;
    struct 
    {
        unsigned char u0:1;
        unsigned char u1:1;
        unsigned char u2:1;
        unsigned char u3:1;
        unsigned char u4:1;
        unsigned char u5:1;
        unsigned char u6:1;
        unsigned char u7:1;
    } sbyte;
};

union byteu abyte, bbyte;

abyte.byte = 123;

bbyte.sbyte.u7 = abyte.sbyte.u0;
bbyte.sbyte.u6 = abyte.sbyte.u1;
bbyte.sbyte.u5 = abyte.sbyte.u2;
bbyte.sbyte.u4 = abyte.sbyte.u3;
bbyte.sbyte.u3 = abyte.sbyte.u4;
bbyte.sbyte.u2 = abyte.sbyte.u5;
bbyte.sbyte.u1 = abyte.sbyte.u6;
bbyte.sbyte.u0 = abyte.sbyte.u7;

abyte.byte = bbyte.byte;

Vola. Swapped with 9 assignments.

Quzah.

Kudos, Quzah.

That was a great solution.

I rarely find the use of bitfields to be an optimization when it comes to speed because what appears to be a simple assignment is often implmented by masking and shifting. For example,

Code:

   ;
   ;        b.sbyte.u5 = a.sbyte.u2;
   ;
        mov       cl,byte ptr [ebp-1]
        shr       ecx,2
        and       ecx,1
        and       cl,1
        shl       ecx,5
        mov       dl,byte ptr [eax]
        and       dl,-33
        or        cl,dl
        mov       byte ptr [eax],cl

Bitfields may pack data more tightly, but this size benefit may be taken at the cost of speed. Some exceptions might be on architectures that actually have bit-addressable memory in which an assignment would be an assignment.

I had run a little comparison, which is less than perfect, but is as follows.

Code:

#include <stdio.h>
#include <limits.h>
#include <time.h>

unsigned char foo(unsigned char value)
{
    unsigned char mask = 1 << (CHAR_BIT - 1), result = 0;
    while ( value ) /* skip most significant bits that are zero */
    {
        if ( value & 1 ) /* replace mod (machine dependency) */
        {
            result |= mask;
        }
        mask  >>= 1;
        value >>= 1;
    }
    return result;
}

unsigned char bar(unsigned char num)
{
    unsigned char byte = 0;
    int i = 0;
    do
    {
        if ( num % 2 )
        {
            byte = byte << 1;
            byte |= 0x01;
        }
        else
            byte = byte << 1;

        num = num >> 1;
        i++;
    } while ( i & 7 );
    return byte;
}

unsigned char baz(unsigned char value)
{
    union byteu
    {
        unsigned char byte;
        struct
        {
            unsigned char u0:1;
            unsigned char u1:1;
            unsigned char u2:1;
            unsigned char u3:1;
            unsigned char u4:1;
            unsigned char u5:1;
            unsigned char u6:1;
            unsigned char u7:1;
        } sbyte;
    } a, b;

    a.byte = value;

    b.sbyte.u7 = a.sbyte.u0;
    b.sbyte.u6 = a.sbyte.u1;
    b.sbyte.u5 = a.sbyte.u2;
    b.sbyte.u4 = a.sbyte.u3;
    b.sbyte.u3 = a.sbyte.u4;
    b.sbyte.u2 = a.sbyte.u5;
    b.sbyte.u1 = a.sbyte.u6;
    b.sbyte.u0 = a.sbyte.u7;

    return b.byte;
}

#define CYCLES 100000000

int main(void)
{
    const char *name[] = { "foo", "bar", "baz" };
    unsigned char (*const function[])(unsigned char) = { foo, bar, baz };
    unsigned char value = 5;
    size_t i,j;
    printf("foo(%X) = %X\n", value, foo(value));
    printf("bar(%X) = %X\n", value, bar(value));
    printf("baz(%X) = %X\n", value, baz(value));
    fflush(stdout);
    for ( i = 0; i < sizeof(function)/sizeof(*function); ++i )
    {
        clock_t end, start = clock();
        for ( j = 0; j < CYCLES; ++j )
        {
            function [ i ] (j);
        }
        end = clock();
        printf("%s = %f\n", name [ i ], (end - start) / CLOCKS_PER_SEC);
        fflush(stdout);
    }

    return 0;
}

Here are the results I obtained.

Code:

foo(5) = A0
bar(5) = A0
baz(5) = A0
foo = 9.614000
bar = 12.738000
baz = 17.766000

If optimizing for speed was the goal, this bitfields implementation was 39% slower than the original.

[OT]
>Vola.
Perhaps you mean voilà.
[/OT]

Code:

union byteu
{
    unsigned char byte;
    struct
    {
        unsigned char u0:1;
        unsigned char u1:1;
        unsigned char u2:1;
        unsigned char u3:1;
        unsigned char u4:1;
        unsigned char u5:1;
        unsigned char u6:1;
        unsigned char u7:1;
    } sbyte;
};

Just an aside, but bitfields have to be either signed or unsigned int, or _Bool for C99 :-)

Originally posted by Dave_Sinkula

[snipped example]
If optimizing for speed was the goal, this bitfields implementation was 39% slower than the original.

You have made MSVC++6 very very unhappy. It compiles but generates a runtime error for me.

Originally posted by Dave_Sinkula

[OT]
>Vola.
Perhaps you mean voilà.
[/OT]

Hm. Yep. I didn't think it had an I in it.

Quzah.

Originally posted by quzah
You have made MSVC++6 very very unhappy. It compiles but generates a runtime error for me.

So it does.

[/EDIT]
I had gotten used to Borland, which has CLOCKS_PER_SEC like this.

Code:

#define CLOCKS_PER_SEC 1000.0

I found that MSVC does it differently.

Code:

#define CLOCKS_PER_SEC 1000

So I shouldn't be trusting that CLOCKS_PER_TICK will trigger an implicit conversion to floating point in code such as this.

Code:

        printf("%s = %f\n", name[i], (end - start) / CLOCKS_PER_SEC);

It needs a cast to ensure portability.
[/EDIT]

And once that has been fixed it shows that MSVC seems to do a much better job than Borland optimizing with bitfields.

Code:

foo(5) = A0
bar(5) = A0
baz(5) = A0
foo = 45.004000
bar = 43.082000
baz = 16.133000

Quzahs solution completes the task in less than a dozen operations - all of them assignment, none are comparisons either. That is what makes this solution superior. You have comparisons for loop bounds, lots of arithametic and so forth, which make for a more intensive program and hence, longer code segments, more register accesses, long math, etc.

Originally posted by Sebastiani
Quzahs solution completes the task in less than a dozen operations - all of them assignment, none are comparisons either. That is what makes this solution superior. You have comparisons for loop bounds, lots of arithametic and so forth, which make for a more intensive program and hence, longer code segments, more register accesses, long math, etc.

I guess you missed a point I was trying to make: this solution may be "superior" on one implementation, and inferior on another (as in the example I gave).

Two specific questions Roaring_Tiger asked were how to avoid unnecessary loop iterations and how to avoid a division. These were the points I addressed. Since quzah already showed an alternate approach, I tried to answer Roaring_Tiger's question as posted -- and offered a comparison to quzah's code. Note that in the implementation I tested, the loop with comparisons was faster than the bitfields. Surely this is a quality of implementation issue, but definitely something worth mention.

If you really want to trim things down to minimal operations, why ignore the lookup table approach found in the link I posted? There you would have only one assignment. Or using similarly unrolled loops, the comparisons and explicit shift operations may be faster than bitfield assignment. On not. Again, I find it relevant to at least mention this.

Generalizing that certain C contructs will always generate optimum code is not a wise thing to do.

This is my change to function 2 to use a lookup table. It scored horribly depending on the implementation:

Code:

unsigned char bar(unsigned char num)
{
    unsigned char table[256] =
    {
        ... table here ...
    };
    return table[num];
}

Using a global variable or declaring the array as static gives nearly a 2x performance boost over my initial example.

Using a non-global and non-static array, my initial example has roughly a 3x performance boost over the lookup table.

Quzah.

Hi all!

Just one question: what happened to the "standard" solution for this problem?

Code:

unsigned char quux(unsigned char value)
{
   value = ((value&0xaa)>>1) | ((value&0x55)<<1);
   value = ((value&0xcc)>>2) | ((value&0x33)<<2);
   return (value>>4) | (value<<4);
}

I found this one still a bit faster:

Code:

unsigned char quuux(unsigned char value)
{
   static unsigned char tab[16]=
         {0x0,0x8,0x4,0xc,0x2,0xa,0x6,0xe,
          0x1,0x9,0x5,0xd,0x3,0xb,0x7,0xf};
   return (tab[value&0xf]<<4) | (tab[value>>4]);
}

I got (on a 1000MHz Athlon):

Code:

foo(5) = A0
bar(5) = A0
baz(5) = A0
quux(5) = A0
quuux(5) = A0
baseline(5) = 0
foo = 9.210000
bar = 9.980000
baz = 3.340000
quux = 1.950000
quuux = 1.730000
baseline = 1.130000

Where the function baseline is obviously wrong, but shows the cost of the function call itself:

Code:

unsigned char baseline(unsigned char value)
{
   return 0;
}

If I change the inner loop to call the function quux directly, instead of indirectly, it runs in 0.6 seconds:

Code:

        volatile int result;
        clock_t end, start = clock();
        for ( j = 0; j < CYCLES; ++j )
        {
           result=quuux(j);
        }
        end = clock();

Where the variable result is marked volatile, to make sure that the compiler really calls the function quuux... (it automatically inlined the function and then optimized it out alltogether)

Have fun,
alex