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.

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


static void Fill1(byte value)
{
byte[] a = Enumerable.Repeat<byte>(value, _arrLength).ToArray();
}

static void Fill2(byte value)
{
byte[] a = ParallelEnumerable.Repeat<byte>(value, _arrLength).ToArray();
}

static void Fill3(byte value)
{
byte[] a = new byte[_arrLength];
for (int i = 0; i < _arrLength; i++)
{
a[i] = value;
}
}

static void Fill4(byte value)
{
byte[] a = new byte[_arrLength];
Parallel.For(0, _arrLength, i =>
{
a[i] = value;
});
}

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

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



11 comments:

  1. can C# do duff's device? I wonder how it would preform? (:

    thanks for profiling this stuff, it makes the choice pretty clear... I'm going with the for loop because i don't think i can use so called "unsafe" code in my situation.

    Thanks man!

    ReplyDelete
  2. Glad you found it helpful :)

    Found an implementation of Duff's Device at http://www.giannistsakiris.com/index.php/2007/07/17/duffs-device/ which I modified to set just one value. When running many tests it 9/10 times performs marginally faster than the for loop and then 1/10 slower or the same.

    I would go with the for loop as well for most cases.

    public static void Fill6(byte value)
    {
    byte[] toBuffer = new byte[_arrLength];
    int count = _arrLength;
    int i = 0;

    if (count%8 == 7) goto case_7;
    if (count%8 == 6) goto case_6;
    if (count%8 == 5) goto case_5;
    if (count%8 == 4) goto case_4;
    if (count%8 == 3) goto case_3;
    if (count%8 == 2) goto case_2;
    if (count%8 == 1) goto case_1;

    case_0:
    toBuffer[i++] = value;
    case_7:
    toBuffer[i++] = value;
    case_6:
    toBuffer[i++] = value;
    case_5:
    toBuffer[i++] = value;
    case_4:
    toBuffer[i++] = value;
    case_3:
    toBuffer[i++] = value;
    case_2:
    toBuffer[i++] = value;
    case_1:
    toBuffer[i++] = value;
    if ((count -= 8) > 0) goto case_0;
    }

    ReplyDelete
  3. I know this is an older post but I was just revisiting an old post of mine on this subject and I noticed my method wasn't represented here.

    I repeatedly call array.copy, doubling the size each time. See the technique at http://g.grax.com/1bB140h

    In my tests, it was quite a bit faster.

    ReplyDelete
    Replies
    1. Hi,
      Did you measure it against the unsafe pointer version (Fill5? If I recall correctly Array.Copy will do something similar behind the scenes. But certainly a nice one! :)

      Delete
    2. It seems to be pretty comparable to the unsafe pointer version. I accidentally left that one out of my tests.

      It does have a few advantages:
      Unsafe compile is not required
      Easy to fill an array with any value type (or string)
      Easy to fill array with a repeating pattern (1,2,3,4,1,2,3,4, etc)

      Delete
    3. If I ever need this in the future, I'll use your code :)

      Requiring unsafe compile is not really that big a deal. People seem to think unsafe is really unsafe, and yet they use programs developed in C++ every day ;)

      Again, thanks for the link, I should have thought of it myself. Embrace the framework and use what's there.

      Delete
    4. The advantage of not using Array.Copy is to save a few cpu cycles on bounds checking. But that is only for really really special cases - like creating a search engine which I was at the time when venturing this.

      Delete
  4. I wish I could +1 this post, and David Walker's reply as well. It's been annoying me that I couldn't find a better method of filling array of number than for-each, even if that turns out to me not so bad fo most cases.

    ReplyDelete
  5. This method is even faster than those mentioned in this article (at least for me anyway).

    using System;
    using System.Diagnostics;
    using System.Runtime.InteropServices;

    class Program
    {
    [DllImport("msvcrt.dll", EntryPoint = "memset", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
    public static extern IntPtr memset(IntPtr dest, int c, int count);

    unsafe static void Main(string[] args)
    {
    byte[] a = new byte[1000 * 1000 * 1000 * 2];
    Stopwatch sw = Stopwatch.StartNew();
    fixed (byte* ptr = a)
    memset((IntPtr)ptr, 97, a.Length);

    sw.Stop();
    Console.WriteLine("a[10]: {0} Elapsed time: {1}", a[10], sw.ElapsedMilliseconds);
    return;
    }
    }

    ReplyDelete
    Replies
    1. Not surprised :D You went one step further linking in a native DLL. Cool stuff!

      Delete
  6. Memset is great for setting large blocks of memory to the same byte value but doesn't work with arrays of types that have more than one byte per element.

    In my testing, if you want to fill a byte array with a single byte, Memset is the fastest solution. Since it doesn't work for types that require multiple bytes, the other solutions are still a better match in those cases.

    ReplyDelete