2

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?

  • You have: an array of: optional int. System.Array is supporting something slightly different: an array of: int, which is a rather efficient data structure. C# stores optional int as Nullable<T>, which is a struct, so I don't think this will even get boxed. It is a larger data structure (as much as 2x) but not terrible enough to merit 10x. Having debugging turned on can result in slower code. Also, timing C# code can have issues, because you may be timing the JIT plus the run instead of the just the run of the JIT'ed code. – Erik Eidt Aug 6 '16 at 23:23
  • These are all things I realize, except: System.Array is working with my Nullable<T> int?[]. So I'm not sure what you are implying when you say System.Array supports int[]. System.Array supports all T, and in both snippets above, the type is Nullable<int>. It almost sounds like you're saying System.Array is treating it as int[], but then how is the Equals(T, T) taking an T[] array and comparing it to a null value? I'm missing something in the direction you're going. – Suamere Aug 7 '16 at 1:16
  • Ok, maybe I misspoke. All I'm really saying is that Nullable<T> costs some but I don't see how that accounts for 10x. So, maybe try to rule out some other things like timing methodology. – Erik Eidt Aug 7 '16 at 1:21
  • Why are you using a boxing Equals function, instead of EqualityComparer<T>.Default? Or just array[i] == null since your code isn't even generic. – CodesInChaos Aug 7 '16 at 12:02
  • 1
    Your premise is incorrect. Array.IndexOf does not boil down to the code you posted, it has a special case for null and 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. – Rotem Aug 7 '16 at 15:09
3

On my machine, the result of the benchmark (compiled in optimized Release mode) is

 LikeDotNet / DotNet = 101.911379048464

 Basic / DotNet = 0.979227574248443

so the second is near to ratio of 1, which is a strong indication the internal implementation in the framework is very similar to your Basic case. The 2% difference are most probably just from the overhead of the additional method call, or from additional checks inside the framework.

Having a look at the link to the source code you posted it seems Array.IndexOf delegates it's calls to

  EqualityComparer<T>.Default.IndexOf

(line 1406), and the Default comparer is initialized by a CreateComparer method which picks one of several special EqualityComparer<T> derivations, optimized for some standard types. For int? this means the IndexOf method of NullableEqualityComparer<T> will be used, which uses .HasValue for null testing, not Equals. A quick benchmark with

    public int GetMissingElement(int?[] array)
    {
        for (int i = 0; i < array.Length; i++)
            if (!array[i].HasValue) return i;
        return -1;
    }

shows similar performance like your Basic test using == (or similar to calling Array.IndexOf directly). So I think this is what is really happening here - .HasValue has probably a much better performance (>factor 100) than Equals for int?.

  • Your answer does more of what I want, to break down the code and find where the difference is. The answer being in the utilization of HasValue over Equals, as well as directing to NullableEqualityComparer. Though John Wu's answer is the short and sweet fact. But it makes more sense with all the snippets and description. Good find! – Suamere Feb 9 '17 at 20:12
3

Value types do not provide an overload for == by default. However, most of the value types provided by the framework provide their own overload. The default implementation of Equals for a value type is provided by ValueType, and uses reflection to make the comparison, which makes it significantly slower than a type-specific implementation normally would be. This implementation also calls Equals on pairs of references within the two values being compared.

Link

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.