From ace0b217f434c47052fefb4b42dd6069d382ff43 Mon Sep 17 00:00:00 2001 From: Ben Adams Date: Fri, 8 Mar 2019 02:06:49 +0000 Subject: [PATCH] Shrink ReadOnlySequence by 8 bytes (dotnet/corefx#35860) * Shrink ReadOnlySequence by 8 bytes * nit * Unwrap Start, End when used interally Commit migrated from https://github.com/dotnet/corefx/commit/fd88c5df4bde4ef56522a1cd81da1ff69c92edc4 --- .../src/System/Buffers/BuffersExtensions.cs | 2 +- .../src/System/Buffers/ReadOnlySequence.Helpers.cs | 146 ++++++++++++++------- .../src/System/Buffers/ReadOnlySequence.cs | 109 +++++++++------ 3 files changed, 171 insertions(+), 86 deletions(-) diff --git a/src/libraries/System.Memory/src/System/Buffers/BuffersExtensions.cs b/src/libraries/System.Memory/src/System/Buffers/BuffersExtensions.cs index b8c5f8d..0a0feaa 100644 --- a/src/libraries/System.Memory/src/System/Buffers/BuffersExtensions.cs +++ b/src/libraries/System.Memory/src/System/Buffers/BuffersExtensions.cs @@ -22,7 +22,7 @@ namespace System.Buffers int index = source.First.Span.IndexOf(value); if (index != -1) { - return source.GetPosition(index); + return source.Seek(index); } return null; diff --git a/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.Helpers.cs b/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.Helpers.cs index 41d9840..8c396df 100644 --- a/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.Helpers.cs +++ b/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.Helpers.cs @@ -24,9 +24,9 @@ namespace System.Buffers } SequenceType type = GetSequenceType(); - object endObject = _sequenceEnd.GetObject(); + object endObject = _endObject; int startIndex = GetIndex(position); - int endIndex = GetIndex(_sequenceEnd); + int endIndex = GetIndex(_endInteger); if (type == SequenceType.MultiSegment) { @@ -81,15 +81,15 @@ namespace System.Buffers [MethodImpl(MethodImplOptions.AggressiveInlining)] private ReadOnlyMemory GetFirstBuffer() { - object startObject = _sequenceStart.GetObject(); + object startObject = _startObject; if (startObject == null) return default; - int startIndex = _sequenceStart.GetInteger(); - int endIndex = _sequenceEnd.GetInteger(); + int startIndex = _startInteger; + int endIndex = _endInteger; - bool isMultiSegment = startObject != _sequenceEnd.GetObject(); + bool isMultiSegment = startObject != _endObject; // The highest bit of startIndex and endIndex are used to infer the sequence type // The code below is structured this way for performance reasons and is equivalent to the following: @@ -125,8 +125,8 @@ namespace System.Buffers if (isMultiSegment) ThrowHelper.ThrowInvalidOperationException_EndPositionNotReached(); - int startIndex = _sequenceStart.GetInteger(); - int endIndex = _sequenceEnd.GetInteger(); + int startIndex = _startInteger; + int endIndex = _endInteger; Debug.Assert(startIndex < 0 || endIndex < 0); @@ -155,13 +155,48 @@ namespace System.Buffers } [MethodImpl(MethodImplOptions.AggressiveInlining)] - private SequencePosition Seek(in SequencePosition start, in SequencePosition end, long offset, ExceptionArgument argument) + internal SequencePosition Seek(long offset, ExceptionArgument exceptionArgument = ExceptionArgument.offset) { - int startIndex = GetIndex(start); - int endIndex = GetIndex(end); + object startObject = _startObject; + object endObject = _endObject; + int startIndex = GetIndex(_startInteger); + int endIndex = GetIndex(_endInteger); + + if (startObject != endObject) + { + Debug.Assert(startObject != null); + var startSegment = (ReadOnlySequenceSegment)startObject; + + int currentLength = startSegment.Memory.Length - startIndex; + + // Position in start segment, defer to single segment seek + if (currentLength > offset) + goto IsSingleSegment; + + if (currentLength < 0) + ThrowHelper.ThrowArgumentOutOfRangeException_PositionOutOfRange(); + + // End of segment. Move to start of next. + return SeekMultiSegment(startSegment.Next, endObject, endIndex, offset - currentLength, exceptionArgument); + } + + Debug.Assert(startObject == endObject); + + if (endIndex - startIndex < offset) + ThrowHelper.ThrowArgumentOutOfRangeException(exceptionArgument); + + // Single segment Seek + IsSingleSegment: + return new SequencePosition(startObject, startIndex + (int)offset); + } + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private SequencePosition Seek(in SequencePosition start, long offset) + { object startObject = start.GetObject(); - object endObject = end.GetObject(); + object endObject = _endObject; + int startIndex = GetIndex(start); + int endIndex = GetIndex(_endInteger); if (startObject != endObject) { @@ -178,13 +213,13 @@ namespace System.Buffers ThrowHelper.ThrowArgumentOutOfRangeException_PositionOutOfRange(); // End of segment. Move to start of next. - return SeekMultiSegment(startSegment.Next, endObject, endIndex, offset - currentLength, argument); + return SeekMultiSegment(startSegment.Next, endObject, endIndex, offset - currentLength, ExceptionArgument.offset); } Debug.Assert(startObject == endObject); if (endIndex - startIndex < offset) - ThrowHelper.ThrowArgumentOutOfRangeException(argument); + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.offset); // Single segment Seek IsSingleSegment: @@ -221,11 +256,12 @@ namespace System.Buffers private void BoundsCheck(in SequencePosition position) { uint sliceStartIndex = (uint)GetIndex(position); - uint startIndex = (uint)GetIndex(_sequenceStart); - uint endIndex = (uint)GetIndex(_sequenceEnd); - object startObject = _sequenceStart.GetObject(); - object endObject = _sequenceEnd.GetObject(); + object startObject = _startObject; + object endObject = _endObject; + + uint startIndex = (uint)GetIndex(_startInteger); + uint endIndex = (uint)GetIndex(_endInteger); // Single-Segment Sequence if (startObject == endObject) @@ -252,11 +288,11 @@ namespace System.Buffers private void BoundsCheck(uint sliceStartIndex, object sliceStartObject, uint sliceEndIndex, object sliceEndObject) { - uint startIndex = (uint)GetIndex(_sequenceStart); - uint endIndex = (uint)GetIndex(_sequenceEnd); + object startObject = _startObject; + object endObject = _endObject; - object startObject = _sequenceStart.GetObject(); - object endObject = _sequenceEnd.GetObject(); + uint startIndex = (uint)GetIndex(_startInteger); + uint endIndex = (uint)GetIndex(_endInteger); // Single-Segment Sequence if (startObject == endObject) @@ -327,13 +363,16 @@ namespace System.Buffers // start >> 31 = 0, end >> 31 = -1 // 2 * 0 + (-1) = -1, result = (SequenceType)1 - return (SequenceType)(-(2 * (_sequenceStart.GetInteger() >> 31) + (_sequenceEnd.GetInteger() >> 31))); + return (SequenceType)(-(2 * (_startInteger >> 31) + (_endInteger >> 31))); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static int GetIndex(in SequencePosition position) => position.GetInteger() & ReadOnlySequence.IndexBitMask; [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int GetIndex(int Integer) => Integer & ReadOnlySequence.IndexBitMask; + + [MethodImpl(MethodImplOptions.AggressiveInlining)] private ReadOnlySequence SliceImpl(in SequencePosition start, in SequencePosition end) { // In this method we reset high order bits from indices @@ -342,19 +381,34 @@ namespace System.Buffers return new ReadOnlySequence( start.GetObject(), - GetIndex(start) | (_sequenceStart.GetInteger() & ReadOnlySequence.FlagBitMask), + GetIndex(start) | (_startInteger & ReadOnlySequence.FlagBitMask), end.GetObject(), - GetIndex(end) | (_sequenceEnd.GetInteger() & ReadOnlySequence.FlagBitMask) + GetIndex(end) | (_endInteger & ReadOnlySequence.FlagBitMask) + ); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private ReadOnlySequence SliceImpl(in SequencePosition start) + { + // In this method we reset high order bits from indices + // of positions that were passed in + // and apply type bits specific for current ReadOnlySequence type + + return new ReadOnlySequence( + start.GetObject(), + GetIndex(start) | (_startInteger & ReadOnlySequence.FlagBitMask), + _endObject, + _endInteger ); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private long GetLength() { - int startIndex = GetIndex(_sequenceStart); - int endIndex = GetIndex(_sequenceEnd); - object startObject = _sequenceStart.GetObject(); - object endObject = _sequenceEnd.GetObject(); + object startObject = _startObject; + object endObject = _endObject; + int startIndex = GetIndex(_startInteger); + int endIndex = GetIndex(_endInteger); if (startObject != endObject) { @@ -370,7 +424,7 @@ namespace System.Buffers internal bool TryGetReadOnlySequenceSegment(out ReadOnlySequenceSegment startSegment, out int startIndex, out ReadOnlySequenceSegment endSegment, out int endIndex) { - object startObject = _sequenceStart.GetObject(); + object startObject = _startObject; // Default or not MultiSegment if (startObject == null || GetSequenceType() != SequenceType.MultiSegment) @@ -382,12 +436,12 @@ namespace System.Buffers return false; } - Debug.Assert(_sequenceEnd.GetObject() != null); + Debug.Assert(_endObject != null); startSegment = (ReadOnlySequenceSegment)startObject; - startIndex = GetIndex(_sequenceStart); - endSegment = (ReadOnlySequenceSegment)_sequenceEnd.GetObject(); - endIndex = GetIndex(_sequenceEnd); + startIndex = GetIndex(_startInteger); + endSegment = (ReadOnlySequenceSegment)_endObject; + endIndex = GetIndex(_endInteger); return true; } @@ -399,10 +453,10 @@ namespace System.Buffers return false; } - Debug.Assert(_sequenceStart.GetObject() != null); + Debug.Assert(_startObject != null); - int startIndex = GetIndex(_sequenceStart); - segment = new ArraySegment((T[])_sequenceStart.GetObject(), startIndex, GetIndex(_sequenceEnd) - startIndex); + int startIndex = GetIndex(_startInteger); + segment = new ArraySegment((T[])_startObject, startIndex, GetIndex(_endInteger) - startIndex); return true; } @@ -416,11 +470,11 @@ namespace System.Buffers return false; } - Debug.Assert(_sequenceStart.GetObject() != null); + Debug.Assert(_startObject != null); - start = GetIndex(_sequenceStart); - length = GetIndex(_sequenceEnd) - start; - text = (string)_sequenceStart.GetObject(); + start = GetIndex(_startInteger); + length = GetIndex(_endInteger) - start; + text = (string)_startObject; return true; } @@ -486,15 +540,13 @@ namespace System.Buffers { first = default; next = default; - SequencePosition start = Start; - int startIndex = start.GetInteger(); - object startObject = start.GetObject(); + object startObject = _startObject; + int startIndex = _startInteger; if (startObject != null) { - SequencePosition end = End; - int endIndex = end.GetInteger(); - bool hasMultipleSegments = startObject != end.GetObject(); + bool hasMultipleSegments = startObject != _endObject; + int endIndex = _endInteger; if (startIndex >= 0) { diff --git a/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.cs b/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.cs index e7ab263..319189f 100644 --- a/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.cs +++ b/src/libraries/System.Memory/src/System/Buffers/ReadOnlySequence.cs @@ -16,8 +16,11 @@ namespace System.Buffers [DebuggerDisplay("{ToString(),raw}")] public readonly partial struct ReadOnlySequence { - private readonly SequencePosition _sequenceStart; - private readonly SequencePosition _sequenceEnd; + // The data is essentially two SequencePositions, however the Start and End SequencePositions are deconstructed to improve packing. + private readonly object _startObject; + private readonly object _endObject; + private readonly int _startInteger; + private readonly int _endInteger; /// /// Returns empty @@ -40,7 +43,7 @@ namespace System.Buffers public bool IsSingleSegment { [MethodImpl(MethodImplOptions.AggressiveInlining)] - get => _sequenceStart.GetObject() == _sequenceEnd.GetObject(); + get => _startObject == _endObject; } /// @@ -51,12 +54,20 @@ namespace System.Buffers /// /// A position to the start of the . /// - public SequencePosition Start => _sequenceStart; + public SequencePosition Start + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + get => new SequencePosition(_startObject, _startInteger); + } /// /// A position to the end of the /// - public SequencePosition End => _sequenceEnd; + public SequencePosition End + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + get => new SequencePosition(_endObject, _endInteger); + } [MethodImpl(MethodImplOptions.AggressiveInlining)] private ReadOnlySequence(object startSegment, int startIndexAndFlags, object endSegment, int endIndexAndFlags) @@ -67,8 +78,10 @@ namespace System.Buffers Debug.Assert((startSegment != null && endSegment != null) || (startSegment == null && endSegment == null && startIndexAndFlags == 0 && endIndexAndFlags == 0)); - _sequenceStart = new SequencePosition(startSegment, startIndexAndFlags); - _sequenceEnd = new SequencePosition(endSegment, endIndexAndFlags); + _startObject = startSegment; + _endObject = endSegment; + _startInteger = startIndexAndFlags; + _endInteger = endIndexAndFlags; } /// @@ -85,8 +98,10 @@ namespace System.Buffers (startSegment == endSegment && endIndex < startIndex)) ThrowHelper.ThrowArgumentValidationException(startSegment, startIndex, endSegment); - _sequenceStart = new SequencePosition(startSegment, ReadOnlySequence.SegmentToSequenceStart(startIndex)); - _sequenceEnd = new SequencePosition(endSegment, ReadOnlySequence.SegmentToSequenceEnd(endIndex)); + _startObject = startSegment; + _endObject = endSegment; + _startInteger = ReadOnlySequence.SegmentToSequenceStart(startIndex); + _endInteger = ReadOnlySequence.SegmentToSequenceEnd(endIndex); } /// @@ -97,8 +112,10 @@ namespace System.Buffers if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); - _sequenceStart = new SequencePosition(array, ReadOnlySequence.ArrayToSequenceStart(0)); - _sequenceEnd = new SequencePosition(array, ReadOnlySequence.ArrayToSequenceEnd(array.Length)); + _startObject = array; + _endObject = array; + _startInteger = ReadOnlySequence.ArrayToSequenceStart(0); + _endInteger = ReadOnlySequence.ArrayToSequenceEnd(array.Length); } /// @@ -111,8 +128,10 @@ namespace System.Buffers (uint)length > (uint)(array.Length - start)) ThrowHelper.ThrowArgumentValidationException(array, start); - _sequenceStart = new SequencePosition(array, ReadOnlySequence.ArrayToSequenceStart(start)); - _sequenceEnd = new SequencePosition(array, ReadOnlySequence.ArrayToSequenceEnd(start + length)); + _startObject = array; + _endObject = array; + _startInteger = ReadOnlySequence.ArrayToSequenceStart(start); + _endInteger = ReadOnlySequence.ArrayToSequenceEnd(start + length); } /// @@ -123,30 +142,38 @@ namespace System.Buffers { if (MemoryMarshal.TryGetMemoryManager(memory, out MemoryManager manager, out int index, out int length)) { - _sequenceStart = new SequencePosition(manager, ReadOnlySequence.MemoryManagerToSequenceStart(index)); - _sequenceEnd = new SequencePosition(manager, ReadOnlySequence.MemoryManagerToSequenceEnd(length)); + _startObject = manager; + _endObject = manager; + _startInteger = ReadOnlySequence.MemoryManagerToSequenceStart(index); + _endInteger = ReadOnlySequence.MemoryManagerToSequenceEnd(length); } else if (MemoryMarshal.TryGetArray(memory, out ArraySegment segment)) { T[] array = segment.Array; int start = segment.Offset; - _sequenceStart = new SequencePosition(array, ReadOnlySequence.ArrayToSequenceStart(start)); - _sequenceEnd = new SequencePosition(array, ReadOnlySequence.ArrayToSequenceEnd(start + segment.Count)); + _startObject = array; + _endObject = array; + _startInteger = ReadOnlySequence.ArrayToSequenceStart(start); + _endInteger = ReadOnlySequence.ArrayToSequenceEnd(start + segment.Count); } else if (typeof(T) == typeof(char)) { if (!MemoryMarshal.TryGetString((ReadOnlyMemory)(object)memory, out string text, out int start, out length)) ThrowHelper.ThrowInvalidOperationException(); - _sequenceStart = new SequencePosition(text, ReadOnlySequence.StringToSequenceStart(start)); - _sequenceEnd = new SequencePosition(text, ReadOnlySequence.StringToSequenceEnd(start + length)); + _startObject = text; + _endObject = text; + _startInteger = ReadOnlySequence.StringToSequenceStart(start); + _endInteger = ReadOnlySequence.StringToSequenceEnd(start + length); } else { // Should never be reached ThrowHelper.ThrowInvalidOperationException(); - _sequenceStart = default; - _sequenceEnd = default; + _startObject = null; + _endObject = null; + _startInteger = 0; + _endInteger = 0; } } @@ -163,11 +190,11 @@ namespace System.Buffers SequencePosition begin; SequencePosition end; - int startIndex = GetIndex(_sequenceStart); - int endIndex = GetIndex(_sequenceEnd); + int startIndex = GetIndex(_startInteger); + int endIndex = GetIndex(_endInteger); - object startObject = _sequenceStart.GetObject(); - object endObject = _sequenceEnd.GetObject(); + object startObject = _startObject; + object endObject = _endObject; if (startObject != endObject) { @@ -238,11 +265,11 @@ namespace System.Buffers uint sliceEndIndex = (uint)GetIndex(end); object sliceEndObject = end.GetObject(); - uint startIndex = (uint)GetIndex(_sequenceStart); - object startObject = _sequenceStart.GetObject(); + uint startIndex = (uint)GetIndex(_startInteger); + object startObject = _startObject; - uint endIndex = (uint)GetIndex(_sequenceEnd); - object endObject = _sequenceEnd.GetObject(); + uint endIndex = (uint)GetIndex(_endInteger); + object endObject = _endObject; // Single-Segment Sequence if (startObject == endObject) @@ -308,11 +335,11 @@ namespace System.Buffers uint sliceStartIndex = (uint)GetIndex(start); object sliceStartObject = start.GetObject(); - uint startIndex = (uint)GetIndex(_sequenceStart); - object startObject = _sequenceStart.GetObject(); + uint startIndex = (uint)GetIndex(_startInteger); + object startObject = _startObject; - uint endIndex = (uint)GetIndex(_sequenceEnd); - object endObject = _sequenceEnd.GetObject(); + uint endIndex = (uint)GetIndex(_endInteger); + object endObject = _endObject; // Single-Segment Sequence if (startObject == endObject) @@ -414,7 +441,7 @@ namespace System.Buffers public ReadOnlySequence Slice(SequencePosition start) { BoundsCheck(start); - return SliceImpl(start, _sequenceEnd); + return SliceImpl(start); } /// @@ -429,8 +456,8 @@ namespace System.Buffers if (start == 0) return this; - SequencePosition begin = Seek(_sequenceStart, _sequenceEnd, start, ExceptionArgument.start); - return SliceImpl(begin, _sequenceEnd); + SequencePosition begin = Seek(start, ExceptionArgument.start); + return SliceImpl(begin); } /// @@ -463,7 +490,13 @@ namespace System.Buffers /// /// Returns a new at an from the start of the sequence. /// - public SequencePosition GetPosition(long offset) => GetPosition(offset, _sequenceStart); + public SequencePosition GetPosition(long offset) + { + if (offset < 0) + ThrowHelper.ThrowArgumentOutOfRangeException_OffsetOutOfRange(); + + return Seek(offset); + } /// /// Returns a new at an from the @@ -473,7 +506,7 @@ namespace System.Buffers if (offset < 0) ThrowHelper.ThrowArgumentOutOfRangeException_OffsetOutOfRange(); - return Seek(origin, _sequenceEnd, offset, ExceptionArgument.offset); + return Seek(origin, offset); } /// -- 2.7.4