--- name: corvus-low-alloc-data-structures description: > Use and extend the custom low-allocation data structures in Corvus.JsonSchema. Covers ref-struct collections (Utf8KeyHashSet, UniqueItemsHashSet, ValueListBuilder, ValueStringBuilder, Utf8ValueStringBuilder, BitStack, Sequence), SIMD scanning patterns, bit manipulation tricks, and happy-path optimisations like lazy error messages. USE FOR: choosing which stack-allocated collection to use, writing new ref-struct types, adding SIMD-accelerated code paths, understanding branchless techniques, writing validation code that avoids allocation on success. DO NOT USE FOR: basic buffer allocation patterns (use corvus-buffer-and-pooling), document model (use corvus-parsed-documents-and-memory). --- # Low-Allocation Data Structures ## Collection Selection Guide Choose the right collection based on your need: | Need | Type | Location | Heap allocation? | |------|------|----------|-----------------| | Deduplicate UTF-8 keys | `Utf8KeyHashSet` | `Common/Utf8KeyHashSet.cs` | No (stack + ArrayPool fallback) | | Check JSON array uniqueness | `UniqueItemsHashSet` | `JsonSchema/Internal/UniqueItemsHashSet.cs` | No (stack + ArrayPool fallback) | | Growable list (small) | `ValueListBuilder` | `System.Private.CoreLib/.../ValueListBuilder.cs` | No (stack + ArrayPool fallback) | | Build a UTF-16 string | `ValueStringBuilder` | `Common/src/System/Text/ValueStringBuilder.cs` | No (stack + ArrayPool fallback) | | Build a UTF-8 string | `Utf8ValueStringBuilder` | `Common/src/System/Text/Utf8ValueStringBuilder.cs` | No (stack + ArrayPool fallback) | | Track nesting depth | `BitStack` | `BitStack.cs` | No (ulong for ≤64 levels) | | Return singleton/multi value | `Sequence` | `Corvus.Text.Json.Jsonata/Sequence.cs` | No for singletons; ArrayPool for multi | | Sliding-window byte buffer | `ArrayBuffer` | `Common/src/System/Net/ArrayBuffer.cs` | ArrayPool backed | All `ref struct` types must be disposed (they implement `IDisposable` to return pooled memory). ## Utf8KeyHashSet — Stack-Allocated UTF-8 Hash Set A `ref struct` separate-chaining hash set for UTF-8 byte-string keys. Used for property deduplication and JSONata merge operations. ```csharp // Typical usage — stack-allocate initial buffers, dispose to return any rented overflow Span buckets = stackalloc int[Utf8KeyHashSet.StackAllocBucketSize]; Span entries = stackalloc byte[Utf8KeyHashSet.StackAllocEntrySize]; Span keyBuffer = stackalloc byte[Utf8KeyHashSet.StackAllocKeyBufferSize]; using Utf8KeyHashSet hashSet = new(estimatedPropertyCount, buckets, entries, keyBuffer); bool added = hashSet.Add(utf8Key); ``` ### Internal design - Entries are packed as 20-byte binary records: `Next(4) + BufOffset(4) + Length(4) + HashCode(8)` - Packed with `MemoryMarshal.Write/Read` and `[MethodImpl(AggressiveInlining)]` - Growth uses a small prime table (`3, 7, 11, 17, ... 521`) — avoids `HashHelpers` dependency - Falls back to `ArrayPool` only when stack buffers overflow - Stack alloc sizes: buckets = 64 ints (256 bytes), entries = 512 bytes, key buffer = 512 bytes ### When to use - Property name deduplication in JSON object processing - Merge operations in JSONata where duplicate keys must be detected - Any scenario needing set membership testing on UTF-8 byte sequences without allocation ## UniqueItemsHashSet — Schema Validation Hash Set Same architectural pattern as `Utf8KeyHashSet`, but specifically for JSON Schema `uniqueItems` keyword validation. Compares full JSON element values (not just strings). ## ValueListBuilder — Stack-Backed Generic List Ported from `dotnet/runtime`'s internal type. A `ref struct` list that starts on the stack and overflows to `ArrayPool`. ```csharp Span initialBuffer = stackalloc int[16]; ValueListBuilder list = new(initialBuffer); try { list.Append(42); list.Append(99); ReadOnlySpan items = list.AsSpan(); } finally { list.Dispose(); // returns any rented array } ``` ### Key behaviours - Initial buffer is the caller's `stackalloc` span — zero heap allocation for small lists - Grows with 2× doubling via `ArrayPool.Shared.Rent()` - `Dispose()` returns the rented array and clears references if `T` is a reference type - Used in YAML writing (`Utf8YamlWriter._contextStack`), JSON parsing, and path navigation ## ValueStringBuilder / Utf8ValueStringBuilder Two parallel `ref struct` string builders — one for `char` (UTF-16), one for `byte` (UTF-8). Both follow the stackalloc → ArrayPool growth pattern. ```csharp // UTF-16 string building Span initialChars = stackalloc char[JsonConstants.StackallocCharThreshold]; ValueStringBuilder sb = new(initialChars); try { sb.Append("hello"); sb.Append(' '); sb.Append("world"); return sb.ToString(); } finally { sb.Dispose(); } // UTF-8 string building Span initialBytes = stackalloc byte[JsonConstants.StackallocByteThreshold]; Utf8ValueStringBuilder usb = new(initialBytes); try { usb.Append("hello"u8); ReadOnlySpan result = usb.AsSpan(); } finally { usb.Dispose(); } ``` ### Differences | Feature | `ValueStringBuilder` | `Utf8ValueStringBuilder` | |---------|----------------------|--------------------------| | Element type | `char` | `byte` | | Double-dispose detection | No | Yes (`_pos = -1` on dispose) | | Interpolation support | `AppendSpanFormattable` | No | ## BitStack — Allocation-Free Nesting Tracker Tracks JSON object/array nesting using bit manipulation on a `ulong`. No allocation for the first 64 levels. ```csharp BitStack stack = default; stack.PushTrue(); // entering an object stack.PushFalse(); // entering an array bool wasObject = stack.Pop(); // leaving — returns true if it was an object ``` ### Internal design - First 64 levels: single `ulong _allocationFreeContainer` with shift/mask operations - Beyond 64 levels: falls back to heap-allocated `int[]` (extremely rare in practice) - `Div32Rem` uses `& 31` instead of `% 32` for the array path ## Sequence — 32-Byte Inline Tagged Union (JSONata) The JSONata evaluator's primary result type. Stores singleton values inline without allocation. ``` Layout (32 bytes): object? payload (8 bytes) — reference-type backing for multi-value double rawValue (8 bytes) — inline double storage JsonElement single (12 bytes) — inline singleton element int countAndTag (4 bytes) — bits 0-23: count, bits 24-31: tag ``` Tags: `Undefined=0, Singleton=1, Multi=2, Lambda=3, Regex=4, RawDouble=7, Tuple=9`. - **Singleton**: zero heap allocation — the JSON element is stored inline in the struct - **Multi**: rents from `ArrayPool` — must be disposed - A single JSON element evaluation produces a `Singleton` sequence with zero allocation ## SIMD Scanning Patterns ### Vector parallel scanning (netstandard path) On platforms without `SearchValues`, the codebase uses explicit SIMD: ```csharp if (Vector.IsHardwareAccelerated && length >= Vector.Count * 2) { Vector vQuote = new((byte)'"'); Vector vBackslash = new((byte)'\\'); Vector vControlMax = new(0x1F); Vector vData = Unsafe.ReadUnaligned>( ref Unsafe.AddByteOffset(ref searchSpace, index)); var vMatches = Vector.BitwiseOr( Vector.BitwiseOr( Vector.Equals(vData, vQuote), Vector.Equals(vData, vBackslash)), Vector.LessThan(vData, vControlMax)); } ``` Scans 16–32 bytes simultaneously for quotes, backslashes, or control characters. ### De Bruijn bit scanning Finding the first set bit in a SIMD match result: ```csharp ulong powerOfTwoFlag = match ^ (match - 1); // isolate lowest set bit return (int)((powerOfTwoFlag * XorPowerOfTwoToHighByte) >> 57); ``` O(1) branchless lookup using a precomputed De Bruijn constant. ### 8× unrolled SIMD count `SpanHelper.Count` in the source generator processes `8 × Vector.Count` elements per iteration for counting matching items in spans. ## Bit Manipulation Techniques ### Branchless token type classification ```csharp public static bool IsTokenTypePrimitive(JsonTokenType tokenType) => (tokenType - JsonTokenType.String) <= (JsonTokenType.Null - JsonTokenType.String); ``` Single unsigned subtraction + comparison replaces a multi-branch switch. ### Bit-packed struct fields `DbRow` (12 bytes) packs token type, location, size, child count, and flags into 3 `uint/int` fields using bit shifts and masks. The top nibble of the third field encodes `JsonTokenType`. ## Happy-Path Optimisations ### Lazy error messages in schema validation ```csharp private static readonly JsonSchemaMessageProvider ExpectedDate = static (buffer, out written) => { /* format error message only when called */ }; ``` On the success path, `EvaluatedKeyword(true, ...)` records success without touching the message provider. Error strings are only materialised on failure. ### Lazy SR (string resources) `ResourceManager` is only created on first exception throw — `UsingResourceKeys()` returns early with the key itself when trimming is active. ### CodeGenThrowHelper Throw helpers set `Exception.Source` to a key instead of formatting a message string. The actual message is only looked up if the exception is caught and displayed. ## Creating New ref struct Collections When adding a new `ref struct` collection, follow these patterns: 1. **Accept initial storage as constructor parameters** — let the caller stackalloc the initial buffers 2. **Define stack-alloc size constants** on the type (e.g., `StackAllocBucketSize`) 3. **Implement `IDisposable`** to return any `ArrayPool`-rented overflow buffers 4. **Use `MemoryMarshal.Write/Read`** with `[MethodImpl(AggressiveInlining)]` for packed entries 5. **Growth via `ArrayPool.Shared.Rent()`** with geometric (2×) sizing 6. **Return old rented buffer** before taking a new one during growth ## Cross-References - For the basic stackalloc/rent pattern and pooling tiers, see `corvus-buffer-and-pooling` - For document memory model, see `corvus-parsed-documents-and-memory` - For full conventions, see `.github/copilot-instructions.md`