Speed Freaks & Bit Fiddlers: Can you make this go faster?

  • Thread starter Thread starter Russell Mangel
  • Start date Start date
R

Russell Mangel

Can someone show me how to speed this up?

1. Whats the fastest way for Unsafe C#?
2. What the fastest way for Safe C#?

public static Int64 ToInt64(Int32 low, Int32 high)
{
Byte[] lowBytes = BitConverter.GetBytes(low);
Byte[] highBytes = BitConverter.GetBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowBytes, 0, bytes, 4, 4);
Array.Copy(highBytes, 0, bytes, 0, 4);

return BitConverter.ToInt64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.
 
How about:
public static Int64 ToInt64(Int32 low, Int32 high)
{
Int64 x = high;
x <<= 32;
x = x | low;
}
 
Geee...

Thats slow ;)

Try this

public static Int64 FastToInt64(Int32 low, Int32 high)

{

return ((Int64)(high) << 32) + low;

}
 
Or, in one line (safe C#):

return (Int64)(((UInt64)high << 32) | (UInt32)low);

Tom Dacon
Dacon Software Consulting
 
public static Int64 ToInt64(Int32 low, Int32 high)
{
Int64 x = high;
x <<= 32;
x = x | low;
}[/QUOTE]

Quite, except that Russell's definition of 'low' and 'high' may be
surprising... The output that I get, with the first line from Russell's
function, I get:

low & high = result
11223344 & aabbccdd = 11223344aabbccdd
11223344 & aabbccdd = 11223343aabbccdd
11223344 & aabbccdd = 11223343aabbccdd

So low is (Intel-wise) high, and high low... :-)

Out of interest I created two slighty different methods of doing it:
public static Int64 Alan1_ToInt64(Int32 low, Int32 high)
{
const Int64 Bit32 = 0x100000000;
System.Diagnostics.Debug.Assert(Bit32 == (0x1L + UInt32.MaxValue));
System.Diagnostics.Debug.Assert(Bit32 == (0x1L << 32));
Int64 result = high + Bit32 * low;
return result;
}

public static Int64 Alan2_ToInt64(Int32 low, Int32 high)
{
Int64 result = high | ((Int64)low << 32);
return result;
}

And on inspecting the disassembly of both, assuming my unqualified
reading of x86 assembler is correct, both are JITted to a x86 shift
operation... So chose either depending on which is more
'understandable'.

Then I re-looked at my results and saw in the latter two lines: 11, 22,
33, 43!!!! WTF?


The I inputted all the functions that have been posted here so far, and
I get:

low & high = result
11223344 & aabbccdd = 11223344aabbccdd
11223344 & aabbccdd = 11223343aabbccdd
11223344 & aabbccdd = 11223343aabbccdd
11223344 & aabbccdd = aabbccdd11223344
11223344 & aabbccdd = aabbccdd11223344
11223344 & aabbccdd = aabbccdd11223344

low & high = result
aabbccdd & 11223344 = aabbccdd11223344
aabbccdd & 11223344 = aabbccdd11223344
aabbccdd & 11223344 = aabbccdd11223344
aabbccdd & 11223344 = ffffffffaabbccdd
aabbccdd & 11223344 = ffffffffaabbccdd
aabbccdd & 11223344 = 11223343aabbccdd

!!! It's past my bedtime, so I leave it for someone else to explain...
Unless I've got a buggy CPU, and only I get this behaviour. I haven't
gone back an re-inspected the assembler for instance.

The code it thus:
{
public void DoIt()
{
const Int32 low = 0x11223344, high =
unchecked((Int32)0xaabbccdd);
DoItWith(low, high);
const Int32 high2 = 0x11223344, low2 =
unchecked((Int32)0xaabbccdd);
DoItWith(low2, high2);
}

private static void DoItWith(Int32 low, Int32 high)
{
Console.WriteLine("{0,8} & {1,8} = {2}", "low", "high",
"result");
Console.WriteLine("{0:x} & {1:x} = {2:x}", low, high,
RussellsOriginal_ToInt64(low, high));
Console.WriteLine("{0:x} & {1:x} = {2:x}", low, high,
Alan1_ToInt64(low, high));
Console.WriteLine("{0:x} & {1:x} = {2:x}", low, high,
Alan2_ToInt64(low, high));
Console.WriteLine("{0:x} & {1:x} = {2:x}", low, high,
TimClark_ToInt64(low, high));
Console.WriteLine("{0:x} & {1:x} = {2:x}", low, high,
TimClark_ToInt64(low, high));
Console.WriteLine("{0:x} & {1:x} = {2:x}", low, high,
rdrunner_FastToInt64(low, high));
}

public static Int64 Alan1_ToInt64(Int32 low, Int32 high)
{
const Int64 Bit32 = 0x100000000;
System.Diagnostics.Debug.Assert(Bit32 == (0x1L +
UInt32.MaxValue));
System.Diagnostics.Debug.Assert(Bit32 == (0x1L << 32));
Int64 result = high + Bit32 * low;
return result;
}

public static Int64 Alan2_ToInt64(Int32 low, Int32 high)
{
Int64 result = high + ((Int64)low << 32);
return result;
}

public static Int64 TimClark_ToInt64(Int32 low, Int32 high)
{
Int64 x = high;
x <<= 32;
// Warning: Bitwise-or operator used on a sign-extended
operand; consider casting to a smaller unsigned type first
x = x | low;
return x;
}

public static Int64 rdrunner_FastToInt64(Int32 low, Int32 high)
{
return ((Int64)(high) << 32) + low;
}

public static Int64 TomDacon_ToInt64(Int32 low, Int32 high)
{
return (Int64)(((UInt64)high << 32) | (UInt32)low);
}

public static Int64 RussellsOriginal_ToInt64(Int32 low, Int32
high)
{
Byte[] lowBytes = BitConverter.GetBytes(low);
Byte[] highBytes = BitConverter.GetBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowBytes, 0, bytes, 4, 4);
Array.Copy(highBytes, 0, bytes, 0, 4);

return BitConverter.ToInt64(bytes, 0);
}

}

Alan


Russell said:
Can someone show me how to speed this up?

1. Whats the fastest way for Unsafe C#?
2. What the fastest way for Safe C#?

public static Int64 ToInt64(Int32 low, Int32 high)
{
Byte[] lowBytes = BitConverter.GetBytes(low);
Byte[] highBytes = BitConverter.GetBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowBytes, 0, bytes, 4, 4);
Array.Copy(highBytes, 0, bytes, 0, 4);

return BitConverter.ToInt64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.
Click to expand...
Click to expand...
 
public static Int64 Alan2_ToInt64(Int32 low, Int32 high)
{
Int64 result = high | ((Int64)low << 32);[/QUOTE]

Actually I was using a + rather than a | there.
return result;
}
Click to expand...
[...]
 
Can someone show me how to speed this up?

1. Whats the fastest way for Unsafe C#?
2. What the fastest way for Safe C#?

public static Int64 ToInt64(Int32 low, Int32 high)
{
Byte[] lowBytes = BitConverter.GetBytes(low);
Byte[] highBytes = BitConverter.GetBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowBytes, 0, bytes, 4, 4);
Array.Copy(highBytes, 0, bytes, 0, 4);

return BitConverter.ToInt64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.
Click to expand...

I have some good news and some bad news. Your method can be speeded
up but all the methods I tried, including yours, come up with the
wrong answer!

The results from the program below look like:
ToInt64A() had 50000 errors and took 1635 ticks on average.
ToInt64B() had 50000 errors and took 190 ticks on average.
ToInt64C() had 50000 errors and took 232 ticks on average.
ToInt64D() had 50000 errors and took 163 ticks on average.
ToInt64E() had 50000 errors and took 145 ticks on average.

where ToInt64A() is your method and B to E are alternative methods.

Running with one repetition and showing errors gives:
ToInt32A: result -53023518752769 != 9223372036854763462 expected
ToInt64A() had 1 errors and took 41386216 ticks on average.
ToInt32B: result 9223372032559796166 != 9223372036854763462 expected
ToInt64B() had 1 errors and took 1436216 ticks on average.
ToInt32C: result 9223372028264828870 != 9223372036854763462 expected
ToInt64C() had 1 errors and took 1839352 ticks on average.
ToInt32D: result 9223372032559796166 != 9223372036854763462 expected
ToInt64D() had 1 errors and took 1245720 ticks on average.
ToInt32E: result 9223372032559796166 != 9223372036854763462 expected
ToInt64E() had 1 errors and took 1245144 ticks on average.

your method appears to have a problem with signs. I have not been
able to track down the problems with the other methods in the short
time I have been looking.

The code I was using is below, perhaps someone else can find the
problem with the different methods (careful with line wrapping).

rossum

/////// Code //////////

public static Int64 ToInt64A(Int32 low, Int32 high) {
Byte[] lowBytes = BitConverter.GetBytes(low);
Byte[] highBytes = BitConverter.GetBytes(high);

Byte[] bytes = new Byte[8];
Array.Copy(lowBytes, 0, bytes, 4, 4);
Array.Copy(highBytes, 0, bytes, 0, 4);

return BitConverter.ToInt64(bytes, 0);
}

public static Int64 ToInt64B(Int32 low, Int32 high) {
const Int64 shift = (Int64)UInt32.MaxValue + 1;
return high * shift + low;
}

public static Int64 ToInt64C(Int32 low, Int32 high) {
return 2 * Math.BigMul(high, Int32.MaxValue) + 2 * high + low;
}

public static Int64 ToInt64D(Int32 low, Int32 high) {
Int64 result = high;
return (result << 32) + low;
}

public static Int64 ToInt64E(Int32 low, Int32 high) {
return ((Int64)high << 32) + low;
}

public delegate Int64 ToInt64(Int32 lo, Int32 hi);

static void Main() {
//const int limit = 1;
const int limit = 50000;

ToInt64[] converters = new ToInt64[5];
converters[0] = ToInt64A;
converters[1] = ToInt64B;
converters[2] = ToInt64C;
converters[3] = ToInt64D;
converters[4] = ToInt64E;

Stopwatch timer = new Stopwatch();

char name = 'A';
Int64 expected = Int64.MaxValue - 12345;
Int32 lo = (Int32)(expected & 0xFFFFFFFFL);
Int32 hi = (Int32)(expected >> 32);
Int64 result;
int errorCount;
foreach (ToInt64 TI64 in converters) {
errorCount = 0;
timer.Reset();
timer.Start();
for (int i = 0; i < limit; ++i) {
result = TI64(lo, hi);
if (result != expected) {
++errorCount;
//Console.WriteLine("ToInt32{0}: result {1} != {2}
expected", name, result, expected);
}
}
timer.Stop();
Console.WriteLine("ToInt64{0}() had {1} errors and took
{2} ticks on average.",
name, errorCount, timer.ElapsedTicks / limit);
++name;
}
Console.Write("Press [Enter] to continue... ");
Console.ReadLine();
} // end Main()

///////////////////////
 
public static Int64 ToInt64F(Int32 low, Int32 high)
{
return (((Int64)high) << 32) | (UInt32)low;
}
 
Russell said:
Can someone show me how to speed this up?

1. Whats the fastest way for Unsafe C#?
2. What the fastest way for Safe C#?

public static Int64 ToInt64(Int32 low, Int32 high)
{
Byte[] lowBytes = BitConverter.GetBytes(low);
Byte[] highBytes = BitConverter.GetBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowBytes, 0, bytes, 4, 4);
Array.Copy(highBytes, 0, bytes, 0, 4);

return BitConverter.ToInt64(bytes, 0);
}
Click to expand...

Some experiments indicates that there are no faster
methods than the shift/arithmetic code.

See code below.

Arne

using System;
using System.Runtime.InteropServices;

namespace E
{
[StructLayout(LayoutKind.Explicit)]
internal struct IntLong
{
[FieldOffset(0)] public int lowintval;
[FieldOffset(4)] public int highintval;
[FieldOffset(0)] public long longval;
}
public class MainClass
{
public static long ToInt64_Bytes(int high, int low)
{
byte[] highBytes = BitConverter.GetBytes(high);
byte[] lowBytes = BitConverter.GetBytes(low);
byte[] bytes = new Byte[8];
Array.Copy(highBytes, 0, bytes, 4, 4);
Array.Copy(lowBytes, 0, bytes, 0, 4);
return BitConverter.ToInt64(bytes, 0);
}
public static long ToInt64_Arith(int high, int low)
{
return high * 0x100000000L + (uint)low;
}
public static long ToInt64_Shift(int high, int low)
{
return (((long)high)<<32) | (uint)low;
}
private static IntLong cvt;
public static long ToInt64_Union(int high, int low)
{
cvt.highintval = high;
cvt.lowintval = low;
return cvt.longval;
}
public unsafe static long ToInt64_Pointer(int high, int low)
{
long res;
*(((int *)&res)+1) = high;
*((int *)&res) = low;
return res;
}
private const int N = 200000000;
public static void Main(string[] args)
{
Random rng = new Random();
for(int i = 0; i < 1000; i++)
{
byte[] b = new byte[8];
rng.NextBytes(b);
long v = BitConverter.ToInt64(b, 0);
int vhigh = (int)(v >> 32);
int vlow = (int)v;
long v2 = ToInt64_Bytes(vhigh, vlow);
if(v2 != v)
{
Console.WriteLine("Bytes: " + v + " -> " + v2);
}
long v3 = ToInt64_Arith(vhigh, vlow);
if(v3 != v)
{
Console.WriteLine("Arith: " + v + " -> " + v3);
}
long v4 = ToInt64_Shift(vhigh, vlow);
if(v4 != v)
{
Console.WriteLine("Shift: " + v + " -> " + v4);
}
long v5 = ToInt64_Union(vhigh, vlow);
if(v5 != v)
{
Console.WriteLine("Union: " + v + " -> " + v5);
}
long v6 = ToInt64_Pointer(vhigh, vlow);
if(v6 != v)
{
Console.WriteLine("Pointer: " + v + " -> " + v6);
}
}
DateTime t1 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Bytes(12345,67890);
}
DateTime t2 = DateTime.Now;
Console.WriteLine("Bytes: " + (t2 - t1).TotalSeconds);
DateTime t3 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Arith(12345,67890);
}
DateTime t4 = DateTime.Now;
Console.WriteLine("Arith: " + (t4 - t3).TotalSeconds);
DateTime t5 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Shift(12345,67890);
}
DateTime t6 = DateTime.Now;
Console.WriteLine("Shift: " + (t6 - t5).TotalSeconds);
DateTime t7 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Union(12345,67890);
}
DateTime t8 = DateTime.Now;
Console.WriteLine("Union: " + (t8 - t7).TotalSeconds);
DateTime t9 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Pointer(12345,67890);
}
DateTime t10 = DateTime.Now;
Console.WriteLine("Pointer: " + (t10 - t9).TotalSeconds);
Console.ReadLine();
}
}
}
 
Back
Top