ContiguousMap.GetKeysSpan/GetValuesSpan allocate and copy the whole map on every call, making indexed loops O(n²)

[matt-edmondson]

What's wrong

ContiguousMap.GetKeysSpan() and GetValuesSpan() (Containers/ContiguousMap.cs:590-630) allocate new TKey[Count] / new TValue[Count] and copy every entry on each call, then return a span over that fresh array. Their remarks say they provide "direct access to the keys from the contiguous memory, enabling high-performance operations", and the return type (ReadOnlySpan<T>) reinforces that it's a view — so callers have no signal it's an O(n) allocation.

Failure scenario

for (int i = 0; i < map.Count; i++) { var k = map.GetKeysSpan()[i]; ... }

is O(n²) time and allocates n arrays: 40k entries took ~2.2 s in a Release probe. Containers.Benchmarks/ContiguousMapBenchmarks.cs:216 benchmarks this copy as if it were a span access.

Suggested fix

Entries are stored as Entry { Key, Value } structs, so a keys-only span can't exist without a copy. Pick one:

• Replace with non-allocating CopyKeysTo(Span<TKey>) / CopyValuesTo(Span<TValue>) (and/or ToKeysArray()), obsoleting the *Span names; or
• Keep the methods but make the allocation explicit in the name/remarks, and point callers at AsReadOnlySpan() (which is genuinely zero-copy) for indexed access to Entry.Key/Entry.Value.

Distinct from #78 (writable AsSpan).

[matt-edmondson]

Triage

• Category: Improvement. Performance and a misleading API; it is labelled enhancement.
• Priority: Medium. *Span names and remarks promise zero-copy access, so ordinary indexed loops silently become O(n²). The benchmark at ContiguousMapBenchmarks.cs:216 also measures the wrong thing.
• Suggested area / assignment: Containers/ContiguousMap.cs public API
• Duplicates / related: Distinct from ContiguousSet.AsSpan() / ContiguousMap.AsSpan() return a writable Span that silently desyncs the uniqueness/key index (duplicates in a set, wrong lookups in a map) #78 (writable AsSpan). It touches the same file as Evicting oldest-first from InsertionOrderMap/ContiguousMap is quadratic: emptying a 40k map takes ~3.6 s #101.
• In progress: No open PR covers it. The open PRs fix: release RingBuffer elements as PushBack evicts them [patch] #99, fix: throw when a RingBuffer is modified during enumeration [patch] #100 and fix: release removed and cleared slots on netstandard builds [patch] #103 are RingBuffer/netstandard fixes.

Recommended next step: Prefer the CopyKeysTo(Span<TKey>) / CopyValuesTo(Span<TValue>) option, with [Obsolete] on the *Span methods pointing callers to AsReadOnlySpan(). Fix the benchmark in the same change. Removing the methods outright would be a breaking change, so tag that as [major].

---

Generated by Claude Code