1 ///
2 module std.experimental.allocator.building_blocks.quantizer;
3
4 import std.experimental.allocator.common;
5
6 /**
7 This allocator sits on top of $(D ParentAllocator) and quantizes allocation
8 sizes, usually from arbitrary positive numbers to a small set of round numbers
9 (e.g. powers of two, page sizes etc). This technique is commonly used to:
10
11 $(UL
12 $(LI Preallocate more memory than requested such that later on, when
13 reallocation is needed (e.g. to grow an array), expansion can be done quickly
14 in place. Reallocation to smaller sizes is also fast (in-place) when the new
15 size requested is within the same quantum as the existing size. Code that's
16 reallocation-heavy can therefore benefit from fronting a generic allocator
17 with a $(D Quantizer). These advantages are present even if
18 $(D ParentAllocator) does not support reallocation at all.)
19 $(LI Improve behavior of allocators sensitive to allocation sizes, such as $(D
20 FreeList) and $(D FreeTree). Rounding allocation requests up makes for smaller
21 free lists/trees at the cost of slack memory (internal fragmentation).)
22 )
23
24 The following methods are forwarded to the parent allocator if present:
25 $(D allocateAll), $(D owns), $(D deallocateAll), $(D empty).
26
27 Preconditions: $(D roundingFunction) must satisfy three constraints. These are
28 not enforced (save for the use of $(D assert)) for the sake of efficiency.
29 $(OL
30 $(LI $(D roundingFunction(n) >= n) for all $(D n) of type $(D size_t);)
31 $(LI $(D roundingFunction) must be monotonically increasing, i.e. $(D
32 roundingFunction(n1) <= roundingFunction(n2)) for all $(D n1 < n2);)
33 $(LI $(D roundingFunction) must be $(D pure), i.e. always return the same
34 value for a given $(D n).)
35 )
36 */
Quantizer(ParentAllocator,alias roundingFunction)37 struct Quantizer(ParentAllocator, alias roundingFunction)
38 {
39 import std.traits : hasMember;
40
41 /**
42 The parent allocator. Depending on whether $(D ParentAllocator) holds state
43 or not, this is a member variable or an alias for
44 `ParentAllocator.instance`.
45 */
46 static if (stateSize!ParentAllocator)
47 {
48 ParentAllocator parent;
49 }
50 else
51 {
52 alias parent = ParentAllocator.instance;
53 static __gshared Quantizer instance;
54 }
55
56 /**
57 Returns $(D roundingFunction(n)).
58 */
59 size_t goodAllocSize(size_t n)
60 {
61 auto result = roundingFunction(n);
62 assert(result >= n);
63 return result;
64 }
65
66 /**
67 Alignment is identical to that of the parent.
68 */
69 enum alignment = ParentAllocator.alignment;
70
71 /**
72 Gets a larger buffer $(D buf) by calling
73 $(D parent.allocate(goodAllocSize(n))). If $(D buf) is $(D null), returns
74 $(D null). Otherwise, returns $(D buf[0 .. n]).
75 */
76 void[] allocate(size_t n)
77 {
78 auto result = parent.allocate(goodAllocSize(n));
79 return result.ptr ? result.ptr[0 .. n] : null;
80 }
81
82 /**
83 Defined only if $(D parent.alignedAllocate) exists and works similarly to
84 $(D allocate) by forwarding to
85 $(D parent.alignedAllocate(goodAllocSize(n), a)).
86 */
87 static if (hasMember!(ParentAllocator, "alignedAllocate"))
88 void[] alignedAllocate(size_t n, uint)
89 {
90 auto result = parent.alignedAllocate(goodAllocSize(n));
91 return result.ptr ? result.ptr[0 .. n] : null;
92 }
93
94 /**
95 First checks whether there's enough slack memory preallocated for $(D b)
96 by evaluating $(D b.length + delta <= goodAllocSize(b.length)). If that's
97 the case, expands $(D b) in place. Otherwise, attempts to use
98 $(D parent.expand) appropriately if present.
99 */
100 bool expand(ref void[] b, size_t delta)
101 {
102 if (!b.ptr) return delta == 0;
103 immutable allocated = goodAllocSize(b.length),
104 needed = b.length + delta,
105 neededAllocation = goodAllocSize(needed);
106 assert(b.length <= allocated);
107 assert(needed <= neededAllocation);
108 assert(allocated <= neededAllocation);
109 // Second test needed because expand must work for null pointers, too.
110 if (allocated == neededAllocation)
111 {
112 // Nice!
113 b = b.ptr[0 .. needed];
114 return true;
115 }
116 // Hail Mary
117 static if (hasMember!(ParentAllocator, "expand"))
118 {
119 // Expand to the appropriate quantum
120 auto original = b.ptr[0 .. allocated];
121 assert(goodAllocSize(needed) >= allocated);
122 if (!parent.expand(original, neededAllocation - allocated))
123 return false;
124 // Dial back the size
125 b = original.ptr[0 .. needed];
126 return true;
127 }
128 else
129 {
130 return false;
131 }
132 }
133
134 /**
135 Expands or shrinks allocated block to an allocated size of $(D
136 goodAllocSize(s)). Expansion occurs in place under the conditions required
137 by $(D expand). Shrinking occurs in place if $(D goodAllocSize(b.length)
138 == goodAllocSize(s)).
139 */
140 bool reallocate(ref void[] b, size_t s)
141 {
142 if (!b.ptr)
143 {
144 b = allocate(s);
145 return b.length == s;
146 }
147 if (s >= b.length && expand(b, s - b.length)) return true;
148 immutable toAllocate = goodAllocSize(s),
149 allocated = goodAllocSize(b.length);
150 // Are the lengths within the same quantum?
151 if (allocated == toAllocate)
152 {
153 // Reallocation (whether up or down) will be done in place
154 b = b.ptr[0 .. s];
155 return true;
156 }
157 // Defer to parent (or global) with quantized size
158 auto original = b.ptr[0 .. allocated];
159 if (!parent.reallocate(original, toAllocate)) return false;
160 b = original.ptr[0 .. s];
161 return true;
162 }
163
164 /**
165 Defined only if $(D ParentAllocator.alignedAllocate) exists. Expansion
166 occurs in place under the conditions required by $(D expand). Shrinking
167 occurs in place if $(D goodAllocSize(b.length) == goodAllocSize(s)).
168 */
169 static if (hasMember!(ParentAllocator, "alignedAllocate"))
170 bool alignedReallocate(ref void[] b, size_t s, uint a)
171 {
172 if (!b.ptr)
173 {
174 b = alignedAllocate(s);
175 return b.length == s;
176 }
177 if (s >= b.length && expand(b, s - b.length)) return true;
178 immutable toAllocate = goodAllocSize(s),
179 allocated = goodAllocSize(b.length);
180 // Are the lengths within the same quantum?
181 if (allocated == toAllocate)
182 {
183 assert(b.ptr); // code above must have caught this
184 // Reallocation (whether up or down) will be done in place
185 b = b.ptr[0 .. s];
186 return true;
187 }
188 // Defer to parent (or global) with quantized size
189 auto original = b.ptr[0 .. allocated];
190 if (!parent.alignedReallocate(original, toAllocate, a)) return false;
191 b = original.ptr[0 .. s];
192 return true;
193 }
194
195 /**
196 Defined if $(D ParentAllocator.deallocate) exists and forwards to
197 $(D parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)])).
198 */
199 static if (hasMember!(ParentAllocator, "deallocate"))
200 bool deallocate(void[] b)
201 {
202 if (!b.ptr) return true;
203 return parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);
204 }
205
206 // Forwarding methods
207 mixin(forwardToMember("parent",
208 "allocateAll", "owns", "deallocateAll", "empty"));
209 }
210
211 ///
212 @system unittest
213 {
214 import std.experimental.allocator.building_blocks.free_tree : FreeTree;
215 import std.experimental.allocator.common : roundUpToMultipleOf;
216 import std.experimental.allocator.gc_allocator : GCAllocator;
217
218 // Quantize small allocations to a multiple of cache line, large ones to a
219 // multiple of page size
220 alias MyAlloc = Quantizer!(
221 FreeTree!GCAllocator,
222 n => n.roundUpToMultipleOf(n <= 16_384 ? 64 : 4096));
223 MyAlloc alloc;
224 const buf = alloc.allocate(256);
225 assert(buf.ptr);
226 }
227
228 @system unittest
229 {
230 import std.experimental.allocator.gc_allocator : GCAllocator;
231 alias MyAlloc = Quantizer!(GCAllocator,
232 (size_t n) => n.roundUpToMultipleOf(64));
233 testAllocator!(() => MyAlloc());
234 }
235