Classes vs. structs in .NET: how not to teach about performance
sergeyteplyakov.github.io
sergeyteplyakov.github.io
Sure, It took me a few head scratches myself originally to understand lazy/unintentional multi-evaluation, but for the original article to still push a PERFORMANCE article through even while the results so clearly say there's something very unexpected happening, boggles the mind.
Do not be single-minded and bulldoze a hypothesis even if you are in a teacher's role. This reminds me of the "nothing to see here" police squad scene with the second example being 100x slower being ignored lol
It's clear that lambdas can be confusing to both humans and tooling, and fixing the latter seems the most viable. Visual Studio greying out LINQ lambda code that isn't reachable given current invocation patterns would be a nice start, and doesn't seem unfeasible to me given the kind of code analysis already done...
I see the same thing when teaching people to program for Apache Spark (which took inspiration from DryadLINQ). They keep wanting to do things in an imperative way. It typically results in unnecessarily complicated code, and it always interacts terribly with the computational model. But it's also the way they've been conditioned to think over years or decades, and, from what I've seen, is often so deeply baked into their thought process that doing it any other way is, at best, deeply uncomfortable.
This is in fact important for two reasons:
1. General inefficiencies as mentioned.
2. There are plenty of `IEnumerable` things out there that -cannot- be repeatedly enumerated. Not the majority, but enough that you can run into day-to-day.
to me, all of the benchmark code looks like an obvious opportunity for dead store elimination. especially this loop in the second round:
for (var i = 0; i < classes.Count(); i++)
{
var x = classes.ElementAt(i).Name;
}
Extrapolating it to a larger sense, this SO thread explains it a little bit.
The GC since the top answer has changed quite a bit; I'd read about the changes to the .net clr/framework since v5/6
as a human, it is obvious from that snippet alone that the variable x is never read. therefore, unless `classes.ElementAt(i).Name` has some side effect, the entire loop could be replaced with a no-op without changing the program semantics.
so my question isn't about GC behavior at all. I expect the entire loop to be optimized away (no code emitted). why doesn't c# make this optimization? is it something subtle about how properties work, or does the compiler not attempt these optimizations in general?
.ElementAt() OTOH has a chance to throw in most implementations AFAIR so yeah, a bit of a moot point in this case.
Edited to add:
Actually, there -could- still be side effects in the case of .Name on a class, specifically, it's possible that .ElementAt() could return a null. I'm not sure what cases (if any) that the JIT could get around that.
OTOH, in the case of a struct, as long as .ElementAt() -doesn't- throw, .Name will always return regardless of if it is a property or field, and as part of a struct the compiler should do a good job of inlining as long as the access has no side effects (and you don't have too many fields on the struct!)
It's kind of down to C# being compiled into bytecode and then JIT compiled at run-time. During the initial compilation phase, the compiler doesn't necessarily have enough information to know whether `ElementAt()` or `Name` has side effects. (I assume here that Name is a property getter and not a field, in keeping with .NET conventions.) And then at run time the JIT compiler isn't as aggressive as an AOT compiler would typically be about optimization, so it may be less likely to do any dead store elimination.
On top of this recent advancements in .net have lead to native AOT.
Something to look into.
Microsoft has been making major moves in how c# gets compiled (AOT/JIT/Native). This is a concurrent effort to cross-platform support.
In doing going so they've minimized performance differences with other languages. The only thing they've yet to completely tackle is memory handling, so in reality, while it might not seem like it at first, your question is asking about that subject. Also some small tidbits with property accessors that the other comments have noted. To my knowledge these will be optimized away soon.
The GC is responsible for allocation and destruction.
And thread management.
> The only thing they've yet to completely tackle is memory handling,
And thread management.
Async/Await did a whole lot to help with concurrency, IValueTaskSource and IThreadPoolWorkItem helped bring the allocation cost for that back down...
But I still don't have a good way to, say, hint to the scheduler that 'these async work loops are important enough that I want them to always run in this dedicated group of threads'.
Also, having a way to get high precision Sleep() without hacks that have impact on the rest of the system would be nice too.
Putting side effects in an `ElementAt` implementation would be an extremely bad idea, but C# won't actually stop you.
So these optimizations would have to occur in the JIT and might come at the cost of worse startup time or memory usage.
Fwiw modern .net is getting pretty good at devirt but I don't expect it would optimize all this out.
e.g.
var classes = Names.Select(x => new PersonStruct { Name = x }).ToList();
for (var i = 0; i < classes.Count; i++)
In contrast, in Python, initial use exhausts generators. Subsequent iterations turns up empty. A gotcha, but also a way to highlight misuse, as it should show up in testing.
But the thing I wanted to highlight is that the blog author is a real authority on structs vs classes at a very very low level. His series on structs performance are must read for any .NET dev who cares about performance at low level. E.g. when to use readonly structs or when to use a mutable one to avoid excessive copying. That kind of things. https://devblogs.microsoft.com/premier-developer/author/sete...
He has published two analyzers on NuGet and both are must have. One is focused on the struct usage ErrorProne.NET.Structs and, for example, highlights cases of defensive copies and could suggest when to make a struct readonly.
https://devblogs.microsoft.com/premier-developer/avoiding-st...
Benchmarking is hard. If not an art then at least a distinct skill. It goes beyond just using Bnechmark.Net. It's a good first step but far from enough. Oftentimes one need to make sure a compiler does not optimize away some benchmark paths, e.g. by using volatile field accesses. Especially if you want to avoid overheads and measure only certain things. But here it was so obvious it could be meme-tagged #YouHadOneJob.
Author has made a career out of providing teaching materials, but hasn't worked to solve actual problems (e.g. in industry) for so long that their skills have degraded. One possible explanation.
Just because you put a name on a plain wrong idea doesn't make it true.
> Benchmarking is hard.
There were no benchmarks since the author didn't even understand how to write simple C#. A subtly flawed benchmark would be a whole different story.
.NET is probably lacking good content. Yet many things from Java are directly applicable.
E.g. on benchmarking & performance, there are true gems on InfoQ by Gil Tene, Martin Thompson, et al. I would pay for that content after watching it. A problem with paid courses is that payment goes first before evaluation. Maybe both sides do not care in cases such as corporate spend on continuous education...
Also, structs do not use an allocator, this is basics of many programming languages - they simply represent a structure in memory, which by default is placed on the stack. Think an integer variable in a local method scope.
(And in a language with stackful closures the stack itself is GCed.)
The following factors contribute to “structs being faster”:
- Heap allocations have go to through allocation calls, which need to find free memory, possibly zero it out, and then return pointer (reference) to it, both in managed and unmanaged languages, with C# being much faster at small object allocation (tlv read, pointer bump, and object header write) while unmanaged wins for large allocations instead (you don't have to go through LOH and extra cost associated with it). In comparison, stack is already zeroed for structs that are written to it, and those are just movs (or ldr/ldp's and str/stp's in case of arm64), and even then, only when spilled to stack at all (see below)
- Stack may not be the best way to describe it - think "local exclusively owned memory" which means that compilers, no matter how strict, can reason about the exact lifetimes of local values and the changes that happen to them. This means that all struct values can be promoted to CPU registers and never touch memory unlike with heap allocations, where multiple reads of the same property may require repeated dereferencing to account for the fact that object memory may be globally observable. This in turn applies to optimizations like CSE which can elide multiple identical checks against struct values knowing they won't change between operations.
- In .NET, generic method bodies for class-based generic arguments are shared (closest example in Rust - Box<dyn Trait>-based dispatch but with less overhead). However, struct generic arguments force method body monomorphization aka emitting specialized version for the exact generic type, which allows to write code with zero-cost abstractions the same way one would do in Rust with generics or in C++ with templates.
This is absolutely not true. Where are you getting this from? Pray tell, what you think this is: https://github.com/dotnet/runtime
This is not possible. A stack is a bump pointer allocator and is the same as any other bump pointer allocator. This includes having to decide when/if to zero memory. (The best time is on free because of memory compression, but most implementations don't do this.)
It's certainly not true that the unused part of the stack is always already zeroed; what if you already used it once? (But it is true if you zero on free.)
> - Stack may not be the best way to describe it - think "local exclusively owned memory" which means that compilers, no matter how strict, can reason about the exact lifetimes of local values and the changes that happen to them.
This is escape analysis and applies to anything with a known lifetime.
Be it C++, Rust or C#, the necessary space on stack is usually reserved in function/method prologue when known statically. Additionally, because C# guarantees that all local variables/memory are initialized, the corresponding stack space is pre-zeroed (it is efficient since it is done with widest applicable writes - scalar, sse/avx(2/512)/neon, etc. (arm64 has dczva which kicks in above certain threshold).
Regardless, the cost is not in bumping the offset/ptr or zeroing out the memory, it is in going through the allocator call (even if it's inlined, you're still executing more code) and the book-keeping required for heap allocations in general (both .NET's GC and allocators like Mimalloc do it), and then there is subsequent cost for tracking and collecting objects in the case of GC.
In addition, .NET does not do escape analysis because, again, it is not JVM - while it may be added in the future, it is (relatively) unprofitable to do today because allocation traffic is far lower since everything isn't a potentially escaping object, and structs or stack-allocated buffers are often used in performance-sensitive code (or where it makes sense to do so in general). The way .NET views the objects is similar to the way C++ views heap allocated data, albeit with less aggressive (and often unsound or UB) assumptions compared to GCC. I cannot stress this enough that while JVM's escape analysis does lead to object stack-allocation, the reasoning the compilers can do about state of the data on stack is what e.g. JVM gets as a result of doing escape analysis, not vice versa. And other "unmanaged" languages are subject to similar limitations when it comes to stack vs heap.
I've noticed Microsoft seems to think ordinary compiler optimizations are deep magic they're very proud of not implementing. Do they just not have good enough compiler people?
Yeah I meant scalar replacement!
What in our discussion has prompted you to respond with an ad-hominem attack?
Anyway, it's the part about how C# doesn't need to implement scalar replacement because it has structs. Do it anyway, it's good!
But I've also noticed (reading some .NET developer blog post I couldn't find for you now) them talking about how they couldn't do inlining because it would take too long and be too slow, so they put some very simple heuristics that did not look like a good trade off. Inlining of course is often very beneficial and can decrease code size.
Rather than imagining issues .NET has without verifying them first and then complaining, I'd like to suggest to spot check assumptions with Godbolt[0] which would be a good start (it can't show DynamicPGO, NativeAOT-specific and some other opts but is still fairly illustrative).
A more comprehensive view of produced asm can be acquired with [DisassemblyDiagnoser] attribute when running code with BenchmarkDotNet [1] (in the Java world a similar solution is called JMH).
[1] https://benchmarkdotnet.org/articles/guides/getting-started....
Do you know enough about C# to realize that .Select() by itself doesn’t materialize the collections, making the benchmark completely nonsensical?
The query structure is the same because it was a failed attempt to evaluate classes vs. structs, not one query vs. another.
And "structs are more performant" isn't even a correct conclusion; they're pass-by-value, so you could construct benchmarks where the copy time outweighs heap memory allocation time, eg constructing a large object once and passing it to a function many times.
Allocation time is going to be around the same for both types due to the GC, but there are performance implications depending on what you do later. In particular you can avoid garbage collection with appropriate use of structs but pass by value can mitigate those improvements.
I would very much verify anything and not take it at face value when a C# performance post use LINQ.
It does have base cost (allocating iterator object(s)), but it's less than what you think, I have seen enough game code that does intermediate list allocations when it doesn't need to, which are far costlier than LINQ.
In addition, the benchmarks that do other positive work alongside the benchmarked aspect can sometimes be more illustrative and overall better because it is much more important how a particular approach works together with surrounding code, matching more closely real world scenarios.
And last but not least - in this case using structs yields additional advantage with LINQ since monomorphization of methods where generic arguments are structs has additional codegen quality benefits.
This type of thinking ("LINQ bad" or "SOLID good") is one reason among many why bad patterns proliferate through the projects e.g. "hey you should rewrite this code with SOLID principles in mind" (without accounting for the context) or "This code calculates the sum using LINQ, you should rewrite it" (LINQ's Sum implementation uses SIMD and is hard to beat).
https://devblogs.microsoft.com/dotnet/performance_improvemen...
> dotnet/runtime#64470 is the result of analyzing various real-world code bases for use of Enumerable.Min and Enumerable.Max, and seeing that it’s very common to use these with arrays, often ones that are quite large. This PR updates the Min<T>(IEnumerable<T>) and Max<T>(IEnumerable<T>) overloads when the input is an int[] or long[] to vectorize the processing, using Vector<T>. The net effect of this is significantly faster execution time for larger arrays, but still improved performance even for short arrays (because the implementation is now able to access the array directly rather than going through the enumerable, leading to less allocation and interface dispatch and more applicable optimizations like inlining).
What are the chances that you'd have patience to write a competitive bug-free SIMD implementation?
I suspect the BCL doesn't include zero-allocation query operators because they generalize poorly, but I'm not sure. Zero-allocation query operators end up looking like 'ZeroAllocSelect<TEnumerable, TSource, TResult> Select (this TEnumerable seq, Func<TSource, TResult> func) where TEnumerable : IEnumerable<TSource>' which is obviously not trivial for the JIT to compile (or trivial to write)
The closures it creates for your queries are kind of a pain though. It's possible that will have improved in NET8 or NET9 because the allocation rules for delegates were recently revised to allow more optimizations, but I don't know if that was fixed.
It is extremely uncommon in performance contexts. It is actively discouraged and removed when writing performant C# code.
It is incredibly common in your "run of the mill" enterprise apps, or contexts where performance can slow down a bit for the sake of programmer happiness.
It’s perfectly fine to use if you learn about how it works and how to use it properly.
LINQ adding overhead is a _technical reality_, it's how it works and that is fine. It's a fine tool in many difference contexts, but when we talk about performant code the context is obviously one in which every cycle matters.
And those of us with enough experience know that LINQ performance and implementation details varies over time in the runtime, and those shifts aren't always positive.
So when writing code where performance is fundamental to the success of the application, avoid LINQ since it WILL add overhead and it will remove implementation control from your team. It is a risk without much benefit when you're in the performance arena. That doesn't mean it's not useful in many other contexts.
I'd certainly be careful about LINQ in certain performance-sensitive code, e.g. about creating unnecessary copies of the data and allocating too much. But I would not trust myself without measuring to really know whether it actually makes a difference or if my "optimized" code might be even slower.
Are you sure? Any examples of such methods? And does AVX actually helps?
I don’t think that’s possible because IMO AVX and other SIMD can only help for dense inputs. The C# type is ReadOnlySpan, however ReadOnlySpan doesn’t implement IEnumerable and therefore incompatible with LINQ.
There’s even an alternative LINQ to workaround https://github.com/NetFabric/NetFabric.Hyperlinq but that thing is a third-party library most people aren’t using.
Still, the support seems very limited. They simply probe argument type for arrays and lists. Any other IEnumerable gonna return false from TryGetSpan, which reverts to the legacy scalar implementation.
it's faster in bigger arrays/lists but smaller ones barely make a difference, even the linq vs non-linq make basically only noise difference as far as I remember.
What is your argument then?
I believe it’s technically possible to vectorize more complicated stuff in C#, just the runtime library is not doing that. For an example, look at how Eigen C++ library https://eigen.tuxfamily.org/index.php?title=Main_Page does their math. Under the hood, they wrap inputs into classes which supply SIMD registers, then do math on these registers. Eigen does that in compile-time with template metaprogramming. A hypothetical C# implementation could do similar things using generics and/or runtime code generation. LINQ from the standard library was never designed for high-performance compute, but I think it might be possible to design similar API for that.
The niche scenario you have outlined is partially covered by a recent System.Numerics.Tensors package update (even though I believe it would have been best if there was a community-maintained package with comparable quality for a variety of reasons).
The goal of LINQ itself is to offer optimal codepaths when it can within the constraints of the current design (naturally, you could improve it significantly if not for backwards compatibility with the previous 15 or so years of .NET codebases). The argument that it's not good because it's not the tool to do BLAS is just nonsensical.
There is, however, an IL optimizer that can further vectorize certain common patterns and rewrite LINQ calls into open-coded loops: https://github.com/dubiousconst282/DistIL
The people I responded to were discussing applicability of LINQ. I think very fast sum of List<int> collections doesn’t compensate for suboptimal performance of pretty much everything else.
For 80% of problems that “suboptimal” is still fast enough for the job, but for other 20% it’s important. Using the same C# language it’s often possible to outperform LINQ by a large factor, using loops, SIMD intrinsics, and minimizing GC allocations.
> partially covered by a recent System.Numerics.Tensors package
They don’t generate code in runtime, they treat C# as a slower and safer C. I’m pretty sure the higher-level parts of the runtime allow more advanced stuff, similar to expression templates in Eigen, but better because runtime codegen could account for different ISA extensions, and even different L1/L2 cache sizes.
The article itself says it:
> However, the main reason why the benchmarks are not correct is because of LINQ and lazy evaluation.
Spoiler: the benchmarking code had quadratic complexity instead of linear. Yes, in the course on performance.
Perhaps just a wording problem, but big-O notation doesn't care about constant factors.