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

[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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.

[Tim Clark]

How about:
public static Int64 ToInt64(Int32 low, Int32 high)
{
Int64 x = high;
x <<= 32;
x = x | low;
}
Russell Mangel wrote:

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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.

[rdrunner]

Geee...

Thats slow ;)

Try this

public static Int64 FastToInt64(Int 32 low, Int32 high)

{

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

}

"Russell Mangel" <ru*****@tymer. netwrote in message
news:O2******** ******@TK2MSFTN GP03.phx.gbl...

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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.

[Tom Dacon]

Or, in one line (safe C#):

return (Int64)(((UInt6 4)high << 32) | (UInt32)low);

Tom Dacon
Dacon Software Consulting
"Russell Mangel" <ru*****@tymer. netwrote in message
news:O2******** ******@TK2MSFTN GP03.phx.gbl...

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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.

[Alan J. McFarlane]

In article news:11******** **************@ n51g2000cwc.goo glegroups.com,
Tim Clark wrote:

How about:
public static Int64 ToInt64(Int32 low, Int32 high)
{
Int64 x = high;
x <<= 32;
x = x | low;
}

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 = 11223344aabbccd d
11223344 & aabbccdd = 11223343aabbccd d
11223344 & aabbccdd = 11223343aabbccd d

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(I nt32 low, Int32 high)
{
const Int64 Bit32 = 0x100000000;
System.Diagnost ics.Debug.Asser t(Bit32 == (0x1L + UInt32.MaxValue ));
System.Diagnost ics.Debug.Asser t(Bit32 == (0x1L << 32));
Int64 result = high + Bit32 * low;
return result;
}

public static Int64 Alan2_ToInt64(I nt32 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 = 11223344aabbccd d
11223344 & aabbccdd = 11223343aabbccd d
11223344 & aabbccdd = 11223343aabbccd d
11223344 & aabbccdd = aabbccdd1122334 4
11223344 & aabbccdd = aabbccdd1122334 4
11223344 & aabbccdd = aabbccdd1122334 4

low & high = result
aabbccdd & 11223344 = aabbccdd1122334 4
aabbccdd & 11223344 = aabbccdd1122334 4
aabbccdd & 11223344 = aabbccdd1122334 4
aabbccdd & 11223344 = ffffffffaabbccd d
aabbccdd & 11223344 = ffffffffaabbccd d
aabbccdd & 11223344 = 11223343aabbccd d

!!! 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((Int3 2)0xaabbccdd);
DoItWith(low, high);
const Int32 high2 = 0x11223344, low2 =
unchecked((Int3 2)0xaabbccdd);
DoItWith(low2, high2);
}

private static void DoItWith(Int32 low, Int32 high)
{
Console.WriteLi ne("{0,8} & {1,8} = {2}", "low", "high",
"result");
Console.WriteLi ne("{0:x} & {1:x} = {2:x}", low, high,
RussellsOrigina l_ToInt64(low, high));
Console.WriteLi ne("{0:x} & {1:x} = {2:x}", low, high,
Alan1_ToInt64(l ow, high));
Console.WriteLi ne("{0:x} & {1:x} = {2:x}", low, high,
Alan2_ToInt64(l ow, high));
Console.WriteLi ne("{0:x} & {1:x} = {2:x}", low, high,
TimClark_ToInt6 4(low, high));
Console.WriteLi ne("{0:x} & {1:x} = {2:x}", low, high,
TimClark_ToInt6 4(low, high));
Console.WriteLi ne("{0:x} & {1:x} = {2:x}", low, high,
rdrunner_FastTo Int64(low, high));
}

public static Int64 Alan1_ToInt64(I nt32 low, Int32 high)
{
const Int64 Bit32 = 0x100000000;
System.Diagnost ics.Debug.Asser t(Bit32 == (0x1L +
UInt32.MaxValue ));
System.Diagnost ics.Debug.Asser t(Bit32 == (0x1L << 32));
Int64 result = high + Bit32 * low;
return result;
}

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

public static Int64 TimClark_ToInt6 4(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_FastTo Int64(Int32 low, Int32 high)
{
return ((Int64)(high) << 32) + low;
}

public static Int64 TomDacon_ToInt6 4(Int32 low, Int32 high)
{
return (Int64)(((UInt6 4)high << 32) | (UInt32)low);
}

public static Int64 RussellsOrigina l_ToInt64(Int32 low, Int32
high)
{
Byte[] lowBytes = BitConverter.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

}

Alan

Russell Mangel wrote:

>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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.

--
Alan J. McFarlane
http://www.alanjmcf.me.uk/
Please follow-up in the newsgroup for the benefit of all.

[Alan J. McFarlane]

In article news:45******** **************@ ptn-nntp-reader02.plus.n et,
Alan J. McFarlane wrote:

In article news:11******** **************@ n51g2000cwc.goo glegroups.com,
Tim Clark wrote:

[...]

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

Actually I was using a + rather than a | there.

return result;
}

[...]

[rossum]

On Sat, 30 Dec 2006 13:39:30 -0800, "Russell Mangel"
<ru*****@tymer. netwrote:

>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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

Thanks.

Russell Mangel
Las Vegas, NV

PS
The winner will receive keys for a Mercedes Benz.

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 != 922337203685476 3462 expected
ToInt64A() had 1 errors and took 41386216 ticks on average.
ToInt32B: result 922337203255979 6166 != 922337203685476 3462 expected
ToInt64B() had 1 errors and took 1436216 ticks on average.
ToInt32C: result 922337202826482 8870 != 922337203685476 3462 expected
ToInt64C() had 1 errors and took 1839352 ticks on average.
ToInt32D: result 922337203255979 6166 != 922337203685476 3462 expected
ToInt64D() had 1 errors and took 1245720 ticks on average.
ToInt32E: result 922337203255979 6166 != 922337203685476 3462 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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];
Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

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

public static Int64 ToInt64C(Int32 low, Int32 high) {
return 2 * Math.BigMul(hig h, 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)(expecte d & 0xFFFFFFFFL);
Int32 hi = (Int32)(expecte d >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.WriteLi ne("ToInt32{0} : result {1} != {2}
expected", name, result, expected);
}
}
timer.Stop();
Console.WriteLi ne("ToInt64{0}( ) had {1} errors and took
{2} ticks on average.",
name, errorCount, timer.ElapsedTi cks / limit);
++name;
}
Console.Write(" Press [Enter] to continue... ");
Console.ReadLin e();
} // end Main()

///////////////////////

[Theneolab]

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

[Theneolab]

Theneolab wrote:

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

Looking back Tom beat me to it.

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

Russell Mangel wrote:

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.Ge tBytes(low);
Byte[] highBytes = BitConverter.Ge tBytes(high);

Byte[] bytes = new Byte[8];

Array.Copy(lowB ytes, 0, bytes, 4, 4);
Array.Copy(high Bytes, 0, bytes, 0, 4);

return BitConverter.To Int64(bytes, 0);
}

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(La youtKind.Explic it)]
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(i nt high, int low)
{
byte[] highBytes = BitConverter.Ge tBytes(high);
byte[] lowBytes = BitConverter.Ge tBytes(low);
byte[] bytes = new Byte[8];
Array.Copy(high Bytes, 0, bytes, 4, 4);
Array.Copy(lowB ytes, 0, bytes, 0, 4);
return BitConverter.To Int64(bytes, 0);
}
public static long ToInt64_Arith(i nt high, int low)
{
return high * 0x100000000L + (uint)low;
}
public static long ToInt64_Shift(i nt high, int low)
{
return (((long)high)<< 32) | (uint)low;
}
private static IntLong cvt;
public static long ToInt64_Union(i nt 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.To Int64(b, 0);
int vhigh = (int)(v >32);
int vlow = (int)v;
long v2 = ToInt64_Bytes(v high, vlow);
if(v2 != v)
{
Console.WriteLi ne("Bytes: " + v + " -" + v2);
}
long v3 = ToInt64_Arith(v high, vlow);
if(v3 != v)
{
Console.WriteLi ne("Arith: " + v + " -" + v3);
}
long v4 = ToInt64_Shift(v high, vlow);
if(v4 != v)
{
Console.WriteLi ne("Shift: " + v + " -" + v4);
}
long v5 = ToInt64_Union(v high, vlow);
if(v5 != v)
{
Console.WriteLi ne("Union: " + v + " -" + v5);
}
long v6 = ToInt64_Pointer (vhigh, vlow);
if(v6 != v)
{
Console.WriteLi ne("Pointer: " + v + " -" + v6);
}
}
DateTime t1 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Bytes(1 2345,67890);
}
DateTime t2 = DateTime.Now;
Console.WriteLi ne("Bytes: " + (t2 - t1).TotalSecond s);
DateTime t3 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Arith(1 2345,67890);
}
DateTime t4 = DateTime.Now;
Console.WriteLi ne("Arith: " + (t4 - t3).TotalSecond s);
DateTime t5 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Shift(1 2345,67890);
}
DateTime t6 = DateTime.Now;
Console.WriteLi ne("Shift: " + (t6 - t5).TotalSecond s);
DateTime t7 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Union(1 2345,67890);
}
DateTime t8 = DateTime.Now;
Console.WriteLi ne("Union: " + (t8 - t7).TotalSecond s);
DateTime t9 = DateTime.Now;
for(int i = 0; i < N; i++)
{
ToInt64_Pointer (12345,67890);
}
DateTime t10 = DateTime.Now;
Console.WriteLi ne("Pointer: " + (t10 - t9).TotalSecond s);
Console.ReadLin e();
}
}
}