Measuring LINQ’s Performance
Back when LINQ was the next big thing, I remember the excitement of showing it to a fellow developer. He frowned and said it looked to slow to be usable. Not wanting to have my new toy taken away, I set out on a quest to justify it.
To compare LINQ to non-LINQ implementations, we must measure the execution time of each. If you’re a Computer Scientist type, you know we can analyze our algorithms using big O notation. One problem with this is that it requires having the LINQ source code. It also ignores other potential costs like increased function calls.
Intersection Results
The last post compared the maintainability of four methods that computed the intersection of two sets. The following graph illustrates how the run time increases as the set sizes grow.
Our goal is to compare the examples. The curvature of each line is more important than the actual times and set sizes.
What does the graph tell us?
- The nested
foreachis slow, because as the set size increases, the execution time increases exponentially. - The optimized sort first algorithm out performed the LINQ query.
- The LINQ call (
IEnumerable.Intersect) outperformed them all.
For this example, the call to IEnumerable.Intersect is both the simplest and fastest approach. If didn’t already exist, the verbose sort first would be our fastest option.
How to measure performance
To benchmark LINQ, we must execute it alongside whatever alternative algorithm we have. To produce the graph above, I used C# and the System.Diagnostics.Stopwatch.
First, run the function for each set size on the graph’s x-axis against a random set of values.
Tailor the range and distribution of the values in the set to fit your needs. To get a nice smooth
curve, execute each test thousands of times (I did 100,000), and then average them.
There is one caveat. LINQ uses lazy evaluation, which means that the query is not performed until it is needed. To time the query, you need to invoke a method like IList.ToArray() to force the evaluation.