Efficient implementation of "ThenBy" sorting

Question

I need to write “immediate” Linq mode (due to the limitations of memory allocation on Unity / Mono - a long story, not very important).

I am fine with everything that works so fast or faster than real Linq until I come to ThenBy . It is clear that my method of applying this is incorrect, since my productivity drops up to 4 times slower than the real deal.

So what am I doing now -

For each offer, ThenBy , ThenBy

• Create a list of results for each selector, add all the results of the evaluation of the selector to the list
• Create a lambda that uses a default mapper that uses a list indexed with two parameters

It looks like this:

 public static IEnumerable<T> OrderByDescending<T,TR>(this IEnumerable<T> source, Func<T,TR> clause, IComparer<TR> comparer = null) { comparer = comparer ?? Comparer<TR>.Default; var linqList = source as LinqList<T>; if(linqList == null) { linqList = Recycler.New<LinqList<T>>(); linqList.AddRange(source); } if(linqList.sorter!=null) throw new Exception("Use ThenBy and ThenByDescending after an OrderBy or OrderByDescending"); var keys = Recycler.New<List<TR>>(); keys.Capacity = keys.Capacity > linqList.Count ? keys.Capacity : linqList.Count; foreach(var item in source) { keys.Add(clause(item)); } linqList.sorter = (x,y)=>-comparer.Compare(keys[x],keys[y]); return linqList; } public static IEnumerable<T> ThenBy<T,TR>(this IEnumerable<T> source, Func<T,TR> clause, IComparer<TR> comparer = null) { comparer = comparer ?? Comparer<TR>.Default; var linqList = source as LinqList<T>; if(linqList == null || linqList.sorter==null) { throw new Exception("Use OrderBy or OrderByDescending first"); } var keys = Recycler.New<List<TR>>(); keys.Capacity = keys.Capacity > linqList.Count ? keys.Capacity : linqList.Count; foreach(var item in source) { keys.Add(clause(item)); } linqList.sorters.Add((z,x,y)=>z != 0 ? z : comparer.Compare(keys[x],keys[y])); return linqList; } 

Then what I am doing in the sort function is creating a lamda that applies sorting in order - so I get a function that looks like Comparer<int> and returns the correct order.

He starts this very bad job. I tried the version using currying and different signatures for the ThenBy and ThenBy , but nothing really works faster, and I wonder if I just missed the trick in sorting by cartoon.

Sort variables and function:

  public List<Func<int,int,int,int>> sorters = new List<Func<int, int, int, int>>(); public Func<int,int,int> sorter; public List<int> sortList = new List<int>(); bool sorted; private List<T> myList = new List<T>(); void ResolveSorters() { if(sorter==null) return; Func<int,int,int> function = null; if(sorters.Count==0) { function = sorter; } else { function = sorter; foreach(var s in sorters) { var inProgress = function; var current = s; function = (x,y)=>current(inProgress(x,y), x,y); } } sortList.Capacity = sortList.Capacity < myList.Count ? myList.Count : sortList.Capacity; sortList.Clear(); sortList.AddRange(System.Linq.Enumerable.Range(0,myList.Count)); //var c = myList.Count; /*for(var i =0; i < c; i++) sortList.Add(i);*/ sortList.Sort(new Comparison<int>(function)); sorted = true; sorters.Clear(); } 

Answer 1

I need to guess, but I'm still doing it. I think we should try to get rid of the embedded lambda material and delegate conversions. I'm not sure how good this is. The sort function should be like this:

 Func<int, int, int>[] sorters = ...; //fill this. it really should be an array! Comparison<int> = (a, b) => { foreach (var s in sorters) { var cmp = s(a, b); if(cmp != 0) return cmp; } return 0; }; 

So, we got rid of nested calls. All simple loop. You can create specialized versions for small loop sizes:

 Func<int, int, int>[] sorters = ...; //fill this. it really should be an array! switch (sorters.Length) { case 2: { var s0 = sorters[0], s1 = sorters[1]; Comparison<int> = (a, b) => { var cmp = s0(a, b); if(cmp != 0) return cmp; var cmp = s1(a, b); if(cmp != 0) return cmp; return 0; }; } 

Expand the loop so that no arrays are displayed anymore during sorting.

All this really works around the fact that we do not have static knowledge about the sorting structure. This would be much faster if the comparison function were simply transmitted by the caller.

Update: Repro (100% more than LINQ)

  Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High; Func<int, int, int>[] sorters = new Func<int, int, int>[] { (a, b) => (a & 0x1).CompareTo(b & 0x1), (a, b) => (a & 0x2).CompareTo(b & 0x2), (a, b) => (a & 0x4).CompareTo(b & 0x4), (a, b) => a.CompareTo(b), }; Func<int, int, int> comparisonB = sorters[0]; for (int i = 1; i < sorters.Length; i++) { var func1 = comparisonB; var func2 = sorters[i]; comparisonB = (a, b) => { var cmp = func1(a, b); if (cmp != 0) return cmp; return func2(a, b); }; } var comparisonC = new Comparison<int>(comparisonB); Comparison<int> comparisonA = (a, b) => { foreach (var s in sorters) { var cmp = s(a, b); if (cmp != 0) return cmp; } return 0; }; Func<int, int, int> s0 = sorters[0], s1 = sorters[1], s2 = sorters[2], s3 = sorters[3]; Comparison<int> comparisonD = (a, b) => { var cmp = s0(a, b); if (cmp != 0) return cmp; cmp = s1(a, b); if (cmp != 0) return cmp; cmp = s2(a, b); if (cmp != 0) return cmp; cmp = s3(a, b); if (cmp != 0) return cmp; return 0; }; { GC.Collect(); var data = CreateSortData(); var sw = Stopwatch.StartNew(); Array.Sort(data, comparisonC); sw.Stop(); Console.WriteLine(sw.Elapsed.TotalSeconds); } { GC.Collect(); var data = CreateSortData(); var sw = Stopwatch.StartNew(); Array.Sort(data, comparisonA); sw.Stop(); Console.WriteLine(sw.Elapsed.TotalSeconds); } { GC.Collect(); var data = CreateSortData(); var sw = Stopwatch.StartNew(); Array.Sort(data, comparisonD); sw.Stop(); Console.WriteLine(sw.Elapsed.TotalSeconds); } { GC.Collect(); var data = CreateSortData(); var sw = Stopwatch.StartNew(); foreach (var source in data.OrderBy(x => x & 0x1).ThenBy(x => x & 0x2).ThenBy(x => x & 0x4).ThenBy(x => x)) { } sw.Stop(); Console.WriteLine(sw.Elapsed.TotalSeconds); } 

Answer 2

I sort my items by [Type], then by [Price] this way

 Items = Items.OrderBy(i => i.Type).ToList(); for (var j = 0; j < Items.Count - 1; j++) // ordering ThenBy() AOT workaround { for (var i = 0; i < Items.Count - 1; i++) { if (Items[i].Type == Items[i + 1].Type && Items[i].Price > Items[i + 1].Price) { var temp = Items[i]; Items[i] = Items[i + 1]; Items[i + 1] = temp; } } }