[Feature]: Improve ChangeSet emission when a single item moves upwards in index on a Sort

[Chicken-Bones]

Describe the functionality desired 🐞

Currently, if a Sort causes a single item to move from a low index to a high index, instead of generating one single Move change for the given item, the Reorder implementation in Internal/List.cs emits move down by 1 events for every item in the list between the old and new index of the 'moved' item.

I understand that moving one item up n spaces, and moving n items down 1 space are equivalent and symmetric operations, but the stream of change events from each item moving can easily trigger reset thresholds (eg on Bind)

It's an uncomfortable gotcha when a 'single' upstream property change explodes into a stream of N events, and then resets all bound view components due to a list refresh just because it moved more than 25 indices.

I understand this is a well known problem in React as well, just in the opposite direction

I know that finding a minimal sequence of moves is O(n^2), but it should be possible to optimize for the 'single item moved up' case by adding some logic in ChangeAwareList.Move which:

• Detects 'move down by 1' events (destination == original - 1)
• Converts them to 'move up by 1' events on the previous item
• Checks the last entry in _changes. If it is a move up by n event, with last.destination == destination then instead of emitting a new event, convert the last event to 'move up by n+1'

The steps the functionality will provide

Performance optimization and no rest threshold triggered when a single item moves up in index due to a sort.

Considerations

I don't have a checkout of the code available to test my theory. A workaround exists to just set resetThreshold: int.MaxValue but it's a bit uncomfortable

[JakenVeina]

I'm not sure what you're referencing when you say Internal/List.cs but it sounds like you're describing the following scenario:

public record Item
{
    public required int Id { get; init; }
    
    public required string Name { get; init; }
    
    public required int SortOrder { get; init; }
}

using var source = new SourceList<Item>();

source.AddRange(new Item[]
{
    new() { Id = 1,     Name = "First",     SortOrder = 1   },
    new() { Id = 2,     Name = "Second",    SortOrder = 9   },
    new() { Id = 3,     Name = "Third",     SortOrder = 2   },
    new() { Id = 4,     Name = "Fourth",    SortOrder = 3   },
    new() { Id = 5,     Name = "Fifth",     SortOrder = 4   },
    new() { Id = 6,     Name = "Sixth",     SortOrder = 5   },
    new() { Id = 7,     Name = "Seventh",   SortOrder = 6   },
    new() { Id = 8,     Name = "Eighth",    SortOrder = 7   },
    new() { Id = 9,     Name = "Ninth",     SortOrder = 8   },
    new() { Id = 10,    Name = "Tenth",     SortOrder = 10  }
});

using var comparer = new BehaviorSubject<IComparer<Item>>(Comparer<Item>.Create(static (x, y) => x.Id.CompareTo(y.Id)));

using var subscription = source.Connect()
    .Sort(comparer)
    .RecordListItems(out var results);

comparer.OnNext(Comparer<Item>.Create(static (x, y) => x.SortOrder.CompareTo(y.SortOrder)));

With this setup, the change in comparer results in the following changeset:

Move: 2 => 1
Move: 3 => 2
Move: 4 => 3
Move: 5 => 4
Move: 6 => 5
Move: 7 => 6
Move: 8 => 7

It sounds like a reasonable enhancement, but what strikes me is how unrealistic the scenario seems: of a re-sort of an entire list resulting in only a single item being moved. Is the extra work to detect the move going to be a significant hit on performance, for more common scenarios? My intuition says "probably not" but my intuition about DynamicData performance has been proven wrong repeatedly by actual benchmarks. We'd definitely want to benchmark the change, before committing to it.

The most common scenario, in my mind, for a single item being moved within a list, is when an item gets replaced or re-freshed, and thus its sorted position changes, without affecting the rest of the list. In that case, the .Sort() operator should absolutely be handling Refresh and Update changes with unique logic, to just generate a single Move. If that's not the case, we should definitely improve it.

Long story short, it sounds like an idea worth benchmarking to see how much overhead it adds to the general use case. I'd happily entertain a PR, if you're interested. Otherwise, it'll probably sit on the back-burner for a while.

A workaround exists to just set resetThreshold: int.MaxValue

I think the truth is that if resets are troublesome for your View layer, due to persistent state you need to keep, this is the only real solution. The nature of DynamicData itself is that you are accepting a certain amount of performance loss, in exchange for an improved developer experience in writing code that itemizes changes for your View layer. The reset threshold is basically just a performance optimization with the assumption that the majority of use cases DON'T require moves to be itemized. If that's what your View layer requires, then a reset threshold is just fundamentally incompatible with your View layer, regardless of how DD itemizes changes.

[Chicken-Bones]

Yes, the changeset example you have provided is indeed what I'm talking about.

Is the extra work to detect the move going to be a significant hit on performance, for more common scenarios? My intuition says "probably not"

Yes, my proposed alteration is just a little bit of additional check and book-keeping adjustment on each Move, so it should be quite low cost (for the single item moved case only).

The most common scenario, in my mind, for a single item being moved within a list, is when an item gets replaced or re-freshed, and thus its sorted position changes, without affecting the rest of the list

Yep, this is my situation. The Sort comparer uses one of the item properties, and a user editing a single item in the UI can only affect the property of one item at a time.

I think the truth is that if resets are troublesome for your View layer, due to persistent state you need to keep, this is the only real solution

This is mostly correct yes, it is the safest option.

For more information about my context, I have a SourceList<ViewModel> _list to which I add and remove items and a ReadOnlyObservableCollection<ViewModel> SortedList which is data bound into a WPF UI, and iterated as part of various interactions in the view model layer. The SortedList needs to always be up to date, so I have passed resort: WhenPropertyChanged(x => x.SortOrder)

var changes = _list.Connect();
changes
	.Sort(SortExpressionComparer<ViewModel>.Ascending(x => x.SortOrder), resort: changes.WhenPropertyChanged(x => x.SortOrder).Select(_ => Unit.Default), resetThreshold: int.MaxValue)
	.Bind(out SortedList, resetThreshold: int.MaxValue)

I went looking for libraries that could offer an 'always up to date' sorted view of a list when I found out that WPF's ListCollectionView always defers live sorting on change via Dispatcher.BeginInvoke, and DynamicData was one of the few libraries with a production tested solution.

Relatedly, I was upset by how lengthy and delicate the incantation required to achieve this even with DynamicData was, and now that I have looked into the implementation, it is clear that for this specific case there would be a simpler and more performant implementation. Since the view is always sorted, and a resort is only triggered by change to a single item's properties, in theory we would be able to bubble sort the changed item in O(n), and always emit a single move. I didn't want to go to the lengths of making my own observable collection view, and risk making mistakes, but perhaps that is indeed the best option.

Note that I am not experiencing any performance problems due to 'excessive move events' so this is not a priority issue for me. I just felt it worth raising for awareness and as a potentially common case.

[JakenVeina]

So, yeah, you've got an X/Y problem. The suggestion is still potentially valid, but there's a far more direct way to accommodate your scenario. You've overlooked the fact that Refresh changes exist.

using var source = new SourceList<Item>();

source.AddRange(new Item[]
{
    new() { Id = 1,     Name = "First",     SortOrder = 1   },
    new() { Id = 2,     Name = "Second",    SortOrder = 2   },
    new() { Id = 3,     Name = "Third",     SortOrder = 3   },
    new() { Id = 4,     Name = "Fourth",    SortOrder = 4   },
    new() { Id = 5,     Name = "Fifth",     SortOrder = 5   },
    new() { Id = 6,     Name = "Sixth",     SortOrder = 6   },
    new() { Id = 7,     Name = "Seventh",   SortOrder = 7   },
    new() { Id = 8,     Name = "Eighth",    SortOrder = 8   },
    new() { Id = 9,     Name = "Ninth",     SortOrder = 9   },
    new() { Id = 10,    Name = "Tenth",     SortOrder = 11  }
});

using var subscription = source.Connect()
    .AutoRefresh()
    .Sort(Comparer<Item>.Create(static (x, y) => x.SortOrder.CompareTo(y.SortOrder)))
    .RecordListItems(out var results);

source.Items[1].SortOrder = 10;

public class Item
    : INotifyPropertyChanged
{
    public required int Id { get; init; }
    
    public required string Name { get; init; }
    
    public required int SortOrder
    {
        get;
        set
        {
            if (value == field)
                return;
            
            field = value;
            PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(SortOrder)));
        }
    }
    
    public event PropertyChangedEventHandler? PropertyChanged;
}

The key here is the .AutoRefresh() operator. It automatically detects when items in the collection implement INotifyPropertyChanged, and subscribes to .PropertyChanged on each one. Whenever any of the properties changes, the operator emits a Refresh change downstream for that item, which tells the .Sort() operator exactly what you describe: that only a single item has changed, not the entire list. It doesn't need to re-sort the entire list, it just needs to re-evaluate that one item.

So, when we change the value of .SortOrder on just a single item, that generates the following downstream changeset:

Refresh: @1
Move: 1 => 8

You can also do something like this, to trigger refreshes ONLY for the .SortOrder property:

.AutoRefreshOnObservable(static item => item.WhenPropertyChanged(
    propertyAccessor:       static item => item.SortOrder,
    notifyOnInitialValue:   false))

The intention of the resort parameter to .Sort() is for you to tell the operator that the entire list needs re-sorted. It's really just the wrong thing to use if you only need to re-sort one item at a time.

I'll also point you to .SortAndBind() instead of .Sort().Bind() as separate operators. It's a relatively new operator, but it's definitely the recommendation when sorting is the last thing you're doing before binding a query up to the UI. Instead of keeping a sorted copy of the list in-memory, within the operator, and then pushing changes from that downstream to be applied to the target, the .SortAndBind() can just apply them directly to the target, and save quite a bit of performance, as well as just AVOID the entire problem of having to itemize sort operations into individual moves.

[Chicken-Bones]

I tried .AutoRefresh but it generated Remove/Add event pairs for moved items

[JakenVeina]

Well, that's not what's being generated in the sample I posted. Shall we take a look at your full setup?

[Chicken-Bones]

Using <PackageReference Include="DynamicData" Version="9.4.1" /> and the following test

	internal class Program
	{
		public class Item : INotifyPropertyChanged
		{
			public int Id { get; set; }

			public string Name { get; set; }

			private int _sortOrder;
			public int SortOrder {
				get => _sortOrder;
				set {
					if (value == _sortOrder)
						return;

					_sortOrder = value;
					PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(SortOrder)));
				}
			}

			public override string ToString() => $"[{SortOrder}] {Id} {Name}";

			public event PropertyChangedEventHandler? PropertyChanged;
		}

		public static void Main()
		{
			using var source = new SourceList<Item>();

			source.AddRange(
			[
				new() { Id = 1,     Name = "First",     SortOrder = 1   },
				new() { Id = 2,     Name = "Second",    SortOrder = 2   },
				new() { Id = 3,     Name = "Third",     SortOrder = 3   },
				new() { Id = 4,     Name = "Fourth",    SortOrder = 4   },
				new() { Id = 5,     Name = "Fifth",     SortOrder = 5   },
				new() { Id = 6,     Name = "Sixth",     SortOrder = 6   },
				new() { Id = 7,     Name = "Seventh",   SortOrder = 7   },
				new() { Id = 8,     Name = "Eighth",    SortOrder = 8   },
				new() { Id = 9,     Name = "Ninth",     SortOrder = 9   },
				new() { Id = 10,    Name = "Tenth",     SortOrder = 11  }
			]);

			using var subscription = source.Connect()
				.AutoRefresh()
				.Sort(Comparer<Item>.Create(static (x, y) => x.SortOrder.CompareTo(y.SortOrder)))
				.Bind(out var results)
				.Subscribe();

			((INotifyCollectionChanged)results).CollectionChanged += (s, e) => {
				Console.WriteLine($"{e.Action}: [{string.Join(", ", e.OldItems?.Cast<Item>() ?? [])}] @ {e.OldStartingIndex} -> [{string.Join(", ", e.NewItems?.Cast<Item>() ?? [])}] @ {e.NewStartingIndex}");
			};

			source.Items[1].SortOrder = 10;
			Console.ReadKey();
		}
	}

I get the output:

Remove: [[10] 2 Second] @ 1 -> [] @ -1
Add: [] @ -1 -> [[10] 2 Second] @ 1
Move: [[10] 2 Second] @ 1 -> [[10] 2 Second] @ 8

Neither .SortAndBind nor .RecordListItems are available to me. Perhaps the Nuget version is outdated?

[JakenVeina]

Neither .SortAndBind nor .RecordListItems are available to me. Perhaps the Nuget version is outdated?

That's on me, you're not out-of-date. I'd forgotten that .SortAndBind() is a cache-only operator. But that does bring up the point that you should definitely consider swapping over to SourceCache<> instead of SourceList<> if at all possible. And .RecordListItems() is an internal testing utility we use. I would like to make it public at some point, though, but there's some other cleanup we should probably do, first.

On to the code, the real issue is that Remove/Add pair being applied to the target, before the Move. The Move we actually want, the Remove/Add we don't, and if we look a little closer we can see where it's coming from. I demonstrated earlier that the changeset coming out of .Sort() in response to a Refresh is correct: it includes the same Refresh being propagated, and a corresponding Move. What you're looking at is the output of .Bind(), which is apparently translating Refreshes into Remove/Add pairs. I'd say that's actually a defect. By definition, a Refresh should only trigger an operator to "re-evaluate" an item. The deeper intention behind this is that Refresh changes should only occur for items that are "the same", but have mutated state.

Ultimately, this traces to IList.Clone(IChangeSet), where the implementation attempts to call RefreshAt() if the target list happens to implement it, but otherwise does a Remove/Add pair. I'm inclined to think this is just funamentally a mistake. Thinking about the external use-cases where we're applying a changeset to a target list that doesn't support .RefreshAt()...

• The target is an ObservableCollection<T> for a View-layer binding, in which case there's already a proper mechanism for "refreshing" an item that has mutated: INotifyPropertyChanged. On top of that, doing a Remove/Add is actively harmful, in scenarios like yours.
• The target is just a plain List<T>, in which case the consumer, I think, should be assumed to not care about Refreshes, by nature of the fact that they chose an IList<T> implementation that doesn't support them. If they DO care about Refreshes, they should use a ChangeAwareList<T>.

I struggle to think of any other use-cases.

I've also confirmed that removing this behavior doesn't break any of our other operators, at least according to our unit testing suite.

@RolandPheasant @dwcullop Any objection to removing this? If not, should we categorize this as a minor change or a breaking change? If we're all in agreement that this is a "bug", I'd say it qualifies as a minor change, although it does seem plausible that it'll break some folks' workflows.

@Chicken-Bones in the meantime, you can toss a .SuppressRefresh() in, right before .Bind().

[Chicken-Bones]

Thanks for taking the time to investigate this in detail

• I have confirmed that AutoRefreshOnObservable and SuppressRefresh work perfectly
• I'm pleased to find that the Sort operator has a mechanism for only resorting a single item via Refresh, this is going to be better than resorting the entire list regardless.
• Unfortunately my input collection is ordered, so I can't use SourceCache