Strategic merge patches cost O(n²) each: resWrangler.ApplySmPatch re-appends every resource with a linear duplicate-ID scan #6300

This issue was drafted in part with the assistance of generative AI; the reproduction and measurements were run and checked locally.

What happened?

Build time grows quadratically with resource count for every strategic merge patch, even when the patch targets a single named resource.

resWrangler.ApplySmPatch (api/resmap/reswrangler.go, unchanged between v5.8.1 and master) applies the patch, then rebuilds the whole map:

m.Clear()
return m.appendAll(list)

appendAll calls Append per resource, and Append checks for a duplicate ID with GetMatchingResourcesByCurrentId(id.Equals), a linear scan over the resources already appended that calls CurId() on each one. One patch therefore does ~n²/2 CurId() + ResId.Equals calls, and a build with p SMP patches does ~p·n²/2.

Reproduction (kustomize v5.8.1, darwin/arm64; one target per patch, n ConfigMaps, 80 SMP patches):

"""Generate a kustomization with N ConfigMaps and P strategic merge patches.

Usage: python3 gen.py N P MODE

MODE:
  distinct  each patch targets a different ConfigMap (cm-0, cm-1, ...)
  same      every patch targets cm-0
  merged    one patch on cm-0 carrying all P annotations
"""

import sys
from pathlib import Path


def config_map(name: str) -> str:
    return f"""\
apiVersion: v1
kind: ConfigMap
metadata:
  name: {name}
data:
  a: x
---
"""


def patch(target: str, annotations: dict[str, str]) -> str:
    lines = "".join(f"          {key}: {value}\n" for key, value in annotations.items())
    return f"""\
  - target: {{kind: ConfigMap, name: {target}}}
    patch: |-
      apiVersion: v1
      kind: ConfigMap
      metadata:
        name: {target}
        annotations:
{lines}"""


def patches(resource_count: int, patch_count: int, mode: str) -> str:
    if mode == "merged":
        return patch("cm-0", {f"k{j}": f"v{j}" for j in range(patch_count)})
    rendered = []
    for j in range(patch_count):
        target = "cm-0" if mode == "same" else f"cm-{j % resource_count}"
        rendered.append(patch(target, {f"k{j}": f"v{j}"}))
    return "".join(rendered)


def main() -> None:
    resource_count, patch_count, mode = int(sys.argv[1]), int(sys.argv[2]), sys.argv[3]
    out = Path("synthetic")
    out.mkdir(exist_ok=True)

    resources = "".join(config_map(f"cm-{i}") for i in range(resource_count))
    (out / "resources.yaml").write_text(resources)

    kustomization = """\
apiVersion: kustomize.config.k8s.io/v1beta1
kind: Kustomization
resources:
- resources.yaml
patches:
"""
    (out / "kustomization.yaml").write_text(
        kustomization + patches(resource_count, patch_count, mode)
    )


if __name__ == "__main__":
    main()

for n in 100 400 800; do python3 gen.py $n 80 distinct; /usr/bin/time -p kustomize build synthetic >/dev/null; done
python3 gen.py 400 80 same;   /usr/bin/time -p kustomize build synthetic >/dev/null
python3 gen.py 400 80 merged; /usr/bin/time -p kustomize build synthetic >/dev/null

Doubling resources from 400 to 800 quadruples the time, and 80 patches on one object cost the same as 80 patches spread across objects, so the cost is per patch × n², not the merge work itself.

Real-world impact. One of our overlays (745 base resources, 51 components, ~1,300 patches in total) takes ~42s to build, CPU-bound on one core. Without components it builds in 11s; without the overlay's own SMP patches, in 31s. A CPU profile of krusty.Kustomizer.Run (v0.21.1 API, output byte-identical to kustomize build) shows, cumulative, out of 41.8s sampled:

PatchTransformer.transformStrategicMerge   27.42s
resWrangler.ApplySmPatch                   27.05s
resWrangler.appendAll / Append             30.4s
resWrangler.GetMatchingResourcesByCurrentId 30.3s
Resource.CurId                             26.48s

Flat time is dominated by IndexByteString, memequal and map hashing under CurId()/ResId.Equals. Converting that overlay's 112 SMP patches to equivalent JSON6902 patches kept the output byte-identical and cut its build from ~42s to ~32s (a second overlay with 94 such patches went from ~35s to ~30s). We're applying that workaround on our side.

What did you expect to happen?

Applying one SMP patch should cost roughly O(n) for selection plus the merge itself, not O(n²).

Possible fix. ApplySmPatch only needs the rebuild to drop resources that the patch emptied ($patch: delete) and to reject ID collisions a patch may introduce (for example, a renamed resource). A single map pass over list, keyed by the ID with its namespace normalised the way ResId.IsNsEquals treats "" and default, detects collisions in O(n) before assigning m.rList = list, without Clear() + appendAll(). Caching CurId() per resource during the pass would also avoid re-parsing each resource's ID. This would complement the regressions discussed in #5422. Happy to send a PR with a failing-benchmark commit followed by the fix, per CONTRIBUTING.md, if a maintainer agrees with the approach.

Kustomize version: v5.8.1 (also via kubectl kustomize, kubectl v1.37.0). Code path unchanged on master.

Operating system: macOS (darwin/arm64); same behaviour on Linux CI runners.