[CmdPal] Optimise MainListPage's results display by merging already-sorted lists

[daverayment]

Summary of the Pull Request

This PR replaces the current LINQ-based results compilation query of combining, sorting and filtering the four result sources with a 3-way merge operation plus a final append. It provides a performance increase as well as a significant reduction in allocations.

PR Checklist

• [ ] Closes: #xxx

• [ ] Communication: I've discussed this with core contributors already. If the work hasn't been agreed, this work might be rejected
• [x] Tests: Added/updated and all pass
• [ ] Localization: All end-user-facing strings can be localized
• [ ] Dev docs: Added/updated
• [ ] New binaries: Added on the required places
  • [ ] JSON for signing for new binaries
  • [ ] WXS for installer for new binaries and localization folder
  • [ ] YML for CI pipeline for new test projects
  • [ ] YML for signed pipeline
• [ ] Documentation updated: If checked, please file a pull request on our docs repo and link it here: #xxx

Detailed Description of the Pull Request / Additional comments

The existing code:

1. Limits the number of apps returned to a pre-defined maximum.
2. Sorts the apps list.
3. Appends filtered items, scored fallback items and the apps list together.
4. Sorts the three lists based on their score.
5. Appends the non-scored fallback items, with empty items excluded.
6. Selects just the Item from each.
7. Creates an array from the enumerable.

    if (_filteredApps?.Count > 0)
    {
        limitedApps = _filteredApps.OrderByDescending(s => s.Score).Take(_appResultLimit).ToList();
    }

    var items = Enumerable.Empty<Scored<IListItem>>()
                          .Concat(_filteredItems is not null ? _filteredItems : [])
                          .Concat(_scoredFallbackItems is not null ? _scoredFallbackItems : [])
                          .Concat(limitedApps)
                          .OrderByDescending(o => o.Score)

                          // Add fallback items post-sort so they are always at the end of the list
                          // and eventually ordered based on user preference
                          .Concat(_fallbackItems is not null ? _fallbackItems.Where(w => !string.IsNullOrEmpty(w.Item.Title)) : [])
                          .Select(s => s.Item)
                          .ToArray();

We can exploit the fact that each of the three 'scored' lists are pre-ordered, and replace the query with a 3-way merge and final append of the non-scored fallback items.

By pre-sizing the results array we can avoid all the extra allocations of the LINQ-based solution.

Proof of pre-ordering

In UpdateSearchText, each of the lists is defined by calling ListHelpers.FilterListWithScores:

    // Produce a list of everything that matches the current filter.
    _filteredItems = [.. ListHelpers.FilterListWithScores<IListItem>(newFilteredItems ?? [], SearchText, scoreItem)];

    _scoredFallbackItems = ListHelpers.FilterListWithScores<IListItem>(newFallbacksForScoring ?? [], SearchText, scoreItem);

    var scoredApps = ListHelpers.FilterListWithScores<IListItem>(newApps, SearchText, scoreItem);

...

    _filteredApps = [.. scoredApps];

In FilterListWithScores, the results are ordered by score:

   var scores = items
        .Select(li => new Scored<T>() { Item = li, Score = scoreFunction(query, li) })
        .Where(score => score.Score > 0)
        .OrderByDescending(score => score.Score);

(This also makes the existing OrderByDescending() for _filteredApps before the LINQ query redundant.)

K-way merge

Since the results are pre-sorted, we can do a direct merge in linear time. This is what the new MainListPageResultFactory's Create achieves. As the lists may be different sizes, the routine does a 3-way merge, followed by a 2-way merge and a single list drain to finish. Each element is only visited once.

Benchmarks

A separate benchmark project is here, written with Benchmark.net.

The project compares the current LINQ-based solution against:

1. An Array-based algorithm which pre-assigns a results array and still sorts the 3 scored sets of results. This shows a naive non-LINQ solution which is still O(n log n) because of the sort.
2. The k-way merge, which is described above. O(n) for both time and space complexity.
3. A heap merge algorithm, which uses a priority queue instead of tracking each of the lists separately. (This is O(n log k) in terms of time complexity and O(n + k) for space.)

Care is taken to ensure stable sorting of items. When preparing the benchmark data, items with identical scores are assigned to confirm each algorithm performs identically to the LINQ OrderBy approach, which performs a stable sort.

Results show that the merge performs best in terms of both runtime performance and allocations, sometimes by a significant margin. Compared to the LINQ approach, merge runs 400%+ faster and with at most ~20% of the allocations:

See here for all charts and raw stats from the run: https://docs.google.com/spreadsheets/d/1y2mmWe8dfpbLxF_eqPbEGvaItmqp6HLfSp-rw99hzWg/edit?usp=sharing

Cons

1. Existing performance is not currently an issue. This could be seen as a premature optimisation.
2. The new code introduces an inherent contract between the results compilation routine and the lists, i.e. that they must be sorted.

This PR was really for research and learning more about CmdPal (and a bit of algorithm practice because it's Advent of Code time), so please feel free to reject if you feel the cons outweigh the pros.

Validation Steps Performed

• Added unit tests to exercise the new code, which confirm that the specific ordering is preserved, and the filtering and pre-trimming of the apps list is performed as before.
• Existing non-UI unit tests run. NB: I could not run any UI Tests on my system and just got an early bail-out each time.
• Manual testing in (non-AOT) Release mode.