freya icon indicating copy to clipboard operation
freya copied to clipboard

enhancement(torin): Common ancestor optimization for separate branches with fixed size nodes

Open marc2332 opened this issue 6 months ago • 1 comments

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

image 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.

marc2332 avatar Aug 15 '24 15:08 marc2332