4 ms·

ToList shouldn't be used as much as it is, most of the time ToArray is good enough, and it doesn't allocate a List on the heap

• Limeray 4y ago
• spErased 4y ago
  Just to add to this, they're essentially the same with ToList beating out ToArray at certain sizes due to how the internal array of a list is resized vs a raw array (true for .net core). A better rule of thumb is deciding if the result needs to added to/modified etc then picking accordingly.
  • WorldMaker 4y ago
    I've written several rants about "ToList considered harmful". I think it is unfortunately too easy to (ab)use and often ToArray is better overall for the use cases of a reifying a query only to simply iterate it later (more than once; otherwise leave things lazy). That rule of thumb "are there calls to Add after this query" is the biggest one where "you might need List<T>" (and even then maybe you are taking a too imperative approach to something that could be reified differently). Though often I find what projects really need are ToDictionary or ToLookup, especially ToLookup, a lot of C# developers sleep on that, because it doesn't have an Add and doesn't implement ICollection<T> and you have to search NuGet for a mutable ILookup<T> implementation that you can just `new` yourself, but ILookup<T> is often the best shape of reified results that have multiple iterations of subsets. Take your O(n^2) operations and make them more O(n log n) or whatever if you pick the right key(s) for your subsets. It's not uncommon for me to start a performance optimization pass on a C# app simply by doing a Find All for ToList and removing every single use.
    • SideburnsOfDoom 4y ago
      > ToLookup, especially ToLookup, a lot of C# developers sleep on that ... and you have to search NuGet for a mutable ILookup<T> implementation Interesting. I have recently replaced a List<int> with Hashset<int> This is a (IMHO, underused) part of the standard library https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1 https://docs.microsoft.com/en-us/dotnet/api/system.collectio... C# Devs tend to know List<T>, Dictionary<K, V> but not HashSet<T>. The reason for that replacement was simply: "we have a lot of 'business category ids' in this opt-in list, all we do is ask 'is the current id in the opt-in list or not?' so duplicates have no meaning, and ordering is possible but of secondary importance ... that's mathematically speaking, a 'Set' not a 'List'. " So using Hashset reduces the check time from O(n) to O(1) and otherwise it's pretty much a drop-in replacement: Same initialiser, same 'Add' and 'Contains' methods, also found in 'System.Collections.Generic'. I'm looking at ILookup<K, V> and it looks fairly similar to Dictionary<K, IEnumerable<V>> When would I go out of my way to use it instead?
      • WorldMaker 4y ago
        Yeah, HashSet<T> is definitely another one to prefer over ToList often enough. There is a ToHashSet finally in Enumerable extensions now so maybe more developers will discover it now. (It was finally added somewhere around .NET Core 2, as I recall.) Also, a quick shoutout to System.Collections.Generic.Immutable for having great tools like ImmutableHashSet<T> and ToImmutableHashSet for when mutability distracts from your algorithm/data structure needs. ILookup<K, V> is basically the "in memory join and group by" tool. If a query sort of naturally ends in a GroupBy because you want things sorted/grouped by an enum field or a foreign key field, but you still want all of the items in the groupings rather than just aggregate stats on the groupings, that's often where you want ToLookup instead of GroupBy to reify your query. In general, Enumerable.Join and other in memory "join" operations (as opposed to the IQueryable's Join which more often than not gets sent to a highly tuned query planner in an SQL server somewhere) are often O(n^2) even at best. A lot of developers do notice this, that joins are expensive when performed in memory, but simply rewrite them by hand as nested foreach loops which still has the same O(n^2) worst cases, but it's hand-written so developers feel more comfortable with how slow it is. On the other side, in C# a lot of developers tend to naturally write these kinds of "in memory join operations" as nested foreach loops anyway (or a foreach loop with a big Enumerable.Where query inside acting as a second foreach loop on the other data source), just because they've always done it that way, and might not even think of them as "an in memory join" much less think to replace hand-written loops with something more LINQ-like anyway. ToLookup is generally the handiest tool to replace both sorts of O(n^2) "joins" the Enumerable.Join operations that do their best but don't know your model domain and don't have the query planner and indexes of an SQL database to fallback on, and the hand-written nested loops: you "index" the "right side" of your join (the inner foreach/if or Enumerable.Where in hand-written loops) on your join key with ToLookup. As an example, perhaps: you've got a list of items in a shopping cart, which is only in memory in session data (so "naturally reified"), and a table of coupon/discount "rules" that apply primarily based on "item category ID" (with a Category FK table in between Item and CouponRule in your normalized DB structure). The most naive way of writing that would be something like: foreach (var item in shoppingCart) { var couponRules = db.CouponRules.AsQueryable() .Where(rule => rule.CategoryId == item.CategoryId); foreach (var rule in couponRules) { if (RulesService.DoesRuleApply(item, couponRule)) { RulesService.Apply(item, couponRule); } } } Written that naively that's at least one database query for every item in the shopping cart, which is obviously not optimal so a developer's first instinct is going to be to reify that query somewhere. The simplest, equally naive reification is often this (though often by this point "hidden" as a cache inside "RulesService"): var allCouponRules = await db.CouponRules.AsQueryable() .ToListAsync(); foreach (var item in shoppingCart) { var couponRules = allCouponRules .Where(rule => rule.CategoryId == item.CategoryId); foreach (var rule in couponRules) { if (RulesService.DoesRuleApply(item, couponRule)) { RulesService.Apply(item, couponRule); } } } (Again, it's maybe more obvious written this way, but often at this point what I find is that allCouponRules cache moves inside RulesService and that Where and foreach get "hidden" inside RulesService at this point, making it even tougher to optimize this situation many times in practice because you don't see all the loops in one place by that point.) To find possibly applicable coupon rules this does an O(n) search over all rules for every single item, even though we already know we primarily only care about the subset that joins on Category ID. This is where handwritten O(n^2) worst cases often hide. If you grow to have a lot of item categories with a lot of coupon rules that might be a huge list in memory. This is where ToLookup most shines as your easily cacheable reification to speed up exactly these sorts of joins. var couponRulesByCategoryId = await db.CouponRules.AsQueryable() .ToLookupAsync(rule => rule.CategoryId); foreach (var item in shoppingCart) { var couponRules = couponRulesByCategoryId[item.CategoryId]; /* most implementations of ILookup return Enumerable.Empty<T>() for missing keys so you don't even need to guard this lookup with a ContainsKey check */ foreach (var rule in couponRules) { if (RulesService.DoesRuleApply(item, couponRule)) { RulesService.Apply(item, couponRule); } } } That couponRulesByCategoryId lookup is itself O(log n) like most Dictionary/Set lookups, bringing the overall worst case here more in line with O(n log n) worst cases than O(n^2). I find so many patterns like this where cached ToLookup "indexes" in memory/caches greatly speed up operations. There's still further things that might be optimized with ToLookup to explore even in this example: you could "index" the "left side" here too (shoppingCart.ToLookup(item => item.CategoryCode) and maybe the "RulesService" can change to take IEnumerable<Item> instead of item at-a-time. Maybe lurking in DoesRuleApply() filter is a secondary key to "index" on, perhaps as a ToLookup to a tuple key instead (in turn saving even more rules that don't need to be checked individually and can be ignored as a group). Once you start finding these sorts of patterns I feel like you start to see them everywhere in C# and that's a big part of why I think ToLookup is an unsung hero of C# optimization work. I do wish some version of the mutable MultiValueDictionary<K, V> which implements ILookup<K, V> finally makes into System.Collections.Generic properly instead of being an "experimental" or "labs" nuget package away. You can fake it with Dictionary<K, List<V>>, but that's a lot more awkward to work with (including a lot of ContainsKey/Add(new List) dances) and doesn't naturally implement ILookup<K, V>. I think an obviously mutable version would make a lot of developers more used to using ToLookup even if there are very good reasons that the default implementations are all immutable.
• neonsunset 4y ago
  Both types `List<T>`and `T[]` are `object` aka Rust's `Box<T>`. There's little profit most of the time for using `ToArray()` over `ToList()`, and in places where it does matter, there is a high chance that using `IEnumerable<T>` is bad idea due to its performance overhead. I believe, the best implementation of `IEnumerable<T>` we have today are Rust's iterator types which provide the same functionality but with performance comparable or even better than manually written imperative loops.
  • WorldMaker 4y ago
    That's not entirely true. .NET's object is very different from Box<T> from my understanding. My rust understanding is rusty (not sorry), but .NET's object is much closer to &mut than Box<T> as it is the top type in the type system. There's the reference type/value type split "below" object. Reference types like `List<T>` are always heap allocated (like Box<T>), but value types like T[] might not be and may be stack allocated. Small enough arrays can reify entirely in stack space (function locals) rather than heap space and with some uses of ToArray() the JIT compiler is smart enough to make the right call, whereas List<T> always creates heap allocations and ToList() unavoidably churns at least Gen 0 of the garbage collector that tiny bit more. IEnumerable<T> doesn't give you enough information of the implementation details to know if that interface is implemented as a reference type or value type. Some implementations of IEnumerable<T> are non-heap allocated value types (structs)! Often many implementations in performance critical areas of the framework are structs.
    • neonsunset 4y ago
      Unfortunately, while I would love JIT to do such kind of optimizations, this is completely not how it works today. First and foremost, '&mut' in Rust is a mutable reference. The C# alternative is just 'ref'. Both point to specific addresses. 'Box<T>' OTOH is a handle for a struct allocated on a heap, just like C#'s one is implementation-wise (except in C# they are further managed by runtime but that's besides the point). Now regarding the arrays - 'T[]' is strictly object withouts ifs and buts. There is no "short array" optimisation that would substitute array type with stack-allocated inline buffer. If you want this, you have to write it manually. See: https://github.com/dotnet/runtime/blob/57bfe474518ab5b7cfe6bf7424a79ce3af9d6657/src/libraries/System.Private.CoreLib/src/System/Globalization/Normalization.Icu.cs#L46 https://github.com/dotnet/runtime/blob/57bfe474518ab5b7cfe6b... The last but not least, if the method signature accepts an argument by its interface type e.g. 'HandleEnumerable<T>(IEnumerable<T> values)', then the IEnumerable-implementing struct will be boxed before method can be called. C#/.NET doesn't do full generic monomorphization like Rust. Instead, for class-type generics a common '_Canon' method body will be JITted which will also implicitly accept generic-type arguments to correctly dispatch on an actual <T> of the method. OTOH, for structs, all method calls will be fully monomorphized per each struct type. This means that you can avoid struct boxing when dispatching by interface by rewriting method signature to 'HandleEnumerable<T, TEnumerable>(TEnumerable values) where TEnumerable : IEnumerable<T>'. In this case, unless you cast your struct to an interface type explicitly beforehand, the struct will not be boxed. For the sake of simplicity, this explanation scope doesn't include advanced optimisations done by Tier-1 JIT compilation such as guarded de-virtualization, more aggressive inlining that can potentially elide boxing, etc.