hashicorp / hashicorp/terraform-plugin-framework

ValueSemanticEqualitySetElements walks all N² element pairs even when no element type implements semantic equality

Open
#1,314 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
384
Forks
107
Avg merge
3m
Merged PRs (30d)
1

Description

### Summary
On every `ReadResource`, the framework reconciles semantic equality. For a `SetNestedAttribute` with N elements, `internal/fwschemadata/value_semantic_equality_set.go` → `ValueSemanticEqualitySetElements` runs a nested loop: for each of N proposed elements it scans all N prior elements, recursively calling `ValueSemanticEquality` on each pair. That is O(n²). It runs even when no element type implements any `*ValuableWithSemanticEquals` interface, in which case every recursive call is a guaranteed no-op and the whole O(n²) pass is dead work.

The List and Map element functions (`value_semantic_equality_list.go`, `value_semantic_equality_map.go`) are O(n) (index-matched and key-matched respectively), so they do not blow up quadratically, but they still make N no-op recursive calls in the no-semantic-equality case.

### Impact
A Cloudflare `cloudflare_list` with ~3,251 inline items (a `SetNestedAttribute`; no field implements semantic equality) takes 10m11s to create and minutes per no-change refresh, with the provider process above 100% CPU. Benchmarking the set reconciliation alone, with no semantic-equality element types:

| N | ns/op | allocs/op |
|---|---|---|
| 100 | 82.6 ms | 896,090 |
| 1,000 | 8.96 s | 93,107,331 |
| 3,251 | 98.9 s | 990,666,514 |

(~46 GB allocated for a single 3,251-element pass.) The before column scales quadratically (10x the elements gives ~108x the time).

### Origin
The nested loop was introduced deliberately in #1064 (v1.14.0) to fix set order-sensitivity (#1061). Before v1.14.0 the walk was a single O(n) index-matched loop. The correctness fix is sound; the cost is that it now compares all pairs unconditionally.

### Relation to #775
#775 tracks the broad "SetNested is ~50-70x slower than ListNested" symptom, but its diagnosis attributes the cost to terraform-plugin-go type conversions, hclog logging, and path-slice allocations, not to the semantic-equality walk. This issue isolates the semantic-equality pass, which is the dominant cost when elements carry no custom equality.

### Suggested direction
Before the element walk, statically check once whether the collection's element type tree can contain any `*ValuableWithSemanticEquals` implementer; if not, skip the walk entirely. Must stay conservative for dynamic types (concrete type only known at runtime) and must not touch the collection-level semantic-equality path. A proof of concept confirms this is behavior-preserving and reduces the no-semantic-equality case from O(n²) to O(1). PR to follow.

Refs #775, #1064, #1061.

Contributor guide

Open the contributing guide

Research direction

Start in internal/fwschemadata/value_semantic_equality_set.go at ValueSemanticEqualitySetElements, then compare the list and map element functions. Trace how the collection element type is represented and how dynamic types are handled. Done means skipping the element walk only when no nested type can implement semantic equality, while preserving dynamic-type behavior and the collection-level semantic-equality path.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.