MrKWatkins

Unsafe C# - Converting Longs to Byte Arrays

In my previous post on converting enums to bytes I didn’t achieve any noticeable speed up using unsafe code, probably because the safe conversion is so simple. What about a more complex conversion that could be done in a different way using unsafe code?

A 64-bit long can be broken down into 8 bytes using bit shifting. If we simply case the long to a byte then we’ll take the rightmost 8-bits and discard the rest. By repeatedly bit shifting the long 8 bits to the right and casting we can chop the long up into 8-bit segments and get ourselves a byte array containing the long:

1
2
3
4
5
6
7
8
9
10
11
12
13
private static byte[] SafeLongToBytes(long value)
{
    var bytes = new byte[8];
    bytes[0] = (byte) value;
    bytes[1] = (byte) (value >> 8);
    bytes[2] = (byte) (value >> 16);
    bytes[3] = (byte) (value >> 24);
    bytes[4] = (byte) (value >> 32);
    bytes[5] = (byte) (value >> 40);
    bytes[6] = (byte) (value >> 48);
    bytes[7] = (byte) (value >> 56);
    return bytes;
}

We can do this in a simpler way using unsafe code. If we take a pointer to the byte array then we can write our long directly to the memory taken up by the byte array:

1
2
3
4
5
6
7
8
9
private static unsafe byte[] UnsafeLongToBytes(long value)
{
    var bytes = new byte[8];
    fixed (byte* pointer = bytes)
    {
        *(long*)pointer = value;
    }
    return bytes;
}

The main difference between the code here and the enum conversion in the last post is the use of the fixed block. This is necessary because the byte array will be allocated on the heap and we don’t want the garbage collector moving it around whilst whilst we’re playing with memory addresses. This wasn’t necessary for the enum conversion because the enum was allocated on the stack.

Is this any quicker? Yes – the safe version was about 17% slower in rough tests on my laptop. The full code of the timing application can be found here.

Is that enough of an increase to warrant added unsafe code to your assembly? Well turns out that it doesn’t matter… Whilst typing up this post I found out about the BitConverter class that has a long to byte array method. Flipping it open with ILSpy shows that its identical to the unsafe code above!

Unsafe C# - Converting Enums to Bytes

Whilst working on my Cards project I needed to convert enum values into bytes. The enums in question have ints as their underlying types rather than bytes (even though I could make the underlying type byte everyone pretty much expects all enums will have ints as their underlying type so I’ve stuck with that) so there will be a (very small!) amount of work to convert them to bytes. I was wondering, purely out of interest as its a silly thing to be doing, if I could do anything quicker using unsafe code. If I could grab the bytes for the underlying int I could simply return the first one and bypass any checks the runtime might do.

To test I used the ConsoleColor enum and came up with the following equivalent functions:

1
2
3
4
5
6
7
8
9
private static byte SafeConvert(ConsoleColor value)
{
    return (byte) value;
}

private unsafe static byte UnsafeConvert(ConsoleColor value)
{
    return *(byte*) &value;
}

Ran some timing tests and there was no detectable difference… To be expected really – its a very simple conversion after all.

Full code of the timing application can be found here.

Combinatorial Explosion!

The other day I hit a combinatorial explosion when using Haskell’s nub function. Whilst I knew it was O(n2) I thought my n (~28,000) wasn’t big enough to cause a problem. Turns out it was…

Therefore to get a better feel for the size of the numbers involved for O(n2) and various other common big O growth rates I’ve built a table comparing the values. Enjoy!

n ⌈log2log2n ⌈log2n ⌈√n n log2n n2 n3 2n n!
2 0 1 2 2 4 8 4 2
5 2 3 3 12 25 125 32 120
10 2 4 4 34 100 1,000 1,024 3,628,800
20 3 5 5 87 400 8,000 1,048,576 2.43x1018
50 3 6 8 283 2,500 125,000 1.12x1015 3.04x1064
100 3 7 10 665 10,000 1,000,000 1.26x1030 9.33x10157
200 3 8 15 1,529 40,000 8,000,000 1.60x1060 7.88x10374
500 4 9 23 4,483 250,000 1.25x108 3.27x10150 1.22x101134
1,000 4 10 32 9,966 1,000,000 1.00x109 1.07x10301 4.02x102567
2,000 4 11 45 21,932 4,000,000 8.00x109 1.14x10602 3.31x105735
5,000 4 13 71 61,439 25,000,000 1.25x1011 1.41x101505 4.22x1016325
10,000 4 14 100 132,878 1.00x108 1.00x1012 1.99x103010 2.84x1035659
20,000 4 15 142 285,755 4.00x108 8.00x1012 3.98x106020 1.81x1077337
50,000 4 16 224 780,483 2.50x109 1.25x1014 3.16x1015051 3.34x10213236
100,000 5 17 317 1,660,965 1.00x1010 1.00x1015 9.99x1030102 2.82x10456573
200,000 5 18 448 3,521,929 4.00x1010 8.00x1015 9.98x1060205 1.42x10973350
500,000 5 19 708 9,465,785 2.50x1011 1.25x1017 9.95x10150514 1.02x102632341
1,000,000 5 20 1,000 19,931,569 1.00x1012 1.00x1018 9.90x10301029 8.26x105565708