Imperative vs. LINQ Performance on WP7
Jesse Liberty had a nice post presenting the concepts around imperative, LINQ and fluent programming to populate a listbox. Check out the post as it’s a great example of some foundational things every .NET programmer should know.
I was more interested in what the IL code that would be generated from imperative vs. LINQ was like and what the performance numbers are and how they differ.
The code at the instruction level is interesting but not surprising. The imperative example with it’s creating lists and loops weighs in at about 60 instructions.
1: .method private hidebysig instance void ImperativeMethod() cil managed
2: {
3: .maxstack 3
4: .locals init (
5: [0] class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> someData,
6: [1] class [mscorlib]System.Collections.Generic.List`1<int32> inLoop,
7: [2] int32 n,
8: [3] class [mscorlib]System.Collections.Generic.IEnumerator`1<int32> CS$5$0000,
9: [4] bool CS$4$0001)
10: L_0000: nop
11: L_0001: ldc.i4.1
12: L_0002: ldc.i4.s 50
13: L_0004: call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> [System.Core]System.Linq.Enumerable::Range(int32, int32)
14: L_0009: stloc.0
15: L_000a: newobj instance void [mscorlib]System.Collections.Generic.List`1<int32>::.ctor()
16: L_000f: stloc.1
17: L_0010: nop
18: L_0011: ldloc.0
19: L_0012: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> [mscorlib]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator()
20: L_0017: stloc.3
21: L_0018: br.s L_003a
22: L_001a: ldloc.3
23: L_001b: callvirt instance !0 [mscorlib]System.Collections.Generic.IEnumerator`1<int32>::get_Current()
24: L_0020: stloc.2
25: L_0021: nop
26: L_0022: ldloc.2
27: L_0023: ldc.i4.5
28: L_0024: cgt
29: L_0026: ldc.i4.0
30: L_0027: ceq
31: L_0029: stloc.s CS$4$0001
32: L_002b: ldloc.s CS$4$0001
33: L_002d: brtrue.s L_0039
34: L_002f: ldloc.1
35: L_0030: ldloc.2
36: L_0031: ldloc.2
37: L_0032: mul
38: L_0033: callvirt instance void [mscorlib]System.Collections.Generic.List`1<int32>::Add(!0)
39: L_0038: nop
40: L_0039: nop
41: L_003a: ldloc.3
42: L_003b: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
43: L_0040: stloc.s CS$4$0001
44: L_0042: ldloc.s CS$4$0001
45: L_0044: brtrue.s L_001a
46: L_0046: leave.s L_005a
47: L_0048: ldloc.3
48: L_0049: ldnull
49: L_004a: ceq
50: L_004c: stloc.s CS$4$0001
51: L_004e: ldloc.s CS$4$0001
52: L_0050: brtrue.s L_0059
53: L_0052: ldloc.3
54: L_0053: callvirt instance void [mscorlib]System.IDisposable::Dispose()
55: L_0058: nop
56: L_0059: endfinally
57: L_005a: nop
58: L_005b: ldarg.0
59: L_005c: ldfld class [System.Windows]System.Windows.Controls.ListBox PerfTest.MainPage::LB1
60: L_0061: ldloc.1
61: L_0062: callvirt instance void [System.Windows]System.Windows.Controls.ItemsControl::set_ItemsSource(class [mscorlib]System.Collections.IEnumerable)
62: L_0067: nop
63: L_0068: ret
64: .try L_0018 to L_0048 finally handler L_0048 to L_005a
65: }
66:
67:
Compare that to the IL generated for the LINQ version which has about half of the instructions and just gets the job done, no fluff.
1: .method private hidebysig instance void LINQMethod() cil managed
2: {
3: .maxstack 4
4: .locals init (
5: [0] class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> someData,
6: [1] class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> queryResult)
7: L_0000: nop
8: L_0001: ldc.i4.1
9: L_0002: ldc.i4.s 50
10: L_0004: call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> [System.Core]System.Linq.Enumerable::Range(int32, int32)
11: L_0009: stloc.0
12: L_000a: ldloc.0
13: L_000b: ldsfld class [System.Core]System.Func`2<int32, bool> PerfTest.MainPage::CS$<>9__CachedAnonymousMethodDelegate6
14: L_0010: brtrue.s L_0025
15: L_0012: ldnull
16: L_0013: ldftn bool PerfTest.MainPage::<LINQProgramming>b__4(int32)
17: L_0019: newobj instance void [System.Core]System.Func`2<int32, bool>::.ctor(object, native int)
18: L_001e: stsfld class [System.Core]System.Func`2<int32, bool> PerfTest.MainPage::CS$<>9__CachedAnonymousMethodDelegate6
19: L_0023: br.s L_0025
20: L_0025: ldsfld class [System.Core]System.Func`2<int32, bool> PerfTest.MainPage::CS$<>9__CachedAnonymousMethodDelegate6
21: L_002a: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> [System.Core]System.Linq.Enumerable::Where<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, class [System.Core]System.Func`2<!!0, bool>)
22: L_002f: ldsfld class [System.Core]System.Func`2<int32, int32> PerfTest.MainPage::CS$<>9__CachedAnonymousMethodDelegate7
23: L_0034: brtrue.s L_0049
24: L_0036: ldnull
25: L_0037: ldftn int32 PerfTest.MainPage::<LINQProgramming>b__5(int32)
26: L_003d: newobj instance void [System.Core]System.Func`2<int32, int32>::.ctor(object, native int)
27: L_0042: stsfld class [System.Core]System.Func`2<int32, int32> PerfTest.MainPage::CS$<>9__CachedAnonymousMethodDelegate7
28: L_0047: br.s L_0049
29: L_0049: ldsfld class [System.Core]System.Func`2<int32, int32> PerfTest.MainPage::CS$<>9__CachedAnonymousMethodDelegate7
30: L_004e: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!1> [System.Core]System.Linq.Enumerable::Select<int32, int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, class [System.Core]System.Func`2<!!0, !!1>)
31: L_0053: stloc.1
32: L_0054: ldarg.0
33: L_0055: ldfld class [System.Windows]System.Windows.Controls.ListBox PerfTest.MainPage::LB2
34: L_005a: ldloc.1
35: L_005b: callvirt instance void [System.Windows]System.Windows.Controls.ItemsControl::set_ItemsSource(class [mscorlib]System.Collections.IEnumerable)
36: L_0060: nop
37: L_0061: ret
38: }
Again, not surprising here but a good indicator that you should consider using LINQ where possible. In fact if you have ReSharper installed you’ll see a squiggly (technical term) in the imperative code that says “Hey Dude, I can convert this to LINQ if you want to be c00L!” (or something like that, it’s the 2010 geek version of Clippy).
What about the fluent version? As Jon correctly pointed out in the comments, when you compare the IL for the LINQ code and the IL for the fluent code it’s the same. LINQ and the fluent interface are just syntactical sugar so you decide what you’re most comfortable with. At the end of the day they’re both the same.
Now onto the numbers. Again I expected the imperative version to be better performing than the LINQ version (before I saw the IL that was generated). Call it womanly instinct. A gut feel. Whatever. Some of the numbers are interesting though.
For Jesse’s example of 50 items, the numbers were interesting. The imperative sample clocked in at 7ms while the LINQ version completed in 4. As the number of items went up, the elapsed time didn’t necessarily climb exponentially. At 500 items they were pretty much the same and the results were similar up to about 50,000 items. After that I tried 500,000 items where the gap widened but not by much (2.2 seconds for imperative, 2.3 for LINQ). It wasn’t until I tried 5,000,000 items where things were noticeable. Imperative filled the list in 20 seconds while LINQ took 8 seconds longer (although personally I wouldn’t suggest you put 5 million items in a list unless you want your users showing up at your door with torches and pitchforks).
Here’s the table with the full results.
| Method/Items |
Like I said, at the end of the day it’s not a huge difference and you really don’t want your users waiting around for 30 seconds on a mobile device filling lists. In fact if Windows Phone 7 detects you’re taking more than 10 seconds to do any one thing, it considers the app hung and shuts it down. The results here are for Windows Phone 7 but frankly they're the same for desktop and web apps so feel free to apply it generally.
From a programming perspective, choose what you like. Some LINQ statements can get pretty hairy so I usually fall back with my simple mind and write it imperatively. If you really want to impress your friends, write it old school then let ReSharper do the hard work for!
Happy programming!