From 311c3a096aea7a6b6bc038d6c1ee334c5a4855b6 Mon Sep 17 00:00:00 2001 From: Stephen Toub Date: Fri, 13 Jul 2018 19:58:11 -0400 Subject: [PATCH] Factor out large generic additions in System.Linq for uap build (dotnet/corefx#31025) * Factor out large generic additions in System.Linq New generic types in System.Linq are causing significant size-on-disk increases in AOT builds. This change addresses some of them: - The many implementations of IPartition and IIListProvider are causing significant binary size increases for AOT. I've factored out the majority of those large changes to only be used in a netcoreapp build, not in a uap build. There are still code paths that test whether an object is IPartition or IIListProvider, but there are no types now in the UAP build that implement them. - As part of this, I replaced several places where `EmptyPartition.Instance` was being used directly to implement an `IEnumerable`, changed them to use `Enumerable.Empty`, and then changed `Enumerable.Empty` so that on netcoreapp it returns `EmptyPartition.Instance`, and on uap it returns `Array.Empty`. This also means now that code paths lighting-up on partitions will also light-up on `Enumerable.Empty`. It also means that I changed the empty partition's `IEnumerator.Reset` method to be a nop instead of throwing, to match the same behavior as array's `IEnumerator.Reset`. - LargeArrayBuilder uses T[][], which introduces lots of new array types and corresponding interface instantiations, helper types, etc. I've specialized LargeArrayBuilder in the UAP build to just be a thin wrapper around ArrayBuilder; we still end up with unnecessary instantiations of LargeArrayBuilder, but they're relatively small, and it saves everything to do with those T[][] instantiations. * Rename files from netcoreapp/uap to SpeedOpt/SizeOpt * Fix tests for Reset-becoming-nop change Commit migrated from https://github.com/dotnet/corefx/commit/143df51926f2ad397fef9c9ca7ede88e2721e801 --- .../src/System/Collections/Generic/ArrayBuilder.cs | 8 +- .../Generic/LargeArrayBuilder.SizeOpt.cs | 49 ++ .../Generic/LargeArrayBuilder.SpeedOpt.cs | 345 ++++++++++ .../Collections/Generic/LargeArrayBuilder.cs | 337 ---------- src/libraries/Common/tests/Common.Tests.csproj | 3 + .../Collections/Generic/ArrayBuilderTests.cs | 27 - .../tests/QueryOperators/GetEnumeratorTests.cs | 12 +- src/libraries/System.Linq/src/System.Linq.csproj | 36 +- .../src/System/Linq/AppendPrepend.SpeedOpt.cs | 214 +++++++ .../System.Linq/src/System/Linq/AppendPrepend.cs | 199 +----- .../System.Linq/src/System/Linq/Concat.SpeedOpt.cs | 222 +++++++ .../System.Linq/src/System/Linq/Concat.cs | 207 +----- .../src/System/Linq/DefaultIfEmpty.SpeedOpt.cs | 47 ++ .../System.Linq/src/System/Linq/DefaultIfEmpty.cs | 35 +- .../src/System/Linq/Distinct.SpeedOpt.cs | 27 + .../System.Linq/src/System/Linq/Distinct.cs | 15 +- .../src/System/Linq/Enumerable.SizeOpt.cs | 13 + .../src/System/Linq/Enumerable.SpeedOpt.cs | 13 + .../System.Linq/src/System/Linq/Enumerable.cs | 2 - .../src/System/Linq/Grouping.SpeedOpt.cs | 68 ++ .../System.Linq/src/System/Linq/Grouping.cs | 56 +- .../System.Linq/src/System/Linq/IIListProvider.cs | 34 + .../System.Linq/src/System/Linq/IPartition.cs | 48 ++ .../System.Linq/src/System/Linq/Lookup.SpeedOpt.cs | 69 ++ .../System.Linq/src/System/Linq/Lookup.cs | 62 +- .../src/System/Linq/OrderedEnumerable.SpeedOpt.cs | 250 ++++++++ .../src/System/Linq/OrderedEnumerable.cs | 240 +------ .../Linq/{Partition.cs => Partition.SpeedOpt.cs} | 73 +-- .../System.Linq/src/System/Linq/Range.SpeedOpt.cs | 90 +++ src/libraries/System.Linq/src/System/Linq/Range.cs | 80 +-- .../System.Linq/src/System/Linq/Repeat.SpeedOpt.cs | 85 +++ .../System.Linq/src/System/Linq/Repeat.cs | 75 +-- .../src/System/Linq/Reverse.SpeedOpt.cs | 52 ++ .../System.Linq/src/System/Linq/Reverse.cs | 40 +- .../System.Linq/src/System/Linq/Select.SpeedOpt.cs | 692 +++++++++++++++++++++ .../System.Linq/src/System/Linq/Select.cs | 681 +------------------- .../src/System/Linq/SelectMany.SpeedOpt.cs | 74 +++ .../System.Linq/src/System/Linq/SelectMany.cs | 62 +- .../System.Linq/src/System/Linq/Skip.SizeOpt.cs | 23 + .../System.Linq/src/System/Linq/Skip.SpeedOpt.cs | 16 + src/libraries/System.Linq/src/System/Linq/Skip.cs | 7 +- .../System.Linq/src/System/Linq/Take.SizeOpt.cs | 23 + .../System.Linq/src/System/Linq/Take.SpeedOpt.cs | 16 + src/libraries/System.Linq/src/System/Linq/Take.cs | 28 +- .../System.Linq/src/System/Linq/Union.SpeedOpt.cs | 35 ++ src/libraries/System.Linq/src/System/Linq/Union.cs | 23 +- .../System.Linq/src/System/Linq/Where.SpeedOpt.cs | 365 +++++++++++ src/libraries/System.Linq/src/System/Linq/Where.cs | 350 +---------- src/libraries/System.Linq/tests/EmptyEnumerable.cs | 25 +- .../System.Linq/tests/EmptyPartitionTests.cs | 17 +- .../System.Linq/tests/OrderedSubsetting.cs | 2 +- src/libraries/System.Linq/tests/RangeTests.cs | 4 +- src/libraries/System.Linq/tests/SelectManyTests.cs | 2 +- src/libraries/System.Linq/tests/TakeTests.cs | 2 +- 54 files changed, 2989 insertions(+), 2591 deletions(-) create mode 100644 src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SizeOpt.cs create mode 100644 src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/AppendPrepend.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Concat.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Distinct.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Enumerable.SizeOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Enumerable.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Grouping.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/IIListProvider.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/IPartition.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Lookup.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.SpeedOpt.cs rename src/libraries/System.Linq/src/System/Linq/{Partition.cs => Partition.SpeedOpt.cs} (87%) create mode 100644 src/libraries/System.Linq/src/System/Linq/Range.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Repeat.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Reverse.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/SelectMany.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Skip.SizeOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Skip.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Take.SizeOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Take.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Union.SpeedOpt.cs create mode 100644 src/libraries/System.Linq/src/System/Linq/Where.SpeedOpt.cs diff --git a/src/libraries/Common/src/System/Collections/Generic/ArrayBuilder.cs b/src/libraries/Common/src/System/Collections/Generic/ArrayBuilder.cs index 6cedb3b..bd6c2ac 100644 --- a/src/libraries/Common/src/System/Collections/Generic/ArrayBuilder.cs +++ b/src/libraries/Common/src/System/Collections/Generic/ArrayBuilder.cs @@ -37,6 +37,9 @@ namespace System.Collections.Generic /// public int Capacity => _array?.Length ?? 0; + /// Gets the current underlying array. + public T[] Buffer => _array; + /// /// Gets the number of items in the array currently in use. /// @@ -53,11 +56,6 @@ namespace System.Collections.Generic Debug.Assert(index >= 0 && index < _count); return _array[index]; } - set - { - Debug.Assert(index >= 0 && index < _count); - _array[index] = value; - } } /// diff --git a/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SizeOpt.cs b/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SizeOpt.cs new file mode 100644 index 0000000..a613236 --- /dev/null +++ b/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SizeOpt.cs @@ -0,0 +1,49 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Diagnostics; + +namespace System.Collections.Generic +{ + // LargeArrayBuilder.netcoreapp.cs provides a "LargeArrayBuilder" that's meant to help + // avoid allocations and copying while building up an array. But in doing so, it utilizes + // T[][] to store T[]s, which results in significant size increases for AOT builds. To + // address that, this minimal wrapper for ArrayBuilder may be used instead; it's a simple + // passthrough to ArrayBuilder, and thus doesn't incur the size increase due to the T[][]s. + + internal struct LargeArrayBuilder + { + private ArrayBuilder _builder; // mutable struct; do not make this readonly + + public LargeArrayBuilder(bool initialize) : this() + { + // This is a workaround for C# not having parameterless struct constructors yet. + // Once it gets them, replace this with a parameterless constructor. + Debug.Assert(initialize); + } + + public int Count => _builder.Count; + + public void Add(T item) => _builder.Add(item); + + public void AddRange(IEnumerable items) + { + Debug.Assert(items != null); + foreach (T item in items) + { + _builder.Add(item); + } + } + + public void SlowAdd(T item) => _builder.Add(item); + + public T[] ToArray() => _builder.ToArray(); + + public CopyPosition CopyTo(CopyPosition position, T[] array, int arrayIndex, int count) + { + Array.Copy(_builder.Buffer, position.Column, array, arrayIndex, count); + return new CopyPosition(0, position.Column + count); + } + } +} diff --git a/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SpeedOpt.cs b/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SpeedOpt.cs new file mode 100644 index 0000000..7847d93 --- /dev/null +++ b/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.SpeedOpt.cs @@ -0,0 +1,345 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Diagnostics; +using System.Runtime.CompilerServices; + +namespace System.Collections.Generic +{ + /// + /// Helper type for building dynamically-sized arrays while minimizing allocations and copying. + /// + /// The element type. + internal struct LargeArrayBuilder + { + private const int StartingCapacity = 4; + private const int ResizeLimit = 8; + + private readonly int _maxCapacity; // The maximum capacity this builder can have. + private T[] _first; // The first buffer we store items in. Resized until ResizeLimit. + private ArrayBuilder _buffers; // After ResizeLimit * 2, we store previous buffers we've filled out here. + private T[] _current; // Current buffer we're reading into. If _count <= ResizeLimit, this is _first. + private int _index; // Index into the current buffer. + private int _count; // Count of all of the items in this builder. + + /// + /// Constructs a new builder. + /// + /// Pass true. + public LargeArrayBuilder(bool initialize) + : this(maxCapacity: int.MaxValue) + { + // This is a workaround for C# not having parameterless struct constructors yet. + // Once it gets them, replace this with a parameterless constructor. + Debug.Assert(initialize); + } + + /// + /// Constructs a new builder with the specified maximum capacity. + /// + /// The maximum capacity this builder can have. + /// + /// Do not add more than items to this builder. + /// + public LargeArrayBuilder(int maxCapacity) + : this() + { + Debug.Assert(maxCapacity >= 0); + + _first = _current = Array.Empty(); + _maxCapacity = maxCapacity; + } + + /// + /// Gets the number of items added to the builder. + /// + public int Count => _count; + + /// + /// Adds an item to this builder. + /// + /// The item to add. + /// + /// Use if adding to the builder is a bottleneck for your use case. + /// Otherwise, use . + /// + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public void Add(T item) + { + Debug.Assert(_maxCapacity > _count); + + int index = _index; + T[] current = _current; + + // Must be >= and not == to enable range check elimination + if ((uint)index >= (uint)current.Length) + { + AddWithBufferAllocation(item); + } + else + { + current[index] = item; + _index = index + 1; + } + + _count++; + } + + // Non-inline to improve code quality as uncommon path + [MethodImpl(MethodImplOptions.NoInlining)] + private void AddWithBufferAllocation(T item) + { + AllocateBuffer(); + _current[_index++] = item; + } + + /// + /// Adds a range of items to this builder. + /// + /// The sequence to add. + /// + /// It is the caller's responsibility to ensure that adding + /// does not cause the builder to exceed its maximum capacity. + /// + public void AddRange(IEnumerable items) + { + Debug.Assert(items != null); + + using (IEnumerator enumerator = items.GetEnumerator()) + { + T[] destination = _current; + int index = _index; + + // Continuously read in items from the enumerator, updating _count + // and _index when we run out of space. + + while (enumerator.MoveNext()) + { + T item = enumerator.Current; + + if ((uint)index >= (uint)destination.Length) + { + AddWithBufferAllocation(item, ref destination, ref index); + } + else + { + destination[index] = item; + } + + index++; + } + + // Final update to _count and _index. + _count += index - _index; + _index = index; + } + } + + // Non-inline to improve code quality as uncommon path + [MethodImpl(MethodImplOptions.NoInlining)] + private void AddWithBufferAllocation(T item, ref T[] destination, ref int index) + { + _count += index - _index; + _index = index; + AllocateBuffer(); + destination = _current; + index = _index; + _current[index] = item; + } + + /// + /// Copies the contents of this builder to the specified array. + /// + /// The destination array. + /// The index in to start copying to. + /// The number of items to copy. + public void CopyTo(T[] array, int arrayIndex, int count) + { + Debug.Assert(arrayIndex >= 0); + Debug.Assert(count >= 0 && count <= Count); + Debug.Assert(array?.Length - arrayIndex >= count); + + for (int i = 0; count > 0; i++) + { + // Find the buffer we're copying from. + T[] buffer = GetBuffer(index: i); + + // Copy until we satisfy count, or we reach the end of the buffer. + int toCopy = Math.Min(count, buffer.Length); + Array.Copy(buffer, 0, array, arrayIndex, toCopy); + + // Increment variables to that position. + count -= toCopy; + arrayIndex += toCopy; + } + } + + /// + /// Copies the contents of this builder to the specified array. + /// + /// The position in this builder to start copying from. + /// The destination array. + /// The index in to start copying to. + /// The number of items to copy. + /// The position in this builder that was copied up to. + public CopyPosition CopyTo(CopyPosition position, T[] array, int arrayIndex, int count) + { + Debug.Assert(array != null); + Debug.Assert(arrayIndex >= 0); + Debug.Assert(count > 0 && count <= Count); + Debug.Assert(array.Length - arrayIndex >= count); + + // Go through each buffer, which contains one 'row' of items. + // The index in each buffer is referred to as the 'column'. + + /* + * Visual representation: + * + * C0 C1 C2 .. C31 .. C63 + * R0: [0] [1] [2] .. [31] + * R1: [32] [33] [34] .. [63] + * R2: [64] [65] [66] .. [95] .. [127] + */ + + int row = position.Row; + int column = position.Column; + + T[] buffer = GetBuffer(row); + int copied = CopyToCore(buffer, column); + + if (count == 0) + { + return new CopyPosition(row, column + copied).Normalize(buffer.Length); + } + + do + { + buffer = GetBuffer(++row); + copied = CopyToCore(buffer, 0); + } while (count > 0); + + return new CopyPosition(row, copied).Normalize(buffer.Length); + + int CopyToCore(T[] sourceBuffer, int sourceIndex) + { + Debug.Assert(sourceBuffer.Length > sourceIndex); + + // Copy until we satisfy `count` or reach the end of the current buffer. + int copyCount = Math.Min(sourceBuffer.Length - sourceIndex, count); + Array.Copy(sourceBuffer, sourceIndex, array, arrayIndex, copyCount); + + arrayIndex += copyCount; + count -= copyCount; + + return copyCount; + } + } + + /// + /// Retrieves the buffer at the specified index. + /// + /// The index of the buffer. + public T[] GetBuffer(int index) + { + Debug.Assert(index >= 0 && index < _buffers.Count + 2); + + return index == 0 ? _first : + index <= _buffers.Count ? _buffers[index - 1] : + _current; + } + + /// + /// Adds an item to this builder. + /// + /// The item to add. + /// + /// Use if adding to the builder is a bottleneck for your use case. + /// Otherwise, use . + /// + [MethodImpl(MethodImplOptions.NoInlining)] + public void SlowAdd(T item) => Add(item); + + /// + /// Creates an array from the contents of this builder. + /// + public T[] ToArray() + { + if (TryMove(out T[] array)) + { + // No resizing to do. + return array; + } + + array = new T[_count]; + CopyTo(array, 0, _count); + return array; + } + + /// + /// Attempts to transfer this builder into an array without copying. + /// + /// The transferred array, if the operation succeeded. + /// true if the operation succeeded; otherwise, false. + public bool TryMove(out T[] array) + { + array = _first; + return _count == _first.Length; + } + + private void AllocateBuffer() + { + // - On the first few adds, simply resize _first. + // - When we pass ResizeLimit, allocate ResizeLimit elements for _current + // and start reading into _current. Set _index to 0. + // - When _current runs out of space, add it to _buffers and repeat the + // above step, except with _current.Length * 2. + // - Make sure we never pass _maxCapacity in all of the above steps. + + Debug.Assert((uint)_maxCapacity > (uint)_count); + Debug.Assert(_index == _current.Length, $"{nameof(AllocateBuffer)} was called, but there's more space."); + + // If _count is int.MinValue, we want to go down the other path which will raise an exception. + if ((uint)_count < (uint)ResizeLimit) + { + // We haven't passed ResizeLimit. Resize _first, copying over the previous items. + Debug.Assert(_current == _first && _count == _first.Length); + + int nextCapacity = Math.Min(_count == 0 ? StartingCapacity : _count * 2, _maxCapacity); + + _current = new T[nextCapacity]; + Array.Copy(_first, 0, _current, 0, _count); + _first = _current; + } + else + { + Debug.Assert(_maxCapacity > ResizeLimit); + Debug.Assert(_count == ResizeLimit ^ _current != _first); + + int nextCapacity; + if (_count == ResizeLimit) + { + nextCapacity = ResizeLimit; + } + else + { + // Example scenario: Let's say _count == 64. + // Then our buffers look like this: | 8 | 8 | 16 | 32 | + // As you can see, our count will be just double the last buffer. + // Now, say _maxCapacity is 100. We will find the right amount to allocate by + // doing min(64, 100 - 64). The lhs represents double the last buffer, + // the rhs the limit minus the amount we've already allocated. + + Debug.Assert(_count >= ResizeLimit * 2); + Debug.Assert(_count == _current.Length * 2); + + _buffers.Add(_current); + nextCapacity = Math.Min(_count, _maxCapacity - _count); + } + + _current = new T[nextCapacity]; + _index = 0; + } + } + } +} diff --git a/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.cs b/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.cs index 1cc6c6c..8cafdaa 100644 --- a/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.cs +++ b/src/libraries/Common/src/System/Collections/Generic/LargeArrayBuilder.cs @@ -3,7 +3,6 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; -using System.Runtime.CompilerServices; namespace System.Collections.Generic { @@ -61,340 +60,4 @@ namespace System.Collections.Generic /// private string DebuggerDisplay => $"[{Row}, {Column}]"; } - - /// - /// Helper type for building dynamically-sized arrays while minimizing allocations and copying. - /// - /// The element type. - internal struct LargeArrayBuilder - { - private const int StartingCapacity = 4; - private const int ResizeLimit = 8; - - private readonly int _maxCapacity; // The maximum capacity this builder can have. - private T[] _first; // The first buffer we store items in. Resized until ResizeLimit. - private ArrayBuilder _buffers; // After ResizeLimit * 2, we store previous buffers we've filled out here. - private T[] _current; // Current buffer we're reading into. If _count <= ResizeLimit, this is _first. - private int _index; // Index into the current buffer. - private int _count; // Count of all of the items in this builder. - - /// - /// Constructs a new builder. - /// - /// Pass true. - public LargeArrayBuilder(bool initialize) - : this(maxCapacity: int.MaxValue) - { - // This is a workaround for C# not having parameterless struct constructors yet. - // Once it gets them, replace this with a parameterless constructor. - Debug.Assert(initialize); - } - - /// - /// Constructs a new builder with the specified maximum capacity. - /// - /// The maximum capacity this builder can have. - /// - /// Do not add more than items to this builder. - /// - public LargeArrayBuilder(int maxCapacity) - : this() - { - Debug.Assert(maxCapacity >= 0); - - _first = _current = Array.Empty(); - _maxCapacity = maxCapacity; - } - - /// - /// Gets the number of items added to the builder. - /// - public int Count => _count; - - /// - /// Adds an item to this builder. - /// - /// The item to add. - /// - /// Use if adding to the builder is a bottleneck for your use case. - /// Otherwise, use . - /// - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public void Add(T item) - { - Debug.Assert(_maxCapacity > _count); - - int index = _index; - T[] current = _current; - - // Must be >= and not == to enable range check elimination - if ((uint)index >= (uint)current.Length) - { - AddWithBufferAllocation(item); - } - else - { - current[index] = item; - _index = index + 1; - } - - _count++; - } - - // Non-inline to improve code quality as uncommon path - [MethodImpl(MethodImplOptions.NoInlining)] - private void AddWithBufferAllocation(T item) - { - AllocateBuffer(); - _current[_index++] = item; - } - - /// - /// Adds a range of items to this builder. - /// - /// The sequence to add. - /// - /// It is the caller's responsibility to ensure that adding - /// does not cause the builder to exceed its maximum capacity. - /// - public void AddRange(IEnumerable items) - { - Debug.Assert(items != null); - - using (IEnumerator enumerator = items.GetEnumerator()) - { - T[] destination = _current; - int index = _index; - - // Continuously read in items from the enumerator, updating _count - // and _index when we run out of space. - - while (enumerator.MoveNext()) - { - T item = enumerator.Current; - - if ((uint)index >= (uint)destination.Length) - { - AddWithBufferAllocation(item, ref destination, ref index); - } - else - { - destination[index] = item; - } - - index++; - } - - // Final update to _count and _index. - _count += index - _index; - _index = index; - } - } - - // Non-inline to improve code quality as uncommon path - [MethodImpl(MethodImplOptions.NoInlining)] - private void AddWithBufferAllocation(T item, ref T[] destination, ref int index) - { - _count += index - _index; - _index = index; - AllocateBuffer(); - destination = _current; - index = _index; - _current[index] = item; - } - - /// - /// Copies the contents of this builder to the specified array. - /// - /// The destination array. - /// The index in to start copying to. - /// The number of items to copy. - public void CopyTo(T[] array, int arrayIndex, int count) - { - Debug.Assert(arrayIndex >= 0); - Debug.Assert(count >= 0 && count <= Count); - Debug.Assert(array?.Length - arrayIndex >= count); - - for (int i = 0; count > 0; i++) - { - // Find the buffer we're copying from. - T[] buffer = GetBuffer(index: i); - - // Copy until we satisfy count, or we reach the end of the buffer. - int toCopy = Math.Min(count, buffer.Length); - Array.Copy(buffer, 0, array, arrayIndex, toCopy); - - // Increment variables to that position. - count -= toCopy; - arrayIndex += toCopy; - } - } - - /// - /// Copies the contents of this builder to the specified array. - /// - /// The position in this builder to start copying from. - /// The destination array. - /// The index in to start copying to. - /// The number of items to copy. - /// The position in this builder that was copied up to. - public CopyPosition CopyTo(CopyPosition position, T[] array, int arrayIndex, int count) - { - Debug.Assert(array != null); - Debug.Assert(arrayIndex >= 0); - Debug.Assert(count > 0 && count <= Count); - Debug.Assert(array.Length - arrayIndex >= count); - - // Go through each buffer, which contains one 'row' of items. - // The index in each buffer is referred to as the 'column'. - - /* - * Visual representation: - * - * C0 C1 C2 .. C31 .. C63 - * R0: [0] [1] [2] .. [31] - * R1: [32] [33] [34] .. [63] - * R2: [64] [65] [66] .. [95] .. [127] - */ - - int row = position.Row; - int column = position.Column; - - T[] buffer = GetBuffer(row); - int copied = CopyToCore(buffer, column); - - if (count == 0) - { - return new CopyPosition(row, column + copied).Normalize(buffer.Length); - } - - do - { - buffer = GetBuffer(++row); - copied = CopyToCore(buffer, 0); - } while (count > 0); - - return new CopyPosition(row, copied).Normalize(buffer.Length); - - int CopyToCore(T[] sourceBuffer, int sourceIndex) - { - Debug.Assert(sourceBuffer.Length > sourceIndex); - - // Copy until we satisfy `count` or reach the end of the current buffer. - int copyCount = Math.Min(sourceBuffer.Length - sourceIndex, count); - Array.Copy(sourceBuffer, sourceIndex, array, arrayIndex, copyCount); - - arrayIndex += copyCount; - count -= copyCount; - - return copyCount; - } - } - - /// - /// Retrieves the buffer at the specified index. - /// - /// The index of the buffer. - public T[] GetBuffer(int index) - { - Debug.Assert(index >= 0 && index < _buffers.Count + 2); - - return index == 0 ? _first : - index <= _buffers.Count ? _buffers[index - 1] : - _current; - } - - /// - /// Adds an item to this builder. - /// - /// The item to add. - /// - /// Use if adding to the builder is a bottleneck for your use case. - /// Otherwise, use . - /// - [MethodImpl(MethodImplOptions.NoInlining)] - public void SlowAdd(T item) => Add(item); - - /// - /// Creates an array from the contents of this builder. - /// - public T[] ToArray() - { - if (TryMove(out T[] array)) - { - // No resizing to do. - return array; - } - - array = new T[_count]; - CopyTo(array, 0, _count); - return array; - } - - /// - /// Attempts to transfer this builder into an array without copying. - /// - /// The transferred array, if the operation succeeded. - /// true if the operation succeeded; otherwise, false. - public bool TryMove(out T[] array) - { - array = _first; - return _count == _first.Length; - } - - private void AllocateBuffer() - { - // - On the first few adds, simply resize _first. - // - When we pass ResizeLimit, allocate ResizeLimit elements for _current - // and start reading into _current. Set _index to 0. - // - When _current runs out of space, add it to _buffers and repeat the - // above step, except with _current.Length * 2. - // - Make sure we never pass _maxCapacity in all of the above steps. - - Debug.Assert((uint)_maxCapacity > (uint)_count); - Debug.Assert(_index == _current.Length, $"{nameof(AllocateBuffer)} was called, but there's more space."); - - // If _count is int.MinValue, we want to go down the other path which will raise an exception. - if ((uint)_count < (uint)ResizeLimit) - { - // We haven't passed ResizeLimit. Resize _first, copying over the previous items. - Debug.Assert(_current == _first && _count == _first.Length); - - int nextCapacity = Math.Min(_count == 0 ? StartingCapacity : _count * 2, _maxCapacity); - - _current = new T[nextCapacity]; - Array.Copy(_first, 0, _current, 0, _count); - _first = _current; - } - else - { - Debug.Assert(_maxCapacity > ResizeLimit); - Debug.Assert(_count == ResizeLimit ^ _current != _first); - - int nextCapacity; - if (_count == ResizeLimit) - { - nextCapacity = ResizeLimit; - } - else - { - // Example scenario: Let's say _count == 64. - // Then our buffers look like this: | 8 | 8 | 16 | 32 | - // As you can see, our count will be just double the last buffer. - // Now, say _maxCapacity is 100. We will find the right amount to allocate by - // doing min(64, 100 - 64). The lhs represents double the last buffer, - // the rhs the limit minus the amount we've already allocated. - - Debug.Assert(_count >= ResizeLimit * 2); - Debug.Assert(_count == _current.Length * 2); - - _buffers.Add(_current); - nextCapacity = Math.Min(_count, _maxCapacity - _count); - } - - _current = new T[nextCapacity]; - _index = 0; - } - } - } } diff --git a/src/libraries/Common/tests/Common.Tests.csproj b/src/libraries/Common/tests/Common.Tests.csproj index 913b459..b8ee4c9 100644 --- a/src/libraries/Common/tests/Common.Tests.csproj +++ b/src/libraries/Common/tests/Common.Tests.csproj @@ -33,6 +33,9 @@ Common\System\Collections\Generic\LargeArrayBuilder.cs + + Common\System\Collections\Generic\LargeArrayBuilder.SpeedOpt.cs + Common\System\IO\PathInternal.CaseSensitivity.cs diff --git a/src/libraries/Common/tests/Tests/System/Collections/Generic/ArrayBuilderTests.cs b/src/libraries/Common/tests/Tests/System/Collections/Generic/ArrayBuilderTests.cs index 1c26472..0664681 100644 --- a/src/libraries/Common/tests/Tests/System/Collections/Generic/ArrayBuilderTests.cs +++ b/src/libraries/Common/tests/Tests/System/Collections/Generic/ArrayBuilderTests.cs @@ -85,33 +85,6 @@ namespace System.Collections.Generic.Tests [Theory] [MemberData(nameof(EnumerableData))] - public void AddAndIndexer(IEnumerable seed) - { - // CreateBuilderFromSequence implicitly tests Add - ArrayBuilder builder = CreateBuilderFromSequence(seed); - - // Continuously shift the elements in the builder over - // using the get/set indexers, until none are left. - for (int left = builder.Count - 1; left >= 0; ) - { - for (int i = 0; i < left; i++) - { - builder[i] = builder[i + 1]; - } - - // Nil out the slot we're no longer using - builder[left--] = default(T); - - int offset = (builder.Count - 1) - left; // How much we've skipped into the enumerable - IEnumerable expected = seed.Skip(offset) - .Concat(Enumerable.Repeat(default(T), offset)); // The count has not been changed, but slots @ the end have been nil'd out - - VerifyBuilderContents(expected, builder); - } - } - - [Theory] - [MemberData(nameof(EnumerableData))] public void ToArray(IEnumerable seed) { ArrayBuilder builder = CreateBuilderFromSequence(seed); diff --git a/src/libraries/System.Linq.Parallel/tests/QueryOperators/GetEnumeratorTests.cs b/src/libraries/System.Linq.Parallel/tests/QueryOperators/GetEnumeratorTests.cs index 5e07723..a1577f2 100644 --- a/src/libraries/System.Linq.Parallel/tests/QueryOperators/GetEnumeratorTests.cs +++ b/src/libraries/System.Linq.Parallel/tests/QueryOperators/GetEnumeratorTests.cs @@ -27,7 +27,11 @@ namespace System.Linq.Parallel.Tests if (labeled.ToString().StartsWith("Enumerable.Range") || labeled.ToString().StartsWith("Partitioner")) { - Assert.Throws(() => enumerator.Reset()); + if (count > 0) + { + Assert.Throws(() => enumerator.Reset()); + } + // Reset behavior is undefined, and for count == 0, some singletons throw while others are nops. } else { @@ -65,7 +69,11 @@ namespace System.Linq.Parallel.Tests if (labeled.ToString().StartsWith("Enumerable.Range") || labeled.ToString().StartsWith("Partitioner")) { - Assert.Throws(() => enumerator.Reset()); + if (count > 0) + { + Assert.Throws(() => enumerator.Reset()); + } + // Reset behavior is undefined, and for count == 0, some singletons throw while others are nops. } else { diff --git a/src/libraries/System.Linq/src/System.Linq.csproj b/src/libraries/System.Linq/src/System.Linq.csproj index f4a6406..49b0cb7 100644 --- a/src/libraries/System.Linq/src/System.Linq.csproj +++ b/src/libraries/System.Linq/src/System.Linq.csproj @@ -10,6 +10,37 @@ netcoreapp + + + + + + + + + + + + + + + + + + + + + System\Collections\Generic\LargeArrayBuilder.SpeedOpt.cs + + + + + + + + System\Collections\Generic\LargeArrayBuilder.SizeOpt.cs + + System\Collections\Generic\ArrayBuilder.cs @@ -47,6 +78,8 @@ + + @@ -54,7 +87,6 @@ - @@ -84,4 +116,4 @@ - \ No newline at end of file + diff --git a/src/libraries/System.Linq/src/System/Linq/AppendPrepend.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/AppendPrepend.SpeedOpt.cs new file mode 100644 index 0000000..a8d3688 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/AppendPrepend.SpeedOpt.cs @@ -0,0 +1,214 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; +using System.Diagnostics; + +namespace System.Linq +{ + public static partial class Enumerable + { + private abstract partial class AppendPrependIterator : IIListProvider + { + public abstract TSource[] ToArray(); + + public abstract List ToList(); + + public abstract int GetCount(bool onlyIfCheap); + } + + private partial class AppendPrepend1Iterator + { + private TSource[] LazyToArray() + { + Debug.Assert(GetCount(onlyIfCheap: true) == -1); + + var builder = new LargeArrayBuilder(initialize: true); + + if (!_appending) + { + builder.SlowAdd(_item); + } + + builder.AddRange(_source); + + if (_appending) + { + builder.SlowAdd(_item); + } + + return builder.ToArray(); + } + + public override TSource[] ToArray() + { + int count = GetCount(onlyIfCheap: true); + if (count == -1) + { + return LazyToArray(); + } + + TSource[] array = new TSource[count]; + int index; + if (_appending) + { + index = 0; + } + else + { + array[0] = _item; + index = 1; + } + + EnumerableHelpers.Copy(_source, array, index, count - 1); + + if (_appending) + { + array[array.Length - 1] = _item; + } + + return array; + } + + public override List ToList() + { + int count = GetCount(onlyIfCheap: true); + List list = count == -1 ? new List() : new List(count); + if (!_appending) + { + list.Add(_item); + } + + list.AddRange(_source); + if (_appending) + { + list.Add(_item); + } + + return list; + } + + public override int GetCount(bool onlyIfCheap) + { + if (_source is IIListProvider listProv) + { + int count = listProv.GetCount(onlyIfCheap); + return count == -1 ? -1 : count + 1; + } + + return !onlyIfCheap || _source is ICollection ? _source.Count() + 1 : -1; + } + } + + private partial class AppendPrependN + { + private TSource[] LazyToArray() + { + Debug.Assert(GetCount(onlyIfCheap: true) == -1); + + var builder = new SparseArrayBuilder(initialize: true); + + if (_prepended != null) + { + builder.Reserve(_prependCount); + } + + builder.AddRange(_source); + + if (_appended != null) + { + builder.Reserve(_appendCount); + } + + TSource[] array = builder.ToArray(); + + int index = 0; + for (SingleLinkedNode node = _prepended; node != null; node = node.Linked) + { + array[index++] = node.Item; + } + + index = array.Length - 1; + for (SingleLinkedNode node = _appended; node != null; node = node.Linked) + { + array[index--] = node.Item; + } + + return array; + } + + public override TSource[] ToArray() + { + int count = GetCount(onlyIfCheap: true); + if (count == -1) + { + return LazyToArray(); + } + + TSource[] array = new TSource[count]; + int index = 0; + for (SingleLinkedNode node = _prepended; node != null; node = node.Linked) + { + array[index] = node.Item; + ++index; + } + + if (_source is ICollection sourceCollection) + { + sourceCollection.CopyTo(array, index); + } + else + { + foreach (TSource item in _source) + { + array[index] = item; + ++index; + } + } + + index = array.Length; + for (SingleLinkedNode node = _appended; node != null; node = node.Linked) + { + --index; + array[index] = node.Item; + } + + return array; + } + + public override List ToList() + { + int count = GetCount(onlyIfCheap: true); + List list = count == -1 ? new List() : new List(count); + for (SingleLinkedNode node = _prepended; node != null; node = node.Linked) + { + list.Add(node.Item); + } + + list.AddRange(_source); + if (_appended != null) + { + IEnumerator e = _appended.GetEnumerator(_appendCount); + while (e.MoveNext()) + { + list.Add(e.Current); + } + } + + return list; + } + + public override int GetCount(bool onlyIfCheap) + { + if (_source is IIListProvider listProv) + { + int count = listProv.GetCount(onlyIfCheap); + return count == -1 ? -1 : count + _appendCount + _prependCount; + } + + return !onlyIfCheap || _source is ICollection ? _source.Count() + _appendCount + _prependCount : -1; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/AppendPrepend.cs b/src/libraries/System.Linq/src/System/Linq/AppendPrepend.cs index e0bb2bf..bc7282c 100644 --- a/src/libraries/System.Linq/src/System/Linq/AppendPrepend.cs +++ b/src/libraries/System.Linq/src/System/Linq/AppendPrepend.cs @@ -37,7 +37,7 @@ namespace System.Linq /// Represents the insertion of one or more items before or after an . /// /// The type of the source enumerable. - private abstract class AppendPrependIterator : Iterator, IIListProvider + private abstract partial class AppendPrependIterator : Iterator { protected readonly IEnumerable _source; protected IEnumerator _enumerator; @@ -80,19 +80,13 @@ namespace System.Linq base.Dispose(); } - - public abstract TSource[] ToArray(); - - public abstract List ToList(); - - public abstract int GetCount(bool onlyIfCheap); } /// /// Represents the insertion of an item before or after an . /// /// The type of the source enumerable. - private class AppendPrepend1Iterator : AppendPrependIterator + private partial class AppendPrepend1Iterator : AppendPrependIterator { private readonly TSource _item; private readonly bool _appending; @@ -165,93 +159,13 @@ namespace System.Linq return new AppendPrependN(_source, new SingleLinkedNode(_item).Add(item), null, prependCount: 2, appendCount: 0); } } - - private TSource[] LazyToArray() - { - Debug.Assert(GetCount(onlyIfCheap: true) == -1); - - var builder = new LargeArrayBuilder(initialize: true); - - if (!_appending) - { - builder.SlowAdd(_item); - } - - builder.AddRange(_source); - - if (_appending) - { - builder.SlowAdd(_item); - } - - return builder.ToArray(); - } - - public override TSource[] ToArray() - { - int count = GetCount(onlyIfCheap: true); - if (count == -1) - { - return LazyToArray(); - } - - TSource[] array = new TSource[count]; - int index; - if (_appending) - { - index = 0; - } - else - { - array[0] = _item; - index = 1; - } - - EnumerableHelpers.Copy(_source, array, index, count - 1); - - if (_appending) - { - array[array.Length - 1] = _item; - } - - return array; - } - - public override List ToList() - { - int count = GetCount(onlyIfCheap: true); - List list = count == -1 ? new List() : new List(count); - if (!_appending) - { - list.Add(_item); - } - - list.AddRange(_source); - if (_appending) - { - list.Add(_item); - } - - return list; - } - - public override int GetCount(bool onlyIfCheap) - { - if (_source is IIListProvider listProv) - { - int count = listProv.GetCount(onlyIfCheap); - return count == -1 ? -1 : count + 1; - } - - return !onlyIfCheap || _source is ICollection ? _source.Count() + 1 : -1; - } } /// /// Represents the insertion of multiple items before or after an . /// /// The type of the source enumerable. - private class AppendPrependN : AppendPrependIterator + private partial class AppendPrependN : AppendPrependIterator { private readonly SingleLinkedNode _prepended; private readonly SingleLinkedNode _appended; @@ -328,113 +242,6 @@ namespace System.Linq var prepended = _prepended != null ? _prepended.Add(item) : new SingleLinkedNode(item); return new AppendPrependN(_source, prepended, _appended, _prependCount + 1, _appendCount); } - - private TSource[] LazyToArray() - { - Debug.Assert(GetCount(onlyIfCheap: true) == -1); - - var builder = new SparseArrayBuilder(initialize: true); - - if (_prepended != null) - { - builder.Reserve(_prependCount); - } - - builder.AddRange(_source); - - if (_appended != null) - { - builder.Reserve(_appendCount); - } - - TSource[] array = builder.ToArray(); - - int index = 0; - for (SingleLinkedNode node = _prepended; node != null; node = node.Linked) - { - array[index++] = node.Item; - } - - index = array.Length - 1; - for (SingleLinkedNode node = _appended; node != null; node = node.Linked) - { - array[index--] = node.Item; - } - - return array; - } - - public override TSource[] ToArray() - { - int count = GetCount(onlyIfCheap: true); - if (count == -1) - { - return LazyToArray(); - } - - TSource[] array = new TSource[count]; - int index = 0; - for (SingleLinkedNode node = _prepended; node != null; node = node.Linked) - { - array[index] = node.Item; - ++index; - } - - if (_source is ICollection sourceCollection) - { - sourceCollection.CopyTo(array, index); - } - else - { - foreach (TSource item in _source) - { - array[index] = item; - ++index; - } - } - - index = array.Length; - for (SingleLinkedNode node = _appended; node != null; node = node.Linked) - { - --index; - array[index] = node.Item; - } - - return array; - } - - public override List ToList() - { - int count = GetCount(onlyIfCheap: true); - List list = count == -1 ? new List() : new List(count); - for (SingleLinkedNode node = _prepended; node != null; node = node.Linked) - { - list.Add(node.Item); - } - - list.AddRange(_source); - if (_appended != null) - { - IEnumerator e = _appended.GetEnumerator(_appendCount); - while (e.MoveNext()) - { - list.Add(e.Current); - } - } - - return list; - } - - public override int GetCount(bool onlyIfCheap) - { - if (_source is IIListProvider listProv) - { - int count = listProv.GetCount(onlyIfCheap); - return count == -1 ? -1 : count + _appendCount + _prependCount; - } - - return !onlyIfCheap || _source is ICollection ? _source.Count() + _appendCount + _prependCount : -1; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Concat.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Concat.SpeedOpt.cs new file mode 100644 index 0000000..33ed9f9 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Concat.SpeedOpt.cs @@ -0,0 +1,222 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; +using System.Diagnostics; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class Concat2Iterator : ConcatIterator + { + public override int GetCount(bool onlyIfCheap) + { + int firstCount, secondCount; + if (!EnumerableHelpers.TryGetCount(_first, out firstCount)) + { + if (onlyIfCheap) + { + return -1; + } + + firstCount = _first.Count(); + } + + if (!EnumerableHelpers.TryGetCount(_second, out secondCount)) + { + if (onlyIfCheap) + { + return -1; + } + + secondCount = _second.Count(); + } + + return checked(firstCount + secondCount); + } + + public override TSource[] ToArray() + { + var builder = new SparseArrayBuilder(initialize: true); + + bool reservedFirst = builder.ReserveOrAdd(_first); + bool reservedSecond = builder.ReserveOrAdd(_second); + + TSource[] array = builder.ToArray(); + + if (reservedFirst) + { + Marker marker = builder.Markers.First(); + Debug.Assert(marker.Index == 0); + EnumerableHelpers.Copy(_first, array, 0, marker.Count); + } + + if (reservedSecond) + { + Marker marker = builder.Markers.Last(); + EnumerableHelpers.Copy(_second, array, marker.Index, marker.Count); + } + + return array; + } + } + + private sealed partial class ConcatNIterator : ConcatIterator + { + public override int GetCount(bool onlyIfCheap) + { + if (onlyIfCheap && !_hasOnlyCollections) + { + return -1; + } + + int count = 0; + ConcatNIterator node, previousN = this; + + do + { + node = previousN; + IEnumerable source = node._head; + + // Enumerable.Count() handles ICollections in O(1) time, but check for them here anyway + // to avoid a method call because 1) they're common and 2) this code is run in a loop. + var collection = source as ICollection; + Debug.Assert(!_hasOnlyCollections || collection != null); + int sourceCount = collection?.Count ?? source.Count(); + + checked + { + count += sourceCount; + } + } + while ((previousN = node.PreviousN) != null); + + Debug.Assert(node._tail is Concat2Iterator); + return checked(count + node._tail.GetCount(onlyIfCheap)); + } + + public override TSource[] ToArray() => _hasOnlyCollections ? PreallocatingToArray() : LazyToArray(); + + private TSource[] LazyToArray() + { + Debug.Assert(!_hasOnlyCollections); + + var builder = new SparseArrayBuilder(initialize: true); + var deferredCopies = new ArrayBuilder(); + + for (int i = 0; ; i++) + { + // Unfortunately, we can't escape re-walking the linked list for each source, which has + // quadratic behavior, because we need to add the sources in order. + // On the bright side, the bottleneck will usually be iterating, buffering, and copying + // each of the enumerables, so this shouldn't be a noticeable perf hit for most scenarios. + + IEnumerable source = GetEnumerable(i); + if (source == null) + { + break; + } + + if (builder.ReserveOrAdd(source)) + { + deferredCopies.Add(i); + } + } + + TSource[] array = builder.ToArray(); + + ArrayBuilder markers = builder.Markers; + for (int i = 0; i < markers.Count; i++) + { + Marker marker = markers[i]; + IEnumerable source = GetEnumerable(deferredCopies[i]); + EnumerableHelpers.Copy(source, array, marker.Index, marker.Count); + } + + return array; + } + + private TSource[] PreallocatingToArray() + { + // If there are only ICollections in this iterator, then we can just get the count, preallocate the + // array, and copy them as we go. This has better time complexity than continuously re-walking the + // linked list via GetEnumerable, and better memory usage than buffering the collections. + + Debug.Assert(_hasOnlyCollections); + + int count = GetCount(onlyIfCheap: true); + Debug.Assert(count >= 0); + + if (count == 0) + { + return Array.Empty(); + } + + var array = new TSource[count]; + int arrayIndex = array.Length; // We start copying in collection-sized chunks from the end of the array. + + ConcatNIterator node, previousN = this; + do + { + node = previousN; + ICollection source = (ICollection)node._head; + int sourceCount = source.Count; + if (sourceCount > 0) + { + checked + { + arrayIndex -= sourceCount; + } + source.CopyTo(array, arrayIndex); + } + } + while ((previousN = node.PreviousN) != null); + + var previous2 = (Concat2Iterator)node._tail; + var second = (ICollection)previous2._second; + int secondCount = second.Count; + + if (secondCount > 0) + { + second.CopyTo(array, checked(arrayIndex - secondCount)); + } + + if (arrayIndex > secondCount) + { + var first = (ICollection)previous2._first; + first.CopyTo(array, 0); + } + + return array; + } + } + + private abstract partial class ConcatIterator : IIListProvider + { + public abstract int GetCount(bool onlyIfCheap); + + public abstract TSource[] ToArray(); + + public List ToList() + { + int count = GetCount(onlyIfCheap: true); + var list = count != -1 ? new List(count) : new List(); + + for (int i = 0; ; i++) + { + IEnumerable source = GetEnumerable(i); + if (source == null) + { + break; + } + + list.AddRange(source); + } + + return list; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Concat.cs b/src/libraries/System.Linq/src/System/Linq/Concat.cs index 11b1bf9..a1cbcdf 100644 --- a/src/libraries/System.Linq/src/System/Linq/Concat.cs +++ b/src/libraries/System.Linq/src/System/Linq/Concat.cs @@ -30,7 +30,7 @@ namespace System.Linq /// Represents the concatenation of two . /// /// The type of the source enumerables. - private sealed class Concat2Iterator : ConcatIterator + private sealed partial class Concat2Iterator : ConcatIterator { /// /// The first source to concatenate. @@ -66,32 +66,6 @@ namespace System.Linq return new ConcatNIterator(this, next, 2, hasOnlyCollections); } - public override int GetCount(bool onlyIfCheap) - { - int firstCount, secondCount; - if (!EnumerableHelpers.TryGetCount(_first, out firstCount)) - { - if (onlyIfCheap) - { - return -1; - } - - firstCount = _first.Count(); - } - - if (!EnumerableHelpers.TryGetCount(_second, out secondCount)) - { - if (onlyIfCheap) - { - return -1; - } - - secondCount = _second.Count(); - } - - return checked(firstCount + secondCount); - } - internal override IEnumerable GetEnumerable(int index) { Debug.Assert(index >= 0 && index <= 2); @@ -103,31 +77,6 @@ namespace System.Linq default: return null; } } - - public override TSource[] ToArray() - { - var builder = new SparseArrayBuilder(initialize: true); - - bool reservedFirst = builder.ReserveOrAdd(_first); - bool reservedSecond = builder.ReserveOrAdd(_second); - - TSource[] array = builder.ToArray(); - - if (reservedFirst) - { - Marker marker = builder.Markers.First(); - Debug.Assert(marker.Index == 0); - EnumerableHelpers.Copy(_first, array, 0, marker.Count); - } - - if (reservedSecond) - { - Marker marker = builder.Markers.Last(); - EnumerableHelpers.Copy(_second, array, marker.Index, marker.Count); - } - - return array; - } } /// @@ -142,7 +91,7 @@ namespace System.Linq /// would be to use an array to store all of the enumerables, but this has a much better memory profile and /// without much additional run-time cost. /// - private sealed class ConcatNIterator : ConcatIterator + private sealed partial class ConcatNIterator : ConcatIterator { /// /// The linked list of previous sources. @@ -209,38 +158,6 @@ namespace System.Linq return new ConcatNIterator(this, next, _headIndex + 1, hasOnlyCollections); } - public override int GetCount(bool onlyIfCheap) - { - if (onlyIfCheap && !_hasOnlyCollections) - { - return -1; - } - - int count = 0; - ConcatNIterator node, previousN = this; - - do - { - node = previousN; - IEnumerable source = node._head; - - // Enumerable.Count() handles ICollections in O(1) time, but check for them here anyway - // to avoid a method call because 1) they're common and 2) this code is run in a loop. - var collection = source as ICollection; - Debug.Assert(!_hasOnlyCollections || collection != null); - int sourceCount = collection?.Count ?? source.Count(); - - checked - { - count += sourceCount; - } - } - while ((previousN = node.PreviousN) != null); - - Debug.Assert(node._tail is Concat2Iterator); - return checked(count + node._tail.GetCount(onlyIfCheap)); - } - internal override IEnumerable GetEnumerable(int index) { Debug.Assert(index >= 0); @@ -265,108 +182,13 @@ namespace System.Linq Debug.Assert(node._tail is Concat2Iterator); return node._tail.GetEnumerable(index); } - - public override TSource[] ToArray() => _hasOnlyCollections ? PreallocatingToArray() : LazyToArray(); - - private TSource[] LazyToArray() - { - Debug.Assert(!_hasOnlyCollections); - - var builder = new SparseArrayBuilder(initialize: true); - var deferredCopies = new ArrayBuilder(); - - for (int i = 0; ; i++) - { - // Unfortunately, we can't escape re-walking the linked list for each source, which has - // quadratic behavior, because we need to add the sources in order. - // On the bright side, the bottleneck will usually be iterating, buffering, and copying - // each of the enumerables, so this shouldn't be a noticeable perf hit for most scenarios. - - IEnumerable source = GetEnumerable(i); - if (source == null) - { - break; - } - - if (builder.ReserveOrAdd(source)) - { - deferredCopies.Add(i); - } - } - - TSource[] array = builder.ToArray(); - - ArrayBuilder markers = builder.Markers; - for (int i = 0; i < markers.Count; i++) - { - Marker marker = markers[i]; - IEnumerable source = GetEnumerable(deferredCopies[i]); - EnumerableHelpers.Copy(source, array, marker.Index, marker.Count); - } - - return array; - } - - private TSource[] PreallocatingToArray() - { - // If there are only ICollections in this iterator, then we can just get the count, preallocate the - // array, and copy them as we go. This has better time complexity than continuously re-walking the - // linked list via GetEnumerable, and better memory usage than buffering the collections. - - Debug.Assert(_hasOnlyCollections); - - int count = GetCount(onlyIfCheap: true); - Debug.Assert(count >= 0); - - if (count == 0) - { - return Array.Empty(); - } - - var array = new TSource[count]; - int arrayIndex = array.Length; // We start copying in collection-sized chunks from the end of the array. - - ConcatNIterator node, previousN = this; - do - { - node = previousN; - ICollection source = (ICollection)node._head; - int sourceCount = source.Count; - if (sourceCount > 0) - { - checked - { - arrayIndex -= sourceCount; - } - source.CopyTo(array, arrayIndex); - } - } - while ((previousN = node.PreviousN) != null); - - var previous2 = (Concat2Iterator)node._tail; - var second = (ICollection)previous2._second; - int secondCount = second.Count; - - if (secondCount > 0) - { - second.CopyTo(array, checked(arrayIndex - secondCount)); - } - - if (arrayIndex > secondCount) - { - var first = (ICollection)previous2._first; - first.CopyTo(array, 0); - } - - return array; - } } /// /// Represents the concatenation of two or more . /// /// The type of the source enumerables. - private abstract class ConcatIterator : Iterator, IIListProvider + private abstract partial class ConcatIterator : Iterator { /// /// The enumerator of the current source, if has been called. @@ -430,29 +252,6 @@ namespace System.Linq return false; } - - public abstract int GetCount(bool onlyIfCheap); - - public abstract TSource[] ToArray(); - - public List ToList() - { - int count = GetCount(onlyIfCheap: true); - var list = count != -1 ? new List(count) : new List(); - - for (int i = 0; ; i++) - { - IEnumerable source = GetEnumerable(i); - if (source == null) - { - break; - } - - list.AddRange(source); - } - - return list; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.SpeedOpt.cs new file mode 100644 index 0000000..19c97c6 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.SpeedOpt.cs @@ -0,0 +1,47 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections; +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class DefaultIfEmptyIterator : IIListProvider + { + public TSource[] ToArray() + { + TSource[] array = _source.ToArray(); + return array.Length == 0 ? new[] { _default } : array; + } + + public List ToList() + { + List list = _source.ToList(); + if (list.Count == 0) + { + list.Add(_default); + } + + return list; + } + + public int GetCount(bool onlyIfCheap) + { + int count; + if (!onlyIfCheap || _source is ICollection || _source is ICollection) + { + count = _source.Count(); + } + else + { + count = _source is IIListProvider listProv ? listProv.GetCount(onlyIfCheap: true) : -1; + } + + return count == 0 ? 1 : count; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.cs b/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.cs index b98f659..8011d54 100644 --- a/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.cs +++ b/src/libraries/System.Linq/src/System/Linq/DefaultIfEmpty.cs @@ -2,7 +2,6 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. -using System.Collections; using System.Collections.Generic; using System.Diagnostics; @@ -23,7 +22,7 @@ namespace System.Linq return new DefaultIfEmptyIterator(source, defaultValue); } - private sealed class DefaultIfEmptyIterator : Iterator, IIListProvider + private sealed partial class DefaultIfEmptyIterator : Iterator { private readonly IEnumerable _source; private readonly TSource _default; @@ -80,38 +79,6 @@ namespace System.Linq base.Dispose(); } - - public TSource[] ToArray() - { - TSource[] array = _source.ToArray(); - return array.Length == 0 ? new[] { _default } : array; - } - - public List ToList() - { - List list = _source.ToList(); - if (list.Count == 0) - { - list.Add(_default); - } - - return list; - } - - public int GetCount(bool onlyIfCheap) - { - int count; - if (!onlyIfCheap || _source is ICollection || _source is ICollection) - { - count = _source.Count(); - } - else - { - count = _source is IIListProvider listProv ? listProv.GetCount(onlyIfCheap: true) : -1; - } - - return count == 0 ? 1 : count; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Distinct.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Distinct.SpeedOpt.cs new file mode 100644 index 0000000..ba942e0 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Distinct.SpeedOpt.cs @@ -0,0 +1,27 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class DistinctIterator : IIListProvider + { + private Set FillSet() + { + var set = new Set(_comparer); + set.UnionWith(_source); + return set; + } + + public TSource[] ToArray() => FillSet().ToArray(); + + public List ToList() => FillSet().ToList(); + + public int GetCount(bool onlyIfCheap) => onlyIfCheap ? -1 : FillSet().Count; + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Distinct.cs b/src/libraries/System.Linq/src/System/Linq/Distinct.cs index e01d319..72b3952 100644 --- a/src/libraries/System.Linq/src/System/Linq/Distinct.cs +++ b/src/libraries/System.Linq/src/System/Linq/Distinct.cs @@ -25,7 +25,7 @@ namespace System.Linq /// An iterator that yields the distinct values in an . /// /// The type of the source enumerable. - private sealed class DistinctIterator : Iterator, IIListProvider + private sealed partial class DistinctIterator : Iterator { private readonly IEnumerable _source; private readonly IEqualityComparer _comparer; @@ -88,19 +88,6 @@ namespace System.Linq base.Dispose(); } - - private Set FillSet() - { - Set set = new Set(_comparer); - set.UnionWith(_source); - return set; - } - - public TSource[] ToArray() => FillSet().ToArray(); - - public List ToList() => FillSet().ToList(); - - public int GetCount(bool onlyIfCheap) => onlyIfCheap ? -1 : FillSet().Count; } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Enumerable.SizeOpt.cs b/src/libraries/System.Linq/src/System/Linq/Enumerable.SizeOpt.cs new file mode 100644 index 0000000..9be511a --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Enumerable.SizeOpt.cs @@ -0,0 +1,13 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + public static IEnumerable Empty() => Array.Empty(); + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Enumerable.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Enumerable.SpeedOpt.cs new file mode 100644 index 0000000..cf413f9 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Enumerable.SpeedOpt.cs @@ -0,0 +1,13 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + public static IEnumerable Empty() => EmptyPartition.Instance; + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Enumerable.cs b/src/libraries/System.Linq/src/System/Linq/Enumerable.cs index 2ea06da..3bf540a 100644 --- a/src/libraries/System.Linq/src/System/Linq/Enumerable.cs +++ b/src/libraries/System.Linq/src/System/Linq/Enumerable.cs @@ -9,7 +9,5 @@ namespace System.Linq public static partial class Enumerable { public static IEnumerable AsEnumerable(this IEnumerable source) => source; - - public static IEnumerable Empty() => Array.Empty(); } } diff --git a/src/libraries/System.Linq/src/System/Linq/Grouping.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Grouping.SpeedOpt.cs new file mode 100644 index 0000000..58dc162 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Grouping.SpeedOpt.cs @@ -0,0 +1,68 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + internal sealed partial class GroupedResultEnumerable : IIListProvider + { + public TResult[] ToArray() => + Lookup.Create(_source, _keySelector, _elementSelector, _comparer).ToArray(_resultSelector); + + public List ToList() => + Lookup.Create(_source, _keySelector, _elementSelector, _comparer).ToList(_resultSelector); + + public int GetCount(bool onlyIfCheap) => + onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _elementSelector, _comparer).Count; + } + + internal sealed partial class GroupedResultEnumerable : IIListProvider + { + public TResult[] ToArray() => + Lookup.Create(_source, _keySelector, _comparer).ToArray(_resultSelector); + + public List ToList() => + Lookup.Create(_source, _keySelector, _comparer).ToList(_resultSelector); + + public int GetCount(bool onlyIfCheap) => + onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _comparer).Count; + } + + internal sealed partial class GroupedEnumerable : IIListProvider> + { + public IGrouping[] ToArray() + { + IIListProvider> lookup = Lookup.Create(_source, _keySelector, _elementSelector, _comparer); + return lookup.ToArray(); + } + + public List> ToList() + { + IIListProvider> lookup = Lookup.Create(_source, _keySelector, _elementSelector, _comparer); + return lookup.ToList(); + } + + public int GetCount(bool onlyIfCheap) => + onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _elementSelector, _comparer).Count; + } + + internal sealed partial class GroupedEnumerable : IIListProvider> + { + public IGrouping[] ToArray() + { + IIListProvider> lookup = Lookup.Create(_source, _keySelector, _comparer); + return lookup.ToArray(); + } + + public List> ToList() + { + IIListProvider> lookup = Lookup.Create(_source, _keySelector, _comparer); + return lookup.ToList(); + } + + public int GetCount(bool onlyIfCheap) => + onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _comparer).Count; + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Grouping.cs b/src/libraries/System.Linq/src/System/Linq/Grouping.cs index 3f98814..76660e4 100644 --- a/src/libraries/System.Linq/src/System/Linq/Grouping.cs +++ b/src/libraries/System.Linq/src/System/Linq/Grouping.cs @@ -134,7 +134,7 @@ namespace System.Linq } } - internal sealed class GroupedResultEnumerable : IIListProvider + internal sealed partial class GroupedResultEnumerable : IEnumerable { private readonly IEnumerable _source; private readonly Func _keySelector; @@ -158,18 +158,9 @@ namespace System.Linq } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); - - public TResult[] ToArray() => - Lookup.Create(_source, _keySelector, _elementSelector, _comparer).ToArray(_resultSelector); - - public List ToList() => - Lookup.Create(_source, _keySelector, _elementSelector, _comparer).ToList(_resultSelector); - - public int GetCount(bool onlyIfCheap) => - onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _elementSelector, _comparer).Count; } - internal sealed class GroupedResultEnumerable : IIListProvider + internal sealed partial class GroupedResultEnumerable : IEnumerable { private readonly IEnumerable _source; private readonly Func _keySelector; @@ -191,18 +182,9 @@ namespace System.Linq } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); - - public TResult[] ToArray() => - Lookup.Create(_source, _keySelector, _comparer).ToArray(_resultSelector); - - public List ToList() => - Lookup.Create(_source, _keySelector, _comparer).ToList(_resultSelector); - - public int GetCount(bool onlyIfCheap) => - onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _comparer).Count; } - internal sealed class GroupedEnumerable : IIListProvider> + internal sealed partial class GroupedEnumerable : IEnumerable> { private readonly IEnumerable _source; private readonly Func _keySelector; @@ -221,24 +203,9 @@ namespace System.Linq Lookup.Create(_source, _keySelector, _elementSelector, _comparer).GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); - - public IGrouping[] ToArray() - { - IIListProvider> lookup = Lookup.Create(_source, _keySelector, _elementSelector, _comparer); - return lookup.ToArray(); - } - - public List> ToList() - { - IIListProvider> lookup = Lookup.Create(_source, _keySelector, _elementSelector, _comparer); - return lookup.ToList(); - } - - public int GetCount(bool onlyIfCheap) => - onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _elementSelector, _comparer).Count; } - internal sealed class GroupedEnumerable : IIListProvider> + internal sealed partial class GroupedEnumerable : IEnumerable> { private readonly IEnumerable _source; private readonly Func _keySelector; @@ -255,20 +222,5 @@ namespace System.Linq Lookup.Create(_source, _keySelector, _comparer).GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); - - public IGrouping[] ToArray() - { - IIListProvider> lookup = Lookup.Create(_source, _keySelector, _comparer); - return lookup.ToArray(); - } - - public List> ToList() - { - IIListProvider> lookup = Lookup.Create(_source, _keySelector, _comparer); - return lookup.ToList(); - } - - public int GetCount(bool onlyIfCheap) => - onlyIfCheap ? -1 : Lookup.Create(_source, _keySelector, _comparer).Count; } } diff --git a/src/libraries/System.Linq/src/System/Linq/IIListProvider.cs b/src/libraries/System.Linq/src/System/Linq/IIListProvider.cs new file mode 100644 index 0000000..2fb3921 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/IIListProvider.cs @@ -0,0 +1,34 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + /// + /// An iterator that can produce an array or through an optimized path. + /// + internal interface IIListProvider : IEnumerable + { + /// + /// Produce an array of the sequence through an optimized path. + /// + /// The array. + TElement[] ToArray(); + + /// + /// Produce a of the sequence through an optimized path. + /// + /// The . + List ToList(); + + /// + /// Returns the count of elements in the sequence. + /// + /// If true then the count should only be calculated if doing + /// so is quick (sure or likely to be constant time), otherwise -1 should be returned. + /// The number of elements. + int GetCount(bool onlyIfCheap); + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/IPartition.cs b/src/libraries/System.Linq/src/System/Linq/IPartition.cs new file mode 100644 index 0000000..07ba168 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/IPartition.cs @@ -0,0 +1,48 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +namespace System.Linq +{ + /// + /// An iterator that supports random access and can produce a partial sequence of its items through an optimized path. + /// + internal interface IPartition : IIListProvider + { + /// + /// Creates a new partition that skips the specified number of elements from this sequence. + /// + /// The number of elements to skip. + /// An with the first items removed. + IPartition Skip(int count); + + /// + /// Creates a new partition that takes the specified number of elements from this sequence. + /// + /// The number of elements to take. + /// An with only the first items. + IPartition Take(int count); + + /// + /// Gets the item associated with a 0-based index in this sequence. + /// + /// The 0-based index to access. + /// true if the sequence contains an element at that index, false otherwise. + /// The element if is true, otherwise, the default value of . + TElement TryGetElementAt(int index, out bool found); + + /// + /// Gets the first item in this sequence. + /// + /// true if the sequence contains an element, false otherwise. + /// The element if is true, otherwise, the default value of . + TElement TryGetFirst(out bool found); + + /// + /// Gets the last item in this sequence. + /// + /// true if the sequence contains an element, false otherwise. + /// The element if is true, otherwise, the default value of . + TElement TryGetLast(out bool found); + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Lookup.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Lookup.SpeedOpt.cs new file mode 100644 index 0000000..052eed5 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Lookup.SpeedOpt.cs @@ -0,0 +1,69 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public partial class Lookup : IIListProvider> + { + IGrouping[] IIListProvider>.ToArray() + { + IGrouping[] array = new IGrouping[_count]; + int index = 0; + Grouping g = _lastGrouping; + if (g != null) + { + do + { + g = g._next; + array[index] = g; + ++index; + } + while (g != _lastGrouping); + } + + return array; + } + + internal TResult[] ToArray(Func, TResult> resultSelector) + { + TResult[] array = new TResult[_count]; + int index = 0; + Grouping g = _lastGrouping; + if (g != null) + { + do + { + g = g._next; + g.Trim(); + array[index] = resultSelector(g._key, g._elements); + ++index; + } + while (g != _lastGrouping); + } + + return array; + } + + List> IIListProvider>.ToList() + { + List> list = new List>(_count); + Grouping g = _lastGrouping; + if (g != null) + { + do + { + g = g._next; + list.Add(g); + } + while (g != _lastGrouping); + } + + return list; + } + + int IIListProvider>.GetCount(bool onlyIfCheap) => _count; + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Lookup.cs b/src/libraries/System.Linq/src/System/Linq/Lookup.cs index 638a369..c4f5d15 100644 --- a/src/libraries/System.Linq/src/System/Linq/Lookup.cs +++ b/src/libraries/System.Linq/src/System/Linq/Lookup.cs @@ -63,7 +63,7 @@ namespace System.Linq [DebuggerDisplay("Count = {Count}")] [DebuggerTypeProxy(typeof(SystemLinq_LookupDebugView<,>))] - public class Lookup : ILookup, IIListProvider> + public partial class Lookup : ILookup { private readonly IEqualityComparer _comparer; private Grouping[] _groupings; @@ -132,7 +132,7 @@ namespace System.Linq return grouping; } - return Array.Empty(); + return Enumerable.Empty(); } } @@ -152,62 +152,6 @@ namespace System.Linq } } - IGrouping[] IIListProvider>.ToArray() - { - IGrouping[] array = new IGrouping[_count]; - int index = 0; - Grouping g = _lastGrouping; - if (g != null) - { - do - { - g = g._next; - array[index] = g; - ++index; - } - while (g != _lastGrouping); - } - - return array; - } - - internal TResult[] ToArray(Func, TResult> resultSelector) - { - TResult[] array = new TResult[_count]; - int index = 0; - Grouping g = _lastGrouping; - if (g != null) - { - do - { - g = g._next; - g.Trim(); - array[index] = resultSelector(g._key, g._elements); - ++index; - } - while (g != _lastGrouping); - } - - return array; - } - - List> IIListProvider>.ToList() - { - List> list = new List>(_count); - Grouping g = _lastGrouping; - if (g != null) - { - do - { - g = g._next; - list.Add(g); - } - while (g != _lastGrouping); - } - - return list; - } - internal List ToList(Func, TResult> resultSelector) { List list = new List(_count); @@ -226,8 +170,6 @@ namespace System.Linq return list; } - int IIListProvider>.GetCount(bool onlyIfCheap) => _count; - public IEnumerable ApplyResultSelector(Func, TResult> resultSelector) { Grouping g = _lastGrouping; diff --git a/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.SpeedOpt.cs new file mode 100644 index 0000000..076ab9e --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.SpeedOpt.cs @@ -0,0 +1,250 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections; +using System.Collections.Generic; + +namespace System.Linq +{ + internal abstract partial class OrderedEnumerable : IPartition + { + public TElement[] ToArray() + { + Buffer buffer = new Buffer(_source); + + int count = buffer._count; + if (count == 0) + { + return buffer._items; + } + + TElement[] array = new TElement[count]; + int[] map = SortedMap(buffer); + for (int i = 0; i != array.Length; i++) + { + array[i] = buffer._items[map[i]]; + } + + return array; + } + + public List ToList() + { + Buffer buffer = new Buffer(_source); + int count = buffer._count; + List list = new List(count); + if (count > 0) + { + int[] map = SortedMap(buffer); + for (int i = 0; i != count; i++) + { + list.Add(buffer._items[map[i]]); + } + } + + return list; + } + + public int GetCount(bool onlyIfCheap) + { + if (_source is IIListProvider listProv) + { + return listProv.GetCount(onlyIfCheap); + } + + return !onlyIfCheap || _source is ICollection || _source is ICollection ? _source.Count() : -1; + } + + internal TElement[] ToArray(int minIdx, int maxIdx) + { + Buffer buffer = new Buffer(_source); + int count = buffer._count; + if (count <= minIdx) + { + return Array.Empty(); + } + + if (count <= maxIdx) + { + maxIdx = count - 1; + } + + if (minIdx == maxIdx) + { + return new TElement[] { GetEnumerableSorter().ElementAt(buffer._items, count, minIdx) }; + } + + int[] map = SortedMap(buffer, minIdx, maxIdx); + TElement[] array = new TElement[maxIdx - minIdx + 1]; + int idx = 0; + while (minIdx <= maxIdx) + { + array[idx] = buffer._items[map[minIdx]]; + ++idx; + ++minIdx; + } + + return array; + } + + internal List ToList(int minIdx, int maxIdx) + { + Buffer buffer = new Buffer(_source); + int count = buffer._count; + if (count <= minIdx) + { + return new List(); + } + + if (count <= maxIdx) + { + maxIdx = count - 1; + } + + if (minIdx == maxIdx) + { + return new List(1) { GetEnumerableSorter().ElementAt(buffer._items, count, minIdx) }; + } + + int[] map = SortedMap(buffer, minIdx, maxIdx); + List list = new List(maxIdx - minIdx + 1); + while (minIdx <= maxIdx) + { + list.Add(buffer._items[map[minIdx]]); + ++minIdx; + } + + return list; + } + + internal int GetCount(int minIdx, int maxIdx, bool onlyIfCheap) + { + int count = GetCount(onlyIfCheap); + if (count <= 0) + { + return count; + } + + if (count <= minIdx) + { + return 0; + } + + return (count <= maxIdx ? count : maxIdx + 1) - minIdx; + } + + public IPartition Skip(int count) => new OrderedPartition(this, count, int.MaxValue); + + public IPartition Take(int count) => new OrderedPartition(this, 0, count - 1); + + public TElement TryGetElementAt(int index, out bool found) + { + if (index == 0) + { + return TryGetFirst(out found); + } + + if (index > 0) + { + Buffer buffer = new Buffer(_source); + int count = buffer._count; + if (index < count) + { + found = true; + return GetEnumerableSorter().ElementAt(buffer._items, count, index); + } + } + + found = false; + return default(TElement); + } + + public TElement TryGetFirst(out bool found) + { + CachingComparer comparer = GetComparer(); + using (IEnumerator e = _source.GetEnumerator()) + { + if (!e.MoveNext()) + { + found = false; + return default(TElement); + } + + TElement value = e.Current; + comparer.SetElement(value); + while (e.MoveNext()) + { + TElement x = e.Current; + if (comparer.Compare(x, true) < 0) + { + value = x; + } + } + + found = true; + return value; + } + } + + public TElement TryGetLast(out bool found) + { + using (IEnumerator e = _source.GetEnumerator()) + { + if (!e.MoveNext()) + { + found = false; + return default(TElement); + } + + CachingComparer comparer = GetComparer(); + TElement value = e.Current; + comparer.SetElement(value); + while (e.MoveNext()) + { + TElement current = e.Current; + if (comparer.Compare(current, false) >= 0) + { + value = current; + } + } + + found = true; + return value; + } + } + + public TElement TryGetLast(int minIdx, int maxIdx, out bool found) + { + Buffer buffer = new Buffer(_source); + int count = buffer._count; + if (minIdx >= count) + { + found = false; + return default(TElement); + } + + found = true; + return (maxIdx < count - 1) ? GetEnumerableSorter().ElementAt(buffer._items, count, maxIdx) : Last(buffer); + } + + private TElement Last(Buffer buffer) + { + CachingComparer comparer = GetComparer(); + TElement[] items = buffer._items; + int count = buffer._count; + TElement value = items[0]; + comparer.SetElement(value); + for (int i = 1; i != count; ++i) + { + TElement x = items[i]; + if (comparer.Compare(x, false) >= 0) + { + value = x; + } + } + + return value; + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.cs b/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.cs index 0f58510..32e9354 100644 --- a/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.cs +++ b/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.cs @@ -7,7 +7,7 @@ using System.Collections.Generic; namespace System.Linq { - internal abstract class OrderedEnumerable : IOrderedEnumerable, IPartition + internal abstract partial class OrderedEnumerable : IOrderedEnumerable { internal IEnumerable _source; @@ -29,53 +29,6 @@ namespace System.Linq } } - public TElement[] ToArray() - { - Buffer buffer = new Buffer(_source); - - int count = buffer._count; - if (count == 0) - { - return buffer._items; - } - - TElement[] array = new TElement[count]; - int[] map = SortedMap(buffer); - for (int i = 0; i != array.Length; i++) - { - array[i] = buffer._items[map[i]]; - } - - return array; - } - - public List ToList() - { - Buffer buffer = new Buffer(_source); - int count = buffer._count; - List list = new List(count); - if (count > 0) - { - int[] map = SortedMap(buffer); - for (int i = 0; i != count; i++) - { - list.Add(buffer._items[map[i]]); - } - } - - return list; - } - - public int GetCount(bool onlyIfCheap) - { - if (_source is IIListProvider listProv) - { - return listProv.GetCount(onlyIfCheap); - } - - return !onlyIfCheap || _source is ICollection || _source is ICollection ? _source.Count() : -1; - } - internal IEnumerator GetEnumerator(int minIdx, int maxIdx) { Buffer buffer = new Buffer(_source); @@ -103,84 +56,6 @@ namespace System.Linq } } - internal TElement[] ToArray(int minIdx, int maxIdx) - { - Buffer buffer = new Buffer(_source); - int count = buffer._count; - if (count <= minIdx) - { - return Array.Empty(); - } - - if (count <= maxIdx) - { - maxIdx = count - 1; - } - - if (minIdx == maxIdx) - { - return new TElement[] { GetEnumerableSorter().ElementAt(buffer._items, count, minIdx) }; - } - - int[] map = SortedMap(buffer, minIdx, maxIdx); - TElement[] array = new TElement[maxIdx - minIdx + 1]; - int idx = 0; - while (minIdx <= maxIdx) - { - array[idx] = buffer._items[map[minIdx]]; - ++idx; - ++minIdx; - } - - return array; - } - - internal List ToList(int minIdx, int maxIdx) - { - Buffer buffer = new Buffer(_source); - int count = buffer._count; - if (count <= minIdx) - { - return new List(); - } - - if (count <= maxIdx) - { - maxIdx = count - 1; - } - - if (minIdx == maxIdx) - { - return new List(1) { GetEnumerableSorter().ElementAt(buffer._items, count, minIdx) }; - } - - int[] map = SortedMap(buffer, minIdx, maxIdx); - List list = new List(maxIdx - minIdx + 1); - while (minIdx <= maxIdx) - { - list.Add(buffer._items[map[minIdx]]); - ++minIdx; - } - - return list; - } - - internal int GetCount(int minIdx, int maxIdx, bool onlyIfCheap) - { - int count = GetCount(onlyIfCheap); - if (count <= 0) - { - return count; - } - - if (count <= minIdx) - { - return 0; - } - - return (count <= maxIdx ? count : maxIdx + 1) - minIdx; - } - private EnumerableSorter GetEnumerableSorter() => GetEnumerableSorter(null); internal abstract EnumerableSorter GetEnumerableSorter(EnumerableSorter next); @@ -194,59 +69,6 @@ namespace System.Linq IOrderedEnumerable IOrderedEnumerable.CreateOrderedEnumerable(Func keySelector, IComparer comparer, bool descending) => new OrderedEnumerable(_source, keySelector, comparer, @descending, this); - public IPartition Skip(int count) => new OrderedPartition(this, count, int.MaxValue); - - public IPartition Take(int count) => new OrderedPartition(this, 0, count - 1); - - public TElement TryGetElementAt(int index, out bool found) - { - if (index == 0) - { - return TryGetFirst(out found); - } - - if (index > 0) - { - Buffer buffer = new Buffer(_source); - int count = buffer._count; - if (index < count) - { - found = true; - return GetEnumerableSorter().ElementAt(buffer._items, count, index); - } - } - - found = false; - return default(TElement); - } - - public TElement TryGetFirst(out bool found) - { - CachingComparer comparer = GetComparer(); - using (IEnumerator e = _source.GetEnumerator()) - { - if (!e.MoveNext()) - { - found = false; - return default(TElement); - } - - TElement value = e.Current; - comparer.SetElement(value); - while (e.MoveNext()) - { - TElement x = e.Current; - if (comparer.Compare(x, true) < 0) - { - value = x; - } - } - - found = true; - return value; - } - } - public TElement TryGetFirst(Func predicate, out bool found) { CachingComparer comparer = GetComparer(); @@ -280,66 +102,6 @@ namespace System.Linq } } - public TElement TryGetLast(out bool found) - { - using (IEnumerator e = _source.GetEnumerator()) - { - if (!e.MoveNext()) - { - found = false; - return default(TElement); - } - - CachingComparer comparer = GetComparer(); - TElement value = e.Current; - comparer.SetElement(value); - while (e.MoveNext()) - { - TElement current = e.Current; - if (comparer.Compare(current, false) >= 0) - { - value = current; - } - } - - found = true; - return value; - } - } - - public TElement TryGetLast(int minIdx, int maxIdx, out bool found) - { - Buffer buffer = new Buffer(_source); - int count = buffer._count; - if (minIdx >= count) - { - found = false; - return default(TElement); - } - - found = true; - return (maxIdx < count - 1) ? GetEnumerableSorter().ElementAt(buffer._items, count, maxIdx) : Last(buffer); - } - - private TElement Last(Buffer buffer) - { - CachingComparer comparer = GetComparer(); - TElement[] items = buffer._items; - int count = buffer._count; - TElement value = items[0]; - comparer.SetElement(value); - for (int i = 1; i != count; ++i) - { - TElement x = items[i]; - if (comparer.Compare(x, false) >= 0) - { - value = x; - } - } - - return value; - } - public TElement TryGetLast(Func predicate, out bool found) { CachingComparer comparer = GetComparer(); diff --git a/src/libraries/System.Linq/src/System/Linq/Partition.cs b/src/libraries/System.Linq/src/System/Linq/Partition.SpeedOpt.cs similarity index 87% rename from src/libraries/System.Linq/src/System/Linq/Partition.cs rename to src/libraries/System.Linq/src/System/Linq/Partition.SpeedOpt.cs index 422b8ed..4f564bd 100644 --- a/src/libraries/System.Linq/src/System/Linq/Partition.cs +++ b/src/libraries/System.Linq/src/System/Linq/Partition.SpeedOpt.cs @@ -10,74 +10,6 @@ using System.Diagnostics.CodeAnalysis; namespace System.Linq { /// - /// An iterator that can produce an array or through an optimized path. - /// - internal interface IIListProvider : IEnumerable - { - /// - /// Produce an array of the sequence through an optimized path. - /// - /// The array. - TElement[] ToArray(); - - /// - /// Produce a of the sequence through an optimized path. - /// - /// The . - List ToList(); - - /// - /// Returns the count of elements in the sequence. - /// - /// If true then the count should only be calculated if doing - /// so is quick (sure or likely to be constant time), otherwise -1 should be returned. - /// The number of elements. - int GetCount(bool onlyIfCheap); - } - - /// - /// An iterator that supports random access and can produce a partial sequence of its items through an optimized path. - /// - internal interface IPartition : IIListProvider - { - /// - /// Creates a new partition that skips the specified number of elements from this sequence. - /// - /// The number of elements to skip. - /// An with the first items removed. - IPartition Skip(int count); - - /// - /// Creates a new partition that takes the specified number of elements from this sequence. - /// - /// The number of elements to take. - /// An with only the first items. - IPartition Take(int count); - - /// - /// Gets the item associated with a 0-based index in this sequence. - /// - /// The 0-based index to access. - /// true if the sequence contains an element at that index, false otherwise. - /// The element if is true, otherwise, the default value of . - TElement TryGetElementAt(int index, out bool found); - - /// - /// Gets the first item in this sequence. - /// - /// true if the sequence contains an element, false otherwise. - /// The element if is true, otherwise, the default value of . - TElement TryGetFirst(out bool found); - - /// - /// Gets the last item in this sequence. - /// - /// true if the sequence contains an element, false otherwise. - /// The element if is true, otherwise, the default value of . - TElement TryGetLast(out bool found); - } - - /// /// Represents an enumerable with zero elements. /// /// The element type. @@ -108,7 +40,10 @@ namespace System.Linq [ExcludeFromCodeCoverage] // Shouldn't be called, and as undefined can return or throw anything anyway. object IEnumerator.Current => default(TElement); - void IEnumerator.Reset() => throw Error.NotSupported(); + void IEnumerator.Reset() + { + // Do nothing. + } void IDisposable.Dispose() { diff --git a/src/libraries/System.Linq/src/System/Linq/Range.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Range.SpeedOpt.cs new file mode 100644 index 0000000..b643781 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Range.SpeedOpt.cs @@ -0,0 +1,90 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class RangeIterator : IPartition + { + public override IEnumerable Select(Func selector) + { + return new SelectIPartitionIterator(this, selector); + } + + public int[] ToArray() + { + int[] array = new int[_end - _start]; + int cur = _start; + for (int i = 0; i != array.Length; ++i) + { + array[i] = cur; + ++cur; + } + + return array; + } + + public List ToList() + { + List list = new List(_end - _start); + for (int cur = _start; cur != _end; cur++) + { + list.Add(cur); + } + + return list; + } + + public int GetCount(bool onlyIfCheap) => unchecked(_end - _start); + + public IPartition Skip(int count) + { + if (count >= _end - _start) + { + return EmptyPartition.Instance; + } + + return new RangeIterator(_start + count, _end - _start - count); + } + + public IPartition Take(int count) + { + int curCount = _end - _start; + if (count >= curCount) + { + return this; + } + + return new RangeIterator(_start, count); + } + + public int TryGetElementAt(int index, out bool found) + { + if (unchecked((uint)index < (uint)(_end - _start))) + { + found = true; + return _start + index; + } + + found = false; + return 0; + } + + public int TryGetFirst(out bool found) + { + found = true; + return _start; + } + + public int TryGetLast(out bool found) + { + found = true; + return _end - 1; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Range.cs b/src/libraries/System.Linq/src/System/Linq/Range.cs index a0fe462..1260a1f 100644 --- a/src/libraries/System.Linq/src/System/Linq/Range.cs +++ b/src/libraries/System.Linq/src/System/Linq/Range.cs @@ -19,7 +19,7 @@ namespace System.Linq if (count == 0) { - return EmptyPartition.Instance; + return Empty(); } return new RangeIterator(start, count); @@ -28,7 +28,7 @@ namespace System.Linq /// /// An iterator that yields a range of consecutive integers. /// - private sealed class RangeIterator : Iterator, IPartition + private sealed partial class RangeIterator : Iterator { private readonly int _start; private readonly int _end; @@ -68,82 +68,6 @@ namespace System.Linq { _state = -1; // Don't reset current } - - public override IEnumerable Select(Func selector) - { - return new SelectIPartitionIterator(this, selector); - } - - public int[] ToArray() - { - int[] array = new int[_end - _start]; - int cur = _start; - for (int i = 0; i != array.Length; ++i) - { - array[i] = cur; - ++cur; - } - - return array; - } - - public List ToList() - { - List list = new List(_end - _start); - for (int cur = _start; cur != _end; cur++) - { - list.Add(cur); - } - - return list; - } - - public int GetCount(bool onlyIfCheap) => unchecked(_end - _start); - - public IPartition Skip(int count) - { - if (count >= _end - _start) - { - return EmptyPartition.Instance; - } - - return new RangeIterator(_start + count, _end - _start - count); - } - - public IPartition Take(int count) - { - int curCount = _end - _start; - if (count >= curCount) - { - return this; - } - - return new RangeIterator(_start, count); - } - - public int TryGetElementAt(int index, out bool found) - { - if (unchecked((uint)index < (uint)(_end - _start))) - { - found = true; - return _start + index; - } - - found = false; - return 0; - } - - public int TryGetFirst(out bool found) - { - found = true; - return _start; - } - - public int TryGetLast(out bool found) - { - found = true; - return _end - 1; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Repeat.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Repeat.SpeedOpt.cs new file mode 100644 index 0000000..1764351 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Repeat.SpeedOpt.cs @@ -0,0 +1,85 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class RepeatIterator : IPartition + { + public override IEnumerable Select(Func selector) => + new SelectIPartitionIterator(this, selector); + + public TResult[] ToArray() + { + TResult[] array = new TResult[_count]; + if (_current != null) + { + Array.Fill(array, _current); + } + + return array; + } + + public List ToList() + { + List list = new List(_count); + for (int i = 0; i != _count; ++i) + { + list.Add(_current); + } + + return list; + } + + public int GetCount(bool onlyIfCheap) => _count; + + public IPartition Skip(int count) + { + if (count >= _count) + { + return EmptyPartition.Instance; + } + + return new RepeatIterator(_current, _count - count); + } + + public IPartition Take(int count) + { + if (count >= _count) + { + return this; + } + + return new RepeatIterator(_current, count); + } + + public TResult TryGetElementAt(int index, out bool found) + { + if ((uint)index < (uint)_count) + { + found = true; + return _current; + } + + found = false; + return default(TResult); + } + + public TResult TryGetFirst(out bool found) + { + found = true; + return _current; + } + + public TResult TryGetLast(out bool found) + { + found = true; + return _current; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Repeat.cs b/src/libraries/System.Linq/src/System/Linq/Repeat.cs index 0eeab78..8ffa47a 100644 --- a/src/libraries/System.Linq/src/System/Linq/Repeat.cs +++ b/src/libraries/System.Linq/src/System/Linq/Repeat.cs @@ -18,7 +18,7 @@ namespace System.Linq if (count == 0) { - return EmptyPartition.Instance; + return Empty(); } return new RepeatIterator(element, count); @@ -28,7 +28,7 @@ namespace System.Linq /// An iterator that yields the same item multiple times. /// /// The type of the item. - private sealed class RepeatIterator : Iterator, IPartition + private sealed partial class RepeatIterator : Iterator { private readonly int _count; @@ -68,77 +68,6 @@ namespace System.Linq Dispose(); return false; } - - public override IEnumerable Select(Func selector) => - new SelectIPartitionIterator(this, selector); - - public TResult[] ToArray() - { - TResult[] array = new TResult[_count]; - if (_current != null) - { - Array.Fill(array, _current); - } - - return array; - } - - public List ToList() - { - List list = new List(_count); - for (int i = 0; i != _count; ++i) - { - list.Add(_current); - } - - return list; - } - - public int GetCount(bool onlyIfCheap) => _count; - - public IPartition Skip(int count) - { - if (count >= _count) - { - return EmptyPartition.Instance; - } - - return new RepeatIterator(_current, _count - count); - } - - public IPartition Take(int count) - { - if (count >= _count) - { - return this; - } - - return new RepeatIterator(_current, count); - } - - public TResult TryGetElementAt(int index, out bool found) - { - if ((uint)index < (uint)_count) - { - found = true; - return _current; - } - - found = false; - return default(TResult); - } - - public TResult TryGetFirst(out bool found) - { - found = true; - return _current; - } - - public TResult TryGetLast(out bool found) - { - found = true; - return _current; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Reverse.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Reverse.SpeedOpt.cs new file mode 100644 index 0000000..e754444 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Reverse.SpeedOpt.cs @@ -0,0 +1,52 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections; +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class ReverseIterator : IIListProvider + { + public TSource[] ToArray() + { + TSource[] array = _source.ToArray(); + Array.Reverse(array); + return array; + } + + public List ToList() + { + List list = _source.ToList(); + list.Reverse(); + return list; + } + + public int GetCount(bool onlyIfCheap) + { + if (onlyIfCheap) + { + switch (_source) + { + case IIListProvider listProv: + return listProv.GetCount(onlyIfCheap: true); + + case ICollection colT: + return colT.Count; + + case ICollection col: + return col.Count; + + default: + return -1; + } + } + + return _source.Count(); + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Reverse.cs b/src/libraries/System.Linq/src/System/Linq/Reverse.cs index e68a4f4..29ae52b 100644 --- a/src/libraries/System.Linq/src/System/Linq/Reverse.cs +++ b/src/libraries/System.Linq/src/System/Linq/Reverse.cs @@ -2,7 +2,6 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. -using System.Collections; using System.Collections.Generic; using System.Diagnostics; @@ -24,7 +23,7 @@ namespace System.Linq /// An iterator that yields the items of an in reverse. /// /// The type of the source enumerable. - private sealed class ReverseIterator : Iterator, IIListProvider + private sealed partial class ReverseIterator : Iterator { private readonly IEnumerable _source; private TSource[] _buffer; @@ -84,43 +83,6 @@ namespace System.Linq _buffer = null; // Just in case this ends up being long-lived, allow the memory to be reclaimed. base.Dispose(); } - - public TSource[] ToArray() - { - TSource[] array = _source.ToArray(); - Array.Reverse(array); - return array; - } - - public List ToList() - { - List list = _source.ToList(); - list.Reverse(); - return list; - } - - public int GetCount(bool onlyIfCheap) - { - if (onlyIfCheap) - { - switch (_source) - { - case IIListProvider listProv: - return listProv.GetCount(onlyIfCheap: true); - - case ICollection colT: - return colT.Count; - - case ICollection col: - return col.Count; - - default: - return -1; - } - } - - return _source.Count(); - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs new file mode 100644 index 0000000..ff5a3a5 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs @@ -0,0 +1,692 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; +using System.Diagnostics; +using static System.Linq.Utilities; + +namespace System.Linq +{ + public static partial class Enumerable + { + static partial void CreateSelectIPartitionIterator( + Func selector, IPartition partition, ref IEnumerable result) + { + result = partition is EmptyPartition ? + EmptyPartition.Instance : + new SelectIPartitionIterator(partition, selector); + } + + private sealed partial class SelectEnumerableIterator : IIListProvider + { + public TResult[] ToArray() + { + var builder = new LargeArrayBuilder(initialize: true); + + foreach (TSource item in _source) + { + builder.Add(_selector(item)); + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + foreach (TSource item in _source) + { + list.Add(_selector(item)); + } + + return list; + } + + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + foreach (TSource item in _source) + { + _selector(item); + checked + { + count++; + } + } + + return count; + } + } + + private sealed partial class SelectArrayIterator : IPartition + { + public TResult[] ToArray() + { + // See assert in constructor. + // Since _source should never be empty, we don't check for 0/return Array.Empty. + Debug.Assert(_source.Length > 0); + + var results = new TResult[_source.Length]; + for (int i = 0; i < results.Length; i++) + { + results[i] = _selector(_source[i]); + } + + return results; + } + + public List ToList() + { + TSource[] source = _source; + var results = new List(source.Length); + for (int i = 0; i < source.Length; i++) + { + results.Add(_selector(source[i])); + } + + return results; + } + + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + if (!onlyIfCheap) + { + foreach (TSource item in _source) + { + _selector(item); + } + } + + return _source.Length; + } + + public IPartition Skip(int count) + { + Debug.Assert(count > 0); + if (count >= _source.Length) + { + return EmptyPartition.Instance; + } + + return new SelectListPartitionIterator(_source, _selector, count, int.MaxValue); + } + + public IPartition Take(int count) => + count >= _source.Length ? (IPartition)this : new SelectListPartitionIterator(_source, _selector, 0, count - 1); + + public TResult TryGetElementAt(int index, out bool found) + { + if (unchecked((uint)index < (uint)_source.Length)) + { + found = true; + return _selector(_source[index]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetFirst(out bool found) + { + Debug.Assert(_source.Length > 0); // See assert in constructor + + found = true; + return _selector(_source[0]); + } + + public TResult TryGetLast(out bool found) + { + Debug.Assert(_source.Length > 0); // See assert in constructor + + found = true; + return _selector(_source[_source.Length - 1]); + } + } + + private sealed partial class SelectListIterator : IPartition + { + public TResult[] ToArray() + { + int count = _source.Count; + if (count == 0) + { + return Array.Empty(); + } + + var results = new TResult[count]; + for (int i = 0; i < results.Length; i++) + { + results[i] = _selector(_source[i]); + } + + return results; + } + + public List ToList() + { + int count = _source.Count; + var results = new List(count); + for (int i = 0; i < count; i++) + { + results.Add(_selector(_source[i])); + } + + return results; + } + + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + int count = _source.Count; + + if (!onlyIfCheap) + { + for (int i = 0; i < count; i++) + { + _selector(_source[i]); + } + } + + return count; + } + + public IPartition Skip(int count) + { + Debug.Assert(count > 0); + return new SelectListPartitionIterator(_source, _selector, count, int.MaxValue); + } + + public IPartition Take(int count) => + new SelectListPartitionIterator(_source, _selector, 0, count - 1); + + public TResult TryGetElementAt(int index, out bool found) + { + if (unchecked((uint)index < (uint)_source.Count)) + { + found = true; + return _selector(_source[index]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetFirst(out bool found) + { + if (_source.Count != 0) + { + found = true; + return _selector(_source[0]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetLast(out bool found) + { + int len = _source.Count; + if (len != 0) + { + found = true; + return _selector(_source[len - 1]); + } + + found = false; + return default(TResult); + } + } + + private sealed partial class SelectIListIterator : IPartition + { + public TResult[] ToArray() + { + int count = _source.Count; + if (count == 0) + { + return Array.Empty(); + } + + var results = new TResult[count]; + for (int i = 0; i < results.Length; i++) + { + results[i] = _selector(_source[i]); + } + + return results; + } + + public List ToList() + { + int count = _source.Count; + var results = new List(count); + for (int i = 0; i < count; i++) + { + results.Add(_selector(_source[i])); + } + + return results; + } + + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + int count = _source.Count; + + if (!onlyIfCheap) + { + for (int i = 0; i < count; i++) + { + _selector(_source[i]); + } + } + + return count; + } + + public IPartition Skip(int count) + { + Debug.Assert(count > 0); + return new SelectListPartitionIterator(_source, _selector, count, int.MaxValue); + } + + public IPartition Take(int count) => + new SelectListPartitionIterator(_source, _selector, 0, count - 1); + + public TResult TryGetElementAt(int index, out bool found) + { + if (unchecked((uint)index < (uint)_source.Count)) + { + found = true; + return _selector(_source[index]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetFirst(out bool found) + { + if (_source.Count != 0) + { + found = true; + return _selector(_source[0]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetLast(out bool found) + { + int len = _source.Count; + if (len != 0) + { + found = true; + return _selector(_source[len - 1]); + } + + found = false; + return default(TResult); + } + } + + /// + /// An iterator that maps each item of an . + /// + /// The type of the source partition. + /// The type of the mapped items. + private sealed class SelectIPartitionIterator : Iterator, IPartition + { + private readonly IPartition _source; + private readonly Func _selector; + private IEnumerator _enumerator; + + public SelectIPartitionIterator(IPartition source, Func selector) + { + Debug.Assert(source != null); + Debug.Assert(selector != null); + _source = source; + _selector = selector; + } + + public override Iterator Clone() => + new SelectIPartitionIterator(_source, _selector); + + public override bool MoveNext() + { + switch (_state) + { + case 1: + _enumerator = _source.GetEnumerator(); + _state = 2; + goto case 2; + case 2: + if (_enumerator.MoveNext()) + { + _current = _selector(_enumerator.Current); + return true; + } + + Dispose(); + break; + } + + return false; + } + + public override void Dispose() + { + if (_enumerator != null) + { + _enumerator.Dispose(); + _enumerator = null; + } + + base.Dispose(); + } + + public override IEnumerable Select(Func selector) => + new SelectIPartitionIterator(_source, CombineSelectors(_selector, selector)); + + public IPartition Skip(int count) + { + Debug.Assert(count > 0); + return new SelectIPartitionIterator(_source.Skip(count), _selector); + } + + public IPartition Take(int count) => + new SelectIPartitionIterator(_source.Take(count), _selector); + + public TResult TryGetElementAt(int index, out bool found) + { + bool sourceFound; + TSource input = _source.TryGetElementAt(index, out sourceFound); + found = sourceFound; + return sourceFound ? _selector(input) : default(TResult); + } + + public TResult TryGetFirst(out bool found) + { + bool sourceFound; + TSource input = _source.TryGetFirst(out sourceFound); + found = sourceFound; + return sourceFound ? _selector(input) : default(TResult); + } + + public TResult TryGetLast(out bool found) + { + bool sourceFound; + TSource input = _source.TryGetLast(out sourceFound); + found = sourceFound; + return sourceFound ? _selector(input) : default(TResult); + } + + private TResult[] LazyToArray() + { + Debug.Assert(_source.GetCount(onlyIfCheap: true) == -1); + + var builder = new LargeArrayBuilder(initialize: true); + foreach (TSource input in _source) + { + builder.Add(_selector(input)); + } + return builder.ToArray(); + } + + private TResult[] PreallocatingToArray(int count) + { + Debug.Assert(count > 0); + Debug.Assert(count == _source.GetCount(onlyIfCheap: true)); + + TResult[] array = new TResult[count]; + int index = 0; + foreach (TSource input in _source) + { + array[index] = _selector(input); + ++index; + } + + return array; + } + + public TResult[] ToArray() + { + int count = _source.GetCount(onlyIfCheap: true); + switch (count) + { + case -1: + return LazyToArray(); + case 0: + return Array.Empty(); + default: + return PreallocatingToArray(count); + } + } + + public List ToList() + { + int count = _source.GetCount(onlyIfCheap: true); + List list; + switch (count) + { + case -1: + list = new List(); + break; + case 0: + return new List(); + default: + list = new List(count); + break; + } + + foreach (TSource input in _source) + { + list.Add(_selector(input)); + } + + return list; + } + + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + if (!onlyIfCheap) + { + foreach (TSource item in _source) + { + _selector(item); + } + } + + return _source.GetCount(onlyIfCheap); + } + } + + /// + /// An iterator that maps each item of part of an . + /// + /// The type of the source list. + /// The type of the mapped items. + private sealed class SelectListPartitionIterator : Iterator, IPartition + { + private readonly IList _source; + private readonly Func _selector; + private readonly int _minIndexInclusive; + private readonly int _maxIndexInclusive; + + public SelectListPartitionIterator(IList source, Func selector, int minIndexInclusive, int maxIndexInclusive) + { + Debug.Assert(source != null); + Debug.Assert(selector != null); + Debug.Assert(minIndexInclusive >= 0); + Debug.Assert(minIndexInclusive <= maxIndexInclusive); + _source = source; + _selector = selector; + _minIndexInclusive = minIndexInclusive; + _maxIndexInclusive = maxIndexInclusive; + } + + public override Iterator Clone() => + new SelectListPartitionIterator(_source, _selector, _minIndexInclusive, _maxIndexInclusive); + + public override bool MoveNext() + { + // _state - 1 represents the zero-based index into the list. + // Having a separate field for the index would be more readable. However, we save it + // into _state with a bias to minimize field size of the iterator. + int index = _state - 1; + if (unchecked((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive)) + { + _current = _selector(_source[_minIndexInclusive + index]); + ++_state; + return true; + } + + Dispose(); + return false; + } + + public override IEnumerable Select(Func selector) => + new SelectListPartitionIterator(_source, CombineSelectors(_selector, selector), _minIndexInclusive, _maxIndexInclusive); + + public IPartition Skip(int count) + { + Debug.Assert(count > 0); + int minIndex = _minIndexInclusive + count; + return (uint)minIndex > (uint)_maxIndexInclusive ? EmptyPartition.Instance : new SelectListPartitionIterator(_source, _selector, minIndex, _maxIndexInclusive); + } + + public IPartition Take(int count) + { + int maxIndex = _minIndexInclusive + count - 1; + return (uint)maxIndex >= (uint)_maxIndexInclusive ? this : new SelectListPartitionIterator(_source, _selector, _minIndexInclusive, maxIndex); + } + + public TResult TryGetElementAt(int index, out bool found) + { + if ((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive) + { + found = true; + return _selector(_source[_minIndexInclusive + index]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetFirst(out bool found) + { + if (_source.Count > _minIndexInclusive) + { + found = true; + return _selector(_source[_minIndexInclusive]); + } + + found = false; + return default(TResult); + } + + public TResult TryGetLast(out bool found) + { + int lastIndex = _source.Count - 1; + if (lastIndex >= _minIndexInclusive) + { + found = true; + return _selector(_source[Math.Min(lastIndex, _maxIndexInclusive)]); + } + + found = false; + return default(TResult); + } + + private int Count + { + get + { + int count = _source.Count; + if (count <= _minIndexInclusive) + { + return 0; + } + + return Math.Min(count - 1, _maxIndexInclusive) - _minIndexInclusive + 1; + } + } + + public TResult[] ToArray() + { + int count = Count; + if (count == 0) + { + return Array.Empty(); + } + + TResult[] array = new TResult[count]; + for (int i = 0, curIdx = _minIndexInclusive; i != array.Length; ++i, ++curIdx) + { + array[i] = _selector(_source[curIdx]); + } + + return array; + } + + public List ToList() + { + int count = Count; + if (count == 0) + { + return new List(); + } + + List list = new List(count); + int end = _minIndexInclusive + count; + for (int i = _minIndexInclusive; i != end; ++i) + { + list.Add(_selector(_source[i])); + } + + return list; + } + + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + int count = Count; + + if (!onlyIfCheap) + { + int end = _minIndexInclusive + count; + for (int i = _minIndexInclusive; i != end; ++i) + { + _selector(_source[i]); + } + } + + return count; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Select.cs b/src/libraries/System.Linq/src/System/Linq/Select.cs index b1c9ae5..942d075 100644 --- a/src/libraries/System.Linq/src/System/Linq/Select.cs +++ b/src/libraries/System.Linq/src/System/Linq/Select.cs @@ -33,7 +33,7 @@ namespace System.Linq if (source is TSource[] array) { return array.Length == 0 ? - EmptyPartition.Instance : + Empty() : new SelectArrayIterator(array, selector); } @@ -47,14 +47,20 @@ namespace System.Linq if (source is IPartition partition) { - return partition is EmptyPartition - ? EmptyPartition.Instance - : new SelectIPartitionIterator(partition, selector); + IEnumerable result = null; + CreateSelectIPartitionIterator(selector, partition, ref result); + if (result != null) + { + return result; + } } return new SelectEnumerableIterator(source, selector); } + static partial void CreateSelectIPartitionIterator( + Func selector, IPartition partition, ref IEnumerable result); + public static IEnumerable Select(this IEnumerable source, Func selector) { if (source == null) @@ -89,7 +95,7 @@ namespace System.Linq /// /// The type of the source enumerable. /// The type of the mapped items. - private sealed class SelectEnumerableIterator : Iterator, IIListProvider + private sealed partial class SelectEnumerableIterator : Iterator { private readonly IEnumerable _source; private readonly Func _selector; @@ -141,54 +147,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new SelectEnumerableIterator(_source, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - var builder = new LargeArrayBuilder(initialize: true); - - foreach (TSource item in _source) - { - builder.Add(_selector(item)); - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - foreach (TSource item in _source) - { - list.Add(_selector(item)); - } - - return list; - } - - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - foreach (TSource item in _source) - { - _selector(item); - checked - { - count++; - } - } - - return count; - } } /// @@ -196,7 +154,7 @@ namespace System.Linq /// /// The type of the source array. /// The type of the mapped items. - private sealed class SelectArrayIterator : Iterator, IPartition + private sealed partial class SelectArrayIterator : Iterator { private readonly TSource[] _source; private readonly Func _selector; @@ -227,91 +185,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new SelectArrayIterator(_source, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - // See assert in constructor. - // Since _source should never be empty, we don't check for 0/return Array.Empty. - Debug.Assert(_source.Length > 0); - - var results = new TResult[_source.Length]; - for (int i = 0; i < results.Length; i++) - { - results[i] = _selector(_source[i]); - } - - return results; - } - - public List ToList() - { - TSource[] source = _source; - var results = new List(source.Length); - for (int i = 0; i < source.Length; i++) - { - results.Add(_selector(source[i])); - } - - return results; - } - - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - if (!onlyIfCheap) - { - foreach (TSource item in _source) - { - _selector(item); - } - } - - return _source.Length; - } - - public IPartition Skip(int count) - { - Debug.Assert(count > 0); - if (count >= _source.Length) - { - return EmptyPartition.Instance; - } - - return new SelectListPartitionIterator(_source, _selector, count, int.MaxValue); - } - - public IPartition Take(int count) => - count >= _source.Length ? (IPartition)this : new SelectListPartitionIterator(_source, _selector, 0, count - 1); - - public TResult TryGetElementAt(int index, out bool found) - { - if (unchecked((uint)index < (uint)_source.Length)) - { - found = true; - return _selector(_source[index]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetFirst(out bool found) - { - Debug.Assert(_source.Length > 0); // See assert in constructor - - found = true; - return _selector(_source[0]); - } - - public TResult TryGetLast(out bool found) - { - Debug.Assert(_source.Length > 0); // See assert in constructor - - found = true; - return _selector(_source[_source.Length - 1]); - } } /// @@ -319,7 +192,7 @@ namespace System.Linq /// /// The type of the source list. /// The type of the mapped items. - private sealed class SelectListIterator : Iterator, IPartition + private sealed partial class SelectListIterator : Iterator { private readonly List _source; private readonly Func _selector; @@ -359,99 +232,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new SelectListIterator(_source, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - int count = _source.Count; - if (count == 0) - { - return Array.Empty(); - } - - var results = new TResult[count]; - for (int i = 0; i < results.Length; i++) - { - results[i] = _selector(_source[i]); - } - - return results; - } - - public List ToList() - { - int count = _source.Count; - var results = new List(count); - for (int i = 0; i < count; i++) - { - results.Add(_selector(_source[i])); - } - - return results; - } - - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - int count = _source.Count; - - if (!onlyIfCheap) - { - for (int i = 0; i < count; i++) - { - _selector(_source[i]); - } - } - - return count; - } - - public IPartition Skip(int count) - { - Debug.Assert(count > 0); - return new SelectListPartitionIterator(_source, _selector, count, int.MaxValue); - } - - public IPartition Take(int count) => - new SelectListPartitionIterator(_source, _selector, 0, count - 1); - - public TResult TryGetElementAt(int index, out bool found) - { - if (unchecked((uint)index < (uint)_source.Count)) - { - found = true; - return _selector(_source[index]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetFirst(out bool found) - { - if (_source.Count != 0) - { - found = true; - return _selector(_source[0]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetLast(out bool found) - { - int len = _source.Count; - if (len != 0) - { - found = true; - return _selector(_source[len - 1]); - } - - found = false; - return default(TResult); - } } /// @@ -459,7 +239,7 @@ namespace System.Linq /// /// The type of the source list. /// The type of the mapped items. - private sealed class SelectIListIterator : Iterator, IPartition + private sealed partial class SelectIListIterator : Iterator { private readonly IList _source; private readonly Func _selector; @@ -510,439 +290,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new SelectIListIterator(_source, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - int count = _source.Count; - if (count == 0) - { - return Array.Empty(); - } - - var results = new TResult[count]; - for (int i = 0; i < results.Length; i++) - { - results[i] = _selector(_source[i]); - } - - return results; - } - - public List ToList() - { - int count = _source.Count; - var results = new List(count); - for (int i = 0; i < count; i++) - { - results.Add(_selector(_source[i])); - } - - return results; - } - - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - int count = _source.Count; - - if (!onlyIfCheap) - { - for (int i = 0; i < count; i++) - { - _selector(_source[i]); - } - } - - return count; - } - - public IPartition Skip(int count) - { - Debug.Assert(count > 0); - return new SelectListPartitionIterator(_source, _selector, count, int.MaxValue); - } - - public IPartition Take(int count) => - new SelectListPartitionIterator(_source, _selector, 0, count - 1); - - public TResult TryGetElementAt(int index, out bool found) - { - if (unchecked((uint)index < (uint)_source.Count)) - { - found = true; - return _selector(_source[index]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetFirst(out bool found) - { - if (_source.Count != 0) - { - found = true; - return _selector(_source[0]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetLast(out bool found) - { - int len = _source.Count; - if (len != 0) - { - found = true; - return _selector(_source[len - 1]); - } - - found = false; - return default(TResult); - } - } - - /// - /// An iterator that maps each item of an . - /// - /// The type of the source partition. - /// The type of the mapped items. - private sealed class SelectIPartitionIterator : Iterator, IPartition - { - private readonly IPartition _source; - private readonly Func _selector; - private IEnumerator _enumerator; - - public SelectIPartitionIterator(IPartition source, Func selector) - { - Debug.Assert(source != null); - Debug.Assert(selector != null); - _source = source; - _selector = selector; - } - - public override Iterator Clone() => - new SelectIPartitionIterator(_source, _selector); - - public override bool MoveNext() - { - switch (_state) - { - case 1: - _enumerator = _source.GetEnumerator(); - _state = 2; - goto case 2; - case 2: - if (_enumerator.MoveNext()) - { - _current = _selector(_enumerator.Current); - return true; - } - - Dispose(); - break; - } - - return false; - } - - public override void Dispose() - { - if (_enumerator != null) - { - _enumerator.Dispose(); - _enumerator = null; - } - - base.Dispose(); - } - - public override IEnumerable Select(Func selector) => - new SelectIPartitionIterator(_source, CombineSelectors(_selector, selector)); - - public IPartition Skip(int count) - { - Debug.Assert(count > 0); - return new SelectIPartitionIterator(_source.Skip(count), _selector); - } - - public IPartition Take(int count) => - new SelectIPartitionIterator(_source.Take(count), _selector); - - public TResult TryGetElementAt(int index, out bool found) - { - bool sourceFound; - TSource input = _source.TryGetElementAt(index, out sourceFound); - found = sourceFound; - return sourceFound ? _selector(input) : default(TResult); - } - - public TResult TryGetFirst(out bool found) - { - bool sourceFound; - TSource input = _source.TryGetFirst(out sourceFound); - found = sourceFound; - return sourceFound ? _selector(input) : default(TResult); - } - - public TResult TryGetLast(out bool found) - { - bool sourceFound; - TSource input = _source.TryGetLast(out sourceFound); - found = sourceFound; - return sourceFound ? _selector(input) : default(TResult); - } - - private TResult[] LazyToArray() - { - Debug.Assert(_source.GetCount(onlyIfCheap: true) == -1); - - var builder = new LargeArrayBuilder(initialize: true); - foreach (TSource input in _source) - { - builder.Add(_selector(input)); - } - return builder.ToArray(); - } - - private TResult[] PreallocatingToArray(int count) - { - Debug.Assert(count > 0); - Debug.Assert(count == _source.GetCount(onlyIfCheap: true)); - - TResult[] array = new TResult[count]; - int index = 0; - foreach (TSource input in _source) - { - array[index] = _selector(input); - ++index; - } - - return array; - } - - public TResult[] ToArray() - { - int count = _source.GetCount(onlyIfCheap: true); - switch (count) - { - case -1: - return LazyToArray(); - case 0: - return Array.Empty(); - default: - return PreallocatingToArray(count); - } - } - - public List ToList() - { - int count = _source.GetCount(onlyIfCheap: true); - List list; - switch (count) - { - case -1: - list = new List(); - break; - case 0: - return new List(); - default: - list = new List(count); - break; - } - - foreach (TSource input in _source) - { - list.Add(_selector(input)); - } - - return list; - } - - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - if (!onlyIfCheap) - { - foreach (TSource item in _source) - { - _selector(item); - } - } - - return _source.GetCount(onlyIfCheap); - } - } - - /// - /// An iterator that maps each item of part of an . - /// - /// The type of the source list. - /// The type of the mapped items. - private sealed class SelectListPartitionIterator : Iterator, IPartition - { - private readonly IList _source; - private readonly Func _selector; - private readonly int _minIndexInclusive; - private readonly int _maxIndexInclusive; - - public SelectListPartitionIterator(IList source, Func selector, int minIndexInclusive, int maxIndexInclusive) - { - Debug.Assert(source != null); - Debug.Assert(selector != null); - Debug.Assert(minIndexInclusive >= 0); - Debug.Assert(minIndexInclusive <= maxIndexInclusive); - _source = source; - _selector = selector; - _minIndexInclusive = minIndexInclusive; - _maxIndexInclusive = maxIndexInclusive; - } - - public override Iterator Clone() => - new SelectListPartitionIterator(_source, _selector, _minIndexInclusive, _maxIndexInclusive); - - public override bool MoveNext() - { - // _state - 1 represents the zero-based index into the list. - // Having a separate field for the index would be more readable. However, we save it - // into _state with a bias to minimize field size of the iterator. - int index = _state - 1; - if (unchecked((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive)) - { - _current = _selector(_source[_minIndexInclusive + index]); - ++_state; - return true; - } - - Dispose(); - return false; - } - - public override IEnumerable Select(Func selector) => - new SelectListPartitionIterator(_source, CombineSelectors(_selector, selector), _minIndexInclusive, _maxIndexInclusive); - - public IPartition Skip(int count) - { - Debug.Assert(count > 0); - int minIndex = _minIndexInclusive + count; - return (uint)minIndex > (uint)_maxIndexInclusive ? EmptyPartition.Instance : new SelectListPartitionIterator(_source, _selector, minIndex, _maxIndexInclusive); - } - - public IPartition Take(int count) - { - int maxIndex = _minIndexInclusive + count - 1; - return (uint)maxIndex >= (uint)_maxIndexInclusive ? this : new SelectListPartitionIterator(_source, _selector, _minIndexInclusive, maxIndex); - } - - public TResult TryGetElementAt(int index, out bool found) - { - if ((uint)index <= (uint)(_maxIndexInclusive - _minIndexInclusive) && index < _source.Count - _minIndexInclusive) - { - found = true; - return _selector(_source[_minIndexInclusive + index]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetFirst(out bool found) - { - if (_source.Count > _minIndexInclusive) - { - found = true; - return _selector(_source[_minIndexInclusive]); - } - - found = false; - return default(TResult); - } - - public TResult TryGetLast(out bool found) - { - int lastIndex = _source.Count - 1; - if (lastIndex >= _minIndexInclusive) - { - found = true; - return _selector(_source[Math.Min(lastIndex, _maxIndexInclusive)]); - } - - found = false; - return default(TResult); - } - - private int Count - { - get - { - int count = _source.Count; - if (count <= _minIndexInclusive) - { - return 0; - } - - return Math.Min(count - 1, _maxIndexInclusive) - _minIndexInclusive + 1; - } - } - - public TResult[] ToArray() - { - int count = Count; - if (count == 0) - { - return Array.Empty(); - } - - TResult[] array = new TResult[count]; - for (int i = 0, curIdx = _minIndexInclusive; i != array.Length; ++i, ++curIdx) - { - array[i] = _selector(_source[curIdx]); - } - - return array; - } - - public List ToList() - { - int count = Count; - if (count == 0) - { - return new List(); - } - - List list = new List(count); - int end = _minIndexInclusive + count; - for (int i = _minIndexInclusive; i != end; ++i) - { - list.Add(_selector(_source[i])); - } - - return list; - } - - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - int count = Count; - - if (!onlyIfCheap) - { - int end = _minIndexInclusive + count; - for (int i = _minIndexInclusive; i != end; ++i) - { - _selector(_source[i]); - } - } - - return count; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/SelectMany.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/SelectMany.SpeedOpt.cs new file mode 100644 index 0000000..15ed767 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/SelectMany.SpeedOpt.cs @@ -0,0 +1,74 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class SelectManySingleSelectorIterator : IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + foreach (TSource element in _source) + { + checked + { + count += _selector(element).Count(); + } + } + + return count; + } + + public TResult[] ToArray() + { + var builder = new SparseArrayBuilder(initialize: true); + var deferredCopies = new ArrayBuilder>(); + + foreach (TSource element in _source) + { + IEnumerable enumerable = _selector(element); + + if (builder.ReserveOrAdd(enumerable)) + { + deferredCopies.Add(enumerable); + } + } + + TResult[] array = builder.ToArray(); + + ArrayBuilder markers = builder.Markers; + for (int i = 0; i < markers.Count; i++) + { + Marker marker = markers[i]; + IEnumerable enumerable = deferredCopies[i]; + EnumerableHelpers.Copy(enumerable, array, marker.Index, marker.Count); + } + + return array; + } + + public List ToList() + { + var list = new List(); + + foreach (TSource element in _source) + { + list.AddRange(_selector(element)); + } + + return list; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/SelectMany.cs b/src/libraries/System.Linq/src/System/Linq/SelectMany.cs index e80c5a1..75ca930 100644 --- a/src/libraries/System.Linq/src/System/Linq/SelectMany.cs +++ b/src/libraries/System.Linq/src/System/Linq/SelectMany.cs @@ -124,7 +124,7 @@ namespace System.Linq } } - private sealed class SelectManySingleSelectorIterator : Iterator, IIListProvider + private sealed partial class SelectManySingleSelectorIterator : Iterator { private readonly IEnumerable _source; private readonly Func> _selector; @@ -162,26 +162,6 @@ namespace System.Linq base.Dispose(); } - public int GetCount(bool onlyIfCheap) - { - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - foreach (TSource element in _source) - { - checked - { - count += _selector(element).Count(); - } - } - - return count; - } - public override bool MoveNext() { switch (_state) @@ -221,46 +201,6 @@ namespace System.Linq Dispose(); return false; } - - public TResult[] ToArray() - { - var builder = new SparseArrayBuilder(initialize: true); - var deferredCopies = new ArrayBuilder>(); - - foreach (TSource element in _source) - { - IEnumerable enumerable = _selector(element); - - if (builder.ReserveOrAdd(enumerable)) - { - deferredCopies.Add(enumerable); - } - } - - TResult[] array = builder.ToArray(); - - ArrayBuilder markers = builder.Markers; - for (int i = 0; i < markers.Count; i++) - { - Marker marker = markers[i]; - IEnumerable enumerable = deferredCopies[i]; - EnumerableHelpers.Copy(enumerable, array, marker.Index, marker.Count); - } - - return array; - } - - public List ToList() - { - var list = new List(); - - foreach (TSource element in _source) - { - list.AddRange(_selector(element)); - } - - return list; - } } } } diff --git a/src/libraries/System.Linq/src/System/Linq/Skip.SizeOpt.cs b/src/libraries/System.Linq/src/System/Linq/Skip.SizeOpt.cs new file mode 100644 index 0000000..8ac33a2 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Skip.SizeOpt.cs @@ -0,0 +1,23 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private static IEnumerable SkipIterator(IEnumerable source, int count) + { + using (IEnumerator e = source.GetEnumerator()) + { + while (count > 0 && e.MoveNext()) count--; + if (count <= 0) + { + while (e.MoveNext()) yield return e.Current; + } + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Skip.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Skip.SpeedOpt.cs new file mode 100644 index 0000000..febf4c0 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Skip.SpeedOpt.cs @@ -0,0 +1,16 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private static IEnumerable SkipIterator(IEnumerable source, int count) => + source is IList sourceList ? + (IEnumerable)new ListPartition(sourceList, count, int.MaxValue) : + new EnumerablePartition(source, count, -1); + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Skip.cs b/src/libraries/System.Linq/src/System/Linq/Skip.cs index 8431a90..99bd870 100644 --- a/src/libraries/System.Linq/src/System/Linq/Skip.cs +++ b/src/libraries/System.Linq/src/System/Linq/Skip.cs @@ -32,12 +32,7 @@ namespace System.Linq return partition.Skip(count); } - if (source is IList sourceList) - { - return new ListPartition(sourceList, count, int.MaxValue); - } - - return new EnumerablePartition(source, count, -1); + return SkipIterator(source, count); } public static IEnumerable SkipWhile(this IEnumerable source, Func predicate) diff --git a/src/libraries/System.Linq/src/System/Linq/Take.SizeOpt.cs b/src/libraries/System.Linq/src/System/Linq/Take.SizeOpt.cs new file mode 100644 index 0000000..0b75ee6 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Take.SizeOpt.cs @@ -0,0 +1,23 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private static IEnumerable TakeIterator(IEnumerable source, int count) + { + if (count > 0) + { + foreach (TSource element in source) + { + yield return element; + if (--count == 0) break; + } + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Take.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Take.SpeedOpt.cs new file mode 100644 index 0000000..afc652b --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Take.SpeedOpt.cs @@ -0,0 +1,16 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private static IEnumerable TakeIterator(IEnumerable source, int count) => + source is IPartition partition ? partition.Take(count) : + source is IList sourceList ? (IEnumerable)new ListPartition(sourceList, 0, count - 1) : + new EnumerablePartition(source, 0, count - 1); + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Take.cs b/src/libraries/System.Linq/src/System/Linq/Take.cs index b73fab3..ce5d201 100644 --- a/src/libraries/System.Linq/src/System/Linq/Take.cs +++ b/src/libraries/System.Linq/src/System/Linq/Take.cs @@ -16,22 +16,9 @@ namespace System.Linq throw Error.ArgumentNull(nameof(source)); } - if (count <= 0) - { - return EmptyPartition.Instance; - } - - if (source is IPartition partition) - { - return partition.Take(count); - } - - if (source is IList sourceList) - { - return new ListPartition(sourceList, 0, count - 1); - } - - return new EnumerablePartition(source, 0, count - 1); + return count <= 0 ? + Empty() : + TakeIterator(source, count); } public static IEnumerable TakeWhile(this IEnumerable source, Func predicate) @@ -103,12 +90,9 @@ namespace System.Linq throw Error.ArgumentNull(nameof(source)); } - if (count <= 0) - { - return EmptyPartition.Instance; - } - - return TakeLastIterator(source, count); + return count <= 0 ? + Empty() : + TakeLastIterator(source, count); } private static IEnumerable TakeLastIterator(IEnumerable source, int count) diff --git a/src/libraries/System.Linq/src/System/Linq/Union.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Union.SpeedOpt.cs new file mode 100644 index 0000000..f00fead22 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Union.SpeedOpt.cs @@ -0,0 +1,35 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private abstract partial class UnionIterator : IIListProvider + { + private Set FillSet() + { + var set = new Set(_comparer); + for (int index = 0; ; ++index) + { + IEnumerable enumerable = GetEnumerable(index); + if (enumerable == null) + { + return set; + } + + set.UnionWith(enumerable); + } + } + + public TSource[] ToArray() => FillSet().ToArray(); + + public List ToList() => FillSet().ToList(); + + public int GetCount(bool onlyIfCheap) => onlyIfCheap ? -1 : FillSet().Count; + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Union.cs b/src/libraries/System.Linq/src/System/Linq/Union.cs index 6136f93..a63121e 100644 --- a/src/libraries/System.Linq/src/System/Linq/Union.cs +++ b/src/libraries/System.Linq/src/System/Linq/Union.cs @@ -31,7 +31,7 @@ namespace System.Linq /// An iterator that yields distinct values from two or more . /// /// The type of the source enumerables. - private abstract class UnionIterator : Iterator, IIListProvider + private abstract partial class UnionIterator : Iterator { internal readonly IEqualityComparer _comparer; private IEnumerator _enumerator; @@ -131,27 +131,6 @@ namespace System.Linq Dispose(); return false; } - - private Set FillSet() - { - Set set = new Set(_comparer); - for (int index = 0; ; ++index) - { - IEnumerable enumerable = GetEnumerable(index); - if (enumerable == null) - { - return set; - } - - set.UnionWith(enumerable); - } - } - - public TSource[] ToArray() => FillSet().ToArray(); - - public List ToList() => FillSet().ToList(); - - public int GetCount(bool onlyIfCheap) => onlyIfCheap ? -1 : FillSet().Count; } /// diff --git a/src/libraries/System.Linq/src/System/Linq/Where.SpeedOpt.cs b/src/libraries/System.Linq/src/System/Linq/Where.SpeedOpt.cs new file mode 100644 index 0000000..83084e4 --- /dev/null +++ b/src/libraries/System.Linq/src/System/Linq/Where.SpeedOpt.cs @@ -0,0 +1,365 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; + +namespace System.Linq +{ + public static partial class Enumerable + { + private sealed partial class WhereEnumerableIterator : IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + checked + { + count++; + } + } + } + + return count; + } + + public TSource[] ToArray() + { + var builder = new LargeArrayBuilder(initialize: true); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + builder.Add(item); + } + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + list.Add(item); + } + } + + return list; + } + } + + internal sealed partial class WhereArrayIterator : IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + checked + { + count++; + } + } + } + + return count; + } + + public TSource[] ToArray() + { + var builder = new LargeArrayBuilder(_source.Length); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + builder.Add(item); + } + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + list.Add(item); + } + } + + return list; + } + } + + private sealed partial class WhereListIterator : Iterator, IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + for (int i = 0; i < _source.Count; i++) + { + TSource item = _source[i]; + if (_predicate(item)) + { + checked + { + count++; + } + } + } + + return count; + } + + public TSource[] ToArray() + { + var builder = new LargeArrayBuilder(_source.Count); + + for (int i = 0; i < _source.Count; i++) + { + TSource item = _source[i]; + if (_predicate(item)) + { + builder.Add(item); + } + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + for (int i = 0; i < _source.Count; i++) + { + TSource item = _source[i]; + if (_predicate(item)) + { + list.Add(item); + } + } + + return list; + } + } + + private sealed partial class WhereSelectArrayIterator : IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + _selector(item); + checked + { + count++; + } + } + } + + return count; + } + + public TResult[] ToArray() + { + var builder = new LargeArrayBuilder(_source.Length); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + builder.Add(_selector(item)); + } + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + list.Add(_selector(item)); + } + } + + return list; + } + } + + private sealed partial class WhereSelectListIterator : IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + for (int i = 0; i < _source.Count; i++) + { + TSource item = _source[i]; + if (_predicate(item)) + { + _selector(item); + checked + { + count++; + } + } + } + + return count; + } + + public TResult[] ToArray() + { + var builder = new LargeArrayBuilder(_source.Count); + + for (int i = 0; i < _source.Count; i++) + { + TSource item = _source[i]; + if (_predicate(item)) + { + builder.Add(_selector(item)); + } + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + for (int i = 0; i < _source.Count; i++) + { + TSource item = _source[i]; + if (_predicate(item)) + { + list.Add(_selector(item)); + } + } + + return list; + } + } + + private sealed partial class WhereSelectEnumerableIterator : IIListProvider + { + public int GetCount(bool onlyIfCheap) + { + // In case someone uses Count() to force evaluation of + // the selector, run it provided `onlyIfCheap` is false. + + if (onlyIfCheap) + { + return -1; + } + + int count = 0; + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + _selector(item); + checked + { + count++; + } + } + } + + return count; + } + + public TResult[] ToArray() + { + var builder = new LargeArrayBuilder(initialize: true); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + builder.Add(_selector(item)); + } + } + + return builder.ToArray(); + } + + public List ToList() + { + var list = new List(); + + foreach (TSource item in _source) + { + if (_predicate(item)) + { + list.Add(_selector(item)); + } + } + + return list; + } + } + } +} diff --git a/src/libraries/System.Linq/src/System/Linq/Where.cs b/src/libraries/System.Linq/src/System/Linq/Where.cs index 34124d1..fe63843 100644 --- a/src/libraries/System.Linq/src/System/Linq/Where.cs +++ b/src/libraries/System.Linq/src/System/Linq/Where.cs @@ -30,7 +30,7 @@ namespace System.Linq if (source is TSource[] array) { return array.Length == 0 ? - (IEnumerable)EmptyPartition.Instance : + Empty() : new WhereArrayIterator(array, predicate); } @@ -78,7 +78,7 @@ namespace System.Linq /// An iterator that filters each item of an . /// /// The type of the source enumerable. - private sealed class WhereEnumerableIterator : Iterator, IIListProvider + private sealed partial class WhereEnumerableIterator : Iterator { private readonly IEnumerable _source; private readonly Func _predicate; @@ -105,29 +105,6 @@ namespace System.Linq base.Dispose(); } - public int GetCount(bool onlyIfCheap) - { - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - checked - { - count++; - } - } - } - - return count; - } - public override bool MoveNext() { switch (_state) @@ -157,36 +134,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new WhereSelectEnumerableIterator(_source, _predicate, selector); - public TSource[] ToArray() - { - var builder = new LargeArrayBuilder(initialize: true); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - builder.Add(item); - } - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - list.Add(item); - } - } - - return list; - } - public override IEnumerable Where(Func predicate) => new WhereEnumerableIterator(_source, CombinePredicates(_predicate, predicate)); } @@ -195,7 +142,7 @@ namespace System.Linq /// An iterator that filters each item of a . /// /// The type of the source array. - internal sealed class WhereArrayIterator : Iterator, IIListProvider + internal sealed partial class WhereArrayIterator : Iterator { private readonly TSource[] _source; private readonly Func _predicate; @@ -211,29 +158,6 @@ namespace System.Linq public override Iterator Clone() => new WhereArrayIterator(_source, _predicate); - public int GetCount(bool onlyIfCheap) - { - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - checked - { - count++; - } - } - } - - return count; - } - public override bool MoveNext() { int index = _state - 1; @@ -257,36 +181,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new WhereSelectArrayIterator(_source, _predicate, selector); - public TSource[] ToArray() - { - var builder = new LargeArrayBuilder(_source.Length); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - builder.Add(item); - } - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - list.Add(item); - } - } - - return list; - } - public override IEnumerable Where(Func predicate) => new WhereArrayIterator(_source, CombinePredicates(_predicate, predicate)); } @@ -295,7 +189,7 @@ namespace System.Linq /// An iterator that filters each item of a . /// /// The type of the source list. - private sealed class WhereListIterator : Iterator, IIListProvider + private sealed partial class WhereListIterator : Iterator { private readonly List _source; private readonly Func _predicate; @@ -312,30 +206,6 @@ namespace System.Linq public override Iterator Clone() => new WhereListIterator(_source, _predicate); - public int GetCount(bool onlyIfCheap) - { - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - for (int i = 0; i < _source.Count; i++) - { - TSource item = _source[i]; - if (_predicate(item)) - { - checked - { - count++; - } - } - } - - return count; - } - public override bool MoveNext() { switch (_state) @@ -365,38 +235,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new WhereSelectListIterator(_source, _predicate, selector); - public TSource[] ToArray() - { - var builder = new LargeArrayBuilder(_source.Count); - - for (int i = 0; i < _source.Count; i++) - { - TSource item = _source[i]; - if (_predicate(item)) - { - builder.Add(item); - } - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - for (int i = 0; i < _source.Count; i++) - { - TSource item = _source[i]; - if (_predicate(item)) - { - list.Add(item); - } - } - - return list; - } - public override IEnumerable Where(Func predicate) => new WhereListIterator(_source, CombinePredicates(_predicate, predicate)); } @@ -406,7 +244,7 @@ namespace System.Linq /// /// The type of the source array. /// The type of the mapped items. - private sealed class WhereSelectArrayIterator : Iterator, IIListProvider + private sealed partial class WhereSelectArrayIterator : Iterator { private readonly TSource[] _source; private readonly Func _predicate; @@ -425,33 +263,6 @@ namespace System.Linq public override Iterator Clone() => new WhereSelectArrayIterator(_source, _predicate, _selector); - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - _selector(item); - checked - { - count++; - } - } - } - - return count; - } - public override bool MoveNext() { int index = _state - 1; @@ -474,36 +285,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new WhereSelectArrayIterator(_source, _predicate, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - var builder = new LargeArrayBuilder(_source.Length); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - builder.Add(_selector(item)); - } - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - list.Add(_selector(item)); - } - } - - return list; - } } /// @@ -511,7 +292,7 @@ namespace System.Linq /// /// The type of the source list. /// The type of the mapped items. - private sealed class WhereSelectListIterator : Iterator, IIListProvider + private sealed partial class WhereSelectListIterator : Iterator { private readonly List _source; private readonly Func _predicate; @@ -531,34 +312,6 @@ namespace System.Linq public override Iterator Clone() => new WhereSelectListIterator(_source, _predicate, _selector); - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - for (int i = 0; i < _source.Count; i++) - { - TSource item = _source[i]; - if (_predicate(item)) - { - _selector(item); - checked - { - count++; - } - } - } - - return count; - } - public override bool MoveNext() { switch (_state) @@ -587,38 +340,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new WhereSelectListIterator(_source, _predicate, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - var builder = new LargeArrayBuilder(_source.Count); - - for (int i = 0; i < _source.Count; i++) - { - TSource item = _source[i]; - if (_predicate(item)) - { - builder.Add(_selector(item)); - } - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - for (int i = 0; i < _source.Count; i++) - { - TSource item = _source[i]; - if (_predicate(item)) - { - list.Add(_selector(item)); - } - } - - return list; - } } /// @@ -626,7 +347,7 @@ namespace System.Linq /// /// The type of the source enumerable. /// The type of the mapped items. - private sealed class WhereSelectEnumerableIterator : Iterator, IIListProvider + private sealed partial class WhereSelectEnumerableIterator : Iterator { private readonly IEnumerable _source; private readonly Func _predicate; @@ -657,33 +378,6 @@ namespace System.Linq base.Dispose(); } - public int GetCount(bool onlyIfCheap) - { - // In case someone uses Count() to force evaluation of - // the selector, run it provided `onlyIfCheap` is false. - - if (onlyIfCheap) - { - return -1; - } - - int count = 0; - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - _selector(item); - checked - { - count++; - } - } - } - - return count; - } - public override bool MoveNext() { switch (_state) @@ -712,36 +406,6 @@ namespace System.Linq public override IEnumerable Select(Func selector) => new WhereSelectEnumerableIterator(_source, _predicate, CombineSelectors(_selector, selector)); - - public TResult[] ToArray() - { - var builder = new LargeArrayBuilder(initialize: true); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - builder.Add(_selector(item)); - } - } - - return builder.ToArray(); - } - - public List ToList() - { - var list = new List(); - - foreach (TSource item in _source) - { - if (_predicate(item)) - { - list.Add(_selector(item)); - } - } - - return list; - } } } } diff --git a/src/libraries/System.Linq/tests/EmptyEnumerable.cs b/src/libraries/System.Linq/tests/EmptyEnumerable.cs index 88ca5ba..adf518a 100644 --- a/src/libraries/System.Linq/tests/EmptyEnumerable.cs +++ b/src/libraries/System.Linq/tests/EmptyEnumerable.cs @@ -2,8 +2,6 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. -using System.Collections; -using System.Collections.Generic; using Xunit; namespace System.Linq.Tests @@ -31,7 +29,7 @@ namespace System.Linq.Tests { Assert.Equal(new T[0], Enumerable.Empty()); Assert.Equal(0, Enumerable.Empty().Count()); - Assert.Same(Enumerable.Empty().GetEnumerator(), ((IList)Enumerable.Empty()).GetEnumerator()); + Assert.Same(Enumerable.Empty().GetEnumerator(), Enumerable.Empty().GetEnumerator()); } [Fact] @@ -42,26 +40,5 @@ namespace System.Linq.Tests TestEmptyEmpty(); TestEmptyEmpty(); } - - [Fact] - public void CastToIList() - { - var emptyEnumerable = Enumerable.Empty(); - Assert.Same(emptyEnumerable, (IList)emptyEnumerable); - } - - [Fact] - public void CastToIListGeneric() - { - var emptyEnumerable = Enumerable.Empty(); - Assert.Same(emptyEnumerable, (IList)emptyEnumerable); - } - - [Fact] - public void CastToArray() - { - var emptyEnumerable = Enumerable.Empty(); - Assert.Same(emptyEnumerable, (object[])emptyEnumerable); - } } } diff --git a/src/libraries/System.Linq/tests/EmptyPartitionTests.cs b/src/libraries/System.Linq/tests/EmptyPartitionTests.cs index 4553e57..2596bb8 100644 --- a/src/libraries/System.Linq/tests/EmptyPartitionTests.cs +++ b/src/libraries/System.Linq/tests/EmptyPartitionTests.cs @@ -31,21 +31,19 @@ namespace System.Linq.Tests } [Fact] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, ".NET Core returns the instance as an optimization")] public void SkipSame() { IEnumerable empty = GetEmptyPartition(); - // .NET Core returns the instance as an optimization. - // see https://github.com/dotnet/corefx/pull/2401. - Assert.Equal(!PlatformDetection.IsFullFramework, ReferenceEquals(empty, empty.Skip(2))); + Assert.Same(empty, empty.Skip(2)); } [Fact] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, ".NET Core returns the instance as an optimization")] public void TakeSame() { IEnumerable empty = GetEmptyPartition(); - // .NET Core returns the instance as an optimization. - // see https://github.com/dotnet/corefx/pull/2401. - Assert.Equal(!PlatformDetection.IsFullFramework, ReferenceEquals(empty, empty.Take(2))); + Assert.Same(empty, empty.Take(2)); } [Fact] @@ -99,11 +97,14 @@ namespace System.Linq.Tests Assert.Empty(GetEmptyPartition().ToList()); } + [SkipOnTargetFramework(TargetFrameworkMonikers.NetFramework, "netfx's Take returns a compiler-generated iterator whose Reset throws.")] [Fact] - public void CantResetEnumerator() + public void ResetIsNop() { IEnumerator en = GetEmptyPartition().GetEnumerator(); - Assert.Throws(() => en.Reset()); + en.Reset(); + en.Reset(); + en.Reset(); } } } diff --git a/src/libraries/System.Linq/tests/OrderedSubsetting.cs b/src/libraries/System.Linq/tests/OrderedSubsetting.cs index eebbc65..c71415a 100644 --- a/src/libraries/System.Linq/tests/OrderedSubsetting.cs +++ b/src/libraries/System.Linq/tests/OrderedSubsetting.cs @@ -226,7 +226,7 @@ namespace System.Linq.Tests } [Fact] - [SkipOnTargetFramework(TargetFrameworkMonikers.NetFramework, "This fails with an OOM with the full .NET Framework, as it iterates through the large array. See https://github.com/dotnet/corefx/pull/6821.")] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, "This fails with an OOM, as it iterates through the large array. See https://github.com/dotnet/corefx/pull/6821.")] public void TakeAndSkip_DoesntIterateRangeUnlessNecessary() { Assert.Empty(Enumerable.Range(0, int.MaxValue).Take(int.MaxValue).OrderBy(i => i).Skip(int.MaxValue - 4).Skip(15)); diff --git a/src/libraries/System.Linq/tests/RangeTests.cs b/src/libraries/System.Linq/tests/RangeTests.cs index 36a529b..ca23eec 100644 --- a/src/libraries/System.Linq/tests/RangeTests.cs +++ b/src/libraries/System.Linq/tests/RangeTests.cs @@ -213,14 +213,14 @@ namespace System.Linq.Tests } [Fact] - [SkipOnTargetFramework(TargetFrameworkMonikers.NetFramework, ".NET Core optimizes Enumerable.Range().Last(). Without this optimization, this test takes a long time. See https://github.com/dotnet/corefx/pull/2401.")] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, ".NET Core optimizes Enumerable.Range().Last(). Without this optimization, this test takes a long time. See https://github.com/dotnet/corefx/pull/2401.")] public void Last() { Assert.Equal(1000000056, Enumerable.Range(57, 1000000000).Last()); } [Fact] - [SkipOnTargetFramework(TargetFrameworkMonikers.NetFramework, ".NET Core optimizes Enumerable.Range().LastOrDefault(). Without this optimization, this test takes a long time. See https://github.com/dotnet/corefx/pull/2401.")] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, ".NET Core optimizes Enumerable.Range().LastOrDefault(). Without this optimization, this test takes a long time. See https://github.com/dotnet/corefx/pull/2401.")] public void LastOrDefault() { Assert.Equal(int.MaxValue - 101, Enumerable.Range(-100, int.MaxValue).LastOrDefault()); diff --git a/src/libraries/System.Linq/tests/SelectManyTests.cs b/src/libraries/System.Linq/tests/SelectManyTests.cs index 1026e93..4b12b40 100644 --- a/src/libraries/System.Linq/tests/SelectManyTests.cs +++ b/src/libraries/System.Linq/tests/SelectManyTests.cs @@ -468,7 +468,7 @@ namespace System.Linq.Tests } [Theory] - [SkipOnTargetFramework(TargetFrameworkMonikers.NetFramework, ".NET Core optimizes SelectMany and throws an OverflowException. On the full .NET Framework this takes a long time. See https://github.com/dotnet/corefx/pull/13942.")] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, ".NET Core optimizes SelectMany and throws an OverflowException. On the full .NET Framework this takes a long time. See https://github.com/dotnet/corefx/pull/13942.")] [InlineData(new[] { int.MaxValue, 1 })] [InlineData(new[] { 2, int.MaxValue - 1 })] [InlineData(new[] { 123, 456, int.MaxValue - 100000, 123456 })] diff --git a/src/libraries/System.Linq/tests/TakeTests.cs b/src/libraries/System.Linq/tests/TakeTests.cs index 3ce5a6a..9389e4d 100644 --- a/src/libraries/System.Linq/tests/TakeTests.cs +++ b/src/libraries/System.Linq/tests/TakeTests.cs @@ -464,7 +464,7 @@ namespace System.Linq.Tests [InlineData(1000)] [InlineData(1000000)] [InlineData(int.MaxValue)] - [SkipOnTargetFramework(TargetFrameworkMonikers.NetFramework, ".NET Core optimizes Take(...).Skip(...) on lazy sequences to avoid unecessary allocation. Without this optimization this test takes many minutes. See https://github.com/dotnet/corefx/pull/13628.")] + [SkipOnTargetFramework(~TargetFrameworkMonikers.Netcoreapp, ".NET Core optimizes Take(...).Skip(...) on lazy sequences to avoid unecessary allocation. Without this optimization this test takes many minutes. See https://github.com/dotnet/corefx/pull/13628.")] public void LazySkipAllTakenForLargeNumbers(int largeNumber) { Assert.Empty(new FastInfiniteEnumerator().Take(largeNumber).Skip(largeNumber)); -- 2.7.4