Tuesday, December 15, 2009

Filling an array with a default value

After following the discussion on Stackoverflow about how to initialize a byte array with a value I decided to do some benchmarking for fun.

[Update 2014-09-13]
As the question on SO has evolved I have now included poth PInvoke and Memset methods into my tests. The most interesting observation is that the Memset method performs excellent on 64bit, but poorly on 32bit. If you are compiling for 32bit, go with unsafe or PIvoke, if you are running 64bit, Memset delegate is the way to go.

Here are the results, and the code follows below (run on Windows 7 64bit dual core).

Array length: 1048576
Iterations: 1000
Enumerable: 00:00:12.3817249
Parallel Enumerable: 00:00:17.6506353
For loop: 00:00:01.7095341
Parallel for loop: 00:00:06.9824434
Unsafe: 00:00:00.7028914


Here are  the results running on Windows 8.1, 64bit i5 processor (Lenovo T420s) with .Net 4.5.1.

Array Length: 1048576
32bit execution - 5000 iterations

EnumerableFill: 00:00:50.1071043
ParallelEnumerableFill: 00:01:12.2980480
ForLoopFill: 00:00:05.3504656
ParallellForLoopFill: 00:00:45.5518340
UnsafeFill: 00:00:02.2804084
MemsetFill: 00:00:03.9383964
PInvokeFill: 00:00:02.4391258

32bit execution - 10000 iterations
UnsafeFill: 00:00:04.1653674
MemsetFill: 00:00:07.2561020
PInvokeFill: 00:00:04.2709875

64bit execution - 10000 iterations

UnsafeFill: 00:00:03.9618905
MemsetFill: 00:00:03.5594970
PInvokeFill: 00:00:03.8012791

using System;
using System.Diagnostics;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Runtime.InteropServices;
using System.Threading.Tasks;

namespace FillArrayBenchmark
{
    internal class Program
    {
        private static readonly Action MemsetDelegate;
        private static int _arrLength = 1048576;

        static Program()
        {
            var dynamicMethod = new DynamicMethod("Memset", MethodAttributes.Public | MethodAttributes.Static,
                CallingConventions.Standard,
                null, new[] {typeof (IntPtr), typeof (byte), typeof (int)}, typeof (Util), true);

            ILGenerator generator = dynamicMethod.GetILGenerator();
            generator.Emit(OpCodes.Ldarg_0);
            generator.Emit(OpCodes.Ldarg_1);
            generator.Emit(OpCodes.Ldarg_2);
            generator.Emit(OpCodes.Initblk);
            generator.Emit(OpCodes.Ret);

            MemsetDelegate =
                (Action) dynamicMethod.CreateDelegate(typeof (Action));
        }

        private static void Main(string[] args)
        {
            EnumerableFill(12);
            ParallelEnumerableFill(12);
            ForLoopFill(12);
            ParallellForLoopFill(12);
            UnsafeFill(12);
            MemsetFill(12);
            PInvokeFill(12);

            int iteration = 10000;
            Stopwatch sw;
            byte b = 129;
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                EnumerableFill(b);
            }
            sw.Stop();
            Console.WriteLine("EnumerableFill: " + sw.Elapsed);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                ParallelEnumerableFill(b);
            }
            sw.Stop();
            Console.WriteLine("ParallelEnumerableFill: " + sw.Elapsed);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                ForLoopFill(b);
            }
            sw.Stop();
            Console.WriteLine("ForLoopFill: " + sw.Elapsed);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                ParallellForLoopFill(b);
            }
            sw.Stop();
            Console.WriteLine("ParallellForLoopFill: " + sw.Elapsed);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                UnsafeFill(b);
            }
            sw.Stop();
            Console.WriteLine("UnsafeFill: " + sw.Elapsed);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                MemsetFill(b);
            }
            sw.Stop();
            Console.WriteLine("MemsetFill: " + sw.Elapsed);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < iteration; i++)
            {
                PInvokeFill(b);
            }
            sw.Stop();
            Console.WriteLine("PInvokeFill: " + sw.Elapsed);
        }

        private static void EnumerableFill(byte value)
        {
            byte[] a = Enumerable.Repeat(value, _arrLength).ToArray();
        }

        private static void ParallelEnumerableFill(byte value)
        {
            byte[] a = ParallelEnumerable.Repeat(value, _arrLength).ToArray();
        }

        private static byte[] ForLoopFill(byte value)
        {
            var a = new byte[_arrLength];
            for (int i = 0; i < _arrLength; i++)
            {
                a[i] = value;
            }
            return a;
        }

        private static byte[] ParallellForLoopFill(byte value)
        {
            var a = new byte[_arrLength];
            Parallel.For(0, _arrLength, i => { a[i] = value; });
            return a;
        }

        private static unsafe byte[] UnsafeFill(byte value)
        {
            Int64 fillValue = BitConverter.ToInt64(new[] {value, value, value, value, value, value, value, value}, 0);

            var a = new byte[_arrLength];
            Int64* src = &fillValue;
            fixed (byte* ptr = &a[0])
            {
                var dest = (Int64*) ptr;
                int length = _arrLength;
                while (length >= 8)
                {
                    *dest = *src;
                    dest++;
                    length -= 8;
                }
                var bDest = (byte*) dest;
                for (byte i = 0; i < length; i++)
                {
                    *bDest = value;
                    bDest++;
                }
            }
            return a;
        }

        public static byte[] MemsetFill(byte value)
        {
            var a = new byte[_arrLength];
            GCHandle gcHandle = GCHandle.Alloc(a, GCHandleType.Pinned);
            MemsetDelegate(gcHandle.AddrOfPinnedObject(), value, _arrLength);
            gcHandle.Free();
            return a;
        }

        private static byte[] PInvokeFill(byte value)
        {
            var arr = new byte[_arrLength];
            GCHandle gch = GCHandle.Alloc(arr, GCHandleType.Pinned);
            MemSet(gch.AddrOfPinnedObject(), value, _arrLength);
            gch.Free();
            return arr;
        }

        [DllImport("msvcrt.dll",
            EntryPoint = "memset",
            CallingConvention = CallingConvention.Cdecl,
            SetLastError = false)]
        public static extern IntPtr MemSet(IntPtr dest, int value, int count);
    }

    public static class Util
    {
        private static readonly Action MemsetDelegate;

        static Util()
        {
            var dynamicMethod = new DynamicMethod("Memset", MethodAttributes.Public | MethodAttributes.Static,
                CallingConventions.Standard,
                null, new[] {typeof (IntPtr), typeof (byte), typeof (int)}, typeof (Util), true);

            ILGenerator generator = dynamicMethod.GetILGenerator();
            generator.Emit(OpCodes.Ldarg_0);
            generator.Emit(OpCodes.Ldarg_1);
            generator.Emit(OpCodes.Ldarg_2);
            generator.Emit(OpCodes.Initblk);
            generator.Emit(OpCodes.Ret);

            MemsetDelegate =
                (Action) dynamicMethod.CreateDelegate(typeof (Action));
        }

        public static void Memset(byte[] array, byte what, int length)
        {
            GCHandle gcHandle = GCHandle.Alloc(array, GCHandleType.Pinned);
            MemsetDelegate(gcHandle.AddrOfPinnedObject(), what, length);
            gcHandle.Free();
        }
    }
}