Search

Linq.Last() has terrible and erratic performance by Joannes Vermorel - Lokad.com Forecasting API

Active

4
0
Sign in
 to vote
Type: Bug
ID: 449211
Opened: 5/13/2009 4:55:51 AM
Access Restriction: Public
0
Workaround(s)
1
User(s) can reproduce this bug
The method Last() is 300x slower than the naive implementation in the case of array. Worse, the performance is erratic as the Last() method execute faster when the array gets larger (while the performance for the naive version is very stable).
Details (expand)
Product Language
English

Version

.NET Framework 3.5 SP1
Operating System
Windows Vista
Operating System Language
English
Steps to Reproduce
Just compile and run the following stand-alone piece of code (it's a console program):

using System;
using System.Linq;
using System.Diagnostics;

namespace ConsoleTest
{
class Program
{
static void Main(string[] args)
{
int count = 10000000;
var watch = new Stopwatch();

var array = new Int32[1000];

watch.Start();
int k = 0;
for (int i = 0; i < count; i++)
{
k += array.Last(); // 10499ms
}

watch.Stop();
Console.WriteLine("Linq.Last() with Int32[1000]: {0}ms", watch.ElapsedMilliseconds);
watch.Reset();

watch.Start();
for (int i = 0; i < count; i++)
{
k += QuickLast(array); //
}

watch.Stop();
Console.WriteLine("QuickLast() with Int32[1000]: {0}ms", watch.ElapsedMilliseconds);
watch.Reset();

array = new Int32[10000];

watch.Start();
for (int i = 0; i < count; i++)
{
k += array.Last(); // 10499ms
}

watch.Stop();
Console.WriteLine("Linq.Last() with Int32[10000]: {0}ms", watch.ElapsedMilliseconds);
watch.Reset();

watch.Start();
for (int i = 0; i < count; i++)
{
k += QuickLast(array); //
}

watch.Stop();
Console.WriteLine("QuickLast() with Int32[10000]: {0}ms", watch.ElapsedMilliseconds);
watch.Reset();
}


/// <summary>Returns the last item of an array in O(1).</summary>
public static T QuickLast<T>(T[] array)
{
if (array.Length == 0)
{
throw new ArgumentOutOfRangeException("array",
"Can't retrieve last item because array is empty.");
}

return array[array.Length - 1];
}
}
}
Actual Results
Here are the output that I get on my machine:

Linq.Last() with Int32[1000]: 10605ms
QuickLast() with Int32[1000]: 32ms
Linq.Last() with Int32[10000]: 3531ms
QuickLast() with Int32[10000]: 33ms

Results are very stable from on run to another, and also from one machine to another.
Expected Results
I would typically expect 300x faster performance such as:

Linq.Last() with Int32[1000]: 32ms
QuickLast() with Int32[1000]: 32ms
Linq.Last() with Int32[10000]: 33ms
QuickLast() with Int32[10000]: 33ms
TAP Code (if applicable)
 
      You can indicate your satisfaction with how Microsoft handled this issue by completing this quick 3 question survey. [Details]

 

File Attachments
0 attachments
Sign in to post a comment.
Posted by Microsoft on 1/6/2011 at 7:16 AM
Thanks for reporting this issue you've encountered with Visual Studio!

There are definitely further perf improvements we could make to the base LINQ sequence operators, and this looks like a great candidate. We have a backlog of such improvements that we may investigate as a group at some point, however the priority is somewhat lower, as anyone who hits a particular perf snag with LINQ can easily write their own more-specific extension method that optimizes for particular types, such as IList<T>.

I've added a vote for optimizing IList<T>.Last() to the OneNote notebook we use internally to track these C# compiler and language requests. We can't promise if or when we'll get to this bucket of LINQ perf fixes, but we'll definitely keep it in mind during planning for the next release!

Alex Turner
Program Manager
Visual Basic and C# Compiler
Posted by Will Dean on 3/1/2010 at 7:44 AM
I've just been looking at this - obviously the cast to IList<T> is a big help over crude stepping through the array. However, the cast from something like int[] to IList<T> is still very time-consuming.

If you add

            TSource[] arr = source as TSource[];
            if (arr != null)
            {
                int count = arr.Length;
                if (count > 0)
                {
                    return arr[count - 1];
                }
            }                

Before the IList<T> cast, then the performance is dramatically (10x) better for arrays, and apparently no worse for Lists<>.

Perhaps this is something which could be considered?


Posted by Joannes Vermorel - Lokad.com Forecasting API on 5/26/2009 at 9:42 AM
Dear Ed,

We have been inspecting the code too, and we have been deeply surprised by the performed caused by the IList<T> cast. We don't really understand as that point why there are such a performance gap, but I really urge MS to optimize this method. A 300x slow down is not acceptable for a robust framework (it makes C# look like JavaScript performance-wise).

Although, it might also be possible that we have hit some hidden problem at the CLR level.

Best regards,
Joannes Vermorel
Posted by Microsoft on 5/26/2009 at 9:26 AM
Dear Joannes Vermorel - MVS,
Thanks for your investigation of the performance of Enumerable.Last(). I've inspected the implementation, and it has an optimization to deal with cases in which the source sequence implements IList<T> like your array case - cast to IList<T> and use the indexer method. I believe the implementation employs the most practical optimization available to us, and we won't invest further to improve the performance of this method. Thanks again for your comments.

Regards,

Ed Maurer
Development Manager, VB and C# compilers.
Posted by Rinat Abdullin on 5/14/2009 at 2:40 PM
Ok, it looks like these are partially memory-related effects.
After changing the order of tests, in order to be completely fair to the extension methods, everything looks like this:

QuickLast() with Int32[10000]: 26ms
Linq.Last() with Int32[10000]: 2993ms
QuickLast() with Int32[1000]: 11ms
Linq.Last() with Int32[1000]: 2418ms
Posted by Microsoft on 5/14/2009 at 12:23 AM
We were able to reproduce the issue you are seeing. We are escalating this bug to the product unit who works on that specific feature area. The team will review this issue and make a decision on whether they will fix it or not for the next release.

Thank you,
Visual Studio Product Team
Posted by Rinat Abdullin on 5/13/2009 at 5:03 AM
Same on my machine (RELEASE with no debugger attached)

Slower performance of Linq.Last could be expected by a safe cast cost, but these two lines puzzle me:

Linq.Last() with Int32[1000]: 10605ms
Linq.Last() with Int32[10000]: 3531ms
Sign in to post a workaround.
© 2012 Microsoft Corporation. All rights reserved. Microsoft Connect Terms of Use | Trademarks | Privacy Statement