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.