hashicorp / hashicorp/terraform-plugin-framework

Three O(n²) paths in set handling make plan and refresh unusable for large sets

Open
#1,322 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.