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

Status : 

 


4
0
Sign in
to vote
ID 449211 Comments
Status Active Workarounds
Type Bug Repros 1
Opened 5/13/2009 4:55:51 AM
Access Restriction Public

Description

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).

Sign in to post a comment.
Posted by Alex [MSFT] 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 Ed [MSFT] 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