Linq to Objects – measuring performance implications (part 1)

After working with Linq-to-objects, I started thinking about how this tool could work in the wrong hands.  At its simplest, a seemingly elegant query could easily turn into a CPU hog if the underlying data structure isn’t organized well.  At its best, how will these queries make use of the underlying data structures?


What to do?  Write some code and get some numbers to compare.


What I found was interesting, eye-opening and opened more questions for another day. I set out to compare Linq performance over a reasonably well-optimized data structure by varying the where clause composition and also comparing this to code going directly after the data structure in typical pre-Linq fashion.


What I learned was fascinating – let’s take a look at the code


Given a dictionary defined as:
private Dictionary<int, string> _lookupList = new Dictionary<int, string>();


I populate it using a loop where the upper limit is a const I can vary:
for (int x = 0; x < _listSize; x++ )
                _lookupList.Add(x, string.Format(“item#{0}”, x));


I can then use Linq to query the item dictionary with something like this:


            string[] myResult = (from i in _lookupList
                                 where i.Key >= lowerLimit && i.Key <= upperLimit && i.Value.Contains(“1″)
                                 select i.Value).ToArray();


Let’s take three variations as follows:


1)      where i.Key >= lowerLimit && i.Key <= upperLimit && i.Value.Contains(“1″)


2)      where i.Value.Contains(“1″) && i.Key >= lowerLimit && i.Key <= upperLimit


3)      Hand-code the query to go against the data structure to compare performance.


To make sure I varied the access in different areas of the dictionary, the query was performed against 10 discrete key values in the beginning, middle and end of the dictionary. Performance was consistent across each item, showing that Linq was utilizing the datastructure to some degree – as expected.  The .Contains method further reduced the return set to range from 1-2 items depending on where the midpoint was calculated. These test sets were run 10 times and the averages taken.


The results:


Item#1 – averaged 2643 ms
Item#2 – averaged 671 ms
Item#3 – averaged <1 ms


Observations: 


The difference between #1 and #2 is a factor of 4.  I am not sure how this actually performed but I suspect that item #2 scanned the entire contents of the dictionary.  It is hard to tell since a test where you eliminate the where clause results in a very different memory allocation pattern and therefore inherently larger timing numbers.


The difference between #3 and the other items is staggering.  Keep in mind, I tried to handicap this with a try/catch block around the indexer into the dictionary, stored the matching values in a List<string> and then performed a List<string>.ToArray() just for good measure. 


That’s eye popping – it’s more than two factors of 10 faster than the best optimized Linq query and more than three factors of 10 faster than the worst optimized. 


Bottom line – despite my best efforts I just couldn’t make my hand-written code perform as poorly as Linq. 


Summary:


So what did I learn? 


·         Variations on where-clause construction have an implied order when considering performance.  What are these implied rules exactly?  I’d love to know.


·         An entirely different test would have to be constructed to understand join performance.


·         How does the [Indexable] attribute play into optimization choices and what are the performance considerations of that attribute?


·         When doing intensive object querying,  Linq for Objects needs to be eyed very carefully in context of the application.


+++  Addition per Comment


Here is the code that Jimmy Bogard requested.  As noted in my post, I added exception handling and chose to use a List<string> to gather the match values and finally convert to an array of strings just as the Linq function did. If anything, I am going for the most conservative path in this case.  The call to this function is responsible for time measurement.


private void HandCodedAccessorFunction(int lowerLimit, int upperLimit)
        {
            List<string> result = new List<string>();
            int y = 0;
            for (int x = lowerLimit; x <= upperLimit; x++)
            {
                try
                {
                    if (_lookupList[x].Contains(“1″))
                    {
                        result.Add(_lookupList[x]);
                        y++;
                    }
                }
                catch (Exception)
                {
                     Console.Writeline(“Exception thrown”);
                }
            }
            string[] ar = result.ToArray();
            Console.WriteLine(y);
        }

This entry was posted in Featured. Bookmark the permalink. Follow any comments here with the RSS feed for this post.

16 Responses to Linq to Objects – measuring performance implications (part 1)

  1. Julian Birch says:

    The question of fairness is valid. The hardcoded version assumes a massive amount about the actual data in the structure, not just the data structure itself. For instance, the linq one will work if the dictionary is only populated with even numbers, will stop running after the first three if you ask it to, &c. You’d have to modify the hardcoded version to use yield return to match that semantic.

    Bear in mind that you can make the linq query use the same algorithm as the hardcoded version, simply by implementing a Numbers(from, to) function. The query then becomes

    from x in Numbers(lowerLimit; upperLimit)
    where _lookupList[x].Contains(“1″)
    select x

  2. shebert says:

    Hi Eric,

    Thanks – it makes perfect sense now. It’ll be interesting to see if MS makes any of the containers Linq-aware in the long run.

    I don’t believe you need paragraph tags – we use Community Server here and I’ve never seen a reference to paragraph tags in their documentation.

    Thanks again,
    -Steve

  3. Eric Lee says:

    Yes, that makes sense if you think about how Linq works. Linq can work in two modes; either it can do all the querying work itself using an IEnumerable interface on your container (in which case it has to use brute-force searching) or it can delegate the responsibility for intelligent execution to the container itself using an IQueryable interface.

    In the case of Linq to SQL, the SQL container implements IQueryable so the end result of a Linq to SQL query is not brute-force and can take advantage of all of the SQL engine’s goodness.

    In the case of the Dictionary<> object, it doesn’t implement IQueryable so Linq has no choice but to fall back to using the IEnumerable interface which of course bypasses all of the Dictionary’s key-based goodness. If Dictionary (or your snazzy custom-built data structure) implemented IQueryable, then that wouldn’t happen.

    So the lesson to learn here is that when you use Linq, you either need to make sure your container implements IQueryable or be prepared for IEnumerable-based algorithm performance. Which is a good lesson to learn because it’s not obvious at first glance, though it makes total sense after a few seconds thought. How could Linq possibly know how to take advantage of the quirks of every conceivable data structure? Obviously it can’t. It has its own strategy that works against anything that can manage to implement IEnumerable, and it can take advantage of custom strategies if they’re provided via IQueryable.

    (I haven’t used CodeBetter much before – are paragraph tags required for proper formatting in comments?)

  4. Anonymous says:

    I believe your HandCodedAccessorFunction is unfairly implemented, to compare apples with apples, you might want to try somethig like

    private void HandCodedAccessorFunction(int lowerLimit, int upperLimit)
    {
    List result = new List();
    int y = 0;
    foreach (KeyValuePair kv in _lookupList)
    {
    try
    {
    if (kv.Key >= lowerLimit && kv.Key <= upperLimit && kv.Value.Contains(“1″))
    {
    result.Add(kv.Value);
    y++;
    }
    }
    catch (Exception)
    {
    Console.WriteLine(“Exception thrown”);
    }
    }

    string[] ar = result.ToArray();

    Console.WriteLine(y);
    }

  5. shebert says:

    Eric – that’s great that you mention that. I was just running that experiment to see if Linq even pays attention to the underlying datastructure to make any optimizations. The answer is a resounding ‘no’.

    If I change my custom function to interate through the entire contents of the dictionary, using the order of the where clause to determine the order of my tests in the custom function then the results are nearly equal. There is slight benefit to the custom function, but it’s really immaterial (typically < 10% speed difference).

    So the bottom line is – if you hand Linq datastructure, performance will be the same as handing it an ‘array’ of elements without being able to leverage the underlying data structure.

  6. Eric Lee says:

    It’s important to draw the correct conclusion from this experiment.

    What the data are (probably) telling us is that Linq isn’t smart enough to realize that the dictionary key in this case is an “iterable” key, that is, that it could iterate through all possible values from the lower limit to the higher limit and look up values that way instead of doing a brute-force test of every key in the dictionary.

    If the key type was anything other than an int or char, like say a float or a string, then it wouldn’t be a iterable key and your hand-rolled algorithm wouldn’t work (at least not without some restrictions on the key data to make it iterable, like only whole-number floats or only strings of length one). I would expect Linq and the hand-rolled code to be much closer in performance in that case.

    So you did answer the question you asked in the beginning of your post: Linq doesn’t always take full advantage of the properties of the underlying data structure. You do have to think about things from Linq’s perspective and realize when it might miss a special optimizable case.

    However, it would (probably) be wrong to conclude that Linq performance is always poor. I haven’t run any experiments myself yet but I bet if you changed the dictionary key to an arbitrary string that Linq’s best time and your best hand-rolled time would be equivalent because you couldn’t take advantage of your “iterate over the key range” trick.

  7. Jimmy Bogard says:

    Ah the numbers are making sense now…your LINQ query iterates over the entire Dictionary, while the reference implementation only iterates over the bounds. The larger the source, the bigger the difference will be, especially if your upper and lower bounds are very close to each other.

    My guess is that the performance difference follows the same ratio as the difference between the bounds size and the total size of the list/dictionary.

    Very interesting stuff, deferred execution magic under the covers and what not.

  8. shebert says:

    Darrell,

    I couldn’t agree more. The question I am trying to get to the heart of is just how expensive is Linq to Objects. Based on that knowledge I can make better decisions of where to use and where not to – as you mentioned. Depending on your application and runtime pattern, this information simply gives me the ability to better understand the topic going into a project.

  9. Jimmy Bogard says:

    Also, I’d like to see what numbers you set for “_listSize”, “lowerLimit” and “upperLimit”. Without the original test code and these numbers it’s difficult to figure out the numbers.

    When compiled, LINQ to objects gets compiled into the Enumerable extension method calls, so it’s semantically equivalent to this:

    _lookupList.Where(i => i.Key >= lowerLimit && i.Key <= upperLimit && i.Value.Contains(“1″)).Select(i.Value).ToArray();

    That’s what you’ll see in reflector (minus the anonymous delegate stuff pulled out).

    There is no runtime-compilation of Linq to Objects as there is for Linq to SQL. Linq to SQL uses expression trees that have to be compiled at runtime.

    It’s not surprising the first query takes longer than the second. Boolean ANDs are short-circuited, and “Contains” is much more expensive than integer comparisons. Now I’m super-duper curious to see your reference implementation.

    Also note that the dictionary is not actually iterated over until you call “ToArray”.

  10. shebert says:

    Jimmy – I added the custom query to the end of the post. I have not looked at the profiler numbers yet. I am just looking at overall numbers to get a grasp of the collective overhead at this point.

  11. Ian Cooper says:

    LINQ To SQL expends a lot of extra time parsing the query expression tree and turning it into code (and SQL). To alleviate this issue Compile.Query lets you amortize that cost http://blogs.msdn.com/ricom/archive/2007/07/05/dlinq-linq-to-sql-performance-part-4.aspx

  12. Jimmy Bogard says:

    Have you looked at any profiler numbers? I’m very curious to know where the time was being spent. Underneath the covers, the LINQ query shouldn’t be doing much more than your custom query. Can you share what your custom query code was also?

  13. I guess this is one of those situations where you must weigh the ease of development and readability vs pure performance. Let the profiler tell us where it is slow later on if it feels slow. 2s vs 1ms for something outside a loop called once is a no brainer.

  14. shebert says:

    Darrell,

    That just brought up another thought: What I am testing is Linq to Objects, not Linq to Sql. However, in any call to the database you would have the actual database interaction + the linq overhead. I believe that isolating each of those cost components is pretty hard to do with Linq to Sql – and I wonder if Linq to Objects will effectively isolate the linq overhead and answer that question as well?

    That’s a great question that I cannot answer off the top of my head – it really depends on the Linq wiring that is specialized for linq to sql.

  15. shebert says:

    To answer Darrell,

    That’s a great question. I actually threw out the first value returned for the following reasons:

    1) It was consistently 85%-95% higher than all the other values.
    2) Given that I had just finished populating a large dictionary< ...> instance, I was concerned that the first run might not be an accurate measure.

    If I had included that first number, Linq’s performance would have looked worse. In hindsight, I should have included it simply because the first execution of my hand-written query did not have any performance degradation on first call.

    -Steve

  16. shebert says:

    My apologies to Darrell Wright – I hit the wrong button when responding to your Comment. Here it is:

    What about subsequent calls to the query? From what I understand, Linq will compile the query on the first use if you don’t precompile it. The 2s time may be reflecting this and on additional uses it will be faster.

    blogs.msdn.com/…/performance-quiz-13-linq-to-sql-compiled-query-cost-solution.aspx

Leave a Reply