updateItems algorithm bugs

[Dolfik1]

I tried to use this algorithm but I found some bugs. It seems that algorithm sometimes detect created as changed. We can try to port Android DiffUtils tests to catch this.

Also I think it would be better to use The Myers Diff Algorithm. This algorithm used in Android DiffUtil (DiffUtil.java)

There are some links about this algo: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ http://www.xmailserver.org/diff2.pdf

[TimLariviere]

Yes, I agree we should take a look at tried-and-tested algorithms like the Myers Diff Algorithm. Thanks for the links, I'll take a look at them as soon as possible.

[VistianOpenSource]

Our Implementations of collection difference operations can be found at https://github.com/VistianOpenSource/Birch/tree/master/Birch.Core/Collections .

There are three implementations - Heckel, Simple & Eugene Myers.

Depending upon what benchmarks are used, Myers can be a lot quicker than Heckel, but under certain circumstances Simple can be quicker. Simple is probably most suited for scenarios whereby items are only being added at the end of a list and this is the scenario in which it gets quicker.

The implementations all have an assumption of an equalitycomparer being provided. Hashes are very important for the execution of the comparisons. If i also remember correctly the Heckel implementation has the ability to provide 'Moves' (even though the ordered diff filters these out), Myers doesn't.

For our scenario however, it is possible that all of these comparers can produce a 'delete'/'insert' operation when in fact its an update operation, so there is an additional class CollectionChangeCompactor that looks to reduce the number of operations - but the required usage of this is more @ the actual requirement level that the comparisons (the delete/insert can be merged if the resultant final 'view' is the same). For our scenario where we update the changes to the 'backing store' for collectionviews/recyclerviews/listviews we use it there (see https://github.com/VistianOpenSource/Birch/blob/master/Birch.Core/Components/BackingStoreUpdateHandler.generic.cs ).

Also, should you be interested, there is a very simple benchmark block of code for comparing their performance with collections of around 10,000 items. https://github.com/VistianOpenSource/Birch/blob/master/Benchmarks/Program.cs .

Final, final, point, given that there may be scenarios under which Simple is the best choice, we allowed for the default comparer to be optionally overridden at the view element level.

[vshapenko]

@VistianOpenSource , would be wise to use ArraySegment and ArrayPool in your Myers implementation to reduce memory footprint and GC pressure

[VistianOpenSource]

@vshapenko I spot a volunteer :-)

[vshapenko]

@VistianOpenSource , i do think when i have time i would try, but on f# :). And my priority is Fabulous, cause i use it in prod

[VistianOpenSource]

@vshapenko Sure, i do wonder (probably too late, but anyway) whether it would make sense to split the Fabulous implementation, with the lower level mapping of properties, diffing & transactions occurring within C# and the higher level implementation of Elmish /Fabulous models in F#. Theoretically (!) it would allow the existing pool of C# developers to benefit from the work, but similarly not impede the development of Fabulous either.

[vshapenko]

@VistianOpenSource , diff algorithm indeed can be written independently i think and used either in fabulous or your lib

[vshapenko]

took a look at Myers implemetation. Looks completely independent itself. Can be rewrittern to f# easily. I will take a look at weekend

[VistianOpenSource]

Did an experiment replacing SubArray with ArraySegment , and then ran with Benchmark - bottom line, no difference at all in the Gen 0,Gen 1 & Gen 2 values at all. There was a grand saving of approx 194 bytes used for comparison of 2 10,000 lists, perhaps other scenarios may produce greater memory benefits.

[TimLariviere]

Thanks @VistianOpenSource.

Sure, i do wonder (probably too late, but anyway) whether it would make sense to split the Fabulous implementation, with the lower level mapping of properties, diffing & transactions occurring within C# and the higher level implementation of Elmish /Fabulous models in F#

I guess it would be possible to reuse the non-F# specific parts of Fabulous in a C#-focused lib, even without rewriting the existing code to C#, after all it's all .NET. What do you have in mind specifically? Fabulous for C#?

The main issue I would have with a shared architecture between F# and C# is that it will make things harder to have a great experience for one language or the other. As well as slowdown evolution because we would need to take into consideration both languages who have different goals.

[VistianOpenSource]

@TimLariviere what was I thinking? Good question. I'll give you a short potted history of what I was looking to achieve.

I initially started off by looking to try and provide some .net solution that was broadly a model, view, update style approach to mobile UI creation. I wasn't particularly interested in looking at Xamarin Forms, but rather the native platforms of Android & iOS since that is what I'd done previously.

I have a few criteria in trying to achieve this:

1. It would broadly take less effort to consume than say the traditional android approach of an axml file or a storyboard. 2.It wouldn't have performance issues on especially Android due to too much work being done on the UI thread. 3.It would allow for easy consumption of 3rd party controls without always resorting to a 'generator app'. 4.The application wouldn't become larger as a result of taking this approach.

I wasn't particularly fussed about what language to do this in. My experience however with F# using Visual Studio 2019 previews did however make me question the commitment to F# as a mobile dev platform. So... given that the underlying UI controls have typically been constructed from an object oriented approach and that C# appeared to be better supported by MS I decided to try and split the job and do those elements which better aligned themselves to object oriented approaches in C# and do the higher level elements in F#.

As of today, I have a cut of code which is as happy running on Android and it is with Xamarin Forms. Doing iOS wouldn't be difficult, once the 'host' has been created for a controller it would be easy to add in the relevant views.

It does have a generator application which , using Handlebars template files, generates the appropriate extension methods/calls. The generator also creates the appropriate dummy code to allow for full linking to be used when a release version is created.

The code, can / does use reflection once for each referenced type to setup the property/method/event mappings. This does mean that 3 party classes can be used without generation e.g. classes like PancakeView. Reflection isn't mandatory for the operation of the framework.

To stay away from the UI thread, all of the layout and comparisons between state occurs on background threads, the only work performed on the UI thread is the actual performance of the updates to the UI elements.

Stateful controls/containers are supported, allowing for the construction of components.

There can be a logical separation between a 'container' and its layout provider, allowing for a model to be shared, but for a different Layout for iOS and Android say.

The F# work hasn't been done plumbing into this - Visual Studio 2019 doesn't even seem to support Xamarin Forms as a target and some of the mobile templates MS provide don't even work, but I do intend to try and use the Fabulous Xamarin Forms setup and see how well it works.

[vshapenko]

Found Myers implementation on f# . https://github.com/nikolamilekic/FsMyers

[TimLariviere]

I fear the Myers diff algorithm won't be enough for Fabulous.

Fabulous actually has 3 ways to consider elements to be identical (not really identical, but reusable so it can run the diff on existing controls):

• First, it will try to find an exact reference match (same instance)
• Then, it will try to find a key match (same key value and canReuseView prev curr is true)
• Finally, it will try to find the next element in the list where canReuseView prev curr is true. Only if no match, it will consider it to be a new element that should be inserted.

So let's take this example:

View.StackLayout([
    View.Button(key = "ButtonWithKey")
])

Let's update it to

View.StackLayout([
    View.Button()
    View.Button(key = "ButtonWithKey")
])

In this case, Fabulous should consider that a new button was added at the top, because the key value was reused. Except, as I understand the Myers diff algorithm, it will say that an element was added at the bottom, since canReuseView prev curr is true since both elements are button.

And that's a simple case because the elements are contiguous. Maybe we can change the algo a bit to make it work. But for more complex cases, I'm not sure this algorithm could support what we want.

[VistianOpenSource]

@TimLariviere for us I believe, in that scenario we would see that the View.Button() is an insertion at position 0. We don't (yet) use keys for matching between items but rely on the comparator to return sequences of insert/deletes/updates/moves.

For some scenarios e.g. imagine that the text for a button at the same index is different then the 'raw' comparator would consider this a delete followed by an insert. We take these operations however and potentially convert them to an update operation if the existing instance can be updated to the new instance.

[vshapenko]

@TimLariviere , i think myers would be good for items diff in collections. Other cases might require additional work

[VistianOpenSource]

@TimLariviere just thinking outloud but is it not the case that the test for equality between two elements (in your case of view elements) is such that if they are of the same type and have a matching key attribute they are considered the same, otherwise they are considered the same if they are of the same type and their attributes match (I've excluded reference equality here, just to make it a bit shorter)? If so, does that then mean the approach then collapses to the single use of a 'standard' comparison algorithm like Myers or Heckel?

[TimLariviere]

We don't compare if all the attributes match between 2 elements, we only compare the key attribute and the control type. Otherwise, we might end up going really deep in the tree to check if 2 elements have indeed the same attributes (they might differ at a different hierarchy depth) and it would drastically reduce the control reuse we do.

The problem I see using a simple comparer with Myers is that it won't respect the priority of reuse. In the example I gave earlier, the Button ButtonWithKey should be reused and a new button inserted at the top.

But the way I understand the Myers diff algorithm (with a simple equality check on key attr or same control type) is that it will reuse the button for the first item (since View.Button() == View.Button(key = "ButtonWithKey") because of control type) and insert a new button at the end. Except View.Button(key = "ButtonWithKey", text = "A") == View.Button(key = "ButtonWithKey", text = "B") has more priority than View.Button() == View.Button(key = "ButtonWithKey").

And in my opinion, it can't be done without scanning the previous collection multiple times (1st time for matching ref, 2nd time for matching key, 3rd time for matching type), which Myers doesn't do.

[TimLariviere]

Moving this discussion to vNext as 0.55 integrates a custom diff algorithm for now.

[TimLariviere]

Closing as this is no longer relevant in v2