Looking for an alternative to bit shifting

[Robert C Cartaino]

jimwawar wrote:

Any ideas about a faster approach?

Probably not what you want to do in this case... but you can divide by 256, which gives me about a 5-10% improvement on my system, but I would test that with your setup. Here's probably what you want to do. You don't discuss your application but you should be able to write your application logic (the calculations and business algorithms) using the numbers as they are given to you by the hardware... as is. Do all the math, comparisons, and manipulation with respect to how the numbers are represented by the hardware. Then convert them to "normal numbers" only when they need to be presented to the end user. Here's what I mean (and I am totally making up this example): Let's say that your hardware is returning temperature data from a large series of sensors. You have to determine if the numbers are in an acceptable range (in my hyptothetical senario, 80,000 +/- 10,000 is acceptable). But the hardware gives you the data in the three-most significant bytes (it's giving you the bytes as 12 34 56 00, which is 203,569,152). So, instead of writing:

for (int probeID = 0; probeID < 1000000; probeID++)
{
int data = GetProbeData(probeID); // Get data from hardware.
data = data >> 8; // Right shift the data to fix the value.
if (data < 70000 || data > 90000)
Console.WriteLine("Value out of range: {0}", data);
}

Just write:

for (int probeID = 0; probeID < 1000000; probeID++)
{
int data = GetProbeData(probeID);
if (data < 17920000 || data > 23040000)
Console.WriteLine("Value out of range: {0}", data >> 8);
}

That assumes that most of the processing time is spent gathering and manipulating the data and not displaying it, which is typically the case. Oh, and I would probably keep all the number in hex (in the source code) so you can avoid all the conversions: 12 34 56 00 (from hardware) = 203569152 (0x0c223800 in hex) 00 12 34 56 (what you want) = 795192 (0x000c2238 in hex, **easier to visualize the bytes**) Enjoy, Robert C. Cartaino

[PIEBALDconsult]

How do you get the data?

[Guffa]

If performance is the first priority, use unsafe code to access the array using a byte pointer. Something like:

fixed (byte* p = &theArray) {
for (int i = 0; i < theArray.Length; i++) {
p++; // skip bits 0-7
byte lo = *(p++); // get bits 8-15
byte mid = *(p++); // get bits 16-23
byte hi = *(p++); // get bits 24-31
// do something with the values?
}
}

Despite everything, the person most likely to be fooling you next is yourself.

[PIEBALDconsult]

I was thinking of something similar; effectively using the byte preceding the array as the first byte, easy enough in C, but I don't think it would work in .net. If he's reading bytes from a socket or similar, it's not a big deal.

[Guffa]

PIEBALDconsult wrote:

using the byte preceding the array as the first byte

You mean to effectively shifting the int value by eight bits? There might be performance problems with accessing an int on an odd adress, so it would probably be faster to just shift the value, and it certainly is simpler.

Despite everything, the person most likely to be fooling you next is yourself.

[PIEBALDconsult]

Guffa wrote:

shifting the int value

Shifting the entire array at once, but without actually moving it.

Guffa wrote:

and it certainly is simpler

Yeah, I'd just stick with the right shift and be done with it. It comes down to: "If performance is important, don't use .net." Edit: I was thinking backward; I meant skip the first byte. I've now tried it in C, I just need to decide how I want to handle the last int.

modified on Saturday, August 2, 2008 1:23 PM

[PIEBALDconsult]

Here's what I just worked up in C, I still have compared it with shifting each int:

int masks[] = { 0xFFFFFFFF , 0x00FFFFFF , 0x0000FFFF , 0x000000FF } ;

int
ShiftAndSumArray
(
int* Array
,
unsigned Length
,
unsigned Shift
)
{
int result = 0 ;

int\* a = (int\*) ( ((char\*) Array) + ( Shift %= sizeof(int) ) ) ;

unsigned i ;

for ( i = 0 ; i < Length-1 ; i++ )
{
    result += a \[ i \] ;
}

result += a \[ i \] & masks \[ Shift \] ;

return ( result ) ;

}

int a[] = { 0x00000100 , 0x00000100 , 0x00000100 , 0x00000100 } ;

printf ( "%d\n" , ShiftAndSumArray ( a , 4 , 1 ) ) ;

It may be possible in C#, but I haven't tried it.

[PIEBALDconsult]

Ha ha ha! Here it is in C#

private static readonly int[] masks = unchecked ( new int[] { (int) 0xFFFFFFFF , 0x00FFFFFF , 0x0000FFFF , 0x000000FF } ) ;

public static unsafe int
ShiftAndSumArray
(
int[] Array
,
uint Shift
)
{
int result = 0 ;

fixed ( int\* b = Array )
{
    int\* a = (int\*) ( ((byte\*) b) + ( Shift %= sizeof(int) ) ) ;
    int  i ;
             
    for ( i = 0 ; i < Array.Length-1 ; i++ )
    {
        result += a \[ i \] ;
    }

    result += a \[ i \] & masks \[ Shift \] ;
}
         
return ( result ) ;

}

This appears to take about half the time of shifting each int separately, but it doesn't involve very much time either way; 100,000,000 (10,000 passes across an array of 10,000 ints) this way takes 507 milliseconds, the shifting technique takes 969 milliseconds. (And 2665 milliseconds for the division technique.)

public static int
ShiftAndSumArray2
(
int[] Array
,
uint Shift
)
{
int result = 0 ;

int shift = (int) Shift % sizeof(int) \* 8 ;

// Using foreach is not much slower 
for ( int i = 0 ; i < Array.Length ; i++ )
{
    result += Array \[ i \] >> shift ;
}            

return ( result ) ;

}

Correction: Earlier I had forgotten to Reset the Stopwatch :doh: , corrected results 457 milliseconds for altered pointer 459 milliseconds for shifted values 1768 milliseconds for division I have also quickened up the implementations somewhat.

[PIEBALDconsult]

Robert.C.Cartaino wrote:

about a 5-10% improvement

On mine it took more than twice four times as long.

modified on Saturday, August 2, 2008 6:03 PM

[Guffa]

I made a few performance tests, and it looks like my suspicion about accessing ints on an odd address was correct. It takes slightly longer (about 3%) to access the value using an adjusted pointer compared to just getting the value from the array and shifting it.

Despite everything, the person most likely to be fooling you next is yourself.