blob: f7b630043dcc8ff530d31dee3438baad3d5ad9ab (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
#if !UNITY_EDITOR
// Extra optimizations when not running in the editor, but less error checking
#define ASTAR_OPTIMIZE_POOLING
#endif
using System;
using System.Collections.Generic;
namespace Pathfinding.Util {
/// <summary>
/// Lightweight Array Pool.
/// Handy class for pooling arrays of type T.
///
/// Usage:
/// - Claim a new array using <code> SomeClass[] foo = ArrayPool<SomeClass>.Claim (capacity); </code>
/// - Use it and do stuff with it
/// - Release it with <code> ArrayPool<SomeClass>.Release (ref foo); </code>
///
/// Warning: Arrays returned from the Claim method may contain arbitrary data.
/// You cannot rely on it being zeroed out.
///
/// After you have released a array, you should never use it again, if you do use it
/// your code may modify it at the same time as some other code is using it which
/// will likely lead to bad results.
///
/// Since: Version 3.8.6
/// See: Pathfinding.Util.ListPool
/// </summary>
public static class ArrayPool<T> {
#if !ASTAR_NO_POOLING
/// <summary>
/// Maximum length of an array pooled using ClaimWithExactLength.
/// Arrays with lengths longer than this will silently not be pooled.
/// </summary>
const int MaximumExactArrayLength = 256;
/// <summary>
/// Internal pool.
/// The arrays in each bucket have lengths of 2^i
/// </summary>
static readonly Stack<T[]>[] pool = new Stack<T[]>[31];
static readonly Stack<T[]>[] exactPool = new Stack<T[]>[MaximumExactArrayLength+1];
#if !ASTAR_OPTIMIZE_POOLING
static readonly HashSet<T[]> inPool = new HashSet<T[]>();
#endif
#endif
/// <summary>
/// Returns an array with at least the specified length.
/// Warning: Returned arrays may contain arbitrary data.
/// You cannot rely on it being zeroed out.
///
/// The returned array will always be a power of two, or zero.
/// </summary>
public static T[] Claim (int minimumLength) {
if (minimumLength <= 0) {
return ClaimWithExactLength(0);
}
int bucketIndex = 0;
while ((1 << bucketIndex) < minimumLength && bucketIndex < 30) {
bucketIndex++;
}
if (bucketIndex == 30)
throw new System.ArgumentException("Too high minimum length");
#if !ASTAR_NO_POOLING
lock (pool) {
if (pool[bucketIndex] == null) {
pool[bucketIndex] = new Stack<T[]>();
}
if (pool[bucketIndex].Count > 0) {
var array = pool[bucketIndex].Pop();
#if !ASTAR_OPTIMIZE_POOLING
inPool.Remove(array);
#endif
return array;
}
}
#endif
return new T[1 << bucketIndex];
}
/// <summary>
/// Returns an array with the specified length.
/// Use with caution as pooling too many arrays with different lengths that
/// are rarely being reused will lead to an effective memory leak.
///
/// Use <see cref="Claim"/> if you just need an array that is at least as large as some value.
///
/// Warning: Returned arrays may contain arbitrary data.
/// You cannot rely on it being zeroed out.
/// </summary>
public static T[] ClaimWithExactLength (int length) {
#if !ASTAR_NO_POOLING
bool isPowerOfTwo = length != 0 && (length & (length - 1)) == 0;
if (isPowerOfTwo) {
// Will return the correct array length
return Claim(length);
}
if (length <= MaximumExactArrayLength) {
lock (pool) {
Stack<T[]> stack = exactPool[length];
if (stack != null && stack.Count > 0) {
var array = stack.Pop();
#if !ASTAR_OPTIMIZE_POOLING
inPool.Remove(array);
#endif
return array;
}
}
}
#endif
return new T[length];
}
/// <summary>
/// Pool an array.
/// If the array was got using the <see cref="ClaimWithExactLength"/> method then the allowNonPowerOfTwo parameter must be set to true.
/// The parameter exists to make sure that non power of two arrays are not pooled unintentionally which could lead to memory leaks.
/// </summary>
public static void Release (ref T[] array, bool allowNonPowerOfTwo = false) {
if (array == null) return;
if (array.GetType() != typeof(T[])) {
throw new System.ArgumentException("Expected array type " + typeof(T[]).Name + " but found " + array.GetType().Name + "\nAre you using the correct generic class?\n");
}
#if !ASTAR_NO_POOLING
bool isPowerOfTwo = array.Length != 0 && (array.Length & (array.Length - 1)) == 0;
if (!isPowerOfTwo && !allowNonPowerOfTwo && array.Length != 0) throw new System.ArgumentException("Length is not a power of 2");
lock (pool) {
#if !ASTAR_OPTIMIZE_POOLING
if (!inPool.Add(array)) {
throw new InvalidOperationException("You are trying to pool an array twice. Please make sure that you only pool it once.");
}
#endif
if (isPowerOfTwo) {
int bucketIndex = 0;
while ((1 << bucketIndex) < array.Length && bucketIndex < 30) {
bucketIndex++;
}
if (pool[bucketIndex] == null) {
pool[bucketIndex] = new Stack<T[]>();
}
pool[bucketIndex].Push(array);
} else if (array.Length <= MaximumExactArrayLength) {
Stack<T[]> stack = exactPool[array.Length];
if (stack == null) stack = exactPool[array.Length] = new Stack<T[]>();
stack.Push(array);
}
}
#endif
array = null;
}
}
/// <summary>Extension methods for List<T></summary>
public static class ListExtensions {
/// <summary>
/// Identical to ToArray but it uses ArrayPool<T> to avoid allocations if possible.
///
/// Use with caution as pooling too many arrays with different lengths that
/// are rarely being reused will lead to an effective memory leak.
/// </summary>
public static T[] ToArrayFromPool<T>(this List<T> list) {
var arr = ArrayPool<T>.ClaimWithExactLength(list.Count);
for (int i = 0; i < arr.Length; i++) {
arr[i] = list[i];
}
return arr;
}
/// <summary>
/// Clear a list faster than List<T>.Clear.
/// It turns out that the List<T>.Clear method will clear all elements in the underlaying array
/// not just the ones up to Count. If the list only has a few elements, but the capacity
/// is huge, this can cause performance problems. Using the RemoveRange method to remove
/// all elements in the list does not have this problem, however it is implemented in a
/// stupid way, so it will clear the elements twice (completely unnecessarily) so it will
/// only be faster than using the Clear method if the number of elements in the list is
/// less than half of the capacity of the list.
///
/// Hopefully this method can be removed when Unity upgrades to a newer version of Mono.
/// </summary>
public static void ClearFast<T>(this List<T> list) {
if (list.Count*2 < list.Capacity) {
list.RemoveRange(0, list.Count);
} else {
list.Clear();
}
}
}
}
|
