Why is using an object property in LINQ slower than using a primitive?

Why does this LINQ query (Id is a property of type long in the Structure object):

IList<Structure> theStructures = new List<Structure>();
public int GetChildrenSlow(Structure aStructure){
   IEnumerable<Structure> childrenQuery =
                         from structure in theStructures
                         where structure.ParentStructureId == aStructure.Id
                         select structure;
   int count = childrenQuery.Count();
   //Functionality continues...
}

Run slower than this one:

IList<Structure> theStructures = new List<Structure>();
public int GetChildrenFast(long aStructureId){
   IEnumerable<Structure> childrenQuery =
                         from structure in theStructures
                         where structure.ParentStructureId == aStructureId
                         select structure;
   int count = childrenQuery.Count();
   //Functionality continues...
}

I am making this call thousands of time (recursively) and using the property is much slower than using the long directly. If I pull the Id out and store it in a long variable before I execute the LINQ command the speed is pretty much equivalent to the speed of GetChildrenFast. Why is using an object property in LINQ slower than using a primitive?

Working Example:

namespace ConsoleApplication1
{
   class Structure
   {
      public int Id
      {
         get; set;
      }

      public int ParentStructureId
      {
         get; set;
      }
   }

   class Program
   {
      private IList<Structure> theStructures = new List<Structure>();
      public Structure FirstStructure
      {
         get; set;
      }

      private int FastCountStructureChildren(long aStructureId)
      {
         IEnumerable<Structure> childrenQuery =
                         from structure in theStructures
                         where structure.ParentStructureId == aStructureId
                         select structure;

         int count = childrenQuery.Count();
         foreach(Structure childStructure in childrenQuery)
         {
            count += FastCountStructureChildren(childStructure.Id);
         }
         return count;
      }

      private int SlowCountStructureChildren(Structure aStructure)
      {
         IEnumerable<Structure> childrenQuery =
                         from structure in theStructures
                         where structure.ParentStructureId == aStructure.Id
                         select structure;

         int count = childrenQuery.Count();
         foreach(Structure childStructure in childrenQuery)
         {
            count += SlowCountStructureChildren(childStructure);
         }
         return count;
      }

      public void BuildStructure()
      {
         FirstStructure = new Structure{Id = 0, ParentStructureId = -1};
         theStructures.Add(FirstStructure);
         //The loop only goes to 6000 as any more than that causes
         //a StackOverflowException my development machine.
         for(int i=1; i<6000; i++)
         {
   开发者_StackOverflow中文版         Structure newStructure = new Structure{Id = i,ParentStructureId = i - 1};
            theStructures.Add(newStructure);
         }
      }

      static void Main(string[] args)
      {
         Program program = new Program();
         program.BuildStructure();

         Stopwatch fastStopwatch = new Stopwatch();
         fastStopwatch.Start();
         program.FastCountStructureChildren(0);
         fastStopwatch.Stop();

         Stopwatch slowStopwatch = new Stopwatch();
         slowStopwatch.Start();
         program.SlowCountStructureChildren(program.FirstStructure);
         slowStopwatch.Stop();

         Console.WriteLine("Fast time: " + fastStopwatch.Elapsed);
         Console.WriteLine("Slow time: " + slowStopwatch.Elapsed);
         Console.ReadLine();
      }
   }
}

Running your full example as you provided

Fast time: 00:00:01.6187793
Slow time: 00:00:01.3977344

Only if I run in debug mode is the slow time actually slower. That is because in debug mode methods are never inlined, and there are NOPs littered everywhere to allow you to break, e.g. inside the Id getter.

Since you obviously care about run speed, I'll point out an unrelated inefficiency: you're running the query twice: once for count and once for iterating over the children. Running it only once (and increasing count by 1 in the loop) should speed things up.

The way I'd usually solve this problem, by the way, is if it ever makes sense to call the GetChildren method directly with an id, provide two overloads. Otherwise, provide the one (Structure) overload and get the id before the query, as in long id = aStructure.id;.

Well, even though the property access is inlined, it's still got to do a nullity check on each iteration, I suspect. That's an extra condition, which may be screwing up branch prediction for example.

It would be interesting to play with a complete example, but I suspect it's just the fact that you're performing an extra operation on every single delegate call. It's also possible that that "extra little bit" has turned off some other bit of inlining to do with the delegate, causing a sort of domino performance effect.

Long is a struct, it has a different construction and memory footprint than an object, which is apparently slower and I believe larger.

In "Functionality continues", do you use childrenQuery again? Do you realize this re-enumerates theStructures each time? Don't enumerate the large dataset so many times and the access cost of a property on each item won't hurt so bad.

IList<Structure> theStructures = new List<Structure>(); 
ILookup<int, Structure> byParentId = null;

public int GetChildren(Structure aStructure){
   if (byParentId = null)
   {
     byParentId = theStructures.ToLookup(x => x.ParentStructureId);
   }
   List<Structure> children = byParentId[aStructure.Id].ToList();
   int count = children.Count; 
   //Functionality continues... 
} 

The property value cannot easily be statically determined to be safely cacheable because side effects are allowed in C#. For example, imagine if this was your code:

public IEnumerable<Structure> FetchChildren()
{
    for (int i = 0; i < 10; i++)
    {
        aStructure.Id++;
        yield return GetChild(a.Structure.Id);
    }
}

public int GetChildrenSlow(Structure aStructure){
   IEnumerable<Structure> childrenQuery =
                         from structure in FetchChildren()
                         where structure.ParentStructureId == aStructure.Id
                         select structure;
   int count = childrenQuery.Count();
   //Functionality continues...
}

As you can see, aStructure.Id changes while you enumerate. True, in your case, none of your enumeration code has side effects, but C# isn't smart enough to know that. Also, it's not only enumeration that could have the side effects. For example:

IList<Structure> theStructures = new List<Structure>();
public int GetChildrenSlow(Structure aStructure){
   IEnumerable<Structure> childrenQuery =
        theStructures.Where(s => s.ParentStructureId == aStructure.Id++);
   int count = childrenQuery.Count();
   //Functionality continues...
}

And there's always multi-threading that can mess things up as well. Because of the possibility of mutation, the hit you'd take for checking the property value is just a necessity.