`ValuesSDKEquivalent` has very poor performance comparing large numbers of deeply nested objects with O(n^2) complexity

[drewtul]

SDK version

HEAD
...

Relevant provider source code

		{
			cty.SetVal([]cty.Value{
				cty.ObjectVal(map[string]cty.Value{
					"a": cty.StringVal("1"),
					"b": cty.StringVal(""),
				}),
				cty.ObjectVal(map[string]cty.Value{
					"a": cty.StringVal("1"),
					"b": cty.NullVal(cty.String),
				}),
				cty.ObjectVal(map[string]cty.Value{
					"a": cty.NullVal(cty.String),
					"b": cty.StringVal(""),
				}),
			}),
			cty.SetVal([]cty.Value{
				cty.ObjectVal(map[string]cty.Value{
					"a": cty.StringVal("1"),
					"b": cty.StringVal(""),
				}),
				cty.ObjectVal(map[string]cty.Value{
					"a": cty.StringVal(""),
					"b": cty.NullVal(cty.String),
				}),
				cty.ObjectVal(map[string]cty.Value{
					"a": cty.NullVal(cty.String),
					"b": cty.NullVal(cty.String),
				}),
			}),
			true,
		},
...

Terraform Configuration Files

resource "aws_wafv2_web_acl" "example" {
  name        = "example"
  description = "Example WAF ACL"
  scope       = "CLOUDFRONT"

  lifecycle {
    ignore_changes = [
      rule,
      custom_response_body,
      token_domains
    ]
  }

  default_action {
    allow {}
  }

  visibility_config {
    cloudwatch_metrics_enabled = false
    metric_name                = "All"
    sampled_requests_enabled   = false
  }
}

Expected Behavior

Users attempting to apply a change to a aws_wafv2_web_acl with a very large number (>500) rules with ignore_changes on the rules should be able to apply quickly.

I'm looking to optimise ValuesSDKEquivalent trying to understand if the above test case should pass or not, it currently passes, but logically the sets are not equivalent.

Actual Behavior

The apply may take a very long time or never succeed or take a very long time, most of it spent in ValuesSDKEquivalent comparing all the rules.

Steps to Reproduce

1. terraform init
2. terraform apply
3. Modify the resource outside of terraform using the AWS CLI or SDK to add a large number of rules (>500)
4. terraform plan - Notice length of plan time for no change
5. Modify description of aws_wafv2_web_acl
6. terraform plan - Notice length of plan time for single attribute change
7. terraform apply - Notice length of time before apply ever calls the AWS API to update the resource.

During both plan and apply a large amount of CPU and memory is consumed as well as taking an excessive amount of time to complete timing out in multi-hour CICD runs.

I would propose changing the loop in valuesSDKEquivalentSets to:

	for ai, av := range as {
		for bi, bv := range bs {
			if beqs[bi] {
				// continue on already matched items in `bs`
				// this allows this `av` to match against later values in `bs` where an earlier `as` valus matched this `bv`
				// this is a case where both sets contain two values each that are ValuesSDKEquivalent to each other
				continue
			}
			if ValuesSDKEquivalent(av, bv) {
				aeqs[ai] = true
				beqs[bi] = true
				// break on first match in `bs` against `av`
				// this leaves any further matches in `bs` for later values in `as`
				break
			}
		}

This changes it such that

1. items in as are compared to bs till finding their first match.
2. bs that are already matched are skipped for comparison allowing later as of 'equivalent' value are matched against later values in bs

This reduces the number of comparisons required significantly, but fails the above test case that is not currently in the unit tests.

References

[austinvalle]

Hey there @drewtul 👋🏻 , thanks for opening the issue!

I think we'd need to do a little digging to ensure the change proposed doesn't make any change in behavior (since essentially any change in behavior to this logic would be considered a bug, even if the new behavior is more correct 😔 ), but to answer your direct question about the failing test, I think the actual setup looks incorrect (unless I'm misunderstanding what you're looking to test)

{
    // setA
    cty.SetVal([]cty.Value{
        cty.ObjectVal(map[string]cty.Value{      // <----------- This exists in setB exactly
            "a": cty.StringVal("1"),
            "b": cty.StringVal(""),
        }),
        cty.ObjectVal(map[string]cty.Value{      // <----------- This does not exist in setB
            "a": cty.StringVal("1"), 
            "b": cty.NullVal(cty.String),
        }),
        cty.ObjectVal(map[string]cty.Value{      // <----------- This exists in setB (empty strings are equal to nil)
            "a": cty.NullVal(cty.String),
            "b": cty.StringVal(""),
        }),
    }),
    // setB
    cty.SetVal([]cty.Value{
        cty.ObjectVal(map[string]cty.Value{
            "a": cty.StringVal("1"),
            "b": cty.StringVal(""),
        }),
        cty.ObjectVal(map[string]cty.Value{
            "a": cty.StringVal(""),      // <----------- Perhaps this was meant to be "1"?
            "b": cty.NullVal(cty.String),
        }),
        cty.ObjectVal(map[string]cty.Value{
            "a": cty.NullVal(cty.String),
            "b": cty.NullVal(cty.String),
        }),
    }),
    true,
},

---

The ValuesSDKEquivalent is only called once, during PlanResourceChange, so the change may not be the immediate performance benefit that we'd like to see (I don't have any benchmarks off-hand though, so not suggesting it wouldn't help at all, if you have some would be great to see). There is equivalent logic in Terraform core that has a similar problem, which could provide even more benefit if fixed: hashicorp/terraform#32940

[drewtul]

Hi @austinvalle thanks for the reply! Essentially I was looking to optimise the loop to reduce comparisons needed, but I was trying to construct a test case that passes with the exist implementation, but does not pass with the proposed optimised implementation.

Essentially There are two sets A and B containing:

A: 1, 2, 3
B: 1, 4, 5

I needs the values to be unequal as far as cty.SetVal is concerned, but equal when using the SDKEquals 'fuzzy' check.

So there are 5 distinct values in the two sets and the comparisons work out as follows

1 ~= 2
3 ~= 4
3 ~= 5
4 ~= 5

So when this code runs it considers these sets equal. Though when you look at it intuitively it feels wrong as one the sets both contain 2 values that match one value in the other set, so almost as if you're saying [1,1,2] == [1,2,2] I was trying to understand if this is an expected match.

[drewtul]

{
    // setA
    cty.SetVal([]cty.Value{
        cty.ObjectVal(map[string]cty.Value{      // <----------- This matches first entry in setB
            "a": cty.StringVal("1"),
            "b": cty.StringVal(""),
        }),
        cty.ObjectVal(map[string]cty.Value{      // <----------- This matches first entry in setB: null ~= empty string
            "a": cty.StringVal("1"), 
            "b": cty.NullVal(cty.String),
        }),
        cty.ObjectVal(map[string]cty.Value{      // <----------- This matches second and third entry in setB: null ~= empty string
            "a": cty.NullVal(cty.String),
            "b": cty.StringVal(""),
        }),
    }),
    // setB
    cty.SetVal([]cty.Value{
        cty.ObjectVal(map[string]cty.Value{
            "a": cty.StringVal("1"),
            "b": cty.StringVal(""),
        }),
        cty.ObjectVal(map[string]cty.Value{
            "a": cty.StringVal(""),      
            "b": cty.NullVal(cty.String),
        }),
        cty.ObjectVal(map[string]cty.Value{
            "a": cty.NullVal(cty.String),
            "b": cty.NullVal(cty.String),
        }),
    }),
    true,
},

With the above matching, since every entry in A is compared to B we have all values in both A and B having a match from their opposite set, so the sets are considered equal.

[jbardin]

Hi @drewtul,

The issue here is that we must iterate through all elements, because the plan may contain partially unknown values to be correlated. The following test case adapted from core would fail:

			cty.ObjectVal(map[string]cty.Value{
				"block": cty.SetVal([]cty.Value{
					cty.ObjectVal(map[string]cty.Value{
						"a": cty.UnknownVal(cty.String),
						"b": cty.UnknownVal(cty.String),
					}),
					cty.ObjectVal(map[string]cty.Value{
						"a": cty.UnknownVal(cty.String),
						"b": cty.UnknownVal(cty.String),
					}),
				}),
			}),
			cty.ObjectVal(map[string]cty.Value{
				"block": cty.SetVal([]cty.Value{
					cty.ObjectVal(map[string]cty.Value{
						"a": cty.StringVal("1"),
						"b": cty.NullVal(cty.String),
					}),
					
				}),
			}),

I just pushed a small fix to core hashicorp/terraform#37280 that I had been sitting on. It can't significantly reduce the comparisons, but it does eliminate some of them. That same change could be made here as well since it can't change the result of the function.

[drewtul]

@jbardin Thanks for looking at this as well, I did mention the first check in the function is a length comparison between as and bs here, so we would return false for your test case today as they're different lengths.

The test case in my comment passes the length check, but its imbalanced featuring two as that match one bs and vice versa, but would not pass with my proposed optimisation.

I think in my case I've got two 'identical' sets without fuzzy duplicates, so if I imagined this as two sets of digits 1-5, then the following comparisons would occur

1,1 = true, true
1,2 = true, false
1,3 = true, false
1,4 = true, false
1,5 = true, false

2,1 = false, true
2,2 = true, true
2,3 = true, false
2,4 = true, false
2,5 = true, false

3,1 = false, true
3,2 = false, true
3,3 = true, true
3,4 = true, false
3,5 = true, false

4,1 = false, true
4,2 = false, true
4,3 = false, true
4,4 = true, true
4,5 = true, false

5,1 = false, true
5,2 = false, true
5,3 = false, true
5,4 = false, true
5,5 = true, true

So at no point till you compare the value to it's corresponding value has itself been matched, so I don't think we'd save any comparisons for sets without duplicates.

If there are duplicates then comparisons will be saved as the second a value will only be matched against the first b value then it'll skip any subsequent b values that were already matched by a prior a value, I don't know how common this is in reality.

Where mine would've just run the following comparisons:

1,1 = true, true
break

skip 1
2,2 = true, true
break

skip 1, 2
3,3 = true, true
break

skip 1, 2, 3
4,4 = true, true
break

skip 1, 2, 3, 4
5,5 = true, true

As it would skip any previously matched bs and break on the first match against as

I know this looks kind of ugly, using my original optimisation but with backup passes for items that didn't match:

func valuesSDKEquivalentSets(a, b cty.Value) bool {
	if aLen, bLen := a.LengthInt(), b.LengthInt(); aLen != bLen {
		return false
	}

	// Our methodology here is a little tricky, to deal with the fact that
	// it's impossible to directly correlate two non-equal set elements because
	// they don't have identities separate from their values.
	// The approach is to count the number of equivalent elements each element
	// of a has in b and vice-versa, and then return true only if each element
	// in both sets has at least one equivalent.
	as := a.AsValueSlice()
	bs := b.AsValueSlice()
	aeqs := make([]bool, len(as))
	beqs := make([]bool, len(bs))
	for ai, av := range as {
		for bi, bv := range bs {
			if beqs[bi] {
				// continue on already matched items in `bs`.
				// this allows this `av` to match against later values in `bs` where an earlier `as` valus matched this `bv`.
				// this is a case where both sets contain two values each that are ValuesSDKEquivalent to each other
				continue
			}
			if ValuesSDKEquivalent(av, bv) {
				aeqs[ai] = true
				beqs[bi] = true
				// break on first match in `bs` against `av`
				// this leaves any further matches in `bs` for later values in `as`
				break
			}
		}
	}

	for aeqi, eq := range aeqs {
		if !eq {
			// If we didn't find a match due to imbalanced sets run one more pass against
			// every `bs` for this `av`
			match := false
			for _, bv := range bs {
				if ValuesSDKEquivalent(as[aeqi], bv) {
					match = true
					break
				}
			}
			if !match {
				return false
			}
		}
	}
	for beqi, eq := range beqs {
		if !eq {
			// If we didn't find a match due to imbalanced sets run one more pass against
			// every `as` for this `bv`
			match := false
			for _, av := range as {
				if ValuesSDKEquivalent(bs[beqi], av) {
					match = true
					break
				}
			}
			if !match {
				return false
			}

		}
	}
	return true
}

[jbardin]

I think the point is that different lengths are also valid, because multiple unknown values can end up being coalesced into fewer values once they are known. The example I posted is a valid situation, and must pass as equivalent for planning to work correctly.

It also seems the latest version would end up calling ValuesSDKEquivalent again for any earlier skipped calls and end up with the same number of calls in aggregate once you take unknowns into account.

[drewtul]

With the existing code as in HEAD your example fails:

=== RUN   TestValuesSDKEquivalent/cty.ObjectVal(map[string]cty.Value{"block":cty.SetVal([]cty.Value{cty.ObjectVal(map[string]cty.Value{"a":cty.StringVal("1"),_"b":cty.NullVal(cty.String)})})})_≈_cty.ObjectVal(map[string]cty.Value{"block":cty.SetVal([]cty.Value{cty.ObjectVal(map[string]cty.Value{"a":cty.UnknownVal(cty.String),_"b":cty.UnknownVal(cty.String)}),_cty.ObjectVal(map[string]cty.Value{"a":cty.UnknownVal(cty.String),_"b":cty.UnknownVal(cty.String)})})})
    values_equiv_test.go:500: wrong result
        for: cty.ObjectVal(map[string]cty.Value{"block":cty.SetVal([]cty.Value{cty.ObjectVal(map[string]cty.Value{"a":cty.StringVal("1"), "b":cty.NullVal(cty.String)})})}) ≈ cty.ObjectVal(map[string]cty.Value{"block":cty.SetVal([]cty.Value{cty.ObjectVal(map[string]cty.Value{"a":cty.UnknownVal(cty.String), "b":cty.UnknownVal(cty.String)}), cty.ObjectVal(map[string]cty.Value{"a":cty.UnknownVal(cty.String), "b":cty.UnknownVal(cty.String)})})})
        got false, but want true

I'm not sure if that's meant to fail here or not, but there appears to be explicit checks for known and unknown values not being equivalent in the SDK version?

	if !a.IsKnown() || !b.IsKnown() {
		// Two unknown values are equivalent regardless of type. A known is
		// never equivalent to an unknown.
		return a.IsKnown() == b.IsKnown()
	}

[drewtul]

I do hear what you're saying, but when I look at the first lines for comparing sets, it's a length check:

func valuesSDKEquivalentSets(a, b cty.Value) bool {
	if aLen, bLen := a.LengthInt(), b.LengthInt(); aLen != bLen {
		return false
	}
...
}

Looking at the core version of the function here: https://github.com/hashicorp/terraform/blob/7b3d9bf1ba4ccc178277a848b17c7d95ffe0e6e8/internal/plans/objchange/compatible.go#L353

I see the length check doesn't exist. So feels like these are slightly different functions with slightly different goals.

[jbardin]

Thanks @drewtul, I see now what you're getting at. You are correct that the goals are slightly different here. While ValuesSDKEquivalent originated form the same code as the core function, that shim is not intended to be useful outside of fixing up inconsistencies in the legacy SDK. Looking more closely at the call site, it is used only to hide perpetual diffs caused by the SDK, so the risk here is that returning false more frequently might cause some provider to not be able to converge on a stable config and always present changes in a Terraform plan.

The core change I made though is really just a remaining edge case, and doesn't represent any real improvement in complexity, which is why I never got around to committing it until now, so I wouldn't expect it to really help with this performance problem.

The IsKnown checks you are looking at are not recursive, you can have known values which contain unknown attributes within them. Digging deeper though, I don't think "known-ness" matters here so much, because it's trying to avoid diffs in the first place and unknown would be an intentional diff (if I remember correctly where the unknown conversions happen), so my comparisons to the core problem were probably misplaced.

What this really comes down to though is that the combined behavior of all these shims is very fragile, and were intended to be frozen for compatibility with legacy providers until they moved off the legacy SDK, bugs and all. Even fixing a bug here could actually result in regressions elsewhere (and they have, when others did attempt to continue work on these parts of the SDK) because those "bugs" all combine to define the behavior of the legacy code.

So a performance improvement here for one resource has to be weighed against possible regressions in any other resource. The interactions between every step of the shimmed provider calls are unfortunately highly coupled and very subtle in order to make the old SDK work at all with modern Terraform, so this could be a tough call to make. This code is technically frozen in time, but pragmatically it may be provable that the change won't make any functional changes, although I would not count on the existing test coverage or even a single provider's usage to verify that it is possible.

[drewtul]

The last version I posted will compare every a to every b if it has to, but tries to avoid it for what is hopefully the common path.

I kinda concluded the best path forward was to migrate the resource to framework and away from SDK as that will remove this issue completely, there are obviously other benefits there too. If the resource was a simple one I probably would've taken that path already, but the WAF rule is a recursive schema of rules making it more complicated.

[jbardin]

Yeah, that resource has caused a number of problems with its, shall we say, "exceptional" schema ;)
Also even if this is improved in the SDK, core still performs the same number of comparisons to verify the plan with even more complex checks, so any improvement in the SDK can only apply to <%50 of the time spent comparing set objects.