From 6f97eb941ffdbe94a98bffcbe0e99685dbd14390 Mon Sep 17 00:00:00 2001 From: Jeremy Kuhne Date: Wed, 19 Oct 2016 16:02:52 -0700 Subject: [PATCH] Move ArrayPool to System.Private.CoreLib Copy ArrayPool source from CoreFX and expose in System.Private.CoreLib. Commit migrated from https://github.com/dotnet/coreclr/commit/d6eecf7f7848d23f99ebc9d7312a59a7f12d2f16 --- .../src/mscorlib/System.Private.CoreLib.sln | 5 + src/coreclr/src/mscorlib/model.xml | 9 ++ .../src/mscorlib/mscorlib.shared.sources.props | 8 + .../src/mscorlib/src/System.Private.CoreLib.txt | 3 + .../src/mscorlib/src/System/Buffers/ArrayPool.cs | 118 +++++++++++++++ .../src/System/Buffers/ArrayPoolEventSource.cs | 78 ++++++++++ .../src/System/Buffers/DefaultArrayPool.cs | 161 +++++++++++++++++++++ .../src/System/Buffers/DefaultArrayPoolBucket.cs | 115 +++++++++++++++ .../src/mscorlib/src/System/Buffers/Utilities.cs | 36 +++++ 9 files changed, 533 insertions(+) create mode 100644 src/coreclr/src/mscorlib/src/System/Buffers/ArrayPool.cs create mode 100644 src/coreclr/src/mscorlib/src/System/Buffers/ArrayPoolEventSource.cs create mode 100644 src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPool.cs create mode 100644 src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPoolBucket.cs create mode 100644 src/coreclr/src/mscorlib/src/System/Buffers/Utilities.cs diff --git a/src/coreclr/src/mscorlib/System.Private.CoreLib.sln b/src/coreclr/src/mscorlib/System.Private.CoreLib.sln index 4ab28af..60a2316 100644 --- a/src/coreclr/src/mscorlib/System.Private.CoreLib.sln +++ b/src/coreclr/src/mscorlib/System.Private.CoreLib.sln @@ -5,6 +5,11 @@ VisualStudioVersion = 14.0.25420.1 MinimumVisualStudioVersion = 10.0.40219.1 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "System.Private.CoreLib", "System.Private.CoreLib.csproj", "{3DA06C3A-2E7B-4CB7-80ED-9B12916013F9}" EndProject +Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution Items", "{E16B1C86-C275-495B-80D6-7CE8196A18B4}" + ProjectSection(SolutionItems) = preProject + model.xml = model.xml + EndProjectSection +EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Checked|amd64 = Checked|amd64 diff --git a/src/coreclr/src/mscorlib/model.xml b/src/coreclr/src/mscorlib/model.xml index c6072f9..a51bb37 100644 --- a/src/coreclr/src/mscorlib/model.xml +++ b/src/coreclr/src/mscorlib/model.xml @@ -510,6 +510,15 @@ + + + + + + + + + diff --git a/src/coreclr/src/mscorlib/mscorlib.shared.sources.props b/src/coreclr/src/mscorlib/mscorlib.shared.sources.props index 3740622..ce68bfc 100644 --- a/src/coreclr/src/mscorlib/mscorlib.shared.sources.props +++ b/src/coreclr/src/mscorlib/mscorlib.shared.sources.props @@ -1133,6 +1133,13 @@ + + + + + + + @@ -1184,5 +1191,6 @@ + diff --git a/src/coreclr/src/mscorlib/src/System.Private.CoreLib.txt b/src/coreclr/src/mscorlib/src/System.Private.CoreLib.txt index e0a4f13..da26c54 100644 --- a/src/coreclr/src/mscorlib/src/System.Private.CoreLib.txt +++ b/src/coreclr/src/mscorlib/src/System.Private.CoreLib.txt @@ -2383,6 +2383,9 @@ InvalidOperation_CollectionBackingListTooLarge=The collection backing this List InvalidOperation_CollectionBackingDictionaryTooLarge=The collection backing this Dictionary contains too many elements. InvalidOperation_CannotRemoveLastFromEmptyCollection=Cannot remove the last element from an empty collection. +; Buffers +ArgumentException_BufferNotFromPool=The buffer is not associated with this pool and may not be returned to it. + ; Globalization resources ;------------------ diff --git a/src/coreclr/src/mscorlib/src/System/Buffers/ArrayPool.cs b/src/coreclr/src/mscorlib/src/System/Buffers/ArrayPool.cs new file mode 100644 index 0000000..af98c20 --- /dev/null +++ b/src/coreclr/src/mscorlib/src/System/Buffers/ArrayPool.cs @@ -0,0 +1,118 @@ +// 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.Runtime.CompilerServices; +using System.Threading; + +namespace System.Buffers +{ + /// + /// Provides a resource pool that enables reusing instances of type . + /// + /// + /// + /// Renting and returning buffers with an can increase performance + /// in situations where arrays are created and destroyed frequently, resulting in significant + /// memory pressure on the garbage collector. + /// + /// + /// This class is thread-safe. All members may be used by multiple threads concurrently. + /// + /// + public abstract class ArrayPool + { + /// The lazily-initialized shared pool instance. + private static ArrayPool s_sharedInstance = null; + + /// + /// Retrieves a shared instance. + /// + /// + /// The shared pool provides a default implementation of + /// that's intended for general applicability. It maintains arrays of multiple sizes, and + /// may hand back a larger array than was actually requested, but will never hand back a smaller + /// array than was requested. Renting a buffer from it with will result in an + /// existing buffer being taken from the pool if an appropriate buffer is available or in a new + /// buffer being allocated if one is not available. + /// + public static ArrayPool Shared + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + get { return Volatile.Read(ref s_sharedInstance) ?? EnsureSharedCreated(); } + } + + /// Ensures that has been initialized to a pool and returns it. + [MethodImpl(MethodImplOptions.NoInlining)] + private static ArrayPool EnsureSharedCreated() + { + Interlocked.CompareExchange(ref s_sharedInstance, Create(), null); + return s_sharedInstance; + } + + /// + /// Creates a new instance using default configuration options. + /// + /// A new instance. + public static ArrayPool Create() + { + return new DefaultArrayPool(); + } + + /// + /// Creates a new instance using custom configuration options. + /// + /// The maximum length of array instances that may be stored in the pool. + /// + /// The maximum number of array instances that may be stored in each bucket in the pool. The pool + /// groups arrays of similar lengths into buckets for faster access. + /// + /// A new instance with the specified configuration options. + /// + /// The created pool will group arrays into buckets, with no more than + /// in each bucket and with those arrays not exceeding in length. + /// + public static ArrayPool Create(int maxArrayLength, int maxArraysPerBucket) + { + return new DefaultArrayPool(maxArrayLength, maxArraysPerBucket); + } + + /// + /// Retrieves a buffer that is at least the requested length. + /// + /// The minimum length of the array needed. + /// + /// An that is at least in length. + /// + /// + /// This buffer is loaned to the caller and should be returned to the same pool via + /// so that it may be reused in subsequent usage of . + /// It is not a fatal error to not return a rented buffer, but failure to do so may lead to + /// decreased application performance, as the pool may need to create a new buffer to replace + /// the one lost. + /// + public abstract T[] Rent(int minimumLength); + + /// + /// Returns to the pool an array that was previously obtained via on the same + /// instance. + /// + /// + /// The buffer previously obtained from to return to the pool. + /// + /// + /// If true and if the pool will store the buffer to enable subsequent reuse, + /// will clear of its contents so that a subsequent consumer via + /// will not see the previous consumer's content. If false or if the pool will release the buffer, + /// the array's contents are left unchanged. + /// + /// + /// Once a buffer has been returned to the pool, the caller gives up all ownership of the buffer + /// and must not use it. The reference returned from a given call to must only be + /// returned via once. The default + /// may hold onto the returned buffer in order to rent it again, or it may release the returned buffer + /// if it's determined that the pool already has enough buffers stored. + /// + public abstract void Return(T[] array, bool clearArray = false); + } +} diff --git a/src/coreclr/src/mscorlib/src/System/Buffers/ArrayPoolEventSource.cs b/src/coreclr/src/mscorlib/src/System/Buffers/ArrayPoolEventSource.cs new file mode 100644 index 0000000..9482744 --- /dev/null +++ b/src/coreclr/src/mscorlib/src/System/Buffers/ArrayPoolEventSource.cs @@ -0,0 +1,78 @@ +// 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.Tracing; + +namespace System.Buffers +{ + [EventSource(Name = "System.Buffers.ArrayPoolEventSource")] + internal sealed class ArrayPoolEventSource : EventSource + { + internal readonly static ArrayPoolEventSource Log = new ArrayPoolEventSource(); + + /// The reason for a BufferAllocated event. + internal enum BufferAllocatedReason : int + { + /// The pool is allocating a buffer to be pooled in a bucket. + Pooled, + /// The requested buffer size was too large to be pooled. + OverMaximumSize, + /// The pool has already allocated for pooling as many buffers of a particular size as it's allowed. + PoolExhausted + } + + /// + /// Event for when a buffer is rented. This is invoked once for every successful call to Rent, + /// regardless of whether a buffer is allocated or a buffer is taken from the pool. In a + /// perfect situation where all rented buffers are returned, we expect to see the number + /// of BufferRented events exactly match the number of BuferReturned events, with the number + /// of BufferAllocated events being less than or equal to those numbers (ideally significantly + /// less than). + /// + [Event(1, Level = EventLevel.Verbose)] + internal unsafe void BufferRented(int bufferId, int bufferSize, int poolId, int bucketId) + { + EventData* payload = stackalloc EventData[4]; + payload[0].Size = sizeof(int); + payload[0].DataPointer = ((IntPtr)(&bufferId)); + payload[1].Size = sizeof(int); + payload[1].DataPointer = ((IntPtr)(&bufferSize)); + payload[2].Size = sizeof(int); + payload[2].DataPointer = ((IntPtr)(&poolId)); + payload[3].Size = sizeof(int); + payload[3].DataPointer = ((IntPtr)(&bucketId)); + WriteEventCore(1, 4, payload); + } + + /// + /// Event for when a buffer is allocated by the pool. In an ideal situation, the number + /// of BufferAllocated events is significantly smaller than the number of BufferRented and + /// BufferReturned events. + /// + [Event(2, Level = EventLevel.Informational)] + internal unsafe void BufferAllocated(int bufferId, int bufferSize, int poolId, int bucketId, BufferAllocatedReason reason) + { + EventData* payload = stackalloc EventData[5]; + payload[0].Size = sizeof(int); + payload[0].DataPointer = ((IntPtr)(&bufferId)); + payload[1].Size = sizeof(int); + payload[1].DataPointer = ((IntPtr)(&bufferSize)); + payload[2].Size = sizeof(int); + payload[2].DataPointer = ((IntPtr)(&poolId)); + payload[3].Size = sizeof(int); + payload[3].DataPointer = ((IntPtr)(&bucketId)); + payload[4].Size = sizeof(BufferAllocatedReason); + payload[4].DataPointer = ((IntPtr)(&reason)); + WriteEventCore(2, 5, payload); + } + + /// + /// Event raised when a buffer is returned to the pool. This event is raised regardless of whether + /// the returned buffer is stored or dropped. In an ideal situation, the number of BufferReturned + /// events exactly matches the number of BufferRented events. + /// + [Event(3, Level = EventLevel.Verbose)] + internal void BufferReturned(int bufferId, int bufferSize, int poolId) => WriteEvent(3, bufferId, bufferSize, poolId); + } +} diff --git a/src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPool.cs b/src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPool.cs new file mode 100644 index 0000000..ca8a066 --- /dev/null +++ b/src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPool.cs @@ -0,0 +1,161 @@ +// 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.Buffers +{ + internal sealed partial class DefaultArrayPool : ArrayPool + { + /// The default maximum length of each array in the pool (2^20). + private const int DefaultMaxArrayLength = 1024 * 1024; + /// The default maximum number of arrays per bucket that are available for rent. + private const int DefaultMaxNumberOfArraysPerBucket = 50; + /// Lazily-allocated empty array used when arrays of length 0 are requested. + private static T[] s_emptyArray; // we support contracts earlier than those with Array.Empty() + + private readonly Bucket[] _buckets; + + internal DefaultArrayPool() : this(DefaultMaxArrayLength, DefaultMaxNumberOfArraysPerBucket) + { + } + + internal DefaultArrayPool(int maxArrayLength, int maxArraysPerBucket) + { + if (maxArrayLength <= 0) + { + throw new ArgumentOutOfRangeException(nameof(maxArrayLength)); + } + if (maxArraysPerBucket <= 0) + { + throw new ArgumentOutOfRangeException(nameof(maxArraysPerBucket)); + } + + // Our bucketing algorithm has a min length of 2^4 and a max length of 2^30. + // Constrain the actual max used to those values. + const int MinimumArrayLength = 0x10, MaximumArrayLength = 0x40000000; + if (maxArrayLength > MaximumArrayLength) + { + maxArrayLength = MaximumArrayLength; + } + else if (maxArrayLength < MinimumArrayLength) + { + maxArrayLength = MinimumArrayLength; + } + + // Create the buckets. + int poolId = Id; + int maxBuckets = Utilities.SelectBucketIndex(maxArrayLength); + var buckets = new Bucket[maxBuckets + 1]; + for (int i = 0; i < buckets.Length; i++) + { + buckets[i] = new Bucket(Utilities.GetMaxSizeForBucket(i), maxArraysPerBucket, poolId); + } + _buckets = buckets; + } + + /// Gets an ID for the pool to use with events. + private int Id => GetHashCode(); + + public override T[] Rent(int minimumLength) + { + // Arrays can't be smaller than zero. We allow requesting zero-length arrays (even though + // pooling such an array isn't valuable) as it's a valid length array, and we want the pool + // to be usable in general instead of using `new`, even for computed lengths. + if (minimumLength < 0) + { + throw new ArgumentOutOfRangeException(nameof(minimumLength)); + } + else if (minimumLength == 0) + { + // No need for events with the empty array. Our pool is effectively infinite + // and we'll never allocate for rents and never store for returns. + return s_emptyArray ?? (s_emptyArray = new T[0]); + } + + var log = ArrayPoolEventSource.Log; + T[] buffer = null; + + int index = Utilities.SelectBucketIndex(minimumLength); + if (index < _buckets.Length) + { + // Search for an array starting at the 'index' bucket. If the bucket is empty, bump up to the + // next higher bucket and try that one, but only try at most a few buckets. + const int MaxBucketsToTry = 2; + int i = index; + do + { + // Attempt to rent from the bucket. If we get a buffer from it, return it. + buffer = _buckets[i].Rent(); + if (buffer != null) + { + if (log.IsEnabled()) + { + log.BufferRented(buffer.GetHashCode(), buffer.Length, Id, _buckets[i].Id); + } + return buffer; + } + } + while (++i < _buckets.Length && i != index + MaxBucketsToTry); + + // The pool was exhausted for this buffer size. Allocate a new buffer with a size corresponding + // to the appropriate bucket. + buffer = new T[_buckets[index]._bufferLength]; + } + else + { + // The request was for a size too large for the pool. Allocate an array of exactly the requested length. + // When it's returned to the pool, we'll simply throw it away. + buffer = new T[minimumLength]; + } + + if (log.IsEnabled()) + { + int bufferId = buffer.GetHashCode(), bucketId = -1; // no bucket for an on-demand allocated buffer + log.BufferRented(bufferId, buffer.Length, Id, bucketId); + log.BufferAllocated(bufferId, buffer.Length, Id, bucketId, index >= _buckets.Length ? + ArrayPoolEventSource.BufferAllocatedReason.OverMaximumSize : ArrayPoolEventSource.BufferAllocatedReason.PoolExhausted); + } + + return buffer; + } + + public override void Return(T[] array, bool clearArray = false) + { + if (array == null) + { + throw new ArgumentNullException(nameof(array)); + } + else if (array.Length == 0) + { + // Ignore empty arrays. When a zero-length array is rented, we return a singleton + // rather than actually taking a buffer out of the lowest bucket. + return; + } + + // Determine with what bucket this array length is associated + int bucket = Utilities.SelectBucketIndex(array.Length); + + // If we can tell that the buffer was allocated, drop it. Otherwise, check if we have space in the pool + if (bucket < _buckets.Length) + { + // Clear the array if the user requests + if (clearArray) + { + Array.Clear(array, 0, array.Length); + } + + // Return the buffer to its bucket. In the future, we might consider having Return return false + // instead of dropping a bucket, in which case we could try to return to a lower-sized bucket, + // just as how in Rent we allow renting from a higher-sized bucket. + _buckets[bucket].Return(array); + } + + // Log that the buffer was returned + var log = ArrayPoolEventSource.Log; + if (log.IsEnabled()) + { + log.BufferReturned(array.GetHashCode(), array.Length, Id); + } + } + } +} diff --git a/src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPoolBucket.cs b/src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPoolBucket.cs new file mode 100644 index 0000000..a3670b1 --- /dev/null +++ b/src/coreclr/src/mscorlib/src/System/Buffers/DefaultArrayPoolBucket.cs @@ -0,0 +1,115 @@ +// 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.Threading; + +namespace System.Buffers +{ + internal sealed partial class DefaultArrayPool : ArrayPool + { + /// Provides a thread-safe bucket containing buffers that can be Rent'd and Return'd. + private sealed class Bucket + { + internal readonly int _bufferLength; + private readonly T[][] _buffers; + private readonly int _poolId; + + private SpinLock _lock; // do not make this readonly; it's a mutable struct + private int _index; + + /// + /// Creates the pool with numberOfBuffers arrays where each buffer is of bufferLength length. + /// + internal Bucket(int bufferLength, int numberOfBuffers, int poolId) + { + _lock = new SpinLock(Debugger.IsAttached); // only enable thread tracking if debugger is attached; it adds non-trivial overheads to Enter/Exit + _buffers = new T[numberOfBuffers][]; + _bufferLength = bufferLength; + _poolId = poolId; + } + + /// Gets an ID for the bucket to use with events. + internal int Id => GetHashCode(); + + /// Takes an array from the bucket. If the bucket is empty, returns null. + internal T[] Rent() + { + T[][] buffers = _buffers; + T[] buffer = null; + + // While holding the lock, grab whatever is at the next available index and + // update the index. We do as little work as possible while holding the spin + // lock to minimize contention with other threads. The try/finally is + // necessary to properly handle thread aborts on platforms which have them. + bool lockTaken = false, allocateBuffer = false; + try + { + _lock.Enter(ref lockTaken); + + if (_index < buffers.Length) + { + buffer = buffers[_index]; + buffers[_index++] = null; + allocateBuffer = buffer == null; + } + } + finally + { + if (lockTaken) _lock.Exit(false); + } + + // While we were holding the lock, we grabbed whatever was at the next available index, if + // there was one. If we tried and if we got back null, that means we hadn't yet allocated + // for that slot, in which case we should do so now. + if (allocateBuffer) + { + buffer = new T[_bufferLength]; + + var log = ArrayPoolEventSource.Log; + if (log.IsEnabled()) + { + log.BufferAllocated(buffer.GetHashCode(), _bufferLength, _poolId, Id, + ArrayPoolEventSource.BufferAllocatedReason.Pooled); + } + } + + return buffer; + } + + /// + /// Attempts to return the buffer to the bucket. If successful, the buffer will be stored + /// in the bucket and true will be returned; otherwise, the buffer won't be stored, and false + /// will be returned. + /// + internal void Return(T[] array) + { + // Check to see if the buffer is the correct size for this bucket + if (array.Length != _bufferLength) + { + throw new ArgumentException(Environment.GetResourceString("ArgumentException_BufferNotFromPool", nameof(array))); + } + + // While holding the spin lock, if there's room available in the bucket, + // put the buffer into the next available slot. Otherwise, we just drop it. + // The try/finally is necessary to properly handle thread aborts on platforms + // which have them. + bool lockTaken = false; + try + { + _lock.Enter(ref lockTaken); + + if (_index != 0) + { + _buffers[--_index] = array; + } + } + finally + { + if (lockTaken) _lock.Exit(false); + } + } + } + } +} diff --git a/src/coreclr/src/mscorlib/src/System/Buffers/Utilities.cs b/src/coreclr/src/mscorlib/src/System/Buffers/Utilities.cs new file mode 100644 index 0000000..372a26c --- /dev/null +++ b/src/coreclr/src/mscorlib/src/System/Buffers/Utilities.cs @@ -0,0 +1,36 @@ +// 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.Runtime.CompilerServices; + +namespace System.Buffers +{ + internal static class Utilities + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + internal static int SelectBucketIndex(int bufferSize) + { + BCLDebug.Assert(bufferSize > 0); + + uint bitsRemaining = ((uint)bufferSize - 1) >> 4; + + int poolIndex = 0; + if (bitsRemaining > 0xFFFF) { bitsRemaining >>= 16; poolIndex = 16; } + if (bitsRemaining > 0xFF) { bitsRemaining >>= 8; poolIndex += 8; } + if (bitsRemaining > 0xF) { bitsRemaining >>= 4; poolIndex += 4; } + if (bitsRemaining > 0x3) { bitsRemaining >>= 2; poolIndex += 2; } + if (bitsRemaining > 0x1) { bitsRemaining >>= 1; poolIndex += 1; } + + return poolIndex + (int)bitsRemaining; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + internal static int GetMaxSizeForBucket(int binIndex) + { + int maxSize = 16 << binIndex; + BCLDebug.Assert(maxSize >= 0); + return maxSize; + } + } +} -- 2.7.4