Is foreach around 9% slower than old-school for-loop?

-
Thanks to #covid19, I've been trying to find ways to kill the lock-down boredom. I decided to investigate the performance of the traditional "for" loop compared to the somewhat more modern (well, modern in the last 20 years, haha) "foreach" loop. 

I remember back in the day when I was actually writing critical-path production code when a co-worker told me: don't use foreach, always use old-school for-loop because the former is much slower

The hypothesis is that the foreach requires use of reflection by the compiler to determine the exact data type of the element in the foreach, and that extra computation results in a slightly less optimized iteration than the traditional loop. True? Well...

I ran the code below for 100s of time. The result? Yeah, anywhere between 8.5% and 10% in favor of the old-school for-loop. Guess my co-worker was right... Cheers, stay safe, love, ACC.

for each:       35720075
old-school for: 32380036
old-school is 9.35059346879871% faster than foreach

public void TestFors()
{
    Random rd = new Random();
    string test = new string((char)(rd.Next(0, 26) + 'a'), 1000000000);

    char t = ' ';
    long ticksBefore = DateTime.Now.Ticks;
    foreach (char c in test) t = c;
    long tickAfter = DateTime.Now.Ticks;
    long x = tickAfter - ticksBefore;

    Console.WriteLine("for each:       {0}", x);

    t = ' ';
    ticksBefore = DateTime.Now.Ticks;
    for (int i = 0; i < test.Length; i++) t = test[i];
    tickAfter = DateTime.Now.Ticks;
    long y = tickAfter - ticksBefore;

    Console.WriteLine("old-school for: {0}", y);

    Console.WriteLine("old-school is {0}% faster than foreach", 100.0 * (x - y) / x);
}

Comments

  1. FredJuly 27, 2020 at 9:56 AM

    Not sure if I agree with the methodology :-)

    Here are my results using a more pragmatic approach(*):

    End of warm-up phase: 0
    End of collection phase: 0
    For loop
    Average: 20781.5728
    P50: 20000
    P90: 20035
    P95: 29997
    P99: 30025

    End of warm-up phase: 0
    End of collection phase: 0
    Foreach loop
    Average: 20551.2984
    P50: 20000
    P90: 20033
    P95: 20211
    P99: 30028

    Based on that, I'd say the difference is insignificant.

    *Approach:

    1. Instead of a single 1 billion entry loop (is that common?) I did 1000 loops over 1 million entries.

    2. Full GC before running each test (for or foreach).

    3. Ran 1000 loops for warm-up caches before running 1000 loops collecting time information.

    ReplyDelete
    Replies
    1. FredJuly 27, 2020 at 10:02 AM

      Source code:

      class PerformanceTests
      {
      private static Random random = new Random(0);
      private static int[] randomData = BuildRandomData(1000000);

      private static int[] BuildRandomData(int length)
      {
      int[] result = new int[length];

      for (int i = 0; i < length; i++)
      {
      result[i] = random.Next();
      }

      return result;
      }

      private static void FullGC()
      {
      GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced, true, true);
      GC.WaitForPendingFinalizers();
      }

      private static void WriteReport(string context, long[] ticks)
      {
      Console.WriteLine(context);
      double[] durations = new double[ticks.Length - 1];
      for (int i = 0; i < durations.Length; i++)
      {
      durations[i] = ticks[i + 1] - ticks[i];
      }

      Array.Sort(durations);

      Console.WriteLine("Average: " + durations.Average());
      Console.WriteLine("P50: " + durations[(int)(durations.Length * .50)]);
      Console.WriteLine("P90: " + durations[(int)(durations.Length * .90)]);
      Console.WriteLine("P95: " + durations[(int)(durations.Length * .95)]);
      Console.WriteLine("P99: " + durations[(int)(durations.Length * .99)]);
      }

      public static void ForLoop(int iterations)
      {
      var ticks = new long[iterations + 1];

      int limit = randomData.Length;
      int dummy = 0;

      for (int it = 0; it < iterations; it++)
      {
      for (int i = 0; i < limit; i++)
      {
      dummy = dummy ^ randomData[i];
      }
      }

      Console.WriteLine("End of warm-up phase: " + dummy);

      ticks[0] = DateTime.UtcNow.Ticks;
      iterations++;

      for (int it = 1; it < iterations; it++)
      {
      for (int i = 0; i < limit; i++)
      {
      dummy = dummy ^ randomData[i];
      }

      ticks[it] = DateTime.UtcNow.Ticks;
      }

      Console.WriteLine("End of collection phase: " + dummy);

      WriteReport("For loop", ticks);
      }

      public static void ForeachLoop(int iterations)
      {
      var ticks = new long[iterations + 1];

      int limit = randomData.Length;
      int dummy = 0;

      for (int it = 0; it < iterations; it++)
      {
      foreach (int value in randomData)
      {
      dummy = dummy ^ value;
      }
      }

      Console.WriteLine("End of warm-up phase: " + dummy);

      ticks[0] = DateTime.UtcNow.Ticks;
      iterations++;

      for (int it = 1; it < iterations; it++)
      {
      foreach (int value in randomData)
      {
      dummy = dummy ^ value;
      }

      ticks[it] = DateTime.UtcNow.Ticks;
      }

      Console.WriteLine("End of collection phase: " + dummy);

      WriteReport("Foreach loop", ticks);
      }

      public static void Run()
      {
      FullGC();
      ForLoop(10000);
      FullGC();
      ForeachLoop(10000);
      }
      }

      Delete
    2. FredJuly 27, 2020 at 10:05 AM

      Sorry, I ran 10,000 iterations over 1,000,000 elements, not 1,000 iterations.

      Delete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more