Hacker News Reader

Comment by fuzzy2 | Hacker News Reader

I’m interested in what performance problems you’re seeing. Maybe then I won’t fall into the same trap in the future.

Off the top of my head, the only possibility I see is allocating objects with `Select` or the like. If one can avoid that, the only overhead should be the predicate/selector method calls...?

View on HN

At the very least, each LINQ method needs an enumerator, which, since it's typed as an interface, cannot be stack-allocated, even for value types (like List<T>'s enumerator). For Roslyn they noticed that the additional GC pressure was indeed a problem. But for most projects I wouldn't say it's much of a difference (and definitely don't start banning LINQ or other things unless a profiler tells you there's a problem).

Interestingly, c#’s foreach construct can operate on types that conform the the IEnumerable/IEnumerator interface even if they don’t implement it; you can have a GetEnumerator method return a struct with MoveNext and Current members and it will be stack allocated, so long as the variable on which you foreach is typed with the concrete type rather than IEnumerable.

Language integrated query comprehension is also duck-typed, so if you explicitly implemented Select and Where and friends to all return appropriately crafted structs, you could write full LINQ queries and enumerate them without heap allocations.

But you’re right that to use LINQ to objects you must have an IEnumerable because you rely on the type to bring in the extension methods.

Be interesting to imagine what c# language features would be needed to deliver a stack-allocatable LINQ...

But that’s ~one small-ish object per operator. Unless you’re using `SelectMany` or otherwise generating queries “in a loop” I don’t see how that could be so bad.

the gc pressure is normally not so bad, but there is also more indirection in each iteration. So you iterate slower, and evict more data on your cpu caches. Whether this "matters" depends of course. Are you doing a ton of work in each step through the collection? If so, the overhead of linq will be small relative to that. How much do you care about wasting microseconds and eating more battery/power? At scale these little things add up, it can get important quick. On small devices it can be important. For a personal script running on a powerful desktop, it definitely doesn't matter, and everything in between.

My LinqFaster repo has some benchmarks showing time differences for some common operations in a fairly worst case scenario (where the work done in each iteration is small) https://github.com/jackmott/LinqFaster

It would just be nice if C# reliably compiled this abstraction down to efficient code, the way C++, Rust, and Java Streams do.

There is also http://nessos.github.io/LinqOptimizer/

At least in my experience, problems with Linq are problems with optimization. For example, if you have an in-memory collection with 100,000 items, and you do collection.First(i => i.id == 123), that will be much slower than a dictionary indexed by id. (Refactor so you can do collection[123] instead of Linq.)

Some developers understand this, for other less savvy developers, it's just voodoo. In any case, if the collection is 100 items, there's no real advantage to optimizing.

Also, a foreach loop with an if statement is probably faster than a select statement, because it's not allocating a lambda and going back and forth in the stack; and a for loop indexed by a counter is probably faster than a foreach loop. Those, however, are micro-optimizations that really need their value shown in a profiler.

I once wrote a library that allowed indexing collections by different properties. It was quite intense, and it paid off as the application has lots of RAM-based queries and its internal collections can scale to 20,000 or 250,000 items.

(Unrelated: I wanted to open source the library, but my boss wouldn't let me. Sigh. Maybe I should have pushed back around my annual review that being able to put my name on a useful open-source library is important career development.)

In my experience, so much of the problems with Linq are problems with knowing the right data structures for the job, and that's something of a universal problem, Linq just makes it easier to forget to pay attention to what your data structures are; the same code written equivalently in indexed for loops or foreach loops makes the exact same mistakes. More junior programmers are just at least somewhat more familiar at spotting where they are using the wrong data type in a for loop or foreach, partly because they'd recognize when they have more loops than they expected (.First() when alone is a loop).

I've long joked that ToList() should be considered harmful, because it's an interesting crutch that gets over used and List<T> is so often the wrong data type for the operations to follow. Every time I have stepped in to performance optimize a Linq-heavy codebase, I've started by finding and removing nearly every use of ToList().

ToLookup() is one of the frequently unsung heroes of Linq that gets overlooked too often. It is the "indexing" operator, as ILookup<K, V> is the out-of-the-box multi-value Dictionary of .NET. I think ToLookup() gets overlooked often because there's no concrete, mutable Lookup<K, V> in the BCL (MultiValueDictionary<K, V> exists in the Experimental Collections NuGet package).

Deleting unnecessary ToList()s (where a query was "cut in half", presumably for debug reasons) and then converting nearly every remaining instance of ToList() to ToDictionary() or ToLookup() based on queries/usage patterns that followed was often alone a huge performance boost to Linq code that I found, simply because it was using a more useful data structure. Sometimes you don't even have to do any of the more complicated performance testing/debugging work and can stop there at the easy stuff.

So, I'm building a language with linq and the solution to this is how data is represented and if the trade off between memory and cpu is expressible via indexing. It seems that linq in c# is simply syntactic sugar rather than deploying a static analysis to extract optimizations.

A problem is Linq in C# is both: Linq against IQueryable<T> is often a case where a query planner gets involved (more often than not an SQL Database's decades optimized Query Planner); IEnumerable<T> takes the simplest in-memory generator/iterable approach that makes sense (one like most functional programming languages have used for decades).

I've thought for a long time that "coloring" IEnumerable<T> versus IQueryable<T> queries differently, at least at the syntax highlighting level, would go a long way to help people better their mental models of Linq. Especially at the complicated transition places where an IQueryable<T> query "falls back" to IEnumerable<T>.

best way to get familiar with the degree of overhead is benchmark some things with benchmarkdotnet using linq and with for loops. lists and arrays and ienumerables. you will build up an intuition for the costs involved. groupby in particular is really nasty. any time you want to use that just put things into a dictionary instead.

BenchmarkDotNet looks cool, thanks for that!

The problem is that I never had problems! (With LINQ-to-Objects performance.) That’s why I’m asking in the first place. Maybe I intuitively avoided all the pitfalls, who knows. It would be cool if you could share some (abstract) operator chains that caused problems in whatever you’re working on.

So I have some benchmarks in this repo showing some comparisons:

https://github.com/jackmott/LinqFaster

While those can look really bad - orders of magnitude slower! Keep in mind with things like Where/Select, its a fixed amount of overhead. If you are larger amounts of work, or IO in those clauses, then the fixed amount of overhead is small in comparison.

There are some common pitfalls you can avoid: Don't use GroupBy - it actually has a lot of overhead. Put things into a dictionary by hand instead. Instead of chaining together multiple Where clauses, just use one Where clause and the && operator. This saves you some overhead and has the same semantics. Consider whether you can presize a collection and then fill it up, rather than calling "ToList()" or "ToDictionary" because those will not presize the collection for you. The list will have to reallocate as it grows etc.

Keep in mind that depending on your .NET version, calls to Count() may have to actually iterate over the whole collection even if that isn't necessary. .NET Core 3 fixes some of those cases, older versions may iterate over an IEnumerable backed by a List just to get the count, when the count is already there.

At work right now, we just operate at very high scale, so in high traffic endpoints its worth it to pull microseconds of time out, and reduce memory use by bytes. Because everything gets multiplied by large numbers of requests.

Actually didn't know about `GroupByˋ. Quite strange, seeing how it builds buckets almost exactly like ˋDictionary<K, V>ˋ, according to Reference Source.

Thanks for your insight. I also found out .NET Core 3 has pre-sized versions of ˋToDictionaryˋ and possibly others.

Reply on news.ycombinator.com