Elmish.wpf: Optimizations using IDs

[TysonMN]

This issue spun out of #131. Here is a brief summary. In the OneWaySeq and SubModelSeq cases of updateValue, the runtime can be decreased from quadratic to nearly linear by making extensive use of the ID that each element in the sequence has.

Progress on this issue should wait until after #134 is fixed.

The hardest part to optimize is when a constant fraction of all items are removed. For example, suppose all items in the first half of the sequence are removed. Calling either Remove or RemoveAt takes linear time for each removal (regardless of the order), so the whole computation will take quadratic time.

To achieve nearly linear time in this case, we would have to derive from ObservableCollection<> and expose a method similar to List<T>.RemoveAll(Predicate<T>). I assumed that someone else would have done this, but I haven't found anything so far.

[TysonMN]

Oh, Move is also troublesome. I think each call takes (in the worst case) linear time.

I assumed that someone else would have done this, but I haven't found anything so far.

I was using the wrong search terms. Searches with "observablecollection" and any of "range", "bulk", or "batch" have great results, including StackOverflow and dotnet/corefx's GitHub.

Everyone seems to be concerned with raising multiple events about changes to individual elements vs raising one event about many element changes. I think the use case there is that those events are being raised on background thread.

That is not the case for Elmish.WPF. I was just stepping through the code in detail today for an unrelated reason, and this is what I observed.

1. Flow of control enters the Elmish dispatch loop
2. Flow of control shifts (if not already there) to the UI thread
3. New model is computed
4. SetState is called
5. Elmish.WPF calls ViewModel<,>.UpdateModel
6. Elmish.WPF raises events for anything that has change
7. Flow of control returns back up the stack and leaves the Elmish dispatch loop

In particular, the UI thread does _not_ process the raised events until some point after step 7. I expect that it would process them all at once. This makes me think that Elmish.WPF wouldn't suffer from the main issue that others have with large changes to an ObservableCollection.

Another issue mentioned in those search results is that WPF doesn't support bulk change events included with the INotifyCollectionChanged interface.

The inefficiency that I am concerned with is simply iterating over the underlying list multiple times. Most of the current inefficiencies are easy to remove. The troublesome parts are removals and moves, but in an Elmish.WPF application, I would expect that most of the time, the number of removals or moves in each update are small (though it is still easy to get really inefficient behavior from such a move).

[cmeeren]

If ObservableCollection is causing unavoidable problems, I guess it would be possible to write another INotifyCollectionChanged implementation tailored to our needs. Or, as you say, derive ObservableCollection.

[inosik]

Another issue mentioned in those search results is that WPF doesn't support bulk change events included with the INotifyCollectionChanged interface.

For completeness, this is the issue in the WPF repository: dotnet/wpf#1887.

[reinux]

Edit: Hang on, there's a bug here. Have to shift every subsequent item down whenever it's moved, but even then, it should still be fast when nothing is moved and should still be reasonably fast when it is.

So I just tried a really crude hack to see if this is a significant bottleneck, and I got some interesting results. Really simple change, just swapping out the Seq.find call in subModelSeq with a Dictionary call:

for newIdx, newSubModel in newSubModels |> Seq.indexed do
  let oldIdx =
    b.Vms
    |> Seq.indexed
    |> Seq.find (fun (_, vm) -> b.GetId newSubModel = b.GetId vm.CurrentModel)
    |> fst
  if oldIdx <> newIdx then b.Vms.Move(oldIdx, newIdx)

Replaced with:

let cids = Dictionary()
for i in 0..(b.Vms.Count-1) do
  cids.Add(b.GetId b.Vms.[i].CurrentModel, i)
for newIdx, newSubModel in newSubModels |> Seq.indexed do
  let oldIdx =
    cids.[b.GetId newSubModel]
  if oldIdx <> newIdx then b.Vms.Move(oldIdx, newIdx)

My collection has about 1000 items, and each item is ID'd by an int64. Measuring that chunk of code with a Stopwatch, the Dictionary approach takes about 0.4ms, down from about 120ms with the Seq.find approach. With the rest of the function included, the Seq.find approach takes about 210ms.

So it may very well be adequate to new up a Dictionary each time, at least as a stop-gap until we have a more proper solution.

Also, I've implemented something similar previously, and I can't remember why, but inheriting ObservableCollection wasn't adequate, so I ended up implementing IObservable. It may have just been an ergonomic issue.

That's the good news.

The bad news is that even with this improvement, there's another bottleneck somewhere else that makes it really slow even when there's nothing actually binding to the seq in xaml. The VS CPU profiler seems to think this function takes up about 44%.

Will try expanding the use of the Dictionary to the rest of the updateValue case and see if I can hunt down the other 56%.

[TysonMN]

Indeed, Seq.find takes much longer than using a dictionary as you have experienced.

So it may very well be adequate to new up a Dictionary each time, at least as a stop-gap until we have a more proper solution.

I think a Dictionary is the right solution.

The bad news is that even with this improvement, there's another bottleneck somewhere else that makes it really slow even when there's nothing actually binding to the seq in xaml. The VS CPU profiler seems to think this function takes up about 44%.

The calls to Remove also take a long time.

Now that I know someone "needs" these improvements, I will create a PR with all of the easy improvements tomorrow.

[TysonMN]

Edit: Hang on, there's a bug here. Have to shift every subsequent item down whenever it's moved, but even then, it should still be fast when nothing is moved and should still be reasonably fast when it is.

The sorting/ordering/movement logic is hard to get right when optimizing. I find it easy to see that the current code is correct. The bug in your code is probably that you cache the old indices in the dictionary, and that cache becomes (at least partially) invalid after doing one move (i.e. the indices in cids no longer match the indices in b.Vms).

The approach that I have been thinking through is to create my own Observable-like collection with a function Swap(int, int). Then I could both "move" an element to its correct location in constant time (instead of linear time with Move) as well as update the dictionary-cached index of the other element involved in the move.

[BentTranberg]

@bender2k14, if you're going to roll your own Observable-like, would use of IBindingList make sense? I'm in over my head again here, so I'm mostly curious.

[reinux]

The bug in your code is probably that you cache the old indices in the dictionary,

Yeah, that's it.

Last time I did something like this, I ended up having a dictionary that tracked refs to indices rather than just the indices themselves, and then another array that tracked how much each value moved.

I think that only works when things are moved by inserts, though, not by arbitrary moves.

[TysonMN]

I think that only works when things are moved by inserts, though, not by arbitrary moves.

Move is implemented by calling Remove and then Add. If the first element is moved to the last position, then the index of every element has changed, which means the dictionary of previously indices is now completely worthless.

The interesting thing is how many move events to raise. Even though the index of every element changed, ObservableCollection only raises one move event. If the collection contained n elements, then the naive approach to the swapping algorithm I am considering would raise 2 (n - 1) move events. I think this would produce the correct behavior and be faster than the current approach, but it seems like there is some more room for improvement.

[TysonMN]

On the other hand, our current sorting/ordering/movement algorithm would call Move n - 1 times.

[reinux]

Don't want to be too much of a backseat driver, but this has had me way past my bedtime... I'm having way too much fun with this problem.

I think some pieces of a diff algorithm could serve as inspiration.

Something like this:

1. Generate the edit script as per this algorithm
2. Identify IDs that appear as both an insert and a delete in the script (a simple groupBy ought to do it)
3. Execute the other inserts and deletes backwards
4. Swap the insert/delete pairs using ObservableCollection.Move(deleted, inserted)

This would do the pruning, adding and moving in one O(N+D^2) fell swoop, where D is the minimum identified number of changes. It might be necessary to track the indexes in order to issue the right events, but I think that could be done in a forward pass prior to step 2. Using a temporary list and a custom INotifyCollectionChanged might completely remove the need to shift items for each change, save for the final List.toArray.

Or I could be crazy. The birds are chirping.

[TysonMN]

...if you're going to roll your own Observable-like, would use of IBindingList make sense?

Maybe. I have only ever used ObservableCollection before. Searching around a bit, I don't get the impression that there is much love for IBindingList. In particular, it seems to have performance and memory issues. Maybe our use case wouldn't encounter those problems.

[BentTranberg]

You are confusing IBindingList with BindingList and with plain List (or ResizeArray in F#'ish) respectively. IBindingList is just an interface. But apparently there's no IBindingList<T>, so maybe that makes it less interesting.

What I find particularly interesting with IBindingList, is that you can decide how much functionality you want to support, since it has AllowEdit, AllowNew, AllowRemove, SupportsChangeNotification, SupportsSearching, SupportsSorting, IsSynchronized, IsReadOnly, IsFixedSize, etc.

[TysonMN]

Oh, ok. Thanks for pointing out my mistake :)

I am thinking I want access to IList<T>.RemoveAll(Predicate<T>) and a function like Swap(int, int). I know that RemoveAll will do what I want, but I am still thinking about the sorting/ordering case.

[TysonMN]

Everyone seems to be concerned with raising multiple events about changes to individual elements vs raising one event about many element changes. I think the use case there is that those events are being raised on background thread.

That is not the case for Elmish.WPF. I was just stepping through the code in detail today for an unrelated reason, and this is what I observed.

1. Flow of control enters the Elmish dispatch loop
2. Flow of control shifts (if not already there) to the UI thread
3. New model is computed
4. SetState is called
5. Elmish.WPF calls ViewModel<,>.UpdateModel
6. Elmish.WPF raises events for anything that has change
7. Flow of control returns back up the stack and leaves the Elmish dispatch loop

In particular, the UI thread does _not_ process the raised events until some point after step 7. I expect that it would process them all at once. This makes me think that Elmish.WPF wouldn't suffer from the main issue that others have with large changes to an ObservableCollection.

After more testing, I determined that the above behavior depends on the fact that the flow of control entered the Elmish dispatch loop from the view model's TrySetMember method. If instead the Elmish dispatch loop is entered from a background thread, then the events are processed as they are raised.

However, this doesn't change the conclusion, which is that since the events are being raised on the UI thread, the huge cost of marshalling the UI thread a linear number of times in order to handle those events doesn't happen for us.

[inosik]

If you're interested, I have build a class, which controls an IList<'T> instance (be it ResizeArray or ObservableCollection) based on immutable F# lists. I can share it next week as I'm on vacation right now.

It uses SimpleDiff to determine the difference between two F# lists, and then applies the diffs to the controlled IList<'T> instance. The algorithm is roughly like this:

// Determine the diff between the old and the new data
let diffs = diffBy getKey old ``new``
// Start at the beginning of the controlled list
let mutable pos = 0
for diff in diffs do
  match diff with
  | Equal items ->
    // These items are the same in terms of their identity, but they might need
    // to be updated with the new data later
    pos <- pos + List.length items
  | Added items ->
    // Insert the new items
    for item in items do
      // Each data item is represented with a view model item
      let item' = createViewModel item
      list.Insert (pos, item')
      pos <- pos + 1
  | Removed items ->
    // Drop the removed items
    for _ in items do
      list.RemoveAt pos

Currently, I have to iterate over the list of view models again, and update the items with the new data, but this could be added to the list controller class.

My port of SimpleDiff is on GitLab.

[reinux]

@inosik Interesting! I wonder how this compares to Myers' algorithm?

[TysonMN]

@inosik, Myers' algorithm for diffing files? I think that is a solution for a different kind of problem than the one we are solving.

[reinux]

@bender2k14 Do you have a specific idea in mind on how to do a sort using a swap function in linear-ish time? Or is that still a WIP?

I have a small hunch that a file diff algorithm might even be the only correct way to do it, and would have the added benefit of simultaneously doing the add/remove/sort, and would even give us a (reverse) ordered list of all the events that need to be triggered.

Of course, this would be a special case of a diff in that each symbol (i.e. the ID) only appears once throughout the entire "file," so I'm not doubting that you might have a better plan.

[TysonMN]

Do you have a specific idea in mind on how to do a sort using a swap function in linear-ish time? Or is that still a WIP?

The sorting via swaps in nearly linear time given nearly constant time access to the final index is trivial. The hard part, and the part I am still unsure of, is what events to raise.

For example, consider the case where a list of length n needs to be reordered so that its first element neediness its last and the index of all other elements decrease by 1. The current code achieves this by calling Move(0, n - 1), which raises exactly one NotifyCollectionChangedEvent with action Move. The algorithm I see using Swap would raise 2 (n - 1) such events.

I have a small hunch that a file diff algorithm might even be the only correct way to do it, and would have the added benefit of simultaneously doing the add/remove/sort, and would even give us a (reverse) ordered list of all the events that need to be triggered.

I really don't think file diffing algorithms apply at all here. Suppose nothing was added, removed, or updated, but the order greatly changed. The output of diff is a sequence of indexed adds and removes. How do you suggest translating this back into a solution to our problem? Particularly, what move events would toy raise?

[reinux]

With a diff, any item that's both removed and added would be moved. Finding those would be a matter of making a set of the removed items and iterating through the added items to find matching IDs, or vice versa.

In your example, moving the first item to the end should result in a remove at 0 and an insert at n-1. That can be expressed as a single Move event.

[TysonMN]

Finding those would be a matter of making a set of the removed items and iterating through the added items to find matching IDs, or vice versa.

How long would that take? It would need to be nearly linear in total to be useful to us.

In your example...

Do you see how it would work in general? I still don't see it.

[reinux]

How long would that take?

Should be linear time and dependent on the number of changes as opposed to the number of elements. The number of changes should usually be relatively small, except when everything's shuffled or it's a new set.

That part would be something like:

type Removal = {
   ix : int
   id : obj
}

type Insert = {
  ix : int
  id : obj
}

type Move = {
   sourceix : int
   destix : int
}

let removedById = Dictionary [ for i in removals -> i.id, i.ix ]

let toMove =
  inserts
  |> Seq.choose(fun i ->
      match removedById.TryGetValue(i.id) with
      | true, r -> Some { sourceix = r.ix; destix = i.ix }
      | false, _ -> None
     )

I'm not familiar with the algorithm @inosik uses, but the classic one by Myers has an expected time of O(N+D²), where D is the number of changes, though I believe it's less than D² when one list is shorter, e.g. when the list is first populated.

Apparently there are optimizations dependent on a finite alphabet, so I suspect there might be optimizations for non-repeating alphabets as well -- or they might just reduce to become equivalent to our current approach (assuming we get Move down to linear time)

[TysonMN]

Should be linear time and dependent on the number of changes as opposed to the number of elements. The number of changes should usually be relatively small, except when everything's shuffled or it's a new set.
...
...the classic one by Myers has an expected time of O(N+D^2), where D is the number of changes...

The code in my current PR has that runtime. The hard part is worst case analysis in which D = N.

[reinux]

Ah, maybe that's where my misunderstanding is then.

Are we doing four internal swaps and four Move events in a case like abcde -> bcdea, or would that be four internal swaps and one Move?

If that's as much of a worst-case as edcba -> abcde, then Myers might be faster for most common cases, but otherwise it should be the same.

[cmeeren]

This issue is partially adressed by v3.5.1 (through #149).

[TysonMN]

...the classic one by Myers has an expected time of O(N+D^2), where D is the number of changes...

The code in my current PR has that runtime.

Well, no. Let's be more precise.

First, when I use the word "nearly" in a phrase like "nearly linear" time, I am giving credence to the fact that dictionary lookups are not free; they are not constant time, but they are "nearly" constant time. The exact runtime of dictionary lookups is not important though, so I will continue to say that it takes "nearly" constant time.

Suppose n is the maximum of the lengths of the old and new sequences. Then

• the runtime of the add and update steps are both nearly O(n),
• the runtime of the removal step is nearly O(r n), where r is the number of removals, and
• the runtime of the sorting step is O(n^2) (even when no elements are moved).

So the most room for improvement is currently in the sorting step.

Deriving from ObservableCollection<> to properly expose List.RemoveAll would allow the runtime of the removal step to decrease to nearly O(n) as well. Which events to raise there is clear. The thing I want to test there is when to raise those events: either one at a time as elements are removed or (still individually but) after all elements have been removed.

[TysonMN]

Are we doing four internal swaps and four Move events in a case like abcde -> bcdea, or would that be four internal swaps and one Move?

In the current algorithm, the moves happen in the order of the new sequence. Suppose we want to move from a to b in a list of length n. If a = b, then there are no moves and no swaps. Otherwise, there is one move as well as

• n - a - 1 swaps to remove at a and
• n - b - 1 swaps to insert at b.

So for your example, there are four moves and a bunch of swaps. The simpler case is bcdea -> abcde, which has one move and four swaps.

If that's as much of a worst-case as edcba -> abcde, then Myers might be faster for most common cases, but otherwise it should be the same.

That case will also have four moves and many swaps.

[reinux]

Thanks for the detailed explanation!

I understand for the most part now. I just wasn't sure the sort step could be simplified, because of how complicated it is normally to track the indexes.

[TysonMN]

...the classic one by Myers has an expected time of O(N+D^2), where D is the number of changes, though I believe it's less than D^2 when one list is shorter, e.g. when the list is first populated.

Your idea to include the number of changes in the analysis is good. I am more familiar with the edit distance problem than diffing algorithms. For that problem, the Wagner-Fischer algorithm is the standard efficient solution with a quadratic runtime with strings have the same length.

However, there are improvements (given here and the last bullet here) with analysis that includes a parameter like the number of changes. The conclusion is that there are algorithms than are significantly faster than the standard solution when the number of changes is less than linear.

I expect that typically a single call to Move would be enough, so it would be great to have an algorithm with a runtime of O(N+D^2) or even O(N D), where D is the number of required calls to Move (assuming that we sort only via calls to Move).

[TysonMN]

I finally thought of good search terms for our problem, which are "apply permutation in place". The most accurate hit is probably this one.

The interesting (and challenging) thing about ObservableCollection<> and its method Move(int, int) is that it moves one element as specified while also shifting over all the intermediate elements by one spot. I don't think any of the solutions to the in-place permutation problem explicitly behave like this.

[TysonMN]

I just wasn't sure the sort step could be simplified, because of how complicated it is normally to track the indexes.

Using a Swap(int, int) method, we can implement some of those in-place permutation algorithms. The interesting part is which Move events to raise. The trivial solution is to raise two per swap, one for each element in the swap. In the worst case, that would be 2 (N - 1) move events raised while the current algorithm would only raise at most N - 1 move events.

[reinux]

Ohh of course, it's a permutation problem. That would have to get us to the best solution.

[TysonMN]

I think I have a solution I like. Here is a sketch.

Let n be the number of elements. In nearly linear time in n, we compute the permutation that we want to apply. Let m be the number of elements that will move (i.e. change their location) when the permutation is applied.

Apply the permutation as specified by some in-place permutation algorithm, such as the one where the permutation is decomposed into cycles and each cycle is applied by sequentially shifting each element into the correct position. I didn't think about the exact runtime here, but it should be efficient.

So far, we haven't raised any move events. Now we compute and raise these events.

Intuitively, we run our current quadratic sorting algorithm, but instead of running it on our whole list so that the runtime is O(n^2), we simulate it on the m elements that were moved so that the runtime is only O(m^2). This gives a total runtime (when ignoring the dictionary lookups) of O(n + m^2), which matches the runtime of efficient algorithms for similar problems.

The only thing left is to decide the order in which we simulate calls to Move. I still didn't know what the optimal order would be. However, I thought of a good heuristic, which is to order by decreasing "distance", where this distance is |newIdx - oldIdx|.

The reason that I am happy with this heuristic is that

1. I don't see any case (especially simple cases) on which our current sorting algorithm performs better, and
2. there are simple cases on which this new sorting algorithm (using this heuristic) performs better.

[reinux]

The problem of tabulating and mirroring change in an immutable list seems so fundamental, it's kind of surprising it doesn't seem to have gotten much attention.

[TysonMN]

...an immutable list...

I don't think immutability is essential. I can phrase the issue as the following (optimization) problem.

Consider a variant of ObservableCollection<> that supports disabling and reenabling change notifications. When it becomes disabled, its current state is saved. When it is reenabled, change notifications are raised to communicate the difference between saved state and the current state.

For example, compare the following two scenario.

Using ObservableCollection<>

1. Add e
2. Remove e

Two change notifications are raised.

Using variant of ObservableCollection<>

1. Disable it
2. Add e
3. Remove e
4. Reenable it

No change notifications are raised.

The problem of tabulating and mirroring change in ~an immutable~ [a] list seems so fundamental, it's kind of surprising it doesn't seem to have gotten much attention.

I think it seems so fundamental from the worldview of the Elm architecture. A theoretical understanding is not lacking, just implementations that practitioners like us can immediately put into use. My impression is that functional programming generally and architectures like the Elm architecture specifically have been growing in popularity (with the reason being that it is a better way to write software).

I think ObservableCollection<> (as part of an MVVM architecture) was designed with the intention of it being the source of truth. For years, there were debates within my company about whether the model should contain instances of ObservableCollection<> (possibly "hidden" behind its IList<> or IReadOnlyCollection<> interface). That debate was never resolved. Those for ObservableCollection<> wanted integration simplicity with WPF. Those against wanted model simplicity, such as immutability. I feel like both sides were correct and that Elmish.WPF satisfies the desires of both sides.

Purity vs impurity is a syntactic property even if compilers typically (never?) detect the difference. One semantic interpretation that I find useful involves code reuse: reusing pure code is simple; reusing impure code is complex. One way to think of the Elm architecture is as taking on all the (complex) impure code so that users only have to write (simple) pure code. I think the task of Elmish.WPF with these ObservableCollection<>s is fundamentally about writing mutable code. With the above heuristic in mind and the fact that Elmish.WPF stands alone at the intersection of the Elm architecture and WPF, I don't think it is surprising that we are unable to solve our problem by reusing existing code.

[reinux]

Good point about ObservableCollection being used as the source of truth and about scenarios where change notifications are disabled.

The opposite's also true, come to think of it, in that you could use, say, a zipper on a list to insert/update/remove with roughly the same time complexity as an array (except the update case), and have an accumulator to track the changes and mirror them on another list of the same length.

Of course, that's not applicable to Elm.

[TysonMN]

The work in this issue corresponds to Elm's HTML.keyed.

[TysonMN]

Apply the permutation as specified by some in-place permutation algorithm, such as the one where the permutation is decomposed into cycles and each cycle is applied by sequentially shifting each element into the correct position. I didn't think about the exact runtime here, but it should be efficient.

I no longer think that this part is needed. I think we can simply create a new list with the desired ordering. I think this will work because I think WPF only subscribes to the change notifications and never directly reads the list. I could be wrong though.

I will definitely try this first since it is much easier.

[reinux]

It looks like React uses a heuristic algorithm to bring the typical case runtime down to close to O(n). I'm looking through the code now, but I'm not too familiar with javascript fibers, so the control flow isn't immediately obvious to me.

From what I'm reading, state-of-the-art permutation/diff algorithms peak at O(nm), where m is the number of changes.

Barring adapting React's heuristics, I wonder if it might be easiest to use, say, a tree sort or other adaptive sort that could bring the time down to O(m log n). That would bring the whole process down from O(mn) with a diff/permutation algorithm, or O(n + n log n) with a more typical sort like QuickSort, to O(n + m log n).

Are there more issues with ObservableCollection.Move() that we need to overcome as well?

[TysonMN]

Thanks for the information @reinux. I believe that I have thought threw this work as much as I can. Now I just need to start working in it. I know I keep saying this, but I should have time soon. Probably this month.

[TysonMN]

I just closed PR #165 because I no longer like that approach.

I still think my https://github.com/elmish/Elmish.WPF/issues/137#issuecomment-544240524 and follow up https://github.com/elmish/Elmish.WPF/issues/137#issuecomment-553571246 would be an interesting solution.

However, I am not enthusiastic about that approach now either. I think it is too complicated.

I previously realized that

The work in this issue corresponds to Elm's HTML.keyed.
https://github.com/elmish/Elmish.WPF/issues/137#issuecomment-549910641

To get a different perspective on this problem, I looked at Elm's implementation of HTML.keyed. I am still trying to internalize the entire implementation, but the basic approach is clear.

The implementation simultaneously iterates over both the source and target lists. If the current elements (one from each list) are the same, then it updates the target element given the source element. If they are not the same, then it replaces the source element with new data corresponding to the target element.

Contrast this with our current approach, which avoids ever creating a copy of a view model for a given ID if impossible by doing a linear-time search through the target list.
https://github.com/elmish/Elmish.WPF/blob/35311e185f3c00fdd729e6eb09cdc862f942b3a4/src/Elmish.WPF/ViewModel.fs#L471-L473

The implementation in Elm is more complicated than I described. Instead of just considering two elements (one from each list) at a time, it considers four elements (two from each list) at a time (in the case that the first two differ). In doing so, they are able to efficiently handle the common cases of swapping adjacent elements, a single addition, and a single removal.

I like this approach. I think it has a good tradeoff between runtime efficiency and implmentation complexity. I will try to implement this for us.