terraform apply of large TypeSet is slow, assertSetValuesCompatible is too complex

[freedge]

Terraform Version

Terraform v1.5.0-dev
on linux_amd64

Terraform Configuration Files

per https://github.com/PaloAltoNetworks/terraform-provider-panos/blob/b4ad451eb47b2c7e463d94b13fd7e2a5a62db158/docs/resources/address_objects.md

# Make address objects like "test1_1", "test1_2", ...
resource "panos_address_objects" "example" {
    dynamic "object" {
        for_each = setproduct(range(1, 6), range(1, 11))
        content {
            name = "test${object.value[0]}_${object.value[1]}"
            type = "ip-netmask"
            value = "10.${object.value[0]}.${object.value[1]}.0/24"
        }
    }

    lifecycle {
        create_before_destroy = true
    }
}

Debug Output

...
2023-03-29T10:59:27.846+0200 [TRACE] checkPlannedChange: Verifying that actual change (action Update) matches planned change (action Update)
...

Expected Behavior

terraform apply should be reasonably fast when applying object with large schema.TypeSet (8k objects)

Actual Behavior

terraform apply is terribly slow

Steps to Reproduce

unfortunately https://github.com/hashicorp/terraform-provider-null does not use schema.TypeSet so I don't know how to provide a reproducer

Additional Context

terraform/internal/plans/objchange/compatible.go

Lines 347 to 349 in d9dfd45

	for ai, av := range as {
	for bi, bv := range bs {
	if f(av, bv) {

complexity is N^2

References

• usage of distinct hurts performance #32937 (comment)

[kmoe]

Thanks for the issue. Do you have an idea as to how that code could be improved?

[freedge]

hi @kmoe ! I am not familiar with this code at all. Here this is an equality function used to compare objects, if we could have a hashing function, or a sorting function, that could work between objects, the algorithm could be improved, but I don't know how complex this would be.

Based on the comments:

// As with assertValueCompatible, we assume that the target audience of error
// messages here is a provider developer

and

// We can't really do anything useful for sets here because changing
// an unknown element to known changes the identity of the element, and
// so we can't correlate them properly.

I infer this check is not really important, so we could either remove it entirely, or limit it to the first elements of the sets (eg: only iterate over the 10 first elements in as, and see they correlate with elements in the whole bs, and report any errors from these 10 ones).

In local I commented all calls to assertSetValuesCompatible and it works better but maybe there are some cases it would still be useful.

[jbardin]

Yes, unfortunately this is inherently an n^2 operation because in order to validate possible all changes in a set, each value might need to be compared with nearly every other value. I can see a little optimization to be had by not comparing values which have already been compared, which could be significant in some cases depending on how deep the values are structured (probably bringing the average case closer to O(n log n)).

The only real way though to not spend so much time validating these values is to not do it at all. That is a hard call however, because incorrect values here don't affect the resources causing the incorrect values, rather they cascade downstream to other resources which fail in confusing ways when their inputs change unexpectedly. Limiting the validation is something we have to look into more carefully.