locked
Is this benchmark test correct. Array vs List (0 ms vs 1100 ms) RRS feed

  • Question

  • Hello!

    I just like to ask if this benchmark test that I have done really is correct because the difference is amazing if this really is correct.

    As seen I am calling func passing on a List and returning a List

    As seen I am calling func passing on an array and returning an array

    I that 1,000,000 times and the benchmark is the below. Is it really true that for the array it takes 0 milliseconds and for the List 1100 milliseconds. The difference is Huge and if that is true. Arrays seems to be much more faster than Lists?

    Thank you!

            private void button4_Click(object sender, EventArgs e)
            {
                new Thread(benchmarktest1).Start();
            }
            void benchmarktest1()
            {
                int[,] arraynums = new int[300, 100000]; int[,] arraynumsOUT = new int[300, 100000];
                List<List<int>> nums = new List<List<int>>(); List<List<int>> numsOUT = new List<List<int>>(); String times = "";
                for (int i = 0; i < 300; i++)
                {
                    nums.Add(new List<int>());
                    for (int i2 = 0; i2 < 100000; i2++)
                    {
                        nums[i].Add(i2);
                        arraynums[i, i2] = i2;
                    }
                }
    
                Stopwatch stopw = new Stopwatch(); stopw.Start();
                for (int i = 0; i < 1000000; i++)
                {
                    func(nums, out numsOUT);
                }
                stopw.Stop(); times = stopw.ElapsedMilliseconds.ToString() + " milliseconds\n"; //1100 milliseconds
    
    
                stopw.Reset(); stopw.Start();
                for (int i = 0; i < 1000000; i++)
                {
                    func2(arraynums, out arraynumsOUT);
                }
                stopw.Stop(); times += stopw.ElapsedMilliseconds.ToString() + " milliseconds\n"; // milliseconds
                MessageBox.Show(times);
            }
            void func(List<List<int>> nums, out List<List<int>> numsOUT)
            {
                numsOUT = new List<List<int>>(nums);
            }
            void func2(int[,] arraynums, out int[,] arraynumsOUT)
            {
                arraynumsOUT = arraynums;
            }

    Thursday, April 16, 2020 8:19 PM

Answers

  • The mystery is why func is so fast. It took me a minute to work it out, it's a bit confusing.

    The constructor for List is copying the elements in that List. That means it is doing this...

    numsOut[0] = nums[0];

    numsOut[1] = nums[1];

    numsOut[2] = nums[2];

    ... and so on.

    That means it is copying a pointer to each element (a pointer to each List). So this is in between your original version of func2, which copies just one pointer, and the new version of func2 which copies every element in the two dimensions.

    You can see this if you try the following.

          void func(List<List<int>> nums, out List<List<int>> numsOUT)
          {
             numsOUT = new List<List<int>>(nums);
    
             numsOUT[0][0] = 999;
          }

    If you do this, you will see that, when you return from func, element [0][0] will be 999 in both nums and numsOut.

    Try changing func to copy element-by-element, like the new func2, and you should see they take a similar time with func2 slightly faster.

    And it would be a good idea to reduce the size of the arrays/Lists so it doesn't take quite so long, for testing purposes.

    • Marked as answer by Silvers11 Friday, April 17, 2020 3:19 PM
    Friday, April 17, 2020 1:09 AM

All replies

  • Hello,

    An array will always be faster than an array.Arrays are great for fixed number of elements while in many cases a list is great for variable number of elements, it all depends on what the task is and how important performance is over more code in some cases with arrays vs list.


    Please remember to mark the replies as answers if they help and unmarked them if they provide no help, this will help others who are looking for solutions to the same or similar problem. Contact via my Twitter (Karen Payne) or Facebook (Karen Payne) via my MSDN profile but will not answer coding question on either.

    NuGet BaseConnectionLibrary for database connections.

    StackOverFlow
    profile for Karen Payne on Stack Exchange

    Thursday, April 16, 2020 9:39 PM
  • Yes I just discovered that arrays can be extremely fast and I try to micro-optimize some code that is critical. 

    As you mention, I declare arrays like this with a predetermined allocation of 100 elements.

    int[] a = new int[100];

    Is it possible to not declare any elements and use .Add as one normally do with the Generic List?

    I have not really found an example of how to do that? I always see declaration of predetermined allocation.

    Thursday, April 16, 2020 10:02 PM
  • Greetings Silvers11.

    Arrays are faster than Lists, but not as much as your test suggests.

    Every time you call the method func, it creates a new List of Lists with a copy of all the elements of the list passed to the constructor. All that creation and copying takes time.

    But func2, on the other hand, only copies a pointer to the original array. It does not create a new array or copy any elements.

    So the test you are doing is unfair. Try creating a new array in func2 and copying all the elements, and you will see the times become a bit more similar. 

    Thursday, April 16, 2020 10:50 PM
  • Thanks Ante,

    I am not sure if I am writing the func2 functions correctly but it takes forever for this function to execute. func1 takes 1100 milliseconds and I have waited more than 2 minutes for this func2 to be finished. 

    I wonder if something is wrong with those declarations?

            void func2(int[,] arraynums, out int[,] arraynumsOUT)
            {
                int[,] newarray = new int[300, 100000];
                newarray = arraynums;
                arraynumsOUT = newarray;
            }


    • Edited by Silvers11 Thursday, April 16, 2020 11:43 PM
    Thursday, April 16, 2020 11:42 PM
  • I'm not sure why that is taking so long, but it's definitely not right. Remember, when you do this...

    newarray = arraynums;

    ... you are copying a pointer to the array, not copying the elements.

    You should be doing something like this.

          void func2(int[,] arraynums, out int[,] arraynumsOUT)
          {
             arraynumsOUT = new int[arraynums.GetLength(0), arraynums.GetLength(1)];
             for (int i = 0; i < arraynums.GetLength(0); i++)
             {
                for (int j = 0; j < arraynums.GetLength(1); j++)
                {
                   arraynumsOUT[i, j] = arraynums[i, j];
                }
             }
          }


    • Edited by Ante Meridian Friday, April 17, 2020 12:13 AM Removed 'static'
    Friday, April 17, 2020 12:06 AM

  • An array will always be faster than an array.

    @Karen -

    Hmm. So if it were a horse race, should I put my money on the array or on 
    the array?

    At the risk of appearing picayune, I suspect you meant to type:

    "An array will always be faster than a list."

    - Wayne

    Friday, April 17, 2020 12:27 AM
  • Yes then I understand, that is a pointer and not an actual copy of the array. That was very good to know.

    I tried with your code also and it takes that long time with your code also. I think it has gone more than 3 minutes and still the func2 is not ready.

    I am just thinking of that for func it takes 1100 milliseconds only. It is a mystery why it takes so long time?

    Friday, April 17, 2020 12:33 AM
  • The mystery is why func is so fast. It took me a minute to work it out, it's a bit confusing.

    The constructor for List is copying the elements in that List. That means it is doing this...

    numsOut[0] = nums[0];

    numsOut[1] = nums[1];

    numsOut[2] = nums[2];

    ... and so on.

    That means it is copying a pointer to each element (a pointer to each List). So this is in between your original version of func2, which copies just one pointer, and the new version of func2 which copies every element in the two dimensions.

    You can see this if you try the following.

          void func(List<List<int>> nums, out List<List<int>> numsOUT)
          {
             numsOUT = new List<List<int>>(nums);
    
             numsOUT[0][0] = 999;
          }

    If you do this, you will see that, when you return from func, element [0][0] will be 999 in both nums and numsOut.

    Try changing func to copy element-by-element, like the new func2, and you should see they take a similar time with func2 slightly faster.

    And it would be a good idea to reduce the size of the arrays/Lists so it doesn't take quite so long, for testing purposes.

    • Marked as answer by Silvers11 Friday, April 17, 2020 3:19 PM
    Friday, April 17, 2020 1:09 AM
  • Hi Silvers11,

    Thank you for posting here.

    First, look at the original code.

    Why is the execution of func2 so much faster than func1?

    Note that the code that calls these two methods is in the for loop, which means they will be called 100,000 times.

    Each time func1 is called, it creates a list with a length of 300, and each element is a list with a length of 100,000.

    In func2, it just point arraynumsOUT to the memory address of arraynums, without any element creation or modification.

    This is why the speed is so different.

    And for the following code:

          void func2(int[,] arraynums, out int[,] arraynumsOUT)
          {
             arraynumsOUT = new int[arraynums.GetLength(0), arraynums.GetLength(1)];
             for (int i = 0; i < arraynums.GetLength(0); i++)
             {
                for (int j = 0; j < arraynums.GetLength(1); j++)
                {
                   arraynumsOUT[i, j] = arraynums[i, j];
                }
             }
          }

    First, each call to func2 will create a new array, arraynums.GetLength (0) is 300, arraynums.GetLength (1) is 100000.

    That is, "rraynumsOUT [i, j] = arraynums [i, j];" will be executed 30 million times, and func2 will be called 100,000 times, so it will be very slow.

    Best Regards,

    Timon


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Friday, April 17, 2020 5:20 AM
  • In order to duplicate arrays, try Clone too. Check these variants:

    static void func( List<List<int>> nums, out List<List<int>> numsOUT )
    {
    	//numsOUT = new List<List<int>>( nums );
    
    	numsOUT = new List<List<int>>( nums );
    	for( int i = 0; i < nums.Count; i++ )
    	{
    		numsOUT[i] = new List<int>( nums[i] );
    	}
    }
    
    static void func2( int[,] arraynums, out int[,] arraynumsOUT )
    {
    	//arraynumsOUT = arraynums;
    
    	arraynumsOUT = (int[,])arraynums.Clone( );
    }
    

    Friday, April 17, 2020 7:53 AM
  • Ante,

    Thank you that was very good information. I know I have seen that before also that when you change like you did there:

    numsOUT[0][0] = 999;

    That it change in both variables. So it is actually a pointer that is created when assigning a List in that way. I have to be careful then when I do this so I know where all the memory is.

    Yes reducing the size for testing is a good idéa also.

    Thank you for your help!


    • Edited by Silvers11 Friday, April 17, 2020 3:19 PM
    Friday, April 17, 2020 3:18 PM

  • An array will always be faster than an array.

    @Karen -

    Hmm. So if it were a horse race, should I put my money on the array or on 
    the array?

    At the risk of appearing picayune, I suspect you meant to type:

    "An array will always be faster than a list."

    - Wayne

    It was a rather long day yesterday and will leave it at that :-)

    Please remember to mark the replies as answers if they help and unmarked them if they provide no help, this will help others who are looking for solutions to the same or similar problem. Contact via my Twitter (Karen Payne) or Facebook (Karen Payne) via my MSDN profile but will not answer coding question on either.

    NuGet BaseConnectionLibrary for database connections.

    StackOverFlow
    profile for Karen Payne on Stack Exchange

    Friday, April 17, 2020 3:29 PM