[Performance; Architecture] Research "Resumable Code" for tree diffing, thus make it streamable

Problem

Currently we calculate diff recursively for the entire tree all at once. As a part of it we use a recursive data structure

and [<Struct; RequireQualifiedAccess>] WidgetChange =
    | Added of added: WidgetAttribute
    | Removed of removed: WidgetAttribute
    | Updated of updated: struct (WidgetAttribute * WidgetDiff)
    | ReplacedBy of replacedBy: WidgetAttribute

and [<Struct; RequireQualifiedAccess>] WidgetCollectionChange =
    | Added of added: WidgetCollectionAttribute
    | Removed of removed: WidgetCollectionAttribute
    | Updated of updated: struct (WidgetCollectionAttribute * WidgetCollectionItemChange [])

and [<Struct; RequireQualifiedAccess>] WidgetCollectionItemChange =
    | Insert of widgetInserted: struct (int * Widget)
    | Replace of widgetReplaced: struct (int * Widget)
    | Update of widgetUpdated: struct (int * WidgetDiff)
    | Remove of removed: int

and [<Struct>] WidgetDiff =
    {
        ScalarChanges: ScalarChange []
        WidgetChanges: WidgetChange []  // <--- children's update
        WidgetCollectionChanges: WidgetCollectionChange [] // <--- children's update
    }

There a a couple of concerns here:

It allocates arrays for every tree node
It is all at once, thus not stoppable nor there is an opportunity to reuse memory.
The diff structures are very short lived, e.g. after calling ApplyDiff they immediately become garbage applying pressure on GC.

Idea to explore

Make calculation of children diff somehow lazy. Note that it potentially ok to have dynamic dispatch (virtual call) if it removes allocations. I haven't researched enough the new feature of "Resumable Code" in F# 6, to understand if that idea is even applicable to us.

But roughly it would be awesome if we can somehow express this (pseudo code):

and [<Struct>] WidgetDiff =
    {
        ScalarChanges: ScalarChange []
        WidgetChanges: LazyCollection<WidgetChange>  // <--- 
        WidgetCollectionChanges: LazyCollection<WidgetCollectionChange> // <---
    }

My intuition tells me that in this form LazyCollection has to be dynamically allocated, thus it is probably not better than status quo.

HOWEVER this is probably an opportunity to express the same recursive Diff via some other data structure. Like so

type WidgetDiff = Stream<struct (ScalarChange [] * WidgetChange[] * WidgetCollectionChange[])>

Where the Stream data structure might be "Resumable Code". If so then we can replace [] with StackArray (stack allocated collection), thus avoiding intermediate allocations. Not sure if it is possible to avoid dynamic dispatch though.

Objective

Research what are the options making diff calculation lazy, and have a PoC ideally backed by benchmark how it might work.

Note that it is probably going to be one of the last perf explorations (at least according to my intuition), because other "[Performance]" tasks probably have more predictable ROI.

TimLariviere / Fabulous-new