In an int?[] garunteed to have original values, I wanted to find the index of null, which will only be a single index.
I drilled into the Array.IndexOf(T[] array, T value) .NET and, after all of the contracts and index checks, it comes down to this method:
internal virtual int IndexOf(T[] array, T value, int startIndex, int count){
int endIndex = startIndex + count;
for (int i = startIndex; i < endIndex; i++)
if (Equals(array[i], value)) return i;
return -1;
}
I have three different instances which attempt a basic loop with array[i] == null, Equals(array[i], null), and using Array.IndexOf(null). I realize ticks and stopwatch time is relative to what's happening on the machine at the time, and the machine in general. But this is the code and benchmarks:
class Program
{
static void Main(string[] args)
{
int?[] jankedArray;
int missingElement = GenRandomizedArrayWithExtraEmptyElement(10000, out jankedArray);
var sw = new Stopwatch();
List<long> DotNetTicks = new List<long>();
List<long> LikeDotNetTicks = new List<long>();
List<long> BasicLoopTicks = new List<long>();
IArrayAnalyzer arrayAnalyzer;
for (var i = 0; i < 100000; i++)
{
arrayAnalyzer = new AnalyzerLikeDotNet();
sw.Restart(); arrayAnalyzer.GetMissingElement(jankedArray); sw.Stop();
LikeDotNetTicks.Add(sw.ElapsedTicks);
arrayAnalyzer = new AnalyzerBasic();
sw.Restart(); arrayAnalyzer.GetMissingElement(jankedArray); sw.Stop();
BasicLoopTicks.Add(sw.ElapsedTicks);
arrayAnalyzer = new AnalyzerUsingDotNet();
sw.Restart(); arrayAnalyzer.GetMissingElement(jankedArray); sw.Stop();
DotNetTicks.Add(sw.ElapsedTicks);
}
Console.WriteLine("LikeDotNet / DotNet = " + LikeDotNetTicks.Average() / DotNetTicks.Average());
Console.WriteLine("Basic / DotNet = " + BasicLoopTicks.Average() / DotNetTicks.Average());
Console.WriteLine("");
Console.WriteLine("Press the Any key to continue");
Console.ReadKey();
}
public static int GenRandomizedArrayWithExtraEmptyElement(int valueCount, out int?[] incompleteArray)
{
incompleteArray = new int?[valueCount + 1];
Random random = new Random();
int randomMissingIndex = random.Next(0, valueCount);
var valueArray = new List<int>();
for (var i = 1; i <= valueCount; i++) valueArray.Add(i);
var arrayElementAt = 0;
while (valueArray.Count > 0)
{
if (arrayElementAt != randomMissingIndex)
{
var randomElement = random.Next(0, valueArray.Count);
var valueAtRandom = valueArray.ElementAt(randomElement);
valueArray.RemoveAt(randomElement);
incompleteArray[arrayElementAt] = valueAtRandom;
}
arrayElementAt++;
}
return randomMissingIndex;
}
}
public interface IArrayAnalyzer
{
int GetMissingElement(int?[] incompleteArray);
}
public class AnalyzerUsingDotNet : IArrayAnalyzer
{
public int GetMissingElement(int?[] incompleteArray)
{
return Array.IndexOf(incompleteArray, null);
}
}
public class AnalyzerLikeDotNet : IArrayAnalyzer
{
public int GetMissingElement(int?[] array)
{
for (int i = 0; i < array.Length; i++)
if (Equals(array[i], null)) return i;
return -1;
}
}
public class AnalyzerBasic : IArrayAnalyzer
{
public int GetMissingElement(int?[] array)
{
for (int i = 0; i < array.Length; i++)
if (array[i] == null) return i;
return -1;
}
}
- Output:
- LikeDotNet / DotNet = 81.3577324867023
- Basic / DotNet = 3.29459064916075
What am I missing between AnalyzerLikeDotNet and AnalyzerUsingDotNet which makes the execution time so different?
Equalsfunction, instead ofEqualityComparer<T>.Default? Or justarray[i] == nullsince your code isn't even generic.Array.IndexOfdoes not boil down to the code you posted, it has a special case fornulland also a special native handler for basic primitive types. Even so, using your code (but with more reasonable benchmarking) I only get about a 1.5x slow down on the custom loop with optimization enabled.