hashicorp / hashicorp/terraform-plugin-framework
Three O(n²) paths in set handling make plan and refresh unusable for large sets
- Dominant language
- Go
- Stars
- 384
- Forks
- 107
- Avg merge
- 3m
- Merged PRs (30d)
- 1
Description
### Module version
`v1.19.0` (also reproduces on `main` at 92c24dfd)
### Summary
Three separate paths in set handling are O(n²) in the number of set elements.
Together they make `plan` and `refresh` unusable for resources with large `SetNestedAttribute` values, independently of the semantic-equality walk already reported in #1314.
All three are reproducible with benchmarks in this repository.
**1. `basetypes.SetType.Validate` — duplicate detection**
```go
// Attempting to use map[tftypes.Value]struct{} for duplicate detection yields:
// panic: runtime error: hash of unhashable type tftypes.primitive
// Instead, use for loops.
for indexOuter, elemOuter := range elems {
...
for indexInner := indexOuter + 1; indexInner < len(elems); indexInner++ {
if !elemInner.Equal(elemOuter) {
```
Every pair of elements is compared. Each comparison is a `tftypes.Value.Equal` → `deepEqual`, which runs two full `Walk`s plus a `walkAttributePath` traversal of the other value per visited path, allocating an `AttributePath` per node — so the constant per pair is large, not just the pair count. `Validate` runs over the whole set on every `State.Set`, via `internal/reflect`.
**2. `basetypes.SetValue.Equal` → `contains`**
`Equal` calls `contains(elem)` for each element and `contains` scans the whole other set. Two problems, not one: `contains` iterates `s.Elements()`, which defensively copies the entire element slice on *every* call, so comparing two n-element sets also allocates n slices of length n. At n=1,000 that is 16 MB of garbage for a single `Equal`.
**3. `fwserver` — whole-value `Equal` after semantic equality**
`ReadResource`, `CreateResource`, `UpdateResource` and `ReadDataSource` all ask "did semantic equality change anything?" by deep-comparing the entire value:
```go
if !semanticEqualityResp.NewData.TerraformValue.Equal(resp.NewState.Raw) {
```
which walks every set in the state through the same `deepEqual`. In a CPU profile of a real provider, **one call to this line was 115s of a 181s profile (63.6%)**, with `mallocgc` at 34% and `gcDrain` at 31% underneath it.
`SchemaSemanticEquality` already knows whether it replaced a value, so the comparison is redundant.
### Impact
Measured with the repository's own benchmarks in `types/basetypes`, `-benchtime 1x`:
| benchmark | current | with fix | speedup |
|---|---|---|---|
| `SetTypeValidate1000` | 70.0 ms, 24 MB, 1,003,917 allocs | 1.13 ms, 0.37 MB, 9,916 allocs | 62x |
| `SetTypeValidate10000` | 7.82 s, 2.40 GB, 100,039,947 allocs | 8.05 ms, 3.6 MB, 99,947 allocs | **971x** |
| `SetValueEqual1000` | 10.1 ms, 16.4 MB | 0.67 ms, 0.20 MB | 15x |
| `SetValueEqual10000` | 1.89 s, 1.64 GB | 7.85 ms, 1.9 MB | **241x** |
Note that the existing `BenchmarkSetTypeValidate*` benchmarks do not currently measure this, because the helper ranges over an empty slice:
```go
elements := make([]tftypes.Value, 0, elementCount)
for idx := range elements { // len(elements) == 0
elements[idx] = tftypes.NewValue(tftypes.String, strconv.Itoa(idx))
}
```
so every one of them validates an empty set. The numbers above are from the same benchmarks with that loop populating the slice.
In a real provider — a Metabase permission graph, ~3,700 set elements of 7-attribute objects, two of them nested objects — this showed up as a `terraform plan` that never completed: killed at a 1 hour CI timeout, with the plugin process pinned at ~110% CPU and the Terraform CLI process at 0:00 of CPU time. With all three fixed, the same plan takes 32s.
### Suggested direction
For 1 and 2: group elements by a hashable key derived from `Value.String()` and run the expensive `Equal` only within a group. `Equal` implies an identical `String()`, so no duplicate or match can be missed, and the comparison count collapses to the number of genuinely colliding elements. `tftypes.Value` cannot be a map key — the panic noted in the comment above — but its string form can, which is what makes this work without introducing a hashing scheme.
**One caveat worth stating explicitly**, because it is easy to miss: this is sound for primitives, objects and maps, but *not* for sets. Set equality ignores element order while `SetValue.String()` renders elements in slice order, so two
equal sets can render differently. A patch that keys blindly on `String()` passes almost the whole suite and fails exactly one test —
`TestValueSemanticEqualitySet/SetValue-SetValue-StringValuableWithSemanticEquals-true-diff-order`, which nests a set inside a set. The fix needs a static check on the element type tree, falling back to pairwise comparison when a set (or a dynamic type, whose concrete type is only known at runtime) appears anywhere inside it.
For 3: have `SchemaSemanticEqualityResponse` report whether it modified anything and check that instead.
I have both fixes ready with tests and benchmarks; the full suite passes unchanged. PRs to follow.
Refs #1314, #775, #1064.
Contributor guide
Research direction
Start with basetypes.SetType.Validate, basetypes.SetValue.Equal and contains, then inspect the fwserver ReadResource, CreateResource, UpdateResource and ReadDataSource equality checks. Run SetTypeValidate1000, SetTypeValidate10000, SetValueEqual1000 and SetValueEqual10000, and review TestValueSemanticEqualitySet/SetValue-SetValue-StringValuableWithSemanticEquals-true-diff-order. Done means the reported large-set benchmarks improve, the nested-set case remains correct, and the full suite passes.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, terraform
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100