Sort And Bind Operator

The sort problem

Sorting data for the observable cache side of Dynamic Data has always been a problematic area, and the current implementation of Sort is very expensive as it has to:

1. Maintain an internal sorted list
2. When changes are received, calculate index differences for new, updated, mutated and removed items.
3. Include the index changes on the change object which forms part of the change set.
4. Finally and this is the very worst part of it all, it transmits a copy of the internal sorted list on a specialised change set ISortedChangeSet<TObject, TKey>.

Parts 1, 2 and 3 are required in order that the changes together with their indices are transmitted to enable down stream operators like Bind to be able apply those changes. This alone is an expensive operation but it gets worse. Binding is also expensive and for most scenarios there's a threshold where for a certain number of changes, it is cheaper to suspend the NotifyCollectionChanged events, rebuild the observable collection and fire the NotifyCollectionChangedAction.Reset . This is the reason for point 4, as in order to apply the reset Bind requires a complete set of state. So basically every sort change results in the sorted list being cloned just in case the Bind operation requires a reset. This is an overblown, bloated and expensive solution.

Here's the offending object:

public interface ISortedChangeSet<TObject, TKey> : IChangeSet<TObject, TKey>
{
    // This is the container which contains a clone of inner state of the Sort operator.
    IKeyValueCollection<TObject, TKey> SortedItems { get; }
}

and additionally the change also carries any related indices.

// not the real implementation
public readonly record struct Change<TObject, TKey>(
	ChangeReason reason, 
	TKey key, 
	TObject current,
	// These are produced by Sort and only used by Bind, Virtualise and Page
	int CurrentIndex,
    int PreviousIndex);    

which again means the extra storage requirement on the change object when the only operators on the cache side of Dynamic Data which use these the results of Sort are Bind, Virtualise and Page. So as a result of Sort, every single change requires more memory than it would have if sort had never existed, and for just three operators, two of which are rarely used.

The solution

How about we bypass Sort altogether, and instead supply the 3 sort dependent operators with a comparer - this solution is so obvious that I seriously cannot believe that I have never considered it until recently. I think to a large degree, I have been inspired by the brilliant input @JakenVeina and @dwcullop has had with Dynamic Data lately. Between us we have started to imagine what the Dynamic Data 2 will look like, what is good, what is bad and how we would implement it from scratch to make if fit for the next 10 years. V2 is still being imagined but this operator is inspired by some of these v2 discussions and where possible it is good to back apply the ideas.

We cannot get rid of Sort overnight so I have introduced SortAndBind which combines the operations of Sort and Bind. This means there is no need to transmit state and subsequently the operator is much faster and has significantly less memory consumption. It's functionality is almost identical to Sort followed by Bind but without the overheads.

// sort person by age then name.
var comparer = SortExpressionComparer<T>.Ascending(p => p.Age).ThenByAscending(p => p.Name);
var cache = new SoureCache<Person, string>();
	
// instead of this
var oldSlowWay = myCache.Connect().Sort(comparer).Bind(out var myList);

// do this
var newFastWay = myCache.Connect().SortAndBind(out var myList, comparer);

// or sort and bind to an arbitary list
var myList = new List<Person>();
var newFastWay = myCache.Connect().SortAndBind(myList, comparer);

This should clearly be an easy transition and Sort will remain a part of Dynamic Data for the foreseeable future so these changes can be applied gradually. The one caveat is that whereas ObserveOn(MainThreadScheduler) is typically applied after Sort and before Bind it should now be applied before SortAndBind.

The same treatment will be applied to Virtualise and Page very soon - watch this space.

I will also need to add overloads which enable the comparer to change ie. add IObservable<IComparer<T>> option.

Additional Optimisations

There is an overload to additionally apply optimizations:

// optionally apply any combination of the following.
var options = new SortAndBindOptions
            {
	        // Applied to ReadonlyObservableCollection only. 
	        // Can help speed up first time load if capacity is known
                InitialCapacity = 10_000,
                
                // Use binary search when the result of the comparer is a pure function.
                // This can work performance wonders but only is there are no inline mutations
                UseBinarySearch = true,
                
                //  When possible, should replace be used instead of remove and add.
                // Some control suites do not support replace.
                UseReplaceForUpdates = false,
			
		// The number of changes before a reset is fired.
		// Adjusting this can speed up the binding
		ResetThreshold = 30
            };

var newFastWay = myCache.SortAndBind(var our myList, comparer, options);

These should be self-explanatory.

Benchmarks

Count = Number of items in the cache.

For first time load

Method	Count	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
Old	100	28.53 μs	0.567 μs	0.557 μs	1.00	0.00	6.6833	0.3052	-	61.66 KB	1.00
New	100	18.29 μs	0.365 μs	0.449 μs	0.64	0.01	4.2114	0.0305	-	38.98 KB	0.63
Old	1000	409.07 μs	8.092 μs	9.319 μs	1.00	0.00	88.8672	24.9023	-	820.42 KB	1.00
New	1000	329.29 μs	6.349 μs	11.609 μs	0.81	0.04	66.8945	4.3945	-	616.48 KB	0.75
Old	10000	8,744.38 μs	173.471 μs	474.875 μs	1.00	0.00	1328.1250	671.8750	500.0000	10041.87 KB	1.00
New	10000	5,562.98 μs	41.159 μs	32.134 μs	0.64	0.03	851.5625	281.2500	-	7836.35 KB	0.78
Old	50000	54,583.32 μs	1,065.639 μs	1,562.000 μs	1.00	0.00	5300.0000	600.0000	600.0000	54878.87 KB	1.00
New	50000	44,452.76 μs	887.386 μs	1,153.852 μs	0.81	0.04	4666.6667	-	-	43980.84 KB	0.80

For a single change, where optimized is using BinarySearch

Method	Count	Mean	Error	StdDev	Median	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
Old	10	1,683.7 ns	20.96 ns	17.51 ns	1,686.1 ns	1.00	0.00	0.2785	-	-	2624 B	1.00
OldOptimized	10	800.3 ns	15.65 ns	29.40 ns	796.5 ns	0.48	0.02	0.1965	-	-	1856 B	0.71
New	10	369.2 ns	6.39 ns	5.67 ns	368.1 ns	0.22	0.00	0.0720	-	-	680 B	0.26
NewOptimized	10	556.3 ns	10.85 ns	13.32 ns	554.1 ns	0.33	0.01	0.0858	-	-	808 B	0.31
Old	100	6,090.6 ns	118.70 ns	141.30 ns	6,091.7 ns	1.00	0.00	1.1673	0.0076	-	11048 B	1.00
OldOptimized	100	1,006.4 ns	14.21 ns	11.87 ns	1,006.4 ns	0.16	0.00	0.3796	0.0019	-	3584 B	0.32
New	100	1,712.9 ns	43.85 ns	125.81 ns	1,662.9 ns	0.27	0.01	0.3014	-	-	2840 B	0.26
NewOptimized	100	686.5 ns	13.74 ns	15.28 ns	681.9 ns	0.11	0.00	0.1163	-	-	1096 B	0.10
Old	1000	49,820.9 ns	991.81 ns	2,506.43 ns	49,273.1 ns	1.00	0.00	9.9487	0.5493	-	93992 B	1.00
OldOptimized	1000	2,211.8 ns	42.17 ns	43.31 ns	2,205.9 ns	0.04	0.00	1.9379	0.1907	-	18272 B	0.19
New	1000	13,712.9 ns	269.31 ns	505.83 ns	13,669.8 ns	0.28	0.02	2.5940	-	-	24440 B	0.26
NewOptimized	1000	907.8 ns	17.21 ns	16.90 ns	904.3 ns	0.02	0.00	0.1469	-	-	1384 B	0.01
Old	10000	731,549.7 ns	12,973.21 ns	22,378.14 ns	721,852.1 ns	1.000	0.00	123.0469	45.8984	42.9688	922226 B	1.000
OldOptimized	10000	24,563.5 ns	2,019.32 ns	5,212.52 ns	24,027.3 ns	0.033	0.01	12.6953	12.6953	12.6953	162677 B	0.176
New	10000	157,586.0 ns	3,135.62 ns	5,889.45 ns	157,696.9 ns	0.216	0.01	25.3906	-	-	239657 B	0.260
NewOptimized	10000	2,072.1 ns	40.10 ns	50.72 ns	2,066.4 ns	0.003	0.00	0.1869	-	-	1768 B	0.002
Old	50000	3,538,953.8 ns	70,395.87 ns	107,501.93 ns	3,549,659.6 ns	1.000	0.00	449.2188	62.5000	46.8750	4602400 B	1.000
OldOptimized	50000	335,438.2 ns	26,403.01 ns	77,849.87 ns	323,205.6 ns	0.122	0.01	17.5781	17.5781	17.5781	802897 B	0.174
New	50000	880,881.6 ns	17,536.51 ns	36,215.94 ns	875,918.3 ns	0.250	0.01	127.9297	0.9766	-	1211196 B	0.263
NewOptimized	50000	7,932.2 ns	152.25 ns	304.07 ns	7,918.4 ns	0.002	0.00	0.1984	0.0153	-	1961 B	0.000