Tutorial :What is the equivalent of memset in C#?



Question:

I need to fill a byte[] with a single non-zero value. How can I do this in C# without looping through each byte in the array?

Update: The comments seem to have split this into two questions -

  1. Is there a Framework method to fill a byte[] that might be akin to memset
  2. What is the most efficient way to do it when we are dealing with a very large array?

I totally agree that using a simple loop works just fine, as Eric and others have pointed out. The point of the question was to see if I could learn something new about C# :) I think Juliet's method for a Parallel operation should be even faster than a simple loop.

Benchmarks: Thanks to Mikael Svenson: http://techmikael.blogspot.com/2009/12/filling-array-with-default-value.html

It turns out the simple for loop is the way to go unless you want to use unsafe code.

Apologies for not being clearer in my original post. Eric and Mark are both correct in their comments; need to have more focused questions for sure. Thanks for everyone's suggestions and responses.


Solution:1

You could use Enumerable.Repeat:

byte[] a = Enumerable.Repeat((byte)10, 100).ToArray();  

The first parameter is the element you want repeated, and the second parameter is the number of times to repeat it.

This is OK for small arrays but you should use the looping method if you are dealing with very large arrays and performance is a concern.


Solution:2

Actually, there is little known IL operation called Initblk (English version) which does exactly that. So, let's use it as a method that doesn't require "unsafe". Here's the helper class:

public static class Util  {      static Util()      {          var dynamicMethod = new DynamicMethod("Memset", MethodAttributes.Public | MethodAttributes.Static, CallingConventions.Standard,              null, new [] { typeof(IntPtr), typeof(byte), typeof(int) }, typeof(Util), true);            var 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<IntPtr, byte, int>)dynamicMethod.CreateDelegate(typeof(Action<IntPtr, byte, int>));      }        public static void Memset(byte[] array, byte what, int length)      {          var gcHandle = GCHandle.Alloc(array, GCHandleType.Pinned);          MemsetDelegate(gcHandle.AddrOfPinnedObject(), what, length);          gcHandle.Free();      }        public static void ForMemset(byte[] array, byte what, int length)      {          for(var i = 0; i < length; i++)          {              array[i] = what;          }      }        private static Action<IntPtr, byte, int> MemsetDelegate;    }  

And what is the performance? Here's my result for Windows/.NET and Linux/Mono (different PCs).

Mono/for:     00:00:01.1356610  Mono/initblk: 00:00:00.2385835     .NET/for:     00:00:01.7463579  .NET/initblk: 00:00:00.5953503  

So it's worth considering. Note that the resulting IL will not be verifiable.


Solution:3

A little bit late, but the following approach might be a good compromise without reverting to unsafe code. Basically it initializes the beginning of the array using a conventional loop and then reverts to Buffer.BlockCopy(), which should be as fast as you can get using a managed call.

public static void MemSet(byte[] array, byte value) {    if (array == null) {      throw new ArgumentNullException("array");    }    const int blockSize = 4096; // bigger may be better to a certain extent    int index = 0;    int length = Math.Min(blockSize, array.Length);    while (index < length) {      array[index++] = value;    }    length = array.Length;    while (index < length) {      Buffer.BlockCopy(array, 0, array, index, Math.Min(blockSize, length-index));      index += blockSize;    }  }  


Solution:4

Building on Lucero's answer, here is a faster version. It will double the number of bytes copied using Buffer.BlockCopy every iteration. Interestingly enough, it outperforms it by a factor of 10 when using relatively small arrays (1000), but the difference is not that large for larger arrays (1000000), it is always faster though. The good thing about it is that it performs well even down to small arrays. It becomes faster than the naive approach at around length = 100. For a one million element byte array, it was 43 times faster. (tested on Intel i7, .Net 2.0)

public static void MemSet(byte[] array, byte value) {      if (array == null) {          throw new ArgumentNullException("array");      }        int block = 32, index = 0;      int length = Math.Min(block, array.Length);        //Fill the initial array      while (index < length) {          array[index++] = value;      }        length = array.Length;      while (index < length) {          Buffer.BlockCopy(array, 0, array, index, Math.Min(block, length-index));          index += block;          block *= 2;      }  }  


Solution:5

If performance is critical, you could consider using unsafe code and working directly with a pointer to the array.

Another option could be importing memset from msvcrt.dll and use that. However, the overhead from invoking that might easily be larger than the gain in speed.


Solution:6

This simple implementation uses successive doubling, and performs quite well (about 3-4 times faster than the naive version according to my benchmarks):

public static void Memset<T>(T[] array, T elem)   {      int length = array.Length;      if (length == 0) return;      array[0] = elem;      int count;      for (count = 1; count <= length/2; count*=2)          Array.Copy(array, 0, array, count, count);      Array.Copy(array, 0, array, count, length - count);  }  

Edit: upon reading the other answers, it seems I'm not the only one with this idea. Still, I'm leaving this here, since it's a bit cleaner and it performs on par with the others.


Solution:7

If performance is absolutely critical, then Enumerable.Repeat(n, m).ToArray() will be too slow for your needs. You might be able to crank out faster performance using PLINQ or Task Parallel Library:

using System.Threading.Tasks;    // ...    byte initialValue = 20;  byte[] data = new byte[size]  Parallel.For(0, size, index => data[index] = initialValue);  


Solution:8

Or use P/Invoke way:

[DllImport("msvcrt.dll",   EntryPoint = "memset",   CallingConvention = CallingConvention.Cdecl,   SetLastError = false)]  public static extern IntPtr MemSet(IntPtr dest, int c, int count);    static void Main(string[] args)  {      byte[] arr = new byte[3];      GCHandle gch = GCHandle.Alloc(arr, GCHandleType.Pinned);      MemSet(gch.AddrOfPinnedObject(), 0x7, arr.Length);   }  


Solution:9

All answers are writing single bytes only - what if you want to fill a byte array with words? Or floats? I find use for that now and then. So after having written similar code to 'memset' in a non-generic way a few times and arriving at this page to find good code for single bytes, I went about writing the method below.

I think PInvoke and C++/CLI each have their drawbacks. And why not have the runtime 'PInvoke' for you into mscorxxx? Array.Copy and Buffer.BlockCopy are native code certainly. BlockCopy isn't even 'safe' - you can copy a long halfway over another, or over a DateTime as long as they're in arrays.

At least I wouldn't go file new C++ project for things like this - it's a waste of time almost certainly.

So here's basically an extended version of the solutions presented by Lucero and TowerOfBricks that can be used to memset longs, ints, etc as well as single bytes.

public static class MemsetExtensions  {      static void MemsetPrivate(this byte[] buffer, byte[] value, int offset, int length) {          var shift = 0;          for (; shift < 32; shift++)              if (value.Length == 1 << shift)                  break;          if (shift == 32 || value.Length != 1 << shift)              throw new ArgumentException(                  "The source array must have a length that is a power of two and be shorter than 4GB.", "value");            int remainder;          int count = Math.DivRem(length, value.Length, out remainder);            var si = 0;          var di = offset;          int cx;          if (count < 1)               cx = remainder;          else               cx = value.Length;          Buffer.BlockCopy(value, si, buffer, di, cx);          if (cx == remainder)              return;            var cachetrash = Math.Max(12, shift); // 1 << 12 == 4096          si = di;          di += cx;          var dx = offset + length;          // doubling up to 1 << cachetrash bytes i.e. 2^12 or value.Length whichever is larger          for (var al = shift; al <= cachetrash && di + (cx = 1 << al) < dx; al++) {              Buffer.BlockCopy(buffer, si, buffer, di, cx);              di += cx;          }          // cx bytes as long as it fits          for (; di + cx <= dx; di += cx)              Buffer.BlockCopy(buffer, si, buffer, di, cx);          // tail part if less than cx bytes          if (di < dx)              Buffer.BlockCopy(buffer, si, buffer, di, dx - di);      }  }  

Having this you can simply add short methods to take the value type you need to memset with and call the private method, e.g. just find replace ulong in this method:

    public static void Memset(this byte[] buffer, ulong value, int offset, int count) {          var sourceArray = BitConverter.GetBytes(value);          MemsetPrivate(buffer, sourceArray, offset, sizeof(ulong) * count);      }  

Or go silly and do it with any type of struct (although the MemsetPrivate above only works for structs that marshal to a size that is a power of two):

    public static void Memset<T>(this byte[] buffer, T value, int offset, int count) where T : struct {          var size = Marshal.SizeOf<T>();          var ptr = Marshal.AllocHGlobal(size);          var sourceArray = new byte[size];          try {              Marshal.StructureToPtr<T>(value, ptr, false);              Marshal.Copy(ptr, sourceArray, 0, size);          } finally {              Marshal.FreeHGlobal(ptr);          }          MemsetPrivate(buffer, sourceArray, offset, count * size);      }  

I changed the initblk mentioned before to take ulongs to compare performance with my code and that silently fails - the code runs but the resulting buffer contains the least significant byte of the ulong only.

Nevertheless I compared the performance writing as big a buffer with for, initblk and my memset method. The times are in ms total over 100 repetitions writing 8 byte ulongs whatever how many times fit the buffer length. The for version is manually loop-unrolled for the 8 bytes of a single ulong.

Buffer Len  #repeat  For millisec  Initblk millisec   Memset millisec  0x00000008  100      For   0,0032  Initblk   0,0107   Memset   0,0052  0x00000010  100      For   0,0037  Initblk   0,0102   Memset   0,0039  0x00000020  100      For   0,0032  Initblk   0,0106   Memset   0,0050  0x00000040  100      For   0,0053  Initblk   0,0121   Memset   0,0106  0x00000080  100      For   0,0097  Initblk   0,0121   Memset   0,0091  0x00000100  100      For   0,0179  Initblk   0,0122   Memset   0,0102  0x00000200  100      For   0,0384  Initblk   0,0123   Memset   0,0126  0x00000400  100      For   0,0789  Initblk   0,0130   Memset   0,0189  0x00000800  100      For   0,1357  Initblk   0,0153   Memset   0,0170  0x00001000  100      For   0,2811  Initblk   0,0167   Memset   0,0221  0x00002000  100      For   0,5519  Initblk   0,0278   Memset   0,0274  0x00004000  100      For   1,1100  Initblk   0,0329   Memset   0,0383  0x00008000  100      For   2,2332  Initblk   0,0827   Memset   0,0864  0x00010000  100      For   4,4407  Initblk   0,1551   Memset   0,1602  0x00020000  100      For   9,1331  Initblk   0,2768   Memset   0,3044  0x00040000  100      For  18,2497  Initblk   0,5500   Memset   0,5901  0x00080000  100      For  35,8650  Initblk   1,1236   Memset   1,5762  0x00100000  100      For  71,6806  Initblk   2,2836   Memset   3,2323  0x00200000  100      For  77,8086  Initblk   2,1991   Memset   3,0144  0x00400000  100      For 131,2923  Initblk   4,7837   Memset   6,8505  0x00800000  100      For 263,2917  Initblk  16,1354   Memset  33,3719  

I excluded the first call every time, since both initblk and memset take a hit of I believe it was about .22ms for the first call. Slightly surprising my code is faster for filling short buffers than initblk, seeing it got half a page full of setup code.

If anybody feels like optimizing this, go ahead really. It's possible.


Solution:10

You could do it when you initialize the array but I don't think that's what you are asking for:

byte[] myBytes = new byte[5] { 1, 1, 1, 1, 1};  


Solution:11

Looks like System.Runtime.CompilerServices.Unsafe.InitBlock now does the same thing as the OpCodes.Initblk instruction that Konrad's answer mentions (he also mentioned a source link).

The code to fill in the array is as follows:

byte[] a = new byte[N];  byte valueToFill = 255;    System.Runtime.CompilerServices.Unsafe.InitBlock(ref a[0], valueToFill, (uint) a.Length);  


Solution:12

Tested several ways, described in different answers. See sources of test in c# test class

benchmark report


Solution:13

.NET Core has a built-in Array.Fill() function, but sadly .NET Framework is missing it. .NET Core has two variations: fill the entire array and fill a portion of the array starting at an index.

Building on the ideas above, here is a more generic Fill function that will fill the entire array of several data types. This is the fastest function when benchmarking against other methods discussed in this post.

This function, along with the version that fills a portion an array are available in an open source and free NuGet package (HPCsharp on nuget.org). Also included is a slightly faster version of Fill using SIMD/SSE instructions that performs only memory writes, whereas BlockCopy-based methods perform memory reads and writes.

    public static void FillUsingBlockCopy<T>(this T[] array, T value) where T : struct      {          int numBytesInItem = 0;          if (typeof(T) == typeof(byte) || typeof(T) == typeof(sbyte))              numBytesInItem = 1;          else if (typeof(T) == typeof(ushort) || typeof(T) != typeof(short))              numBytesInItem = 2;          else if (typeof(T) == typeof(uint) || typeof(T) != typeof(int))              numBytesInItem = 4;          else if (typeof(T) == typeof(ulong) || typeof(T) != typeof(long))              numBytesInItem = 8;          else              throw new ArgumentException(string.Format("Type '{0}' is unsupported.", typeof(T).ToString()));            int block = 32, index = 0;          int endIndex = Math.Min(block, array.Length);            while (index < endIndex)          // Fill the initial block              array[index++] = value;            endIndex = array.Length;          for (; index < endIndex; index += block, block *= 2)          {              int actualBlockSize = Math.Min(block, endIndex - index);              Buffer.BlockCopy(array, 0, array, index * numBytesInItem, actualBlockSize * numBytesInItem);          }      }  


Solution:14

The Array object has a method called Clear. I'm willing to bet that the Clear method is faster than any code you can write in C#.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »