12 ms·
“ZLinq”, a Zero-Allocation LINQ Library for .NET
- incoming1211 1y agoIs there a reason these sort of improvements cannot be contributed back into .NET itself?
- lmz 1y agoI can easily imagine the kind of person that goes out and builds something like this would have little patience with the bureaucracy of getting it integrated into .NET.
- CharlieDigital 1y agoI'd say it's less about bureaucracy and more about what the .NET team has to consider when they make sweeping changes. Backwards compatibility, security, edge cases, downstream effects on other libraries that are reliant on LINQ, etc. One guy with an optional library can break things. If the .NET team breaks things in LINQ, it's going to be a bad, bad time for a lot of people. I think Evan You's approach with Vue is really interesting. Effectively, they have set up a build pipeline that includes testing major downstream projects as well for compatibility. This means that when the Vue team build something like "Vapor Mode" for 3.6, they've already run it against a large body of community projects to check for breaking changes and edge cases. You can see some of the work they do in this video: https://www.youtube.com/watch?v=zvjOT7NHl4Q https://www.youtube.com/watch?v=zvjOT7NHl4Q
- mrmedix 1y agoYou have to add an extra function call at the start of the Linq method chain in order to make it zero-allocation. So I don't think it would break backwards compatibility. But adding it does create an additional maintenance burden.
- akdev1l 1y agoI think this approach predates Vue. I know of two examples: 1. Fedora in collaboration with GCC maintainers keep GCC on the bleeding edge so it can be used to compile the whole Fedora corpus. This validates the compiler against a set of packages which known to work with the previous GCC 2. I think the rust team also builds all crates on crates.io when working on `rustc`. It seems they created a tool to achieve that: https://github.com/rust-lang/crater https://github.com/rust-lang/crater I would assume the .NET guys have something similar already but maybe there’s not enough open code to do that
- zamalek 1y agoRust also has the advantage of having no ABI. Binary interface is a whole lot more difficult to maintain than code interface. C# has multiple technologies built to deal with ABI (though it probably all goes unused these days with folder-based deployments, you really need the GAC for it to work).
- jasonjayr 1y agoIIRC perl tested new releases by running all the unit tests in the CPAN library, waaaaay back when.
- clscott 1y agoThey still do and investigate each failure. If the end result is that the library is “wrong” tickets and patches get sent to the library maintainers.
- qingcharles 1y agoFrom some experience, the MS guys are actually really eager to get more outside help and many will help guide you through the process if you have something to offer. Every release has a fairly decent amount of fixes and additions from outside contributors, and while I can see a lot of to/fro on the PRs to get them through, it's probably not quite as bad as you'd expect.
- bob1029 1y agoI don't see why not: https://github.com/dotnet/runtime/pulls https://github.com/dotnet/runtime/pulls There's an official process for API change requests: https://github.com/dotnet/runtime/blob/main/docs/project/api-review-process.md https://github.com/dotnet/runtime/blob/main/docs/project/api...
- nikeee 1y agoZLinq relies on its own enumerable type called ValueEnumerable, which is a struct. While it would probably work when using this as a drop-in replacement and re-compiling, things will be more complicated in larger applications. There might be some code that depends on the exact signature of the Linq methods. This might not even be detectable in cases involving reflection and could break stuff silently. Adding another enumerable type would be a very large change that could effectively double the API surface of the entire ecosystem. This could take some time. Some places still don't even support Span<T>. Also there were some design decisions related to Linq where the number of overloads were a consideration. Adding this API to .NET could probably be done with that extension method that converts to ValueEnumerable. But without support for that enumerable, this would pretty much be a walled garden where you have to convert back and forth between different enumerable types. Not that great if you'd ask me, but possible I guess.
- kevingadd 1y agoFrom looking at the blog post I suspect the explosion of generic instances could be a serious problem for code size and startup time, but that's probably solvable somehow. The performance certainly seems impressive. The way LINQ currently works by default makes aggressive use of interfaces like IEnumerable to hide the actual types being iterated over. This has performance consequences (which is part of why ZLinq can beat it) but it has advantages - for example, the same implementation of Where<T>(seq) can be used for various T's instead of having to JIT or AOT-compile a unique body for every distinct class you iterate over. From looking at ZLinq it seems like it would potentially have an explosion of unique generic struct types as your queries get more complex, since for it to work you potentially end up with types vaguely resembling Query3<Query2<Query1<T>>>>. But it might not actually be that bad in practice.
- jayd16 1y agoUsing reference types are more idiomatic in C#. To some degree they are less bug prone as well (they can be passed around without issue). Most of the core library use them instead of starting with value types and boxing. The Task library has successfully added ValueTask but it took some doing. LINQ on the other hand can be replaced with unrolled loops or libraries more easily so the pressure just hasn't been there. I could see something happening in the future but it would take a lot of be work.
- chris_pie 1y agoTo your point, ValueTask is less safe than Task. For example, it's important not to await it more than once.
- theolivenbaum 1y agoThere are some minor breaking changes like the order of iteration is not always the same as the official Linq implementation, or Sum might give different values due to checked vs unchecked summing. Probably not an issue for most people, but a subtle breaking change nevertheless.
- theolivenbaum 1y agoSee here for more info: https://github.com/Cysharp/ZLinq?tab=readme-ov-file#difference-and-limitation https://github.com/Cysharp/ZLinq?tab=readme-ov-file#differen...
- fdadsfdsd 1y ago[flagged]
- fefawfefafds 1y ago[dead]
- fdaffeafe 1y ago[dead]
- jasonthorsness 1y agoThis is great. I've worked on production .NET services and we often had to avoid LINQ in hot paths because of the allocations. Reimplementing functions with for-loops and other structures was time-consuming and error-prone compared to LINQ method chaining. Chaining LINQ methods is extremely powerful; like filter, map, and reduce in JS but with a bunch of other operators and optimizations. I wish more languages had something like it.
- meisel 1y agoWhat are the advantages of this over using higher order functions? In Ruby I can do list.map { }.select { } …. That feels more natural (doesn’t require special language support), has a very rich set of functions (group_by, chunk_while, etc.), and is something the user can extend with their own methods (if they don’t mind monkeypatching)
- int_19h 1y agoLINQ is higher-order functions - Ruby `map` is 'Enumerable.Select`, Ruby `select` is `Enumerable.Where` etc. The special syntax is really just syntactic sugar on top of all this that makes things a little bit more readable for complex queries because e.g. you don't have to repeat computed variables every time after binding it once in the chain. Consider: from x in xs where x.IsFoo let y = Frob(x) where y.IsBar let z = Frob(y) where z.IsBaz order by x, y descending, z select z; If you were to rewrite this with explicit method calls and lambdas, it becomes something like: xs.Where(x => x.IsFoo) .Select(x => (x: x, y: Frob(x)) } .Where(xy => xy.y.IsBar) .Select(xy => (x: xy.x, y: xy.y, z: Frob(xy.y))) .Where(xyz => xyz.z.IsBaz) .OrderBy(xyz => xyz.x) .ThenByDescending(xyz => xyz.y) .ThenBy(xyz => xyz.z) .Select(xyz => xyz.z) Note how it needs to weave `x` and `y` through all the Select/Where calls so that they can be used for ordering in the end here, whereas with syntactic sugar the scope of `let` extends to the remainder of the expression (although under the hood it still does roughly the same thing as the handwritten code).
- deleted 1y ago[deleted]
- zamalek 1y agoIn theory .Net 10 should make this obsolete, the headline features[1] are basically all about this. In practice, well, it's heuristics, I'm adding this to a particularly performance sensitive project right now :) Edit: what's also nice is that C# recognizes Linq as a contract. So long as this has the correct method names and signatures (it does), the Linq syntax will light up automatically. You can also use this trick for your own home-grown things (add Select, Join, Where, etc. overloads) if the Linq syntax is something you like. [1]: https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotnet-10/runtime https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotn...
- Jordanpomeroy 1y agoCould you elaborate? I don’t see anything about improving the performance of enumerator. Zlinq appears to remove the penalty of allocating enumerators on the heap to be garbage collected. The link you sent mention improvements, but I don’t see how they lead to linq avoiding heap allocations.
- giancarlostoro 1y agoNot just that but Zlinq also works across all C# environments it seems including versions embedded in game engines like Godot, Unity, .NET Standard, .NET 8 and 9.
- kevingadd 1y agoI believe they're referring to the stack allocation improvements, which would ideally allow all the LINQ temporary objects to live on the stack. I'm not sure whether it does in practice though.
- andyayers 1y agoUnfortunately, those improvements don't work for Linq. Some notes on why this is so here: https://github.com/dotnet/runtime/blob/main/docs/design/coreclr/jit/DeabstractionAndConditionalEscapeAnalysis.md#linq https://github.com/dotnet/runtime/blob/main/docs/design/core...
- HexDecOctBin 1y agoWhat features does C# has that makes LINQ possible in it and not in other languages?
- sherburt3 1y agoI feel like pretty much every language with generics has a LINQ, like functools/itertools in Python, lodash for javascript. It’s just a different expression of the same ideas.
- jeswin 1y agoNope, very different. Depending on whether the expression is on an Enumerable or a Queryable, the compiler generates an anonymous function or an AST. That is, you can get "code as data" as in say Lisp; and allows expressions to be converted to say SQL based on the backend.
- pjmlp 1y agoYou can do exactly the same with Smalltalk metaclasses and reflection. However I do conceed most developers will only see them for the first time in .NET languages.
- tehlike 1y agoIt's part of the compiler - ast. Linq has two forms - one in the linq ordinary syntax from x select x.name And other is just lambda with anonymous types and so on. For the lambda syntax, you can just do this: https://www.npmjs.com/package/linq https://www.npmjs.com/package/linq Of course, if you want to run this against a query provider, you do need compiler support to instead give you an expression tree, and provider to process it and convert them to a language (often sql) that database can understand. There seems to be some transpilers, or things like that - but i don't know what the state of the art is on this: https://github.com/sinclairzx81/linqbox https://github.com/sinclairzx81/linqbox
- Merad 1y agoBasic LINQ on in-memory collections isn't really that different from what you have in other languages. Where things get special is the LINQ used by Entity Framework. It operates on expressions, which allow code to be compiled into the application and manipulated at runtime. For example, the lambda expression that you pass to Where() will be examined by an EF query provider that translates it into the where clause for a SQL query.
- bigmattystyles 1y agoThis is cool - excited to try it - I would note that I've been a dotnet grunt for almost 15 years now. I am good at it, I know how to use the language, I know the ecosystem - this level of familiarity with the language is just not within my grasp. I can understand the code (mostly) reading it, but I never would have been able to conjure up, let alone implement this. Props to the author.
- KallDrexx 1y agoThis is neat, but how does this get away with being zero allocation? It appears to use `Func<T,U>` for its predicates, and since `Func<T>` is a reference type this will allocate. The IL definitely generates definitely seems like it's forming a reference type from what I can tell.
- ziml77 1y agoThe JIT can optimize this. I know for sure if there's no captures in the lambda it won't allocate. It's likely also smart enough to recognize when a function parameter doesn't have its lifetime extended past the caller's, which is a case where it would also be possible to not allocate.
- theolivenbaum 1y agoTo add on that, you can define your lambdas as static to make sure you're not capturing anything by mistake. Something like dates.Where(static x => x.Date > DateTime.Now)
- ImHereToVote 1y agoWhy is LINQ allocating memory in the first place?
- debugnik 1y agoLINQ methods build up a chain of IEnumerable/IQueryable objects, which then build up chains of IEnumerator objects each time you iterate. These types are all .NET interfaces, which are reference types, so they're allocated on the heap. .NET's escape analysis can sometimes move reference types to the stack, but this feature is currently very limited and didn't even exist until .NET 9. ZLinq uses generic structs to prevent these allocations at the expense of some really verbose intermediate types.
- ImHereToVote 1y agoThanks.
- oaiey 1y agoInternal iterators, expression trees, etc. Many LINQ variants (depends on the data source) also do not execute the chain step by step but building first an expression tree and then translating that into native query syntax (e.g. SQL)
- stuaxo 1y agoI don't use .NET, but always thought LINQ a really interesting part of it.
- martijn_himself 1y agoCould anyone more across the detail of this chime in on what this means for the 'average' .NET developer? I rely heavily on LINQ calls in a .NET (Core) Web App, should I replace these with Zlinq calls? Or is this only helpful in case you want to do LINQ operations on let's say 1000's of objects that would get garbage collected at the end of a game loop?
- ozim 1y agoIn the article author writes about linq.js that he is not maintaining anymore but someone forked it. I guess this library will at some point end up unmaintained after author is bored with it. So I would not use it in any of my production code of a web app unless I get some problem I need to fix with this library specifically. Replacing all just because “it is faster” doesn’t seem good enough.
- thatwasunusual 1y agoAs the saying goes: if you don't know if you need something or not, you probably don't need it. :) I have been using .NET (and LINQ) for many years on a daily basis, and I've yet to run into performance problems that can't be fixed by either rewriting the LINQ statement or do some other quick workarounds. But will I try out ZLinq? Sure, but I won't create anything that depends on it.
- Jordanpomeroy 1y agoI think many people don’t need to worry performance of reference type allocations vs value type. I don’t mean to assume you do or do not need to worry about that consideration. But 99% of the code I’ve written does not need to be concerned about it.
- gwbas1c 1y agoIt really depends on how simple / complex ZLinq is. Sometimes simple libraries are "done" and don't need constant updates.
- garganzol 1y agoInteresting approach, but it should be .NET Runtime (or JIT) who would optimize small memory allocations preferring the stack rather than the heap when possible. .NET 10 takes a step in that direction [1]. [1] https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotnet-10/runtime#stack-allocation-of-small-arrays-of-value-types https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotn...
- srean 1y agoI don't know if anyone remembers expression templates of C++ nowadays. Once upon a time I had written a library of expression templates primitives to chain streams of computations and maps so that the sub-streams do not need to be fully realized in memory - essentially the old idea of Unix pipelines. Writing it was a lot of fun. Debugging compiler errors were a lot less fun because the template language of C++ has no static typing, so errors would be triggered very deep in the expression tree. The expression tree got processed and inlined at compile time so there was no to minimal overhead at runtime. I was very impressed with GCC's inlining and vectorization. Especially the messages that explained why it could not vectorize.
- torginus 1y agoIs it just me, or does this have a case of false advertising? One of the biggest sources of allocation is lambda captures, like when you write something like this var myPerson = people.First(x=>x.Name==myPersonName); in this case, a phantom object is allocated, that captures the myPersonName variable, for which a delegate is allocated, which is then passed to the First() method, making the number of allocations per call a minimum of 2. I don't see ZLinq doing anything about this.