David Walker

Better Array Fill Function

by David Walker
So last week, Michael Hsu visited my blog and took my array fill function and made it better.

First, he turned it into an extension method and changed the signature so that the overload isn't needed.
   public static class ArrayExtensions
        public static void Fill<T>>(this T[] destinationArray, params T[] value)

Next, he took the if statement that I was executing inside the for loop and re-factored it so that it was not needed.

First rule of high-performing code, anything you can do before or after your loop is going to perform better than something you execute for each time through the loop.

Where I had

 int arrayToFillHalfLength = arrayToFill.Length / 2;

 for (int i = fillValue.Length; i < arrayToFill.Length; i *= 2)
  int copyLength = i;
  if (i > arrayToFillHalfLength)
   copyLength = arrayToFill.Length - i;

  Array.Copy(arrayToFill, 0, arrayToFill, i, copyLength);
Michael re-factored to

 int arrayToFillHalfLength = destinationArray.Length / 2;
 int copyLength;

 for(copyLength = value.Length; copyLength < arrayToFillHalfLength; copyLength <<= 1)
  Array.Copy(destinationArray, 0, destinationArray, copyLength, copyLength);

 Array.Copy(destinationArray, 0, destinationArray, copyLength, destinationArray.Length - copyLength);

This has a number of advantages.
  1. Since arrayToFillHalfLength is a variable, we don't have to look up the array length property each time through the loop.
  2. A bit shift operation is cheaper than a multiply operation.
  3. This is the big one. Since the loop stops 1 short of the final copy operation, the previous "if" operation is effectively handled by the loop without having to execute the if each time through the loop.
  4. The copyLength variable is defined once, outside of the loop.
When I compared the speed of Michael's version of the method, my version took 252 milliseconds to fill a 357,913,941 sized byte array with a five byte pattern and Michael's improved version did the same thing in 156 milliseconds.

See the improved version here.

David Walker

David Walker is a Software Consultant, Photographer, and Digital Artist based out of Orlando, Florida, USA.

He believes in secure reliable software and productive happy teams.

More ...