corvus-low-alloc-data-structures

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<T>	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.

// Typical usage — stack-allocate initial buffers, dispose to return any rented overflow
Span<int> buckets = stackalloc int[Utf8KeyHashSet.StackAllocBucketSize];
Span<byte> entries = stackalloc byte[Utf8KeyHashSet.StackAllocEntrySize];
Span<byte> 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.

Span<int> initialBuffer = stackalloc int[16];
ValueListBuilder<int> list = new(initialBuffer);

try
{
    list.Append(42);
    list.Append(99);
    ReadOnlySpan<int> 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<T>.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.

// UTF-16 string building
Span<char> 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<byte> initialBytes = stackalloc byte[JsonConstants.StackallocByteThreshold];
Utf8ValueStringBuilder usb = new(initialBytes);
try
{
    usb.Append("hello"u8);
    ReadOnlySpan<byte> 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.

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<JsonElement> — 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<byte>, the codebase uses explicit SIMD:

if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2)
{
    Vector<byte> vQuote = new((byte)'"');
    Vector<byte> vBackslash = new((byte)'\\');
    Vector<byte> vControlMax = new(0x1F);

    Vector<byte> vData = Unsafe.ReadUnaligned<Vector<byte>>(
        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:

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<T>.Count elements per iteration for counting matching items in spans.

Bit Manipulation Techniques

Branchless token type classification

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

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<T>.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