Building LINQ from scratch with Stephen Toub

This is a great interview with the master of performance-optimization in .NET Stephen Toub. If you’re relatively well-versed in C#, .NET, and Linq, then you can just jump to the second video (linked below). I actually watched the second one first. I didn’t feel like I’d missed anything.

Deep Dive on LINQ with Stephen Toub by dotnet (YouTube)

Stephen Toub’s the guy who writes the 100+-page release notes on performance. See the following links.

• Performance Improvements in .NET 5 (46 pages)
• Performance Improvements in .NET 6 (109 pages)
• Performance Improvements in .NET 7 (170 pages)
• Performance Improvements in .NET 8 (235 pages)
• …more to come.

In this video, at 26:00, Scott flubbed the joke. It doesn’t really matter but, according to the article Two Hard Things by Martin Fowler, the original saying was:

This was “upgraded” to:

At 33:00, Toub talks about how the Current property of IEnumerable is not checked for nullability because … it can technically always be null, but we also don’t use it that much and we don’t want the compiler yelling at you for possibly-null access when the item type is a value type (for example) or a non-nullable reference type. See the code for the annotation and more comments.

At 49:00, they discuss the use of goto, where Hanselmann says, “there’s the kind that you can see; and there are the kind that are hidden,” which I feel like he fumbled as well. I think what he meant was that there are implicit gotos everywhere. A goto maps to an assembler jmp, so every if has an implicit goto. The break statement inside of a case block of a switch statement jumps (or goes to) the end of the switch block.

You should be careful about using goto—i.e., it’s a code smell—but sometimes it’s the clearest and most concise way of expressing intent. In their case, they used it to “fall through” from one case statement to the next with goto case 2.

I feel the same way about goto as I do about the continue keyword in a loop. I like to write all of my loops in a consistent and idiomatic manner. That means I use break. So, for me, using continue is a code smell, but sometimes it’s the most elegant way of expressing the intent.

At about 55:00, Hanselmann shows Toub how to use Winget to install SysInternals and then to use ZoomIt for presentations. This was a nice bonus that probably a lot of viewers didn’t know: (A) Zoomit is a poor tool compared to Ctrl + mouse-scroll on MacOS, but it’s better than nothing and (B) running Winget from PowerShell is a pretty powerful install-and-update tool on Windows.

In this presentation, I notice that Toub doesn’t use the “extract variable” refactoring either. I’m not sure whether something like that is available in VS. He also installs packages with the VS NuGet interface rather than just adding the package reference manually in the project file. I note other inefficiencies in his coding style in the notes to the second video below. He’s fast! …but he could be even faster.

An even DEEPER Dive into LINQ with Stephen Toub by dotnet (YouTube)

At about 22:00, he mentions something interesting that makes me change my opinion about the type to use for private variables. I’d always used interfaces to keep it clear which API my implementations depended on. This included list variables, which I would type as IList<IBase> instead of List<IBase>. Toub says that the second formulation is better for performance because the compiler doesn’t have to deal with virtual dispatch—it can just call the functions of List directly.

This makes me realize that it’s a good reason to use var. When you use var with new, the resulting type of the local variable will automatically be the “right” type for performance. The same goes for target-typed new expressions, which force you to use a non-interface type for fields.

At 27:00, they talk about the IDE features for tracking change and inspection states—the colorful splotches of color in the left and right gutters and on the vertical scroll bar. First of all, Toub doesn’t know left from right, but he’s a genius so we’ll grant him that. Second of all, neither he nor Hanselmann really understands what the file-state markings are.

The IDE tracks not only unsaved changes but also uncommitted changes. That’s why there is so much green in the gutter on the left and the right: because Toub had rewritten much of the file since the last commit but he’s been saving the file the entire time. It’s an important distinction to make for understanding what’s going on. The right-hand side of the right-hand gutter shows inspections: suggestions, warnings, and errors.

It was interesting to see that, since Toub uses Visual Studio without ReSharper, he instinctively used the mouse to copy/paste the name of the constructor from the class after he’d renamed the class. That is, he’d renamed the class and, in order to fix the constructor being named incorrectly, he copy/pasted with the mouse. With ReSharper, he could have just pressed Alt + Enter and selected the quick-fix called “This is a constructor”, which just renames the method to the name of the containing class.

I could see several places where he used the mouse rather than being able to stay on the keyboard, letting the IDE do his work for him. For example, he also copy/pasted the name of the iterator class again in order to use the more highly specialized version—but he could have just started typing to have the auto-complete suggest the right type. Or he could have used multiple clipboards to paste the type name that he’d just copied before (when he’d fixed the constructor).

When the type of the actual argument no longer matched the formal argument, he copy/pasted again to get the more specific type. Here, he could have also asked ReSharper to show variables in scope with an appropriate type. It would have shown only array and been done with it. No mouse, no copy/pasting, no moving away from the keyboard, no guesswork.

At about 35:00 or so, shit gets real, as Toub starts hand-optimizing the code for his iterator. He does some obvious stuff first, removing iterator complexity that is no longer needed when the iterator has to handle only fixed-length and integer-indexable arrays. Next, though, he does a neat trick with a uint cast that ensures that a check for i < source.Length will never be true, even if i is less than 0 (because (uint)-1 wraps to approximately 2 × int.Max, so it will never be less than Length. After that, he talks about how the jitter can use that condition to avoid the automated bounds-checking that comes with .NET’s managed code by default when indexing the array.

So the cast to uint not only avoids a branch, it also avoids the hidden cost of bounds-checking. Nice! 👏 After running the benchmark again, we can see that he’s rebuilt the optimizations available in C# by default. Very nice! 👏 👏 This is why running against a newer runtime and library may increase the performance ⏱ of your own code. Toub mentions that these types of optimizations are great, but they have to balance the value of the optimization versus the additional code to maintain as well as the size of the runtime assemblies.

At 49:00, he mentions that the size issue also affects Native AOT, since AOT can’t take advantage of PGO or anything else that the jitter has available to eliminate unnecessary code. AOT doesn’t have as much information available, so it can’t optimize away as much code. That is, if it can’t guarantee that only the array-optimized version is called, then it has to keep all of the versions, increasing the binary size. There are also vector-optimizations and SIMD-optimizations that may have to be included. For more information, see AOT, JIT, and PGO in .NET.

The extremely detailed chapter overview.

00:00:00 Deep Dive into Implementing Iteration in Programming
00:01:50 Understanding the Implementation and Functionality of Custom Iterators in Link
00:07:45 Discussing Optimization Strategies and Array Specialization in Programming
00:10:43 Understanding the Use of Sharp Lab and Compiler Optimization in C
00:15:20 Discussing Optimizations in Link Methods in Programming
00:16:39 Understanding SIMD and its Application in Computer Processing
00:20:12 Discussion on Code Analysis and Optimization Techniques in Software Development
00:23:46 Discussing and Implementing Iteration-Based and Manual Arrays in Programming
00:30:30 Exploring Compiler Optimizations and State Management in Programming
00:37:04 Exploring Hyper and Micro Optimization in Programming
00:40:11 Exploring Code Optimizations and Trade-offs in Programming
00:45:41 Discussing the Challenges and Implications of Optimizations in Software Performance
00:47:54 Discussing the Implementation and Optimization of Select in Programming
00:51:49 Discussion on Programming Syntax and Benchmarks
00:54:41 Implementing and Discussing Iteration Code in Programming
00:57:12 Understanding the Functionality and Implementation of C# Compiler Keywords
01:02:42 Improving Functionality and Performance of Manual Implementation of Iteration Methods
01:08:39 Exploring the Optimization and Implementation of Select Operators in Programming
01:12:57 Understanding and Optimizing Iteration Operations in Programming
01:18:09 Implementing and Utilizing LINQ Programming: A Two-Parter