1 // Written in the D programming language.
2 /**
3 Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/quantizer.d)
4 */
5 module std.experimental.allocator.building_blocks.quantizer;
6
7 import std.experimental.allocator.common;
8
9 /**
10 This allocator sits on top of `ParentAllocator` and quantizes allocation sizes,
11 usually from arbitrary positive numbers to a small set of round numbers (e.g.
12 powers of two, page sizes etc). This technique is commonly used to:
13
14 $(UL
15 $(LI Preallocate more memory than requested such that later on, when
16 reallocation is needed (e.g. to grow an array), expansion can be done quickly
17 in place. Reallocation to smaller sizes is also fast (in-place) when the new
18 size requested is within the same quantum as the existing size. Code that's
19 reallocation-heavy can therefore benefit from fronting a generic allocator with
20 a `Quantizer`. These advantages are present even if `ParentAllocator` does not
21 support reallocation at all.)
22 $(LI Improve behavior of allocators sensitive to allocation sizes, such as
23 `FreeList` and `FreeTree`. Rounding allocation requests up makes for smaller
24 free lists/trees at the cost of slack memory (internal fragmentation).)
25 )
26
27 The following methods are forwarded to the parent allocator if present:
28 `allocateAll`, `owns`, `deallocateAll`, `empty`.
29
30 Preconditions: `roundingFunction` must satisfy three constraints. These are
31 not enforced (save for the use of `assert`) for the sake of efficiency.
32 $(OL
33 $(LI $(D roundingFunction(n) >= n) for all `n` of type `size_t`;)
34 $(LI `roundingFunction` must be monotonically increasing, i.e. $(D
35 roundingFunction(n1) <= roundingFunction(n2)) for all $(D n1 < n2);)
36 $(LI `roundingFunction` must be `nothrow`, `@safe`, `@nogc` and `pure`, i.e.
37 always return the same value for a given `n`.)
38 )
39 */
40 struct Quantizer(ParentAllocator, alias roundingFunction)
41 {
42 import std.traits : hasMember;
43
44 /**
45 The parent allocator. Depending on whether `ParentAllocator` holds state
46 or not, this is a member variable or an alias for
47 `ParentAllocator.instance`.
48 */
49 static if (stateSize!ParentAllocator)
50 {
51 ParentAllocator parent;
52 }
53 else
54 {
55 alias parent = ParentAllocator.instance;
56 __gshared Quantizer instance;
57 }
58
59 /**
60 Returns `roundingFunction(n)`.
61 */
62 size_t goodAllocSize(size_t n)
63 {
64 auto result = roundingFunction(n);
65 assert(result >= n);
66 return result;
67 }
68
69 /**
70 Alignment is identical to that of the parent.
71 */
72 enum alignment = ParentAllocator.alignment;
73
74 /**
75 Gets a larger buffer `buf` by calling
76 `parent.allocate(goodAllocSize(n))`. If `buf` is `null`, returns
77 `null`. Otherwise, returns $(D buf[0 .. n]).
78 */
79 void[] allocate(size_t n)
80 {
81 auto result = parent.allocate(goodAllocSize(n));
82 return result.ptr ? result.ptr[0 .. n] : null;
83 }
84
85 static if (hasMember!(ParentAllocator, "allocateZeroed"))
86 package(std) void[] allocateZeroed()(size_t n)
87 {
88 auto result = parent.allocateZeroed(goodAllocSize(n));
89 return result.ptr ? result.ptr[0 .. n] : null;
90 }
91
92 /**
93 Defined only if `parent.alignedAllocate` exists and works similarly to
94 `allocate` by forwarding to
95 $(D parent.alignedAllocate(goodAllocSize(n), a)).
96 */
97 static if (hasMember!(ParentAllocator, "alignedAllocate"))
98 void[] alignedAllocate(size_t n, uint a)
99 {
100 auto result = parent.alignedAllocate(goodAllocSize(n), a);
101 return result.ptr ? result.ptr[0 .. n] : null;
102 }
103
104 /**
105 First checks whether there's enough slack memory preallocated for `b`
106 by evaluating $(D b.length + delta <= goodAllocSize(b.length)). If that's
107 the case, expands `b` in place. Otherwise, attempts to use
108 `parent.expand` appropriately if present.
109 */
110 bool expand(ref void[] b, size_t delta)
111 {
112 if (!b || delta == 0) return delta == 0;
113 immutable allocated = goodAllocSize(b.length),
114 needed = b.length + delta,
115 neededAllocation = goodAllocSize(needed);
116 assert(b.length <= allocated);
117 assert(needed <= neededAllocation);
118 assert(allocated <= neededAllocation);
119 // Second test needed because expand must work for null pointers, too.
120 if (allocated == neededAllocation)
121 {
122 // Nice!
123 b = (() @trusted => b.ptr[0 .. needed])();
124 return true;
125 }
126 // Hail Mary
127 static if (hasMember!(ParentAllocator, "expand"))
128 {
129 // Expand to the appropriate quantum
130 auto original = (() @trusted => b.ptr[0 .. allocated])();
131 assert(goodAllocSize(needed) >= allocated);
132 if (!parent.expand(original, neededAllocation - allocated))
133 return false;
134 // Dial back the size
135 b = (() @trusted => original.ptr[0 .. needed])();
136 return true;
137 }
138 else
139 {
140 return false;
141 }
142 }
143
144 /**
145 Expands or shrinks allocated block to an allocated size of $(D
146 goodAllocSize(s)). Expansion occurs in place under the conditions required
147 by `expand`. Shrinking occurs in place if $(D goodAllocSize(b.length)
148 == goodAllocSize(s)).
149 */
150 bool reallocate(ref void[] b, size_t s)
151 {
152 if (!b.ptr)
153 {
154 b = allocate(s);
155 return b.length == s;
156 }
157 if (s >= b.length && expand(b, s - b.length)) return true;
158 immutable toAllocate = goodAllocSize(s),
159 allocated = goodAllocSize(b.length);
160 // Are the lengths within the same quantum?
161 if (allocated == toAllocate)
162 {
163 // Reallocation (whether up or down) will be done in place
164 b = b.ptr[0 .. s];
165 return true;
166 }
167 // Defer to parent (or global) with quantized size
168 auto original = b.ptr[0 .. allocated];
169 if (!parent.reallocate(original, toAllocate)) return false;
170 b = original.ptr[0 .. s];
171 return true;
172 }
173
174 /**
175 Defined only if `ParentAllocator.alignedAllocate` exists. Expansion
176 occurs in place under the conditions required by `expand`. Shrinking
177 occurs in place if $(D goodAllocSize(b.length) == goodAllocSize(s)).
178 */
179 static if (hasMember!(ParentAllocator, "alignedAllocate"))
180 bool alignedReallocate(ref void[] b, size_t s, uint a)
181 {
182 if (!b.ptr)
183 {
184 b = alignedAllocate(s, a);
185 return b.length == s;
186 }
187 if (s >= b.length && b.ptr.alignedAt(a) && expand(b, s - b.length)) return true;
188 immutable toAllocate = goodAllocSize(s),
189 allocated = goodAllocSize(b.length);
190 // Are the lengths within the same quantum?
191 if (allocated == toAllocate && b.ptr.alignedAt(a))
192 {
193 assert(b.ptr); // code above must have caught this
194 // Reallocation (whether up or down) will be done in place
195 b = b.ptr[0 .. s];
196 return true;
197 }
198 // Defer to parent (or global) with quantized size
199 auto original = b.ptr[0 .. allocated];
200 if (!parent.alignedReallocate(original, toAllocate, a)) return false;
201 b = original.ptr[0 .. s];
202 return true;
203 }
204
205 /**
206 Defined if `ParentAllocator.deallocate` exists and forwards to
207 $(D parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)])).
208 */
209 static if (hasMember!(ParentAllocator, "deallocate"))
210 bool deallocate(void[] b)
211 {
212 if (!b.ptr) return true;
213 return parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);
214 }
215
216 // Forwarding methods
217 mixin(forwardToMember("parent",
218 "allocateAll", "owns", "deallocateAll", "empty"));
219 }
220
221 ///
222 @system unittest
223 {
224 import std.experimental.allocator.building_blocks.free_tree : FreeTree;
225 import std.experimental.allocator.gc_allocator : GCAllocator;
226
227 size_t roundUpToMultipleOf(size_t s, uint base)
228 {
229 auto rem = s % base;
230 return rem ? s + base - rem : s;
231 }
232
233 // Quantize small allocations to a multiple of cache line, large ones to a
234 // multiple of page size
235 alias MyAlloc = Quantizer!(
236 FreeTree!GCAllocator,
237 n => roundUpToMultipleOf(n, n <= 16_384 ? 64 : 4096));
238 MyAlloc alloc;
239 const buf = alloc.allocate(256);
240 assert(buf.ptr);
241 }
242
243 version (StdUnittest)
244 @system unittest
245 {
246 import std.experimental.allocator.gc_allocator : GCAllocator;
247 alias MyAlloc = Quantizer!(GCAllocator,
248 (size_t n) => n.roundUpToMultipleOf(64));
249 testAllocator!(() => MyAlloc());
250
251 assert((() pure nothrow @safe @nogc => MyAlloc().goodAllocSize(1))() == 64);
252
253 auto a = MyAlloc();
254 auto b = a.allocate(42);
255 assert(b.length == 42);
256 // Inplace expand, since goodAllocSize is 64
257 assert((() @safe => a.expand(b, 22))());
258 //assert((() nothrow @safe => a.expand(b, 22))());
259 assert(b.length == 64);
260 // Trigger parent.expand, which may or may not succed
261 //() nothrow @safe { a.expand(b, 1); }();
262 () @safe { a.expand(b, 1); }();
263 assert(a.reallocate(b, 100));
264 assert(b.length == 100);
265 // Ensure deallocate inherits from parent
266 () nothrow @nogc { a.deallocate(b); }();
267 }
268
269 @system unittest
270 {
271 import std.experimental.allocator.building_blocks.region : Region;
272 import std.experimental.allocator.mallocator : Mallocator;
273 import std.typecons : Ternary;
274
275 alias Alloc = Quantizer!(Region!(Mallocator),
276 (size_t n) => n.roundUpToMultipleOf(64));
277 auto a = Alloc(Region!Mallocator(1024 * 64));
278 const b = a.allocate(42);
279 assert(b.length == 42);
280 // Check that owns inherits from parent, i.e. Region
281 assert((() pure nothrow @safe @nogc => a.owns(b))() == Ternary.yes);
282 assert((() pure nothrow @safe @nogc => a.owns(null))() == Ternary.no);
283
284 auto c = a.allocate(42);
285 assert(c.length == 42);
286 assert((() pure nothrow @safe @nogc => a.owns(c))() == Ternary.yes);
287 // Inplace expand, since goodAllocSize is 64
288 assert((() nothrow @safe => a.expand(c, 22))());
289 assert(c.length == 64);
290 // Trigger parent.expand
291 assert((() nothrow @safe => a.expand(c, 1))());
292 assert(c.length == 65);
293 // Check that reallocate inherits from parent
294 assert((() nothrow @nogc => a.reallocate(c, 100))());
295 assert(c.length == 100);
296 }
297
298 version (StdUnittest)
299 @system unittest
300 {
301 import std.experimental.allocator.building_blocks.region : Region;
302 import std.experimental.allocator.mallocator : Mallocator;
303
304 alias MyAlloc = Quantizer!(Region!(Mallocator),
305 (size_t n) => n.roundUpToMultipleOf(64));
306 testAllocator!(() => MyAlloc(Region!Mallocator(1024 * 64)));
307
308 auto a = MyAlloc(Region!Mallocator(1024 * 64));
309 void[] b;
310 assert((() nothrow @nogc => a.alignedReallocate(b, 42, 16))());
311 assert(b.length == 42);
312 assert(alignedAt(&b[0], 16));
313 }
314
315 version (StdUnittest)
316 @system unittest
317 {
318 import std.experimental.allocator.building_blocks.region : BorrowedRegion;
319 import std.typecons : Ternary;
320
321 alias MyAlloc = Quantizer!(BorrowedRegion!(),
322 (size_t n) => n.roundUpToMultipleOf(64));
323 testAllocator!(() => MyAlloc(BorrowedRegion!()(new ubyte[1024 * 64])));
324
325 auto a = MyAlloc(BorrowedRegion!()(new ubyte[1024 * 64]));
326 // Check that empty inherits from parent
327 assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes);
328 auto b = a.allocate(42);
329 assert(b.length == 42);
330 assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.no);
331 // Check that deallocateAll inherits from parent
332 assert((() nothrow @nogc => a.deallocateAll())());
333 assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes);
334 }