FC44: Linq.Enumerable - Total disregard of proper data structure/algorithm design

When I found a bad usage of Linq.Enumerable at Microsoft, I would send strong reminder to developers that Linq.Enumerable is total disregard of proper data structure/algorithm design.

Found one such case in Nuget client:

LockFile.Equals is responsible for 0.6% of total allocations in Visual Studio, due to usage of Linq.Enumerable.SequenceEquals with OrderBy inside. Source code:

Data structure: quite a few Lists exposed as IList:

Implementation of OrderedEquals:

List is not the proper data structure to use here. Using sorted list would be the perfect fit, with that no sorting is needed in Equals check.

The strange thing is that .Net does not have a real sorted list class. The SortedList class there is really a dictionary implemented using sorted arrays. Let’s add a simple implementation:

Now we can add an equality comparer:

This will be much faster than List + Linq.Enumerable based implementation. This is proper data structure and algorithm design.

Source code: FrugalCafe/Common/SortedList.cs at master · ProfFrugal/FrugalCafe (github.com)