Performance: avoiding duplicating reusable work #2854

myitcv · 2024-02-22T06:13:08Z

References in CUE are resolved using late binding: CUE re-evaluates the expressions of the field they point to within the context of the reference.

The current evaluator follows this pattern mindlessly. In practice, however, this is often not necessary. Consider this CUE:

a: exp: ... // some really expensive expression

b: a.exp

In theory, exp needs to be evaluated twice: once at a and once at b. In practice, however, as a.exp is not merged with anything else, we know up front that the value at b will be identical to the one at a. So, in practice, we can save us the trouble of recomputation and share the work.

In fact, we can generalize this principle to many more situations and apply sharing even if a reference is merged.

This optimization can result in significant performance gains for configurations that have large and frequently used disjunctions, but also for tools/flow workflows.

Note that structure sharing can reduce exponential evaluation times to linear times. Consider the following CUE encoding of the Billion Laughs Attack:

a: ["lol", "lol", "lol", "lol", "lol", "lol", "lol", "lol", "lol"]
b: [a, a, a, a, a, a, a, a, a]
c: [b, b, b, b, b, b, b, b, b]
d: [c, c, c, c, c, c, c, c, c]
e: [d, d, d, d, d, d, d, d, d]
f: [e, e, e, e, e, e, e, e, e]
g: [f, f, f, f, f, f, f, f, f]
h: [g, g, g, g, g, g, g, g, g]
i: [h, h, h, h, h, h, h, h, h]

As the linked article explains, many languages, including YAML, are susceptible to attacks of this sort: this "bomb" expands to an enormous data structure.

With structure sharing, this would evaluate to a value linear in the input. Of course, it would still be up to the user to not mindlessly traverse all fields of the resulting cue.Value, or export the concrete value as YAML or JSON.

This performance sub-issue captures details and narrative specific to duplicate work-related performance issues. We will post updates and commentary related to this topic below.

The umbrella performance issue captures higher-level performance updates.

Existing closedness-related bug reports/issues

…

The text was updated successfully, but these errors were encountered:

This prepares for several things, including the implementation of disjunctions and structure sharing. Issue #2851 Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I831d5419e6b035667aae6f254f45456b34dfd93c

We did not yet implement cyclicReferences for the new evaluator. This mechanism is an important aspect for performance. It is hard to implement for the new evaluator, at least for now, as we want to retain the flexibility of not having to evaluate a referenced node first. Maybe later that is okay. We implement an approximate alternative. This may give some spurious structural cycles. The idea is also that once we have structure sharing implemented, we could probably implement a neater alternative to using cyclicReferences. Issue #2854 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5f9b0d570cd8d122bd535e1fbc9b3ceafa848ba

This prepares for several things, including the implementation of disjunctions and structure sharing. Issue #2851 Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I831d5419e6b035667aae6f254f45456b34dfd93c

This prepares for several things, including the implementation of disjunctions and structure sharing. Issue #2851 Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I831d5419e6b035667aae6f254f45456b34dfd93c Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1190799 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

We did not yet implement cyclicReferences for the new evaluator. This mechanism is an important aspect for performance. It is hard to implement for the new evaluator, at least for now, as we want to retain the flexibility of not having to evaluate a referenced node first. Maybe later that is okay. We implement an approximate alternative. This may give some spurious structural cycles. The idea is also that once we have structure sharing implemented, we could probably implement a neater alternative to using cyclicReferences. Issue #2854 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5f9b0d570cd8d122bd535e1fbc9b3ceafa848ba

We did not yet implement cyclicReferences for the new evaluator. This mechanism is an important aspect for performance. It is hard to implement for the new evaluator, at least for now, as we want to retain the flexibility of not having to evaluate a referenced node first. Maybe later that is okay. We implement an approximate alternative. This may give some spurious structural cycles. The idea is also that once we have structure sharing implemented, we could probably implement a neater alternative to using cyclicReferences. Also, this change is blocking the implementation of structure sharing. Altogether we think it is a good tradeoff to introduce the new errors in favor of fixing the others. Issue #2854 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5f9b0d570cd8d122bd535e1fbc9b3ceafa848ba

We did not yet implement cyclicReferences for the new evaluator. This mechanism is an important aspect for performance. It is hard to implement for the new evaluator, at least for now, as we want to retain the flexibility of not having to evaluate a referenced node first. Maybe later that is okay. We implement an approximate alternative. This may give some spurious structural cycles. The idea is also that once we have structure sharing implemented, we could probably implement a neater alternative to using cyclicReferences. Also, this change is blocking the implementation of structure sharing. Altogether we think it is a good tradeoff to introduce the new errors in favor of fixing the others. Issue #2854 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: If5f9b0d570cd8d122bd535e1fbc9b3ceafa848ba Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1191589 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

Structure sharing allows the same node to be used in multiple positions if the evaluation is known to be the same. This is particularly the case if a field has a single reference to another field: a: b // reference to b can be used as is b: 2 Structure sharing has the potential to greatly reduce the time complexity of evaluation in certain conditions. See, for instance, benchmarks/share.txtar, where a simplified version of the Billion Laughs attack vector is evaluated in O(n) time, where n is the number of input nodes. In practice, there are many cases in CUE where repeated computation can be avoided, and structure sharing has been seen as one of the big wins to improve performance. Note that although structure sharing is purely meant as a performance improvement, it also alters computation order and it may cut evaluation short before tricky cycle situations are encountered. So it may fix some bugs as a side effect. Note that structure sharing may also interact with other performance improvements, resulting in compounding reductions. Note that although this change also largely makes structure sharing work with the API, it is mostly intended to make it work with the core evaluator only. We will still need to add thorough tests and evaluation of the API w.r.t. structure sharing. This is generally true for the new evaluator, so we plan to do this towards the end of its development. Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ic1c888e9567242d6779093fcb391d6e001881f60

Now we have structure sharing, we need to ensure that Vertex values are dereferenced properly. Issue #3060 Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ied35aa7f7f08205bbdb54415d78e78f1b83c8b62 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194081 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

There are now different kinds of dereferencing. We rename Indirect to DerefValue and move it close to its siblings. Goals: - keep all types of dereference together - keep naming consistent - use DerefValue, instead of Deref or DerefAll, to make the purpose of this particular dereference clear: getting the underlying value. Added notes on which dereferences might need to change in the future. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I3ccde0ac21e248f65d9a462515840c77348f658a

Recent changes were dereferencing was introduced elsewhere make this use unnecessary. Keep this in a separate CL to allow tracking possible bugs this introduces. Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Iffbbbb3bef513205a0f6a29571bc6c6a37692bb1

There are now different kinds of dereferencing. We rename Indirect to DerefValue and move it close to its siblings. Goals: - keep all types of dereference together - keep naming consistent - use DerefValue, instead of Deref or DerefAll, to make the purpose of this particular dereference clear: getting the underlying value. Added notes on which dereferences might need to change in the future. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I3ccde0ac21e248f65d9a462515840c77348f658a Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194087 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Recent changes were dereferencing was introduced elsewhere make this use unnecessary. Keep this in a separate CL to allow tracking possible bugs this introduces. Issue #2884 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Iffbbbb3bef513205a0f6a29571bc6c6a37692bb1 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1194088 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

As Eval V3 introduces more structure shraing, we have to also do more dereferencing in the API. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I9c5299f6122658f5bbd743895857ca4a2e002de5 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202229 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Matthew Sackman <matthew@cue.works>

These tests expose cases where structure sharing is currently not working, and where we would like it to work. Fixing these can be a significant performance boost, especially for chained references. Issue #2854 Issue #2850 Issue #1795 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I723b2fbd4c0e44431f1cce47023e535b1d81043a Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202208 Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

This change is needed for an upcoming change, where it would otherwise cause a crash. It addresses a few issues: In allChildConjunctsKnown: it was sometimes called with a status that is finalized. This was possible in some rare cases. It should be safe to simply return true in these cases, so that is what we do now. Separately, we changed one of the call sites in unify to no call this function if such a condition is met. Note that Rooted additionally tests whether the nonRooted flag is set. We separate out these changes so that bisection will isolate any issues caused by this. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I87df035ccdde61309884391131fa2a6de7d4887e Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202209 Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

This is needed to pass various tests. Bugs still remains, but the main point is that it unblocks a next phase in structure sharing. Issue #2854 Issue #2850 Issue #3165 Fixes #3410 Fixes #3420 Issue #3443 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibd2a41e25e07bd37899620af6bd9665435d68e8a Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202212 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

We will treat the point where cyclicity of a conjunct is considered slightly differently for ancestor cycles and indirect cycles through reoccuring references. This fixes some spurious cycles and is needed for upcoming changes. See updated comments for more detail. Issue #2850 Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I6547ff13436999fcee316971afb0830051086cfe Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202213 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

The finalized state of a node was set before processing patterns. This caused cycles in patterns to go unnoticed. Fixing this further exposed some issues with cycle detection in sharing: allowing cyclic nodes to share could make structure sharing go unnoticed. We now do not allow sharing in this case. Another issue was that clearing the Refs in a nonRooted struct could remove a necessary cycle detection. Issue #3476 Issue #2854 Issue #2850 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibfbf716b9aa2b07ac83d0125a8e5188486eda4eb Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202216 Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

This change uses depth counters to be able to find ancestor nodes that are currently being processed. The old mechanism used the evaluatingArcs status to determine this, as well as walking up the parent tree. The new mechanism replaces evaluatingArcs, but also tracks some parent nodes where the Parent field may not be set. For instance, when computing an inline struct, the parent node is not set (it is non rooted), but for the purpose of cycle detection, the computing node should be seen as a parent. We keep the use of evaluatingArcs around for now as a definsive mechanism and remove it in a later CL to allow finding possible negative consequences in a bisection. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I958905711a8bbcdb51b862c6ee60da06f1d9972c Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202217 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

With eval V3, as more structure sharing is implemented, we will need to do more dereferencing. This change prevents a bug as more sharing is supported in an upcoming CL. This also adds some testing infrastructure to select the evaluator version and to enable logging by default. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I7f15f8d1955d9ff9c0cafa1ed6e5196b44d02f1f Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202234 Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Before inline structs were always recomputed for any given arc, so it was safe to assume a rooted struct could be dropped. This does not have a big impact on performance as of this CL, but it will have a big impact in combination with upcoming changes. Now inline structs can be structure shared, it is important to know where the inline struct orginated. This has an effect on dependency analysis. It also allows us to work around some issues with internal/core/dep w.r.t. these upcoming changes. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Id795fc7d710b992782342d4db046a41f9ef703ff Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202264 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

With an upcoming change, inline structs can be shared and reappropriated as regular structs in some cases. This means that the current algorithm, which assumes that inline structs are always local to the current field, is no longer correct. We modify the algorithm to prepare for this change. One aspect of this is isLocal, which checks whether the field references resolve to within the current scope of dependency analysis (by comparing to empty). Another change is that we now need to be more precise when it comes to checking whether a Vertex is rooted or not. We use IsDetached and MayAttach instead of Rooted for V3 in some cases. Finally, we are now more aggressive with taking the top reference, instead of an interstitial reference, as the representative reference. This results in better output even for V2 Changes: issue2247.txtar: appropriate simplication import.txtar: fixes an issue in v2 let2.txtar: the v3 output seems more correct, as the original reference is more important than the interstitial one. Issue #2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I618bb38bc6cfe0200f6950a30063bc2fcfa31b34 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202268 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works>

We know from the cycle algorithm that inline and non-rooted structs/lists should get the same treatment as regular fields. This is a first step in removing their discrepancies. To avoid some test breakages, we had to move where the unification of shared structures was done. This indeed seems to be a more sensible spot. Issue #3476 Issue #2850 Issue #2854 Fixes #3509 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ic26cb31f207d7be0209d01bad5c6df3130251e2f Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202269 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

As Eval V3 introduces more structure shraing, we have to also do more dereferencing in the API. Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I9c5299f6122658f5bbd743895857ca4a2e002de5 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202229 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Matthew Sackman <matthew@cue.works>

These tests expose cases where structure sharing is currently not working, and where we would like it to work. Fixing these can be a significant performance boost, especially for chained references. Issue cue-lang#2854 Issue cue-lang#2850 Issue cue-lang#1795 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I723b2fbd4c0e44431f1cce47023e535b1d81043a Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202208 Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

This change is needed for an upcoming change, where it would otherwise cause a crash. It addresses a few issues: In allChildConjunctsKnown: it was sometimes called with a status that is finalized. This was possible in some rare cases. It should be safe to simply return true in these cases, so that is what we do now. Separately, we changed one of the call sites in unify to no call this function if such a condition is met. Note that Rooted additionally tests whether the nonRooted flag is set. We separate out these changes so that bisection will isolate any issues caused by this. Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I87df035ccdde61309884391131fa2a6de7d4887e Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202209 Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

This is needed to pass various tests. Bugs still remains, but the main point is that it unblocks a next phase in structure sharing. Issue cue-lang#2854 Issue cue-lang#2850 Issue cue-lang#3165 Fixes cue-lang#3410 Fixes cue-lang#3420 Issue cue-lang#3443 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibd2a41e25e07bd37899620af6bd9665435d68e8a Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202212 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

We will treat the point where cyclicity of a conjunct is considered slightly differently for ancestor cycles and indirect cycles through reoccuring references. This fixes some spurious cycles and is needed for upcoming changes. See updated comments for more detail. Issue cue-lang#2850 Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I6547ff13436999fcee316971afb0830051086cfe Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202213 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

The finalized state of a node was set before processing patterns. This caused cycles in patterns to go unnoticed. Fixing this further exposed some issues with cycle detection in sharing: allowing cyclic nodes to share could make structure sharing go unnoticed. We now do not allow sharing in this case. Another issue was that clearing the Refs in a nonRooted struct could remove a necessary cycle detection. Issue cue-lang#3476 Issue cue-lang#2854 Issue cue-lang#2850 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibfbf716b9aa2b07ac83d0125a8e5188486eda4eb Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202216 Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

This change uses depth counters to be able to find ancestor nodes that are currently being processed. The old mechanism used the evaluatingArcs status to determine this, as well as walking up the parent tree. The new mechanism replaces evaluatingArcs, but also tracks some parent nodes where the Parent field may not be set. For instance, when computing an inline struct, the parent node is not set (it is non rooted), but for the purpose of cycle detection, the computing node should be seen as a parent. We keep the use of evaluatingArcs around for now as a definsive mechanism and remove it in a later CL to allow finding possible negative consequences in a bisection. Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I958905711a8bbcdb51b862c6ee60da06f1d9972c Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202217 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

With eval V3, as more structure sharing is implemented, we will need to do more dereferencing. This change prevents a bug as more sharing is supported in an upcoming CL. This also adds some testing infrastructure to select the evaluator version and to enable logging by default. Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I7f15f8d1955d9ff9c0cafa1ed6e5196b44d02f1f Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202234 Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Before inline structs were always recomputed for any given arc, so it was safe to assume a rooted struct could be dropped. This does not have a big impact on performance as of this CL, but it will have a big impact in combination with upcoming changes. Now inline structs can be structure shared, it is important to know where the inline struct orginated. This has an effect on dependency analysis. It also allows us to work around some issues with internal/core/dep w.r.t. these upcoming changes. Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Id795fc7d710b992782342d4db046a41f9ef703ff Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202264 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

With an upcoming change, inline structs can be shared and reappropriated as regular structs in some cases. This means that the current algorithm, which assumes that inline structs are always local to the current field, is no longer correct. We modify the algorithm to prepare for this change. One aspect of this is isLocal, which checks whether the field references resolve to within the current scope of dependency analysis (by comparing to empty). Another change is that we now need to be more precise when it comes to checking whether a Vertex is rooted or not. We use IsDetached and MayAttach instead of Rooted for V3 in some cases. Finally, we are now more aggressive with taking the top reference, instead of an interstitial reference, as the representative reference. This results in better output even for V2 Changes: issue2247.txtar: appropriate simplication import.txtar: fixes an issue in v2 let2.txtar: the v3 output seems more correct, as the original reference is more important than the interstitial one. Issue cue-lang#2854 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I618bb38bc6cfe0200f6950a30063bc2fcfa31b34 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202268 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Matthew Sackman <matthew@cue.works>

We know from the cycle algorithm that inline and non-rooted structs/lists should get the same treatment as regular fields. This is a first step in removing their discrepancies. To avoid some test breakages, we had to move where the unification of shared structures was done. This indeed seems to be a more sensible spot. Issue cue-lang#3476 Issue cue-lang#2850 Issue cue-lang#2854 Fixes cue-lang#3509 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ic26cb31f207d7be0209d01bad5c6df3130251e2f Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1202269 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Matthew Sackman <matthew@cue.works> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>

myitcv assigned mpvl Feb 22, 2024

myitcv added this to Evaluator Roadmap Feb 22, 2024

github-project-automation bot moved this to Backlog in Evaluator Roadmap Feb 22, 2024

myitcv moved this from Backlog to In progress in Evaluator Roadmap Feb 22, 2024

myitcv added the evaluator label Feb 22, 2024

cue-lang locked as resolved and limited conversation to collaborators Feb 22, 2024

myitcv mentioned this issue Feb 22, 2024

Performance #2850

Open

myitcv changed the title ~~Placeholder 5~~ Performance: avoiding duplicating reusable work Feb 22, 2024

cue-lang unlocked this conversation Feb 22, 2024

This was referenced Oct 9, 2024

cmd/cue: serious performance regression #2243

Closed

evalv3: OOM and signal killed (64GB) #3334

Open

evaluator: general performance enhancements #804

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Performance: avoiding duplicating reusable work #2854

Performance: avoiding duplicating reusable work #2854

myitcv commented Feb 22, 2024 •

edited

Loading

Performance: avoiding duplicating reusable work #2854

Performance: avoiding duplicating reusable work #2854

Comments

myitcv commented Feb 22, 2024 • edited Loading

Existing closedness-related bug reports/issues

myitcv commented Feb 22, 2024 •

edited

Loading