Feature Request: ReadOnlySequence<T>.GetPosition(offset, origin) should support negative offsets.

[thargy]

Currently calling ReadOnlySequence<T>.GetPosition(offset, origin) with a negative offset results in an ArgumentOutOfRangeException.

Allowing negative offset's would allow code such as:

// Get the last element in the sequence.
sequence.GetPosition(-1, sequence.End);

(Raised at request of @pakrym, see this comment)

[davidfowl]

It’ll be inefficient for multi-segmented backed sequences since it’s a singly linked list.

[thargy]

It’ll be inefficient for multi-segmented backed sequences since it’s a singly linked list.

Very true, though in many use cases I suspect it will not need to backtrack more than one segment, and will most commonly be able to return a result in the origin's own segment; as the most common negative offset will be -1. In it's simplest form it can be implemented as GetPosition(Origin position - offset) which requires a full scan to get the origin's position and a second scan to get the actual position, so is still O(n). This can be optimised when the origin lies in the first segment and when the offset lies in the origin's segments (two extremely common cases).

[ahsonkhan]

Have you looked at the Rewind API on the new SequenceReader? https://github.com/dotnet/corefx/blob/3172386e3e6f268b1811a831c6890665c3154f8a/src/System.Memory/src/System/Buffers/SequenceReader.cs#L151

It captures the common cases you mentioned quite well (since we can avoid the sequence walk), and generally would be called rarely anyway. I am not sure if we should provide such functionality on the ReadonlySequence itself since it would (probably) make GetPosition slower. For more meaningful higher-level workloads (parsing data, etc.), SequenceReader should be sufficient which is why we could justify introducing "backwards" lookup there.

Do you have a scenario that requires ReadOnlySequence (and negative offsets) that SequenceReader doesn't fit for? That said, we should try supporting negative offsets here and measure the regression as a data point.

API review notes/video where we discuss SequenceReader: https://github.com/dotnet/apireviews/tree/master/2018/System.Buffers.SequenceReader

[thargy]

Have you looked at the Rewind API on the new SequenceReader?

I think that was only committed a couple of weeks after this issue, so I didn't notice it; however it does pretty much what I suggested already, noticing that if the current index in the current span is greater than, or equal to the offset then it is a trivial operation, otherwise it needs to rescan from the start.

I am not sure if we should provide such functionality on the ReadonlySequence itself since it would (probably) make GetPosition slower.

You will notice that GetPosition already checks for negative values here, instead of throwing an exception (yuck!), it could always call a private method for this 'edge' case to provide Rewind functionality directly. As such, it is unlikely that it will slow down the normal case by adding this functionality (to be proved with benchmarking of course).

Do you have a scenario that requires ReadOnlySequence (and negative offsets) that SequenceReader doesn't fit for? That said, we should try supporting negative offsets here and measure the regression as a data point.

It's really about discoverability and expectation. There's a method that takes a signed offset and origin. An experienced .NET dev is likely to assume that negative offsets would therefore be supported (if there were no origin it wouldn't be implied). This expectation is set by similar methods such as Stream.Seek which do support negatives.

Allowing negatives will make callers more able to avoid an additinoal if check. In the case where caller needs to support moving forward or backwards, it would need to check whether the input is positive or negative (or use a boolean, etc.) then call the relevant method on SequenceReader (either Advance or Reverse). Reverse then rechecks the index to ensure it's not negative. If SequenceReader used a more consistent Seek instead of 2 seperate methods, this would be mitigated somewhat, but there's already a GetPosition on the sequence itself, so why aren't we just using that?

Unless there are provable performance implications to the 'common case' of positive offsets in allowing a negative offset then it would be my contention that it is far superior to avoid another unnecessary exception and support negative offsets in GetPosition directly.

[davidfowl]

I'm not opposed to this.

Unless there are provable performance implications to the 'common case' of positive offsets in allowing a negative offset then it would be my contention that it is far superior to avoid another unnecessary exception and support negative offsets in GetPosition directly.

This would be part of the PR. @thargy do you have time to prove this out?

[thargy]

This would be part of the PR. @thargy do you have time to prove this out?

My wife an I normally volunteer to cover the Christmas period at work to allow more of my staff to take time off, so I'm going to be pretty swamped over the next few weeks and I'm not immediately set up to run the benchmarks.

I suspect the opptimal implementation will be to use the existing if check to call a private Reverse method, in which case there is no possible reason the forward case (+ve offset) would be impacted as the existing code does the same if followed by a throw helper method so the IL size won't change and the +ve path remains identical.

The main benefit of benchmarking will be to see the performance of the negative path, but we already accept this is a less performant use case and the accompanying documentation should point out the implication of calling with a negative offset is that it can be unperformant if the offset moves the position to the preceeding chunk (it being a forward linked list).

The performance of a negative offset will be equivalent to either very quick if in the same chunk (equivalent, if not identical, to a positive offset in the same chunk) or identical to a forward seek to the new position from the beginning of the sequence.

[ahsonkhan]

You will notice that GetPosition already checks for negative values here, instead of throwing an exception (yuck!), it could always call a private method for this 'edge' case to provide Rewind functionality directly. As such, it is unlikely that it will slow down the normal case by adding this functionality (to be proved with benchmarking of course).

I suspect the opptimal implementation will be to use the existing if check to call a private Reverse method, in which case there is no possible reason the forward case (+ve offset) would be impacted as the existing code does the same if followed by a throw helper method so the IL size won't change and the +ve path remains identical.

Unfortunately, it isn't that straightforward :(

The method currently gets inlined by the JIT and adding a method call would no longer make it a candidate for inlining. The JIT is able to infer (at least as far as I know) that the throw code path never returns and is able to optimize the method much more. Adding a method call would end up causing a ~50% regression. Even if we were to explicitly mark the method as AggressiveInlining now, we would still see a ~30% regression since the disassembly is larger now.

The only way to get the performance to match your expectations would be to mark the method as NoInlining (and now there is barely any performance difference between adding a method call or just throwing). However, that means we would end up with the the 50%+ regression anyway. This is why I previously said "it would (probably) make GetPosition slower".

Disassembly difference between current and potential change: https://www.diffchecker.com/NLd8gvIn

cc @dotnet/jit-contrib

Unless there are provable performance implications to the 'common case' of positive offsets in allowing a negative offset then it would be my contention that it is far superior to avoid another unnecessary exception and support negative offsets in GetPosition directly.

Let's say we do something like this (where SeekNegative is explicitly marked as NoInlining):

public SequencePosition GetPosition(long offset, SequencePosition origin)
{
    if (offset < 0)
        ThrowHelper.ThrowArgumentOutOfRangeException_OffsetOutOfRange();

    return Seek(origin, _sequenceEnd, offset, ExceptionArgument.offset);
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public SequencePosition GetPosition_new(long offset, SequencePosition origin)
{
    if (offset < 0)
        return SeekNegative(origin, _sequenceEnd, offset, ExceptionArgument.offset);

    return Seek(origin, _sequenceEnd, offset, ExceptionArgument.offset);
}

Here are some results.

BenchmarkDotNet=v0.11.3, OS=Windows 10.0.17763.194 (1809/October2018Update/Redstone5)
Intel Core i7-6700 CPU 3.40GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.0.100-preview-009825
  [Host] : .NET Core 3.0.0-preview-27206-02 (CoreCLR 4.6.27204.02, CoreFX 4.7.18.60501), 64bit RyuJIT
  Core   : .NET Core 3.0.0-preview-27206-02 (CoreCLR 4.6.27204.02, CoreFX 4.7.18.60501), 64bit RyuJIT

Job=Core  EnvironmentVariables=COMPlus_TieredCompilation=0  Runtime=Core  
Toolchain=.NET Core 3.0  

Method	Mean	Error	StdDev	Ratio
GetPosition	30.74 ns	0.3645 ns	0.3231 ns	1.00
GetPositionNew	56.45 ns	0.8405 ns	0.7451 ns	1.84

Marking as AggressiveInlining explicitly

Method	Mean	Error	StdDev	Ratio	RatioSD
GetPosition	31.66 ns	0.6538 ns	1.1451 ns	1.00	0.00
GetPositionNew	44.30 ns	1.0094 ns	0.9442 ns	1.36	0.05

Now, we may be able to address some of the JIT issues here OR try to implement it more creatively, but it isn't a straightforward implementation change as one would expect and there is definitely a risk of regressing performance for the common case. What are your thoughts? Should we still do it?

Diff of disassembly for the whole benchmark: https://www.diffchecker.com/h1ZcYNSN

Benchmark itself:

[Benchmark(Baseline = true)]
public SequencePosition GetPosition()
{
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    buffer.GetPosition(offset);
    return buffer.GetPosition(offset);
}

[Benchmark]
public SequencePosition GetPositionNew()
{
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    buffer.GetPosition_new(offset);
    return buffer.GetPosition_new(offset);
}

[thargy]

Sorry for the delay @ahsonkhan, I didn't notice you're excellent response! I never realised the JIT could optimise for the throw condition, particularly as the throw is behind a static method invocation! I always thought throws made things worse. Or is it more that the method called never returns?

There is an 'argument' that the fact GetPosition can throw will mean that consumers are more likely to wrap it in a try...catch, whereas if the method is changed to never throw (returns an EOF SequencePosition, or similar for OOB values) that would mitigate this issue as try...GetPosition...catch would probably be slower then GetPositionNew. Not the strongest counter argument I admit.

This then comes down to the old trade off between performance and maintainability/reliability. There's no 'right' answer to that question. The only easy way forward is to find a performant way for negative to be supported, if that can't be found then it's really up to you design committee.

Out of interest is SeekNegative aggressively inlined or inlinable, and does that have an impact? I also noticed you're still passing around ExceptionAgument.offset, there might be performance gains to be made by removing bound checks/exception handling further into the code that offset the loss.

[AndyAyersMS]

I would like to see this benchmarked as it is actually used somewhere.

I worry that benchmarking GetPosition this way via repeated back to back calls may have introduced some artifacts. The fact that this method returns a struct coupled with inlining, the two internal call sites, and the repeated calls with unused results expose some jit issues in effectively using the stack for temporary structs. You can see aspects of this with the much larger stack frame in the "new" case (0x1A8 -> 0x2E8) and corresponding larger offsets for locals. In actual use cases the amount of stack growth should be smaller.

[ghost]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.

[thargy]

Is this being abandoned then?