Performance: Disjunctions #2851

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

Disjunctions are somewhat like enums and sum types in other languages. They allow you to express that a field is constrained by one or more of a number of options:

a?: string | int  // the field a can be a string or int

In many situations, elements of a disjunction (the values separated by | on the right hand side) are mutually exclusive: it is not possible, for example, for a concrete value to be both a string and int at the same time.

Values being mutually exclusive can even extend to container types:

x?: { type: "a" } | { type: "b" }

The type field is referred to as a discriminator field.

Disjunctions can get expensive very fast because the number of elements introduces a complexity multiplier. In the worst case in some situations, we end up effectively needing to compute the cross product between two such disjunctions in the course of an evaluation.

The current evaluator does not exploit the benefits of mutually exclusive fields. On top of that, the current evaluator has a bug that prevents early elimination of duplicates, which, in turn, can lead to significantly increased running times! The new evaluator is designed to allow eliminating duplicates as early as possible, allowing for an optimized run time even if disjuncts are not mutually exclusive.

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

The umbrella performance issue captures higher-level performance updates.

Existing disjunction-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

This is an incomplete implementation. The following mechanisms are still TODO: - cross product of disjunctions - inheriting tasks from "forked" nodeContexts (this is especially relavant for list values). - efficient dedupping of incomplete disjuncts - efficient memory management - "quick check" fast paths The main algorithm is implemented in disjunct2.go and overlay.go. See a description of the algorith in disjuncts2.go. Tests are enabled in a follow-up CL. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibaa052678572302abd380530fc891fc9495c75cc

As this is still a partial implementation, many of the tests are manually disabled in the todo list. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I7e8357d13a71bed45478b45c02f91301dd638530

This disjunction performance issue should be fixed with the new evaluator. Issue #2850 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I505f9fe68604e55bf2117295c4935add3a5249d0

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 is an incomplete implementation. The following mechanisms are still TODO: - cross product of disjunctions - inheriting tasks from "forked" nodeContexts (this is especially relavant for list values). - efficient dedupping of incomplete disjuncts - efficient memory management - "quick check" fast paths The main algorithm is implemented in disjunct2.go and overlay.go. See a description of the algorith in disjuncts2.go. Tests are enabled in a follow-up CL. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibaa052678572302abd380530fc891fc9495c75cc

As this is still a partial implementation, many of the tests are manually disabled in the todo list. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I7e8357d13a71bed45478b45c02f91301dd638530

Sometimes evaluating disjunctions is triggered before all conjuncts have been added. If then another disjunction was added, these results were not properly merged with previously computed disjunctions. This change fixes that. Issue #2851 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I248b9ecc4694b2cb9a1e478343d9a8d233e14929

This disjunction performance issue should be fixed with the new evaluator. Issue #2850 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I505f9fe68604e55bf2117295c4935add3a5249d0 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1177865 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

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 is an incomplete implementation. The following mechanisms are still TODO: - cross product of disjunctions - inheriting tasks from "forked" nodeContexts (this is especially relavant for list values). - efficient dedupping of incomplete disjuncts - efficient memory management - "quick check" fast paths The main algorithm is implemented in disjunct2.go and overlay.go. See a description of the algorith in disjuncts2.go. Tests are enabled in a follow-up CL. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibaa052678572302abd380530fc891fc9495c75cc

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>

This is an incomplete implementation. The following mechanisms are still TODO: - cross product of disjunctions - inheriting tasks from "forked" nodeContexts (this is especially relavant for list values). - efficient dedupping of incomplete disjuncts - efficient memory management - "quick check" fast paths The main algorithm is implemented in disjunct2.go and overlay.go. See a description of the algorith in disjuncts2.go. Tests are enabled in a follow-up CL. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibaa052678572302abd380530fc891fc9495c75cc

As this is still a partial implementation, many of the tests are manually disabled in the todo list. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I7e8357d13a71bed45478b45c02f91301dd638530

Sometimes evaluating disjunctions is triggered before all conjuncts have been added. If then another disjunction was added, these results were not properly merged with previously computed disjunctions. This change fixes that. Issue #2851 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I248b9ecc4694b2cb9a1e478343d9a8d233e14929

This is an incomplete implementation. The following mechanisms are still TODO: - cross product of disjunctions - inheriting tasks from "forked" nodeContexts (this is especially relavant for list values). - efficient dedupping of incomplete disjuncts - efficient memory management - "quick check" fast paths The main algorithm is implemented in disjunct2.go and overlay.go. See a description of the algorith in disjuncts2.go. Tests are enabled in a follow-up CL. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: Ibaa052678572302abd380530fc891fc9495c75cc Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1190800 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

As this is still a partial implementation, many of the tests are manually disabled in the todo list. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I7e8357d13a71bed45478b45c02f91301dd638530 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1190801 TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

Sometimes evaluating disjunctions is triggered before all conjuncts have been added. If then another disjunction was added, these results were not properly merged with previously computed disjunctions. This change fixes that. Issue #2851 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I248b9ecc4694b2cb9a1e478343d9a8d233e14929

In some rare cases a closeContext will not have a parent. This is currently only the case if Sharing is false. It is safe to return the input pointers in this case. In the worst case, it will just limits duplicate elimination, which will be corrected when a node is finalized. Note that this CL has no test. It will be hard, and perhaps futile, to devise a test that exposes this bug within the current txtar file setup, because even small changes in the evaluator may cause this issue to no longer be exposed. The only way to really expose it is by means of a unit test. Added a TODO in the function. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I20bdd0f6488624d1ad384338a9becbf43ab18515

In some rare cases a closeContext will not have a parent. This is currently only the case if Sharing is false. It is safe to return the input pointers in this case. In the worst case, it will just limits duplicate elimination, which will be corrected when a node is finalized. Note that this CL has no test. It will be hard, and perhaps futile, to devise a test that exposes this bug within the current txtar file setup, because even small changes in the evaluator may cause this issue to no longer be exposed. The only way to really expose it is by means of a unit test. Added a TODO in the function. Issue #2884 Issue #2851 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I20bdd0f6488624d1ad384338a9becbf43ab18515 Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1193672 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com>

Vertex.BaseValue may point to another Vertex. There are now three kinds of vertices that this value may point to: - computed, external results, like from builtins. - disjuncts resulting from resolved disjunctions - structure shared nodes The old evaluator only had the first. When access the actual value of a Vertex, one should dereference the pointers. However, there is lots of interesting meta information that one may want to access. The new evaluator should therefore be more careful as to when something is dereferenced. In this CL, we introduce a means to identify whether a Vertex was the result of a disjunction. We adjust various Indirect calls by removing them or replacing them with more fine-grained versions. This should be a no-op changes. Various points where indirect have been tightened to dereferences only the kinds of vertices that should be dereferenced. The idea is to do a bunch of such changes in separate CLs to allow bisecting to specific changes if there are any issues. We rename the new "Indirect*" functions to "Deref*", which is a more accurate term. This also allows us to visually inspect if we have considered all call sites. We will rename and inspect Indirect in a separate CL. Issue #2854 Issue #2851 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I659d075f61aa7f96db99a504c31bd658c54ee58b

Vertex.BaseValue may point to another Vertex. There are now three kinds of vertices that this value may point to: - computed, external results, like from builtins. - disjuncts resulting from resolved disjunctions - structure shared nodes The old evaluator only had the first. When accessing the actual value of a Vertex, one should dereference the pointers. However, there is lots of interesting meta information that one may want to access, i.e. the original path and the original full disjunction expression. The new evaluator should therefore be more careful as to when something is dereferenced. In this CL, we introduce a means to identify whether a Vertex was the result of a disjunction. We adjust various Indirect calls by removing them or replacing them with more fine-grained versions. This should be a no-op change. Various points where indirect have been tightened to dereference only the kinds of vertices that should be dereferenced. The idea is to do a bunch of such changes in separate CLs to allow bisecting to specific changes if there are any issues. We rename the new "Indirect*" functions to "Deref*", which is a more accurate term. This also allows us to visually inspect if we have considered all call sites. We will rename and inspect Indirect in a separate CL. Issue #2854 Issue #2851 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I659d075f61aa7f96db99a504c31bd658c54ee58b

Vertex.BaseValue may point to another Vertex. There are now three kinds of vertices that this value may point to: - computed, external results, like from builtins. - disjuncts resulting from resolved disjunctions - structure shared nodes The old evaluator only had the first. When accessing the actual value of a Vertex, one should dereference the pointers. However, there is lots of interesting meta information that one may want to access, i.e. the original path and the original full disjunction expression. The new evaluator should therefore be more careful as to when something is dereferenced. In this CL, we introduce a means to identify whether a Vertex was the result of a disjunction. We adjust various Indirect calls by removing them or replacing them with more fine-grained versions. This should be a no-op change. Various points where indirect have been tightened to dereference only the kinds of vertices that should be dereferenced. The idea is to do a bunch of such changes in separate CLs to allow bisecting to specific changes if there are any issues. We rename the new "Indirect*" functions to "Deref*", which is a more accurate term. This also allows us to visually inspect if we have considered all call sites. We will rename and inspect Indirect in a separate CL. Issue #2854 Issue #2851 Issue #2884 Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com> Change-Id: I659d075f61aa7f96db99a504c31bd658c54ee58b Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/1193844 Unity-Result: CUE porcuepine <cue.porcuepine@gmail.com> TryBot-Result: CUEcueckoo <cueckoo@cuelang.org> Reviewed-by: Daniel Martí <mvdan@mvdan.cc>

myitcv assigned mpvl 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 2~~ Performance: Disjunctions Feb 22, 2024

cue-lang unlocked this conversation Feb 22, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Performance: Disjunctions #2851

Performance: Disjunctions #2851

myitcv commented Feb 22, 2024 •

edited

Loading

Performance: Disjunctions #2851

Performance: Disjunctions #2851

Comments

myitcv commented Feb 22, 2024 • edited Loading

Existing disjunction-related bug reports/issues

myitcv commented Feb 22, 2024 •

edited

Loading