-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathstack_alloc.html
240 lines (205 loc) · 7.4 KB
/
stack_alloc.html
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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>Stack Allocators</title>
</head>
<body>
<h1 align="center">stack_alloc</h1>
<p align = "center">Howard Hinnant</p>
<h2>Introduction</h2>
<hr/>
<p>
<b>Update 2015-12-13:</b>
</p>
<p>
Thanks to
<a href="http://stackoverflow.com/q/33722907/576911">this stackoverflow question</a>
I have revisited this handy little allocator and made several improvements.
</p>
<hr/>
<p>
<b>Update:</b>
</p>
<p>
I've updated this article with a new allocator that is fully C++11 conforming.
The allocator it replaces was not fully C++03 nor C++11 conforming because
copies were not equal.
</p>
<hr/>
<p>
Sometimes you need a container that is <i>almost</i> always going to hold just a
few elements, but it must be prepared for the "large" use case as well. It is
often advantageous to have the container allocate off of the local stack up to
a given size, in order to avoid a dynamic allocation for the common case.
</p>
<p>
Programmers often believe they need to write custom containers to get this
optimization instead of using the standard containers such as
<tt>std::vector<T></tt> and <tt>std::list<T></tt>. This is certainly
doable. However I do not believe this is the best way to go.
</p>
<p>
Instead I prefer to write a custom allocator which can be used with any of the
standard containers. This custom allocator can be written in several different
variants and this brief paper outlines only one. But in general, such an
allocator refers to a buffer either on the stack, or with static or thread
storage duration. So the end result is the same as writing your own
container, but you get to reuse the standard container code.
</p>
<p>
Allocator requirements for C++11 are backwards compatible in that C++98/03
allocators will work in C++11 containers. However C++11 allocators will not
work in C++98/03 containers. The allocator demonstrated here is purposefully a
C++11 allocator and thus will not work with C++98/03 containers. I chose this
presentation because C++11 allocators need not have a lot of distracting
boiler-plate (it can be defaulted). However it is a relatively trivial task to
add the boiler-plate C++98/03 allocator requirements to this allocator if
desired.
</p>
<p>
This allocator will dole out memory in units of <code>alignment</code> which defaults
to <code>alignof(std::max_align_t)</code>. This is the same alignment which
<code>malloc</code> and <code>new</code> hand out memory. If there is room on
the stack supplied buffer (you specify the buffer size), the memory will be
allocated on the stack, else it will ask <code>new</code> for the memory.
</p>
<p>
If memory is tight (when is it not!), you can reduce the alignment requirements
via the defaulted third template argument of <code>short_alloc</code>. If you
do this, and then the container attempts to allocate memory with alignment
requirements greater than you have specified, a compile-time error will result.
Thus you can safely experiment with reducing the alignment requirement, without
having to know implementation details of the container you're using
<code>short_alloc</code> with.
</p>
<h2>A small <tt>vector</tt></h2>
<blockquote><pre>
#include "<a href="short_alloc.h">short_alloc.h</a>"
#include <iostream>
#include <new>
#include <vector>
// Replace new and delete just for the purpose of demonstrating that
// they are not called.
std::size_t memory = 0;
std::size_t alloc = 0;
void* operator new(std::size_t s) throw(std::bad_alloc)
{
memory += s;
++alloc;
return malloc(s);
}
void operator delete(void* p) throw()
{
--alloc;
free(p);
}
void memuse()
{
std::cout << "memory = " << memory << '\n';
std::cout << "alloc = " << alloc << '\n';
}
// Create a vector<T> template with a small buffer of 200 bytes.
// Note for vector it is possible to reduce the alignment requirements
// down to alignof(T) because vector doesn't allocate anything but T's.
// And if we're wrong about that guess, it is a compile-time error, not
// a run time error.
template <class T, std::size_t BufSize = 200>
using SmallVector = std::vector<T, short_alloc<T, BufSize, alignof(T)>>;
int main()
{
// Create the stack-based arena from which to allocate
SmallVector<int>::allocator_type::arena_type a;
// Create the vector which uses that arena.
SmallVector<int> v{a};
// Exercise the vector and note that new/delete are not getting called.
v.push_back(1);
memuse();
v.push_back(2);
memuse();
v.push_back(3);
memuse();
v.push_back(4);
memuse();
// Yes, the correct values are actually in the vector
for (auto i : v)
std::cout << i << ' ';
std::cout << '\n';
}
memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
1 2 3 4
</pre></blockquote>
<p>
In the above example I've created a custom <tt>new/delete</tt> just for the purpose
of monitoring heap allocations. A <tt>vector<int></tt> is created that
will allocate up to 200 <tt>bytes</tt>'s before going to the heap.
</p>
<h2>A small <tt>list</tt></h2>
<p>
This works with <tt>list</tt> too. Note though that here I have defaulted the alignment
requirements because <code>std::list<T></code> allocates internal nodes that may
have larger alignment requirements than <code>T</code>. If desired, I could experiment
with reduced alignment requirements here and get a per-instantiation compile-time check
for each experiment. Those results won't be portable, but on porting the experiment will
either run correctly or fail to compile.
</p>
<blockquote><pre>
template <class T, std::size_t BufSize = 200>
using SmallList = std::list<T, short_alloc<T, BufSize>>;
int main()
{
SmallList<int>::allocator_type::arena_type a;
SmallList<int> v{a};
v.push_back(1);
memuse();
v.push_back(2);
memuse();
v.push_back(3);
memuse();
v.push_back(4);
memuse();
for (auto i : v)
std::cout << i << ' ';
std::cout << '\n';
}
memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
memory = 0
alloc = 0
1 2 3 4
</pre></blockquote>
<h2>A small <tt>unordered_set</tt></h2>
<p>
Yes, you can make a small <tt>unordered_set</tt> too. Here I've experimentally
determined on my system that I can reduce the alignment requirement down as low as
8 for many types <code>T</code>. The compiler may tell you that this number is too
small on your system.
</p>
<blockquote><pre>
template <class T, std::size_t BufSize = 200>
using SmallSet = std::unordered_set<T, std::hash<T>, std::equal_to<T>,
short_alloc<T, BufSize, alignof(T) < 8 ? 8 : alignof(T)>>;
int main()
{
SmallSet<int>::allocator_type::arena_type a;
SmallSet<int> v{a};
...
</pre></blockquote>
<p>
Next time you're tempted to write your own container, take a moment to explore
the possibility of reusing the standard containers. That's what they are there
for. You may be surprised at how they can be customized to meet your needs.
</p>
</body>
</html>