JBlam.Collections.Immutable 0.0.1-testing

JBlam's Immutable Sequences

Provides two immutable collection types:

• ValueArray: an immutable array that behaves like a record type.
• ReadOnlySnapshotBuffer: snapshot changes to a list with minimal overhead.

ValueArray

This is a sort-of drop in replacement for System.Collections.Immutable.ImmutableArray<T> which aims to resolve three issues:

1. The default value is logically empty, rather than exploding with null reference exceptions.
2. It implements value equality, and is therefore suitable to use in record types.
3. It overrides the default string representation to print at least some of the contents, similar to the generated ToString for record types.

Implementation details

The struct layout of ValueArray is identical to ImmutableArray. The type design is similar, except it special-cases the default value, provides value equality, and overrides ToString to print its contents.

Converting to and from ImmutableArray<T> is effectively free. (Roughly the cost of copying a single reference.)

I will release this with minimal API around it, on the understanding that if you want "immutable mutations" you can easily convert to the equivalent ImmutableArray, do your business, and convert back.

Rants

ImmutableArray<T> is a value type which wraps a hidden reference to a reference type, and as such default contains a null reference. This is a massive footgun, because the only safe way to interact with an ImmutableArray is to inspect it for IsDefault; that's incredibly unexpected because C# programmers don't normally inspect value types for null. It also hides the null reference from the nullable type annotation system, which otherwise makes NullReferenceException more-or-less a solved problem.

ValueArray<T> solves this issue by making default logically equal to an empty array.

But wait! if default is equal to [], doesn't that mean equality is broken? Well, have I got a story to tell you ...

ImmutableArray<T> is a value type which wraps a hidden reference to a reference type and doesn't manage equality meaning that ImmutableArray<T>.Equals is effectively reference-equality on the hidden reference. This is again highly surprising for the C# developer who assumes that value types support value equality, because they are values.

ValueArray<T> solves this issue by making Equals return sequence equality. Yes, that's O(n). I suggest not making ValueArray<T> wrap multiple gigabytes of data.

ReadOnlySnapshotBuffer

ReadOnlySnapshotBuffer provides a "sequence builder" interface which generates immutable snapshots, where the amortised append cost scales linearly with the size of one element.

The design motivation is "convert IObservable<T> into IObservable<IReadOnlyList<T>>": we don't technically hit IReadOnlyList<T>, but rather ReadOnlySequence<T>, but it's close enough to be useful.

The snapshot buffer itself doesn't actually provide the observable collection, since I don't want to take System.Reactive's transitive dependence on winforms, but it's not challenging:

// infinite length "memory leak edition"
static IObservable<ReadOnlySnapshot<T>> Collect(this IObservable<T> items)
{
  var buffer = new ReadOnlySnapshotBuffer<T>();
  return items.Select(t => { buffer.Enqueue(t); return buffer.Snapshot; });
}

// fixed-length "circular buffer"
static IObservable<ReadOnlySnapshot<T>> Collect(this IObservable<T> items, int itemCount)
{
  var buffer = new ReadOnlySnapshotBuffer<T>();
  return items.Select(t =>
  {
    buffer.Enqueue(t);
    while (buffer.Count > itemCount) { buffer.Dequeue(); }
    return buffer.Snapshot; 
  });
}

The main drawbacks are:

• The collection snapshot is ReadOnlySequence<T>, which doesn't allow indexing into the collection, doesn't natively implement IEnumerable<T>, and may otherwise be a bit unfamiliar to a typical C# dev.
• The "sequence builder" is necessarily a separate object to the sequence, which may be surprising if you're familiar with the System.Collections.Immutable API design.
• It is challenging to implement a "newest value first" version.

To address these points, we provide some extension methods on ReadOnlySequence<T>:

• EnumerateItems() provides ItemsEnumerable<T>, an implementation of IEnumerable<T>
• ItemsEnumerable<T>.Reverse() enumerates the sequence in reverse order.

Somewhat related; the GetActualOffset(SequencePosition) extension method is provided to make interacting with slices of the sequence possible in the presence of a design bug in the BCL which makes GetOffset(SequencePosition) return misleading values.

Implementation details

ReadOnlySnapshotBuffer is implemented as a linked list of "segment" buffers. The linked list and the individual buffers are internally mutable, but by contract guaranteed to be forward-only; thus every snapshot is guaranteed immutable, but the only legal operations are Enqueue and Dequeue. Further, only the buffer can make those changes; whereas for a more typical immutable collection, the observer is free to "modify" the snapshot.

Let's compare some existing relevant collection implementations. Assume we make a circular buffer with n elements of size q that generates immutable snapshots; the snapshot must never change even if the "source" collection observes new elements. For ReadOnlySnapshotBuffer, the segment size is b. The asymptotic behaviour of each append is:

• Queue<T> is a mutable buffer, so each append allocates no memory and has a complexity of q (copying the value into the buffer) provided we dequeue the old item first. Since the "snapshot" mutates, it's not fit for our stated purpose; it's included for reference.
• ImmutableQueue<T> is an immutable linked list; every append needs to rewrite (and realloc) every single link, and also alloc the new value. (Note that ImmutableList<T> is implemented as a forward-queue and a reverse-queue, so its performance is a constant factor worse.)
• ImmutableArray<T> is a copy-on-write immutable buffer: every append copies the entire buffer. This is obviously a terrible idea.
• The "immutable finger tree" is a recursive nested data structure, so the complexities are q times the number of "layers" (scales with log n).
• ReadOnlySnapshot<T> needs to allocate a new segment (size b) and one linked list node (size 1) every b/q elements. Amortised cost is therefore (b + 1) / (b/q) or equivalently q + q/b.
• The final row assumes ReadOnlySnapshotBuffer uses a segment size much greater than the element size, so the b/q terms are small. The ReadOnlySnapshotBuffer API uses a default segment size b = 128 q.

I note that the "comparison" collections above are each high-quality robust implementations (or presented as a teaching exercise, in the case of the finger tree). They just solve a different problem.