Skip to content

memory-model.md

Latest commit

 

History

History
319 lines (227 loc) · 7.85 KB

memory-model.md

File metadata and controls

319 lines (227 loc) · 7.85 KB

Memory Model

This document explains the memory semantics and lifetime rules for InlineCollections.

Stack vs heap allocation

InlineCollections are stack-allocated

When you declare an InlineList8<int>, InlineList16<int>, or InlineList32<int> as a local variable:

void MyMethod()
{
    var list8 = new InlineList8<int>();    // 36 bytes on stack
    var list16 = new InlineList16<int>();  // 68 bytes on stack
    var list32 = new InlineList32<int>();  // 132 bytes on stack
    list32.Add(1);
}
// All structs go out of scope; stack pointer restored

Each collection is allocated directly on the method's stack frame. No heap allocation occurs.

Memory layout on stack (InlineList32):

Stack pointer: [...] [InlineList32<int> = 132 bytes] [← ESP]
              [buffer (32 ints = 128 bytes) + _count (4 bytes)]

After the method returns, the stack pointer moves past the struct; memory is implicitly freed.

Standard collections are heap-allocated

In contrast, List<T> is a reference type:

void MyMethod()
{
    var list = new List<int>();  // Reference on stack, array on heap
    list.Add(1);                  // Allocates 16 elements on heap
}
// Reference goes out of scope; GC may eventually collect heap array

The reference (this pointer) sits on the stack, but the data lives on the GC heap.

Value-type semantics

Copying on assignment

InlineList8<T>, InlineList16<T>, and InlineList32<T> are value types; assignments copy the entire struct:

var list1 = new InlineList8<int>();
list1.Add(42);

var list2 = list1;  // COPY: all 8 elements + metadata copied (36 bytes)
list2.Add(99);

// list1.Count == 1, list2.Count == 2  (independent!)

Stack memory note: Each collection instance consumes Capacity * sizeof(T) bytes on the stack. Using a large unmanaged T (or copying the struct by value in a deep call chain) can add significant stack pressure and increase the risk of a StackOverflowException. Passing the collection by ref or in, or selecting a smaller capacity, mitigates this cost.


This is identical to how `int` or `DateTime` work: assignment creates a copy.

### Struct size and copy cost

The copy cost is proportional to struct size. For `InlineList32<int>`:

Size = 32 * 4 (elements) + 4 (_count) = 132 bytes Copy cost ≈ 2-3 nanoseconds (on modern CPUs with cache loaded)


For large element types, copy cost increases:

```csharp
struct LargeElement {
    public long A, B, C, D;  // 32 bytes
}

var list = new InlineList32<LargeElement>();
// Size = 32 * 32 + 4 = 1,028 bytes
// Copy cost ≈ 100+ nanoseconds (noticeable!)

Recommendation: Avoid passing InlineList32<T> by value in hot loops. Use ref parameter:

void Process(ref InlineList32<int> list)  // No copy
{
    list.Add(1);
}

var list = new InlineList32<int>();
Process(ref list);  // Efficient: no copy

Ref struct lifetime safety

Ref struct constraint

InlineList8<T>, InlineList16<T>, and InlineList32<T> are ref struct types:

public ref struct InlineList8<T> where T : unmanaged, IEquatable<T>
{
    private InlineArray8<T> _buffer;
    private int _count;
}

This prevents:

  • Storage in reference types: Cannot be a field of a class
  • Boxing: Cannot be assigned to object
  • Arrays: Cannot be an array element
  • Async capture: Cannot be captured in async/await

These restrictions enforce compile-time safety: the struct's stack memory is never escaped to the heap or async context.

Valid vs invalid code

✅ Valid:

var list = new InlineList8<int>();  // Stack local
list.Add(42);

void Method(ref InlineList8<int> list) { ... }
Method(ref list);  // Pass by ref (reference to stack memory)

❌ Invalid (compile error):

class Container
{
    public InlineList8<int> List;  // ❌ Cannot be a field of a class
}

object boxed = new InlineList8<int>();  // ❌ Cannot box

Inline storage and buffer

Inline array

The InlineArray8<T>, InlineArray16<T>, and InlineArray32<T> structs embed consecutive elements:

[InlineArray(8)]
internal struct InlineArray8<T>
{
    private T _element0;
}

[InlineArray(16)]
internal struct InlineArray16<T>
{
    private T _element0;
}

[InlineArray(32)]
internal struct InlineArray32<T>
{
    private T _element0;
}

At runtime, this becomes a contiguous buffer of 32 T values.

Memory layout for InlineList32<byte>:

Offset  Content
------  -------
0-31    32 bytes (elements)
32-35   4 bytes (_count)

Memory access

Methods use System.Runtime.CompilerServices.Unsafe for direct memory access:

public void Add(T item)
{
    if ((uint)_count >= Capacity) ThrowFull();
    Unsafe.Add(ref _buffer[0], _count++) = item;
}

Unsafe.Add(ref _buffer[0], _count++) computes the address of the element at index _count by pointer arithmetic: no bounds check, no exception.

Span conversion

AsSpan() returns a Span<T> over the active portion:

public Span<T> AsSpan() => MemoryMarshal.CreateSpan(ref Unsafe.AsRef(in _buffer[0]), _count);

This creates a span of length _count over the buffer, allowing safe iteration and LINQ.

Stack pressure and struct size

Stack frame size

Each InlineList32<int> occupies ~132 bytes on the stack. Multiple collections add up:

void DeepRecursion()
{
    var list1 = new InlineList32<int>();    // 132 bytes
    var list2 = new InlineList32<int>();    // 132 bytes
    var list3 = new InlineList32<int>();    // 132 bytes
    // Frame uses 396 bytes so far

    var large = new InlineList32<LargeStruct>();  // 1KB
    // Frame now 1.4KB

    if (depth < max)
        DeepRecursion();  // Nested frame adds more stack
}

Typical stack is 1 MB, so even 1000 frames of 1.4KB each is feasible. However, deeply nested code with many large structs can risk stack overflow.

Guidance: Profile stack usage in deep recursion scenarios. Consider using List<T> if stack pressure is a concern.

Enumerator lifetimes

Span-based enumerator

Enumerators are value types wrapping a Span<T>:

public ref struct Enumerator
{
    private Span<T> _span;
    private int _index;

    public bool MoveNext() => ++_index < _span.Length;
    public readonly ref T Current => ref _span[_index];
}

The enumerator's lifetime is tied to the underlying collection. Modifying the collection during enumeration causes undefined behavior:

var list = new InlineList32<int>();
list.Add(1); list.Add(2);

foreach (var item in list)
{
    list.Add(3);  // ❌ Modifying during enumeration (undefined behavior)
}

Safe pattern: copy first

If you must modify during iteration, iterate over a copy:

var list = new InlineList32<int>();
list.Add(1); list.Add(2);

var snapshot = list.AsSpan().ToArray();  // Copy to array
foreach (var item in snapshot)
{
    list.Add(3);  // ✅ Safe: iterating over copy
}

Reference returns and in-place modification

Ref semantics

Indexer and Peek/Peek methods return ref T:

public ref T this[int index] => ref Unsafe.Add(ref Unsafe.AsRef(in _buffer[0]), index);

public ref T Peek() => ref Unsafe.Add(ref Unsafe.AsRef(in _buffer[0]), _count - 1);

This enables in-place modification without copying:

ref int top = ref stack.Peek();
top = 100;  // Modifies element directly in stack

ref int elem = ref list[5];
elem += 1;  // Modifies element directly in list

Safety

Ref returns are valid as long as the collection (struct) is not reassigned or moved:

var list = new InlineList32<int>();
list.Add(42);

ref int value = ref list[0];
value = 100;  // ✅ Safe: list is in scope

void UseRef(InlineList32<int>& list)
{
    ref int value = ref list[0];  // ❌ Dangerous: ref escapes method scope
}

The compiler prevents this pattern. Ref returns must not outlive their source struct.