freya
freya copied to clipboard
enhancement(torin): Common ancestor optimization for separate branches with fixed size nodes
What if Torin tried to measure different invalidated nodes branches as separate root candidates if only there was a fixed node in the path to their common ancestor.
Having a fixed size node in the path to their common ancestor would confirm that any change to that node would not affect the other invalidated nodes, thus making measuring faster.
Consider this example
Let's suppose we are modifying
[6, 8]
and we know [2, 3, 4, 5, 7]
have a size dependent on their children. Torin would need to start measuring from 1
because any change to 6
could affect [2, 3]
and thus, end up affecting [4, 5, 7, 8]
. But what if Torin knows 2
is fixed size? Then we could measure the branch of 2
from 2
itself, and then do 8
from 8
itself as well.