[WIP] Replace Dispatcher.Sort with Array.Sort

[froce]

PR Details

Closes #1792 by deprecating Dispatcher.Sort and replacing all call sites with Array.Sort.

Motivation and Context

Performance improvement.

Types of changes

• [ ] Docs change / refactoring / dependency upgrade
• [ ] Bug fix (non-breaking change which fixes an issue)
• [ ] New feature (non-breaking change which adds functionality)
• [ ] Breaking change (fix or feature that would cause existing functionality to change)

Checklist

• [ ] My change requires a change to the documentation.
• [ ] I have added tests to cover my changes.
• [x] All new and existing tests passed.

[Eideren]

The previous implementation might need some love then. You could embed the call to array sort within public call sites, and mention that this is temporary while an engineer investigates this performance issue further, that way we don't have any breaking changes.

[froce]

I don't think there's a problem with the implementation, it's just not the right algorithm, so I don't see it as temporary. We could do better than Array.Sort, but ultimately this much per-frame sorting should not be necessary.

for example this is the first call site:

// Sort per render feature (used for later sorting)
// We'll be able to process data more efficiently for the next steps
Array.Sort(view.RenderObjects.Items, 0, view.RenderObjects.Count, RenderObjectFeatureComparer.Default);

So this sorts RenderObjects by (Root)RenderFeature.Index (for later sorting??), but this sorting is really just putting many RenderObjects into a few buckets. And then, each RootRenderFeature already has a list of associated RenderObjects, so the buckets already exist in some way, but they get mixed together at some point. I think investigating things like that might be worth it.

Getting back to Dispatcher.Sort - If we want to keep a parallel quicksort around, we should rename it and find a better place for it.

[Eideren]

I don't think there's a problem with the implementation, it's just not the right algorithm

It doesn't matter too much whether it's a poor choice of algorithm or a bad implementation of one I don't think. The method name and context does not imply which algorithm would be used to sort, callers only expect that sorting take as much or less time than a single threaded one.

Like you said, a bunch of call sites should use Array.Sort and others should not sort in the first place.

Still, I don't think it makes sense to mark Dispatch.Sort as obsolete, even if none of those call sites would benefit from a parallel sort, something in the future very well could. And, if our current parallel sort doesn't perform as well in all cases as a single threaded one, like you've shown in #1792, let's just call the single threaded ones from those functions in the mean time.