diff options
Diffstat (limited to 'src/mscorlib/corefx/System/Buffers')
7 files changed, 867 insertions, 0 deletions
diff --git a/src/mscorlib/corefx/System/Buffers/ArrayPool.cs b/src/mscorlib/corefx/System/Buffers/ArrayPool.cs new file mode 100644 index 0000000000..441e48dab4 --- /dev/null +++ b/src/mscorlib/corefx/System/Buffers/ArrayPool.cs @@ -0,0 +1,113 @@ +// 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 +{ + /// <summary> + /// Provides a resource pool that enables reusing instances of type <see cref="T:T[]"/>. + /// </summary> + /// <remarks> + /// <para> + /// Renting and returning buffers with an <see cref="ArrayPool{T}"/> can increase performance + /// in situations where arrays are created and destroyed frequently, resulting in significant + /// memory pressure on the garbage collector. + /// </para> + /// <para> + /// This class is thread-safe. All members may be used by multiple threads concurrently. + /// </para> + /// </remarks> + public abstract class ArrayPool<T> + { + /// <summary> + /// Retrieves a shared <see cref="ArrayPool{T}"/> instance. + /// </summary> + /// <remarks> + /// The shared pool provides a default implementation of <see cref="ArrayPool{T}"/> + /// 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 <see cref="Rent"/> 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. + /// </remarks> + public static ArrayPool<T> Shared => SharedPool.Value; + + /// <summary>Stores a cached pool instance for T[].</summary> + /// <remarks> + /// Separated out into a nested class to enable lazy-initialization of the pool provided by + /// the runtime, only forced when Shared is used (and not when Create is called or when + /// other non-Shared accesses happen). + /// </remarks> + private static class SharedPool + { + /// <summary>Per-type cached pool.</summary> + /// <remarks> + /// byte[] and char[] are the most commonly pooled array types. For these we use a special pool type + /// optimized for very fast access speeds, at the expense of more memory consumption. + /// </remarks> + internal readonly static ArrayPool<T> Value = + typeof(T) == typeof(byte) || typeof(T) == typeof(char) ? new TlsOverPerCoreLockedStacksArrayPool<T>() : + Create(); + } + + /// <summary> + /// Creates a new <see cref="ArrayPool{T}"/> instance using default configuration options. + /// </summary> + /// <returns>A new <see cref="ArrayPool{T}"/> instance.</returns> + public static ArrayPool<T> Create() => new ConfigurableArrayPool<T>(); + + /// <summary> + /// Creates a new <see cref="ArrayPool{T}"/> instance using custom configuration options. + /// </summary> + /// <param name="maxArrayLength">The maximum length of array instances that may be stored in the pool.</param> + /// <param name="maxArraysPerBucket"> + /// 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. + /// </param> + /// <returns>A new <see cref="ArrayPool{T}"/> instance with the specified configuration options.</returns> + /// <remarks> + /// The created pool will group arrays into buckets, with no more than <paramref name="maxArraysPerBucket"/> + /// in each bucket and with those arrays not exceeding <paramref name="maxArrayLength"/> in length. + /// </remarks> + public static ArrayPool<T> Create(int maxArrayLength, int maxArraysPerBucket) => + new ConfigurableArrayPool<T>(maxArrayLength, maxArraysPerBucket); + + /// <summary> + /// Retrieves a buffer that is at least the requested length. + /// </summary> + /// <param name="minimumLength">The minimum length of the array needed.</param> + /// <returns> + /// An <see cref="T:T[]"/> that is at least <paramref name="minimumLength"/> in length. + /// </returns> + /// <remarks> + /// This buffer is loaned to the caller and should be returned to the same pool via + /// <see cref="Return"/> so that it may be reused in subsequent usage of <see cref="Rent"/>. + /// 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. + /// </remarks> + public abstract T[] Rent(int minimumLength); + + /// <summary> + /// Returns to the pool an array that was previously obtained via <see cref="Rent"/> on the same + /// <see cref="ArrayPool{T}"/> instance. + /// </summary> + /// <param name="array"> + /// The buffer previously obtained from <see cref="Rent"/> to return to the pool. + /// </param> + /// <param name="clearArray"> + /// If <c>true</c> and if the pool will store the buffer to enable subsequent reuse, <see cref="Return"/> + /// will clear <paramref name="array"/> of its contents so that a subsequent consumer via <see cref="Rent"/> + /// will not see the previous consumer's content. If <c>false</c> or if the pool will release the buffer, + /// the array's contents are left unchanged. + /// </param> + /// <remarks> + /// 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 <see cref="Rent"/> must only be + /// returned via <see cref="Return"/> once. The default <see cref="ArrayPool{T}"/> + /// 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. + /// </remarks> + public abstract void Return(T[] array, bool clearArray = false); + } +} diff --git a/src/mscorlib/corefx/System/Buffers/ArrayPoolEventSource.cs b/src/mscorlib/corefx/System/Buffers/ArrayPoolEventSource.cs new file mode 100644 index 0000000000..9482744144 --- /dev/null +++ b/src/mscorlib/corefx/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(); + + /// <summary>The reason for a BufferAllocated event.</summary> + internal enum BufferAllocatedReason : int + { + /// <summary>The pool is allocating a buffer to be pooled in a bucket.</summary> + Pooled, + /// <summary>The requested buffer size was too large to be pooled.</summary> + OverMaximumSize, + /// <summary>The pool has already allocated for pooling as many buffers of a particular size as it's allowed.</summary> + PoolExhausted + } + + /// <summary> + /// 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). + /// </summary> + [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); + } + + /// <summary> + /// 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. + /// </summary> + [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); + } + + /// <summary> + /// 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. + /// </summary> + [Event(3, Level = EventLevel.Verbose)] + internal void BufferReturned(int bufferId, int bufferSize, int poolId) => WriteEvent(3, bufferId, bufferSize, poolId); + } +} diff --git a/src/mscorlib/corefx/System/Buffers/ConfigurableArrayPool.cs b/src/mscorlib/corefx/System/Buffers/ConfigurableArrayPool.cs new file mode 100644 index 0000000000..1e0e769530 --- /dev/null +++ b/src/mscorlib/corefx/System/Buffers/ConfigurableArrayPool.cs @@ -0,0 +1,265 @@ +// 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 ConfigurableArrayPool<T> : ArrayPool<T> + { + /// <summary>The default maximum length of each array in the pool (2^20).</summary> + private const int DefaultMaxArrayLength = 1024 * 1024; + /// <summary>The default maximum number of arrays per bucket that are available for rent.</summary> + private const int DefaultMaxNumberOfArraysPerBucket = 50; + + private readonly Bucket[] _buckets; + + internal ConfigurableArrayPool() : this(DefaultMaxArrayLength, DefaultMaxNumberOfArraysPerBucket) + { + } + + internal ConfigurableArrayPool(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; + } + + /// <summary>Gets an ID for the pool to use with events.</summary> + 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 EmptyArray<T>.Value; + } + + 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); + } + } + + /// <summary>Provides a thread-safe bucket containing buffers that can be Rent'd and Return'd.</summary> + 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; + + /// <summary> + /// Creates the pool with numberOfBuffers arrays where each buffer is of bufferLength length. + /// </summary> + 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; + } + + /// <summary>Gets an ID for the bucket to use with events.</summary> + internal int Id => GetHashCode(); + + /// <summary>Takes an array from the bucket. If the bucket is empty, returns null.</summary> + 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; + } + + /// <summary> + /// 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. + /// </summary> + 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(SR.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/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.Unix.cs b/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.Unix.cs new file mode 100644 index 0000000000..8a1d006b12 --- /dev/null +++ b/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.Unix.cs @@ -0,0 +1,28 @@ +// 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 Microsoft.Win32; +using System.Runtime.CompilerServices; + +namespace System.Buffers +{ + internal sealed partial class TlsOverPerCoreLockedStacksArrayPool<T> + { + /// <summary>Get an identifier for the current thread to use to index into the stacks.</summary> + private static int ExecutionId + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + get + { + // On Unix, CurrentProcessorNumber is implemented in terms of sched_getcpu, which + // doesn't exist on all platforms. On those it doesn't exist on, GetCurrentProcessorNumber + // returns -1. As a fallback in that case and to spread the threads across the buckets + // by default, we use the current managed thread ID as a proxy. + int id = CurrentProcessorNumber; + if (id < 0) id = Environment.CurrentManagedThreadId; + return id; + } + } + } +} diff --git a/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.Windows.cs b/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.Windows.cs new file mode 100644 index 0000000000..d42242c910 --- /dev/null +++ b/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.Windows.cs @@ -0,0 +1,20 @@ +// 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 Microsoft.Win32; +using System.Runtime.CompilerServices; +using System.Threading; + +namespace System.Buffers +{ + internal sealed partial class TlsOverPerCoreLockedStacksArrayPool<T> : ArrayPool<T> + { + /// <summary>Get an identifier for the current thread to use to index into the stacks.</summary> + private static int ExecutionId + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + get { return CurrentProcessorNumber; } + } + } +} diff --git a/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.cs b/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.cs new file mode 100644 index 0000000000..debc33615f --- /dev/null +++ b/src/mscorlib/corefx/System/Buffers/TlsOverPerCoreLockedStacksArrayPool.cs @@ -0,0 +1,328 @@ +// 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 Microsoft.Win32; +using System.Runtime.CompilerServices; +using System.Threading; + +namespace System.Buffers +{ + /// <summary> + /// Provides an ArrayPool implementation meant to be used as the singleton returned from ArrayPool.Shared. + /// </summary> + /// <remarks> + /// The implementation uses a tiered caching scheme, with a small per-thread cache for each array size, followed + /// by a cache per array size shared by all threads, split into per-core stacks meant to be used by threads + /// running on that core. Locks are used to protect each per-core stack, because a thread can migrate after + /// checking its processor number, because multiple threads could interleave on the same core, and because + /// a thread is allowed to check other core's buckets if its core's bucket is empty/full. + /// </remarks> + internal sealed partial class TlsOverPerCoreLockedStacksArrayPool<T> : ArrayPool<T> + { + // TODO: #7747: "Investigate optimizing ArrayPool heuristics" + // - Explore caching in TLS more than one array per size per thread, and moving stale buffers to the global queue. + // - Explore dumping stale buffers from the global queue, similar to PinnableBufferCache (maybe merging them). + // - Explore changing the size of each per-core bucket, potentially dynamically or based on other factors like array size. + // - Explore changing number of buckets and what sizes of arrays are cached. + // - Investigate whether false sharing is causing any issues, in particular on LockedStack's count and the contents of its array. + // ... + + /// <summary>The number of buckets (array sizes) in the pool, one for each array length, starting from length 16.</summary> + private const int NumBuckets = 17; // Utilities.SelectBucketIndex(2*1024*1024) + /// <summary>Maximum number of per-core stacks to use per array size.</summary> + private const int MaxPerCorePerArraySizeStacks = 64; // selected to avoid needing to worry about processor groups + /// <summary>The maximum number of buffers to store in a bucket's global queue.</summary> + private const int MaxBuffersPerArraySizePerCore = 8; + + /// <summary>The length of arrays stored in the corresponding indices in <see cref="_buckets"/> and <see cref="t_tlsBuckets"/>.</summary> + private readonly int[] _bucketArraySizes; + /// <summary> + /// An array of per-core array stacks. The slots are lazily initialized to avoid creating + /// lots of overhead for unused array sizes. + /// </summary> + private readonly PerCoreLockedStacks[] _buckets = new PerCoreLockedStacks[NumBuckets]; + /// <summary>A per-thread array of arrays, to cache one array per array size per thread.</summary> + [ThreadStatic] + private static T[][] t_tlsBuckets; + /// <summary> + /// Cached processor number used as a hint for which per-core stack to access. + /// </summary> + [ThreadStatic] + private static int? t_cachedProcessorNumber; + + /// <summary>Initialize the pool.</summary> + public TlsOverPerCoreLockedStacksArrayPool() + { + var sizes = new int[NumBuckets]; + for (int i = 0; i < sizes.Length; i++) + { + sizes[i] = Utilities.GetMaxSizeForBucket(i); + } + _bucketArraySizes = sizes; + } + + /// <summary>Allocate a new PerCoreLockedStacks and try to store it into the <see cref="_buckets"/> array.</summary> + private PerCoreLockedStacks CreatePerCoreLockedStacks(int bucketIndex) + { + var inst = new PerCoreLockedStacks(); + return Interlocked.CompareExchange(ref _buckets[bucketIndex], inst, null) ?? inst; + } + + /// <summary>Gets an ID for the pool to use with events.</summary> + private int Id => GetHashCode(); + + /// <summary>Gets the processor number associated with the current thread.</summary> + /// <remarks>Uses a cached value if one exists on the current thread.</remarks> + private static int CurrentProcessorNumber + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + get + { + int? num = t_cachedProcessorNumber; + if (!num.HasValue) + { + t_cachedProcessorNumber = num = Environment.CurrentProcessorNumber; + } + return num.GetValueOrDefault(); + } + } + + 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 to log the empty array. Our pool is effectively infinite + // and we'll never allocate for rents and never store for returns. + return EmptyArray<T>.Value; + } + + ArrayPoolEventSource log = ArrayPoolEventSource.Log; + T[] buffer; + + // Get the bucket number for the array length + int bucketIndex = Utilities.SelectBucketIndex(minimumLength); + + // If the array could come from a bucket... + if (bucketIndex < _buckets.Length) + { + // First try to get it from TLS if possible. + T[][] tlsBuckets = t_tlsBuckets; + if (tlsBuckets != null) + { + buffer = tlsBuckets[bucketIndex]; + if (buffer != null) + { + tlsBuckets[bucketIndex] = null; + if (log.IsEnabled()) + { + log.BufferRented(buffer.GetHashCode(), buffer.Length, Id, bucketIndex); + } + return buffer; + } + } + + // We couldn't get a buffer from TLS, so try the global stack. + PerCoreLockedStacks b = _buckets[bucketIndex]; + if (b != null) + { + buffer = b.TryPop(); + if (buffer != null) + { + if (log.IsEnabled()) + { + log.BufferRented(buffer.GetHashCode(), buffer.Length, Id, bucketIndex); + } + return buffer; + } + } + + // No buffer available. Allocate a new buffer with a size corresponding to the appropriate bucket. + buffer = new T[_bucketArraySizes[bucketIndex]]; + } + 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, bucketIndex >= _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)); + } + + // Determine with what bucket this array length is associated + int bucketIndex = Utilities.SelectBucketIndex(array.Length); + + // If we can tell that the buffer was allocated (or empty), drop it. Otherwise, check if we have space in the pool. + if (bucketIndex < _buckets.Length) + { + // Clear the array if the user requests. + if (clearArray) + { + Array.Clear(array, 0, array.Length); + } + + // Check to see if the buffer is the correct size for this bucket + if (array.Length != _bucketArraySizes[bucketIndex]) + { + throw new ArgumentException(SR.ArgumentException_BufferNotFromPool, nameof(array)); + } + + // Write through the TLS bucket. If there weren't any buckets, create them + // and store this array into it. If there were, store this into it, and + // if there was a previous one there, push that to the global stack. This + // helps to keep LIFO access such that the most recently pushed stack will + // be in TLS and the first to be popped next. + T[][] tlsBuckets = t_tlsBuckets; + if (tlsBuckets == null) + { + t_tlsBuckets = tlsBuckets = new T[NumBuckets][]; + tlsBuckets[bucketIndex] = array; + } + else + { + T[] prev = tlsBuckets[bucketIndex]; + tlsBuckets[bucketIndex] = array; + if (prev != null) + { + PerCoreLockedStacks bucket = _buckets[bucketIndex] ?? CreatePerCoreLockedStacks(bucketIndex); + bucket.TryPush(prev); + } + } + } + + // Log that the buffer was returned + ArrayPoolEventSource log = ArrayPoolEventSource.Log; + if (log.IsEnabled()) + { + log.BufferReturned(array.GetHashCode(), array.Length, Id); + } + } + + /// <summary> + /// Stores a set of stacks of arrays, with one stack per core. + /// </summary> + private sealed class PerCoreLockedStacks + { + /// <summary>The stacks.</summary> + private readonly LockedStack[] _perCoreStacks; + + /// <summary>Initializes the stacks.</summary> + public PerCoreLockedStacks() + { + // Create the stacks. We create as many as there are processors, limited by our max. + var stacks = new LockedStack[Math.Min(Environment.ProcessorCount, MaxPerCorePerArraySizeStacks)]; + for (int i = 0; i < stacks.Length; i++) + { + stacks[i] = new LockedStack(); + } + _perCoreStacks = stacks; + } + + /// <summary>Try to push the array into the stacks. If each is full when it's tested, the array will be dropped.</summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public void TryPush(T[] array) + { + // Try to push on to the associated stack first. If that fails, + // round-robin through the other stacks. + LockedStack[] stacks = _perCoreStacks; + int index = ExecutionId % stacks.Length; + for (int i = 0; i < stacks.Length; i++) + { + if (stacks[index].TryPush(array)) return; + if (++index == stacks.Length) index = 0; + } + } + + /// <summary>Try to get an array from the stacks. If each is empty when it's tested, null will be returned.</summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public T[] TryPop() + { + // Try to pop from the associated stack first. If that fails, + // round-robin through the other stacks. + T[] arr; + LockedStack[] stacks = _perCoreStacks; + int index = ExecutionId % stacks.Length; + for (int i = 0; i < stacks.Length; i++) + { + if ((arr = stacks[index].TryPop()) != null) return arr; + if (++index == stacks.Length) index = 0; + } + return null; + } + } + + /// <summary>Provides a simple stack of arrays, protected by a lock.</summary> + private sealed class LockedStack + { + private readonly T[][] _arrays = new T[MaxBuffersPerArraySizePerCore][]; + private int _count; + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public bool TryPush(T[] array) + { + bool enqueued = false; + MonitorEnterWithProcNumberFlush(this); + if (_count < MaxBuffersPerArraySizePerCore) + { + _arrays[_count++] = array; + enqueued = true; + } + Monitor.Exit(this); + return enqueued; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public T[] TryPop() + { + T[] arr = null; + MonitorEnterWithProcNumberFlush(this); + if (_count > 0) + { + arr = _arrays[--_count]; + _arrays[_count] = null; + } + Monitor.Exit(this); + return arr; + } + + /// <summary> + /// Enters the monitor on the object. If there is any contention while trying + /// to acquire the monitor, it flushes the cached processor number so that subsequent + /// attempts to access the per-core stacks will use an updated processor number. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static void MonitorEnterWithProcNumberFlush(object obj) + { + if (!Monitor.TryEnter(obj)) + { + t_cachedProcessorNumber = null; + Monitor.Enter(obj); + } + } + } + } +} diff --git a/src/mscorlib/corefx/System/Buffers/Utilities.cs b/src/mscorlib/corefx/System/Buffers/Utilities.cs new file mode 100644 index 0000000000..823299f5fc --- /dev/null +++ b/src/mscorlib/corefx/System/Buffers/Utilities.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.Diagnostics; +using System.Runtime.CompilerServices; + +namespace System.Buffers +{ + internal static class Utilities + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + internal static int SelectBucketIndex(int bufferSize) + { + 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; + Debug.Assert(maxSize >= 0); + return maxSize; + } + } +} |