Elmish.wpf: Trees done right

[TysonMN]

This is a spin off of https://github.com/elmish/Elmish.WPF/issues/143#issuecomment-644371235.

That issue is about adding lazy behavior to the SubModelSeq binding (i.e. what the OneWaySeq binding calls itemEquals). Even after that lazy behavior is implemented, there might still be an issue for trees.

To gain a better understanding of the potential issue, I will modify the SubModelSeq sample, which involves trees, to use _explicit_ trees. By "explicit tree", I mean a tree in which each node contains direct references to its children. To achieve this, I expect to add an extra layer in the XAML to map from the tree node containing the counter to the counter itself....much like how a SubModel binding looks in the XAML.

I briefly searched for how to create a tree in ELM, but I only found independent solutions to correctly and efficiently handle the case of trees, so this makes me think that ELM doesn't directly support trees.

[ScottHutchinson]

And googling for "elm trees" yields more results botanical than software. ;o)

[cmeeren]

Even after that lazy behavior is implemented, there might still be an issue for trees.

Could you elaborate? (If it's still relevant.)

[TysonMN]

Yes, it is still relevant.

First, https://github.com/elmish/Elmish.WPF/issues/143#issuecomment-641532812 is about the SubModelSeq sample being slow when the tree becomes large. It is slow even when the tree is flat. To see this, test on the branch testing/large_TreeView_slow/MWE. It is slow because of code in the sample.

Second, I hastily implemented the "lazy"-style behavior as described in #143. Then I modified the sample to use the lazy behavior with the refEq function. See the branch testing/large_TreeView_slow/lazy_SubModelSeq. The resulting code is fast, but the behavior is wrong. The short circuit of update is incorrect because it ignores changes in the children. In order to see a change in a child, there has to be a change in its parent, grandparent, and so on all the way up to a top-level counter. See this GIF for the behavior in the simplest case of a child counter with top-level parent counter.

To recap, the current SubModelSeq sample is slow for large trees because the user code is inefficient. After adding lazy feature, the SubModelSeq sample is buggy if it uses refEq to stop the update computation early. In both cases, the issue is the user code and not the core Elmish.WPF code.

The sample code flattens the tree before providing the sequence of nodes to Elmish.WPF. I want to see if I can avoid flattening the tree in the sample. If the tree is not flattened, then I should be able to optimize the code so that updates bug free are instantaneous. If I can't figure out how to keep the tree from being flattened, then I consider how to change the core Elmish.WPF code to support this case.

[TysonMN]

I finally attempted to change the SubModelSeq sample to use "explicit" trees, and the attempt was very successful. The UI now responses (nearly) instantly (when the tree contains 1000 top-level counters). I didn't have to change any of the core Elmish.WPF code either; I only changed the SubModelSeq code.

I first made this change on top of the v4 branch because I found it easier to figure out the new binding structure when I am able to remove all duplication with mapModel. However, to show that the optimization doesn't depend on the breaking changes already in the v4 branch, I then ported the optimization to the master branch.

Here is the same optimization on those two branches.

• master: optimize_SubModelSeq_sample_on_master
• v4: optimize_SubModelSeq_sample_on_v4

Contrasting these two branches is a good example of the difference between not using mapModel at all and using mapModel as much as possible.

@ScottHutchinson, can you try either of those branches (especially after making the corresponding changes in your private application) and see if this is fast enough for you?

[ScottHutchinson]

This is great news! I will try it out as soon as possible. Thanks so much!

[cmeeren]

Great news, @bender2k14! I don't really understand at a high level what the difference is, and I don't have time right now to reverse engineer that from the branch diff. Is it much more effective using mapModel where you can? Is this always the case? If so, we should definitely mention that in all relevant sections of the tutorial. And if it is "the only right way to do it", we may even consider changing the API (for v4?) to force users to do it the right way.

[TysonMN]

I don't really understand at a high level what the difference is...

The only difference between the two branches is that the one on master doesn't use mapModel (or mapMsgWithModel) and the one on v4 has one call to mapMsgWIthModel and many calls to mapModel.

...if [using the binding functions] is "the only right way to do it"...

The purpose of these calls to the binding mapping functions is to _to remove all duplication_. It is "the right way to do it" in the sense that it removes duplicate code. However, small amounts of duplication can be better than the effort and code used to deduplicate, so I would not say that the binding mapping functions are the only right way.

The first commit changes the 'model type parameter in the list of bindings from...
```F#
Model * RoseTree>

...to...
```F#
Model * (RoseTree<Identifiable<Counter>> * RoseTree<Identifiable<Counter>>)

Given that my goal was to provide each child a reference to its parent, this type change might seem obvious. Well, many things seem obvious in hindsight or when someone else tells you it is the right answer, but I can assure you that I was confused with compiler errors for about three hours before figuring this out. It would have taken me much longer to figure this out if everytime I changed the 'model type parameter I had to adjust the duplicate mapping code in 13 bindings. Instead, I used mapModel to remove all duplication so that I only had two or three unique compiler errors at any one time.

The actual goal is to improve or maximize the efficiency of the development process. If removing duplicate code via the binding mapping functions increases the efficiency of the development process, then using the binding mapping functions "is the right way to do it". But if removing duplicate code via the binding mapping functions decreases the efficiency of the development process, then using the binding mapping functions "is the wrong way to do it".

...if [using binding mapping functions] is "the only right way to do it", we may even consider changing the API (for v4?) to force users to do it the right way.

I do want a more composable binding API. I want user to to be able to "binding effects" (like lazy, cached, optional, and seq). Part of that achieving that goal is removing the duplication in the bindings.

Consider that...
```F#
"BindingName" |> Binding.OneWay f

...is the same as
```F#
"BindingName" |> (Binding.OneWay id |> Binding.mapModel f)

Does this mean Binding.OneWay f contains duplication? All bindings have a function that goes from 'model to...something, just like f in that example. Does that mean that all bindings are duplicating some concept? I don't know yet. I need to write more Elmish.WPF code (especially with the new binding mappings) and think more.

So for now, I don't want to make big changes to the binding API.

[cmeeren]

Thanks for the explanation. When I said:

Is it much more effective using mapModel where you can?

I should probably have said performant, not effective. I was mostly wondering whether mapModel used like this increases performance, or at the very least upens up some ways of improving the performance of user code. That is what I was suggesting we add to the tutorial. To me (without having delved too much into this), it seems that the change from not using mapModel to using mapModel allowed you to improve the performance of the code by many orders of magnitude. I'm not clear exactly what the main cause of this improvement is.

[cmeeren]

I do want a more composable binding API. I want user to to be able to "binding effects" (like lazy, cached, optional, and seq).

Side note, I absolutely love this. I would very much like to see this, too.

[TysonMN]

My guess is that using the binding mapping functions are slightly less performant in the same sense that I think fun a -> a |> f |> g is slower than f >> g, but not in a way that I think is worth optimizing (and probably not even testing until someone asks for it).

To me (without having delved too much into this), it seems that the change from not using mapModel to using mapModel allowed you to improve the performance of the code by many orders of magnitude. I'm not clear exactly what the main cause of this improvement is.

Sorry for being unclear where the performance gain came from.

• master is slow and can be tested via the branch testing/large_TreeView_slow/MWE. I think the runtime is (always) quadratic in the tree size.
• The following branches are both much faster. I think the runtime is (always) linear in the tree size.
  
  
  
  • optimize_SubModelSeq_sample_on_master
  
  
  • optimize_SubModelSeq_sample_on_v4
  
  

The point of creating both of these fast optimize_SubModelSeq_sample branches is to show that the speed improvements is _not_ because of mapModel.

I think the runtime is (always) linear in the tree size.

I have another idea to improve the runtime to at most linear in the tree size and sometimes constant time (when editing the first top-level counter).

[TysonMN]

I do want a more composable binding API. I want user to to be able to "binding effects" (like lazy, cached, optional, and seq).

Side note, I absolutely love this. I would very much like to see this, too.

I created issue #263 to track this.

[cmeeren]

So, going back to https://github.com/elmish/Elmish.WPF/issues/236#issuecomment-673871992:

Yes, it is still relevant.

Are you saying this issue is no longer relevant since changing user code solves the performance problem?

[TysonMN]

Yes.

However, @ScottHutchinson is going to help me confirm this believe of mine by incorporating my changes into his program and testing the performance.

I also have another performance improvement in the user code to make the runtime ever faster (in some cases).

[TysonMN]

I also have another performance improvement in the user code to make the runtime ever faster (in some cases).

Quoting https://github.com/elmish/Elmish.WPF/issues/236#issuecomment-674248106

The UI now responses (nearly) instantly (when the tree contains 1000 top-level counters).

I finished the second performance improvement, and the UI now responses instantly in many cases. More specifically, the performance scales with the distance down the tree and across the lists of children. That is, the closer to the root of the tree and the closer to the beginning of children lists the faster the performance.

This optimization adds a recursive RoseTreeMsg<'a, 'msg> type. To change something at a particular spot in the tree, this recursive message type has all the information needed walk the tree directly to the change point, make the change, and then put the tree back together. If some part of the tree doesn't need to be traversed, then this new code doesn't touch that part of the tree. Previously, the whole tree touched in case it might need to be changed. Then the whole tree was recreated. So the runtime before was always exactly linear in the tree size. Now that only the nodes along the path from the root the change point are touched, the runtime is typically sublinear in the tree size. For example, changing something about the first top-level counter is now a constant-time computation.

I pushed this optimizations to the same branches (because, just as before, this optimization doesn't depend on the breaking changes in v4). Here are the branches to compare now.

• master is slow and can be tested via the branch testing/large_TreeView_slow/MWE. I think the runtime is _always_ quadratic in the tree size.

• The following branches are both much faster. I think the runtime is ~always~ _at most_ linear in the tree size.

  • optimize_SubModelSeq_sample_on_master
  • optimize_SubModelSeq_sample_on_v4

[ScottHutchinson]

I will try to implement this optimization today on https://github.com/ScottHutchinson/Elmish.WPF-1/tree/ShowDialog_subModelSeq/src/Samples/ShowDialog.subModelSeq

[TysonMN]

I can make the change for you on this public branch.

[ScottHutchinson]

I just rebased it, so it's even with upstream master now.

[TysonMN]

Try people/Scott/ShowDialog_subModelSeq. The response isn't instance, but it is nearly so.

[ScottHutchinson]

Yeah, a release build is pretty fast. I'd guess roughly 100 ms. I will incorporate this change into our production app, which should see the same improvement. Thanks so much!

[cmeeren]

This optimization adds a recursive RoseTreeMsg<'a, 'msg> type. To change something at a particular spot in the tree, this recursive message type has all the information needed walk the tree directly to the change point, make the change, and then put the tree back together.

Oh, that is b-e-a-utiful. We should probably merge that into the sample in this repo, if you're happy with it.

[TysonMN]

This optimization adds a recursive RoseTreeMsg<'a, 'msg> type. To change something at a particular spot in the tree, this recursive message type has all the information needed walk the tree directly to the change point, make the change, and then put the tree back together.

Oh, that is b-e-a-utiful.

Thanks! :D I really like it as well.

We should probably merge that into the sample in this repo, if you're happy with it.

Yes, I definitely want to merge it in. I will clean in up a bit first and then make a PR for master. After we get it in there, I will make a second PR for merging master into v4.