5 ms·

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 a

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.

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.