Runtime: Proposal: writable equivalents of ReadOnlySequence<T> APIs

[DaZombieKiller]

Currently, there appears to be no writable equivalent to the ReadOnlySequence<T> APIs in the framework. This complicates matters when dealing with non-contiguous mutable buffers (such as in a custom memory allocator).

Below is the basic API surface I'd expect to see (effectively the API surface of ReadOnlySequence<T>, but writable), although ideally this would be accompanied by a SequenceWriter<T> type (which I believe is out of scope for this proposal).

public abstract class SequenceSegment<T>
{
    protected SequenceSegment();
    public Memory<T> Memory { get; protected set; }
    public SequenceSegment<T> Next { get; protected set; }
    public long RunningIndex { get; protected set; }
}

public readonly struct Sequence<T>
{
    public static readonly Sequence<T> Empty;
    public Sequence(SequenceSegment<T> startSegment, int startIndex, SequenceSegment<T> endSegment, int endIndex);
    public Sequence(Memory<T> memory);
    public Sequence(T[] array);
    public Sequence(T[] array, int start, int length);
    public SequencePosition End { get; }
    public Memory<T> First { get; }
    public Span<T> FirstSpan { get; }
    public bool IsEmpty { get; }
    public bool IsSingleSegment { get; }
    public long Length { get; }
    public SequencePosition Start { get; }
    public Enumerator GetEnumerator();
    public SequencePosition GetPosition(long offset);
    public SequencePosition GetPosition(long offset, SequencePosition origin);
    public Sequence<T> Slice(int start, int length);
    public Sequence<T> Slice(int start, SequencePosition end);
    public Sequence<T> Slice(long start);
    public Sequence<T> Slice(long start, long length);
    public Sequence<T> Slice(long start, SequencePosition end);
    public Sequence<T> Slice(SequencePosition start);
    public Sequence<T> Slice(SequencePosition start, int length);
    public Sequence<T> Slice(SequencePosition start, long length);
    public Sequence<T> Slice(SequencePosition start, SequencePosition end);
    public bool TryGet(ref SequencePosition position, out Memory<T> memory, bool advance = true);
    public override string ToString();

    public struct Enumerator
    {
        public Enumerator(in Sequence<T> sequence);
        public Memory<T> Current { get; }
        public bool MoveNext();
    }
}

Questions:

• Is the current lack of a Sequence<T> type a conscious, deliberate decision? Or was it simply left out because it was never brought up/needed at the time the API was designed?
• How would the addition of this type affect System.IO.Pipelines?
• Should SequenceSegment<T> subclass ReadOnlySequenceSegment<T>?
  
  
  
  • If not, should a conversion be provided? Although unlike subclassing, this would incur GC allocations.
  
  

[GrabYourPitchforks]

@ahsonkhan speaking:

What is the scenario you are targeting with this API?

• Is the current lack of a Sequence<T> type a conscious, deliberate decision? Or was it simply left out because it was never brought up/needed at the time the API was designed?

@davidfowl - did we intentionally leave this out from the initial design when pipelines/sequence was being prototyped in corefxlab?

[DaZombieKiller]

What is the scenario you are targeting with this API?

I was intending to use it for a scripting VM's memory heap (which can often be accessed non-contiguously), and figured it'd be convenient to have Sequence<T> for passing it around.

For additional use cases, I'd like to refer to the Pipelines.Sockets.Unofficial project, which offers an implementation of Sequence<T> for its arena allocation API: https://mgravell.github.io/Pipelines.Sockets.Unofficial/docs/arenas

[davidfowl]

@davidfowl - did we intentionally leave this out from the initial design with pipelines/sequence was being prototyped in corefxlab?

IBufferWriter\

But have no fear, @AArnott has your back https://github.com/AArnott/Nerdbank.Streams/blob/66186b4fa1daafcacb657ee09a9ea4c6a1194f98/doc/Sequence.md.

This should be added to the BCL.

[DaZombieKiller]

@davidfowl

But have no fear, @AArnott has your back https://github.com/AArnott/Nerdbank.Streams/blob/66186b4fa1daafcacb657ee09a9ea4c6a1194f98/doc/Sequence.md.

That looks almost perfect for my purposes, although it lacks the ability to seek backwards in the sequence, which would be needed to enable writes to arbitrary positions.

[AArnott]

@DaZombieKiller You want random write access rather than append-only?
Would you need insert capabilities or simply overwrite of existing bytes?

[DaZombieKiller]

@AArnott I have no need for insertion, only the ability to write to an arbitrary position in the sequence, overwriting anything already present there.

[AArnott]

Well, that extends beyond anything IBufferWriter<byte> would ever expose. What API are you imagining you'd use while writing to arbitrary positions? Keep in mind the backing buffers are broken up into potentially many backing arrays, at somewhat arbitrary positions.

[AArnott]

BTW, if your writing at arbitrary positions is limited to what I call "length prefixing", I have a solution for that too.

[DaZombieKiller]

What API are you imagining you'd use while writing to arbitrary positions?

I was imagining a situation where I could retrieve a Sequence<T> starting at a requested position, and then enumerate its Memory<T>s. Something along these lines (forgive the likely bad example, I just woke up):

void WriteBytes(SequencePosition position, ReadOnlySpan<byte> bytes)
{
    var slice = sequence.Slice(position);
    slice.EnsureAvailable(bytes.Length);

    foreach (Memory<byte> memory in slice)
    {
        if (bytes.Length == 0)
            break;

        if (memory.Length >= bytes.Length)
        {
            bytes.CopyTo(memory.Span);
            break;
        }

        var span = bytes.Slice(0, memory.Length);
        span.CopyTo(memory);
        bytes = bytes.Slice(memory.Length);
    }
}

[AArnott]

Ya, I think your example might need some tweaking to make sense. Or at least some code comments.

What is the scenario for this? If you're just trying to recycle memory, Sequence<T> can already do that.

[DaZombieKiller]

My use case is a memory heap for a virtual machine, which I briefly mentioned earlier. The VM has instructions that can access random memory locations. Memory is allocated for "out of bounds" accesses. An alternative implementation I was considering was a sparse array, but I was hoping I could leverage ReadOnlySequence<T> and a writable equivalent.

[davidfowl]

Seems achievable with a Seek functionality but it’s for the writer not the reader. So the Sequence\

[AArnott]

@DaZombieKiller Are you expecting Sequence<T> to support sparse buffers behind the scenes then, where your sequence is allegedly very long but only allocates buffers to back non-zero writes?

[DaZombieKiller]

@AArnott That would be an ideal scenario, yes.

[AArnott]

IMO that's a far cry different from what IBufferWriter<T> and ReadOnlySequence<T> were ever intended to address. I wonder why this would be better than sparse arrays by themselves.

ReadOnlySequence<T> as a struct doesn't have support for sparse arrays, so to represent huge amounts of 'empty space' you'd have to actually allocate huge arrays, or repeatedly use smaller arrays, where each repeat still allocates a tracking object.

[DaZombieKiller]

If sparse arrays are out of scope for IBufferWriter<T> and (ReadOnly)Sequence<T> then that's fine, I'll likely just end up using sparse arrays directly in that case. I appreciate you taking the time to address this.

I'll leave this issue open so that it can track a potential BCL implementation of Sequence<T> in the future, assuming there are plans to do something of the sort.