1
\$\begingroup\$

I timed a few ways to look for a string in a string array (with 82 elements in the example) in a case sensitive manner plus ignoring case.

I am kind of suprised, that the plain for loops are faster than all other variants.

  1. Sure, there are no checks, but are there any other flaws here?
  2. Does Linq not do some vectorization behind the scenes?
  3. Can I w/o concerns use these loops?
  4. Any other notes?

Code

class Program
{
    static void Main(string[] args)
    {
        Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
        StringArrayContains();
        Console.Read();
    }
    public static void StringArrayContains()
    {
        // Init timing
        var watch = Start();
        watch.Stop();
        watch.Reset();

        // Setup vars
        string query = "big";
        string[] stringArray = GetStringArray();
        bool contains = false;
        int times = (int)1e6;

        Console.WriteLine("Case Sensitive Search");

        // Loop with case sensitive equal
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            for (int j = 0; j < stringArray.Length; j++)
            {
                if (string.CompareOrdinal(query, stringArray[j]) == 0)
                {
                    contains = true;
                    break;
                }
            }
        }
        Stop(watch, $"Loop with case sensitive equal", times);

        // Array.Exists + Equals
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = Array.Exists(stringArray, item => string.CompareOrdinal(item, query) == 0);
        }
        Stop(watch, $"Array.Exists + Equals", times);

        // Array.Exists + ==
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = Array.Exists(stringArray, item => item == query);
        }
        Stop(watch, $"Array.Exists + ==", times);

        // Array.IndexOf
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = Array.IndexOf(stringArray, query) > -1;
        }
        Stop(watch, $"Array.IndexOf", times);


        Console.WriteLine("Case Insensitive Search");

        // Loop with case insensitive equal
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            for (int j = 0; j < stringArray.Length; j++)
            {
                if (string.Equals(query, stringArray[j], StringComparison.OrdinalIgnoreCase))
                {
                    contains = true;
                    break;
                }
            }
        }
        Stop(watch, $"Loop with case insensitive equal", times);

        // Array.Exists + EqualsIgnoreCase
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = Array.Exists(stringArray, item => string.Equals(item, query, StringComparison.OrdinalIgnoreCase));
        }
        Stop(watch, $"Array.Exists + EqualsIgnoreCase", times);

        // Linq Contains: OrdinalIgnoreCase
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = stringArray.Contains(query, StringComparer.OrdinalIgnoreCase);
        }
        Stop(watch, $"Linq Contains: OrdinalIgnoreCase", times);

        // Linq Contains: InvariantCultureIgnoreCase
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = stringArray.Contains(query, StringComparer.InvariantCultureIgnoreCase);
        }
        Stop(watch, $"Linq Contains: InvariantCultureIgnoreCase", times);

        // Linq Contains: CurrentCultureIgnoreCase
        watch.Start();
        for (int i = 0; i < times; i++)
        {
            contains = stringArray.Contains(query, StringComparer.CurrentCultureIgnoreCase);
        }
        Stop(watch, $"Linq Contains: CurrentCultureIgnoreCase", times);

        if (!contains)
            throw new Exception();
    }

    #region Miscellaneous
    public static string[] GetStringArray()
    {
        string words =
            @"the that not look put
            and with then don’t could
            a all were come house
            to we go will old
            said can little into too
            in are as back by
            he up no from day
            I had mum children made
            of my one him time
            it her them Mr I’m
            was what do get if
            you there me just help
            they out down now Mrs
            on this dad came called
            she have big oh here
            is went when about off
            for be it’s got asked
            at like see their saw
            his some looked people make
            but so very your an ";
        return words.Split(" ");
    }

    public static Stopwatch Start() => Stopwatch.StartNew();

    public static void Stop(Stopwatch watch, string item, int? cnt = null)
    {
        watch.Stop();
        string msg = $"{item,53}\ttook {watch.ElapsedMilliseconds,6:#,0} ms";

        if (cnt != null)
            msg += $" to execute {cnt:#,0} times ({watch.ElapsedMilliseconds * 1e3 / cnt:0.0} us per exec).";

        watch.Reset();

        Console.WriteLine(msg);
        Debug.WriteLine(msg);
        Console.WriteLine("");
        Debug.WriteLine("");
    }
    #endregion
}

Result

Case Sensitive Search
                   Loop with case sensitive equal   took    323 ms to execute 1,000,000 times (0.3 us per exec).
                            Array.Exists + Equals   took    445 ms to execute 1,000,000 times (0.4 us per exec).
                                Array.Exists + ==   took    461 ms to execute 1,000,000 times (0.5 us per exec).
                                    Array.IndexOf   took    511 ms to execute 1,000,000 times (0.5 us per exec).

Case Insensitive Search
                 Loop with case insensitive equal   took    408 ms to execute 1,000,000 times (0.4 us per exec).
                  Array.Exists + EqualsIgnoreCase   took    543 ms to execute 1,000,000 times (0.5 us per exec).
                 Linq Contains: OrdinalIgnoreCase   took    827 ms to execute 1,000,000 times (0.8 us per exec).
        Linq Contains: InvariantCultureIgnoreCase   took  6,220 ms to execute 1,000,000 times (6.2 us per exec).
          Linq Contains: CurrentCultureIgnoreCase   took  6,249 ms to execute 1,000,000 times (6.2 us per exec).

Edit: Added code to have MWE

\$\endgroup\$
  • \$\begingroup\$ Could you post the other functions, so the benchmark can be replicated? I made up some reasonable implementations, but I got different results. The .NET runtime version is also a variable: I used .NET Core 3.0. The result didn't contradict yours by the way, it was even more extreme, the plain loop was almost 2.5 times as fast as Array.Exists \$\endgroup\$ – harold Apr 3 '20 at 10:06
  • \$\begingroup\$ @harold Yepp, sorry. I edited and posted the complete class. Results are from running it using .NET Core 3.1 on a simply i5 3570 Win10 x64 machine. \$\endgroup\$ – embert Apr 3 '20 at 16:17
  • \$\begingroup\$ Aside: consider using benchmarkDotNet for this kind of micro benchmark. \$\endgroup\$ – AndreasHassing Apr 3 '20 at 21:50
  • \$\begingroup\$ I'm sorry but, unless this is an academic question, then any answer won't have any sense. This sort of comparison makes no sense without MUCH more context and a much more careful setup. Just to mention few: you're comparing with String.CompareOrdinal while you actually need String.Equal() with the appropriate comparer. Why? Because, in theory, an implementation MIGHT perform an ordinal case sensitive comparison slightly faster (for example because it just need to compare ZF after calling REPE CMPSx, this assuming that the compiler will optimize your own == 0 away anyway)... \$\endgroup\$ – Adriano Repetti Apr 6 '20 at 11:13
  • \$\begingroup\$ ...also, for IndexOf you're comparing different things then it doesn't really make sense to have it here. If - in the real world case - you will search inside the array multiple times then you'll find yourself that (MAYBE) to sort the array and then performing a BinarySearch is actually faster. Also, other approaches might be easier to make parallel (if the number of items in the array is big enough to justify it). \$\endgroup\$ – Adriano Repetti Apr 6 '20 at 11:15
3
\$\begingroup\$

I don't know why you are surprised plain loops are faster, without an explanation of why you were surprised, it is hard to comment on that. Linq is bound to have some overhead.

By vectorisation I guess you mean the use of special machine instructions, I doubt these would have any significant effect here. Most of the comparisons will fail at the first letter, so I don't see how a special string compare instruction would help.

A fast way of checking whether a string is in a large set of strings would be to use hashing, using the library class System.Collections.Generic.HashSet.

\$\endgroup\$

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.