The Lwd abstraction tracks dependencies between different parts of the UI, implementing a primitive form of reactive programming.
The current code suffers from two problems:
1) A limitation: reverse dependency tracking is linear w.r.t the number of dependencies of a node. The performance could possibly degenerate to O(n^2) when there is a large number of dependencies. This can occur in typical UI code, but should be rare... The maximum number of dependencies in Citty is ~3.
2) A bug: some dependencies are not cleaned, leading to a space leak and degenerate performances (proportional to the size of history).
This branch implements a new reverse dependency tracking algorithm with two code-paths:
a naive one in small cases (up to 4 reverse dependencies), which should cover the vast majority of use
a heavy one (with complex invariants that I have yet to document, but I need more testing to be sure it solves the problem first :)), with O(1) amortized behavior.
I don't really expect anyone to review this PR, the purpose is rather to keep track of my developments around that problem. (But if someone feels like it, I will be happy to help reviewing)
The
Lwdabstraction tracks dependencies between different parts of the UI, implementing a primitive form of reactive programming. The current code suffers from two problems: 1) A limitation: reverse dependency tracking is linear w.r.t the number of dependencies of a node. The performance could possibly degenerate toO(n^2)when there is a large number of dependencies. This can occur in typical UI code, but should be rare... The maximum number of dependencies in Citty is ~3. 2) A bug: some dependencies are not cleaned, leading to a space leak and degenerate performances (proportional to the size of history).This branch implements a new reverse dependency tracking algorithm with two code-paths:
O(1)amortized behavior.I don't really expect anyone to review this PR, the purpose is rather to keep track of my developments around that problem. (But if someone feels like it, I will be happy to help reviewing)