2 * This file is open source software, licensed to you under the terms
3 * of the Apache License, Version 2.0 (the "License"). See the NOTICE file
4 * distributed with this work for additional information regarding copyright
5 * ownership. You may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing,
12 * software distributed under the License is distributed on an
13 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 * KIND, either express or implied. See the License for the
15 * specific language governing permissions and limitations
19 * Copyright (C) 2016 ScyllaDB Ltd.
29 // An unbounded FIFO queue of objects of type T.
31 // It provides operations to push items in one end of the queue, and pop them
32 // from the other end of the queue - both operations are guaranteed O(1)
33 // (not just amortized O(1)). The size() operation is also O(1).
34 // chunked_fifo also guarantees that the largest contiguous memory allocation
35 // it does is O(1). The total memory used is, of course, O(N).
37 // How does chunked_fifo differ from std::list<>, circular_buffer<> and
40 // std::list<> can also make all the above guarantees, but is inefficient -
41 // both at run speed (every operation requires an allocation), and in memory
42 // use. Much more efficient than std::list<> is our circular_buffer<>, which
43 // allocates a contiguous array to hold the items and only reallocates it,
44 // exponentially, when the queue grows. On one test of several different
45 // push/pop scenarios, circular_buffer<> was between 5 and 20 times faster
46 // than std::list, and also used considerably less memory.
47 // The problem with circular_buffer<> is that gives up on the last guarantee
48 // we made above: circular_buffer<> allocates all the items in one large
49 // contiguous allocation - that might not be possible when the memory is
51 // std::deque<> aims to solve the contiguous allocation problem by allocating
52 // smaller chunks of the queue, and keeping a list of them in an array. This
53 // array is necessary to allow for O(1) random access to any element, a
54 // feature which we do not need; But this array is itself contiguous so
55 // std::deque<> attempts larger contiguous allocations the larger the queue
56 // gets: std::deque<>'s contiguous allocation is still O(N) and in fact
57 // exactly 1/64 of the size of circular_buffer<>'s contiguous allocation.
58 // So it's an improvement over circular_buffer<>, but not a full solution.
60 // chunked_fifo<> is such a solution: it also allocates the queue in fixed-
61 // size chunks (just like std::deque) but holds them in a linked list, not
62 // a contiguous array, so there are no large contiguous allocations.
64 // Unlike std::deque<> or circular_buffer<>, chunked_fifo only provides the
65 // operations needed by std::queue, i.e.,: empty(), size(), front(), back(),
66 // push_back() and pop_front(). For simplicity, we do *not* implement other
67 // possible operations, like inserting or deleting elements from the "wrong"
68 // side of the queue or from the middle, nor random-access to items in the
69 // middle of the queue or iteration over the items without popping them.
71 // Another feature of chunked_fifo which std::deque is missing is the ability
72 // to control the chunk size, as a template parameter. In std::deque the
73 // chunk size is undocumented and fixed - in gcc, it is always 512 bytes.
74 // chunked_fifo, on the other hand, makes the chunk size (in number of items
75 // instead of bytes) a template parameter; In situations where the queue is
76 // expected to become very long, using a larger chunk size might make sense
77 // because it will result in fewer allocations.
79 // chunked_fifo uses uninitialized storage for unoccupied elements, and thus
80 // uses move/copy constructors instead of move/copy assignments, which are
83 template <typename T, size_t items_per_chunk = 128>
85 static_assert((items_per_chunk & (items_per_chunk - 1)) == 0,
86 "chunked_fifo chunk size must be power of two");
88 maybe_item() noexcept {}
93 maybe_item items[items_per_chunk];
95 // begin and end interpreted mod items_per_chunk
99 // We pop from the chunk at _front_chunk. This chunk is then linked to
100 // the following chunks via the "next" link. _back_chunk points to the
101 // last chunk in this list, and it is where we push.
102 chunk* _front_chunk = nullptr; // where we pop
103 chunk* _back_chunk = nullptr; // where we push
104 // We want an O(1) size but don't want to maintain a size() counter
105 // because this will slow down every push and pop operation just for
106 // the rare size() call. Instead, we just keep a count of chunks (which
107 // doesn't change on every push or pop), from which we can calculate
108 // size() when needed, and still be O(1).
109 // This assumes the invariant that all middle chunks (except the front
110 // and back) are always full.
112 // A list of freed chunks, to support reserve() and to improve
113 // performance of repeated push and pop, especially on an empty queue.
114 // It is a performance/memory tradeoff how many freed chunks to keep
115 // here (see save_free_chunks constant below).
116 chunk* _free_chunks = nullptr;
117 size_t _nfree_chunks = 0;
119 using value_type = T;
120 using size_type = size_t;
121 using reference = T&;
123 using const_reference = const T&;
124 using const_pointer = const T*;
126 chunked_fifo() = default;
127 chunked_fifo(chunked_fifo&& x) noexcept;
128 chunked_fifo(const chunked_fifo& X) = delete;
130 chunked_fifo& operator=(const chunked_fifo&) = delete;
131 chunked_fifo& operator=(chunked_fifo&&) noexcept;
132 inline void push_back(const T& data);
133 inline void push_back(T&& data);
135 const T& back() const;
136 template <typename... A>
137 inline void emplace_back(A&&... args);
138 inline T& front() const noexcept;
139 inline void pop_front() noexcept;
140 inline bool empty() const noexcept;
141 inline size_t size() const noexcept;
142 void clear() noexcept;
143 // reserve(n) ensures that at least (n - size()) further push() calls can
144 // be served without needing new memory allocation.
145 // Calling pop()s between these push()es is also allowed and does not
146 // alter this guarantee.
147 // Note that reserve() does not reduce the amount of memory already
148 // reserved - use shrink_to_fit() for that.
149 void reserve(size_t n);
150 // shrink_to_fit() frees memory held, but unused, by the queue. Such
151 // unused memory might exist after pops, or because of reserve().
152 void shrink_to_fit();
154 void back_chunk_new();
155 void front_chunk_delete() noexcept;
156 inline void ensure_room_back();
157 void undo_room_back();
158 inline size_t mask(size_t idx) const noexcept;
162 template <typename T, size_t items_per_chunk>
164 chunked_fifo<T, items_per_chunk>::chunked_fifo(chunked_fifo&& x) noexcept
165 : _front_chunk(x._front_chunk)
166 , _back_chunk(x._back_chunk)
167 , _nchunks(x._nchunks)
168 , _free_chunks(x._free_chunks)
169 , _nfree_chunks(x._nfree_chunks) {
170 x._front_chunk = nullptr;
171 x._back_chunk = nullptr;
173 x._free_chunks = nullptr;
177 template <typename T, size_t items_per_chunk>
179 chunked_fifo<T, items_per_chunk>&
180 chunked_fifo<T, items_per_chunk>::operator=(chunked_fifo&& x) noexcept {
182 this->~chunked_fifo();
183 new (this) chunked_fifo(std::move(x));
188 template <typename T, size_t items_per_chunk>
190 chunked_fifo<T, items_per_chunk>::mask(size_t idx) const noexcept {
191 return idx & (items_per_chunk - 1);
194 template <typename T, size_t items_per_chunk>
196 chunked_fifo<T, items_per_chunk>::empty() const noexcept {
197 return _front_chunk == nullptr;
200 template <typename T, size_t items_per_chunk>
202 chunked_fifo<T, items_per_chunk>::size() const noexcept{
203 if (_front_chunk == nullptr) {
205 } else if (_back_chunk == _front_chunk) {
207 return _front_chunk->end - _front_chunk->begin;
209 return _front_chunk->end - _front_chunk->begin
210 +_back_chunk->end - _back_chunk->begin
211 + (_nchunks - 2) * items_per_chunk;
215 template <typename T, size_t items_per_chunk>
216 void chunked_fifo<T, items_per_chunk>::clear() noexcept {
222 // This is specialized code to free the contents of all the chunks and the
223 // chunks themselves. but since destroying a very full queue is not an
224 // important use case to optimize, the simple loop above is preferable.
226 // Empty, nothing to do
229 // Delete front chunk (partially filled)
230 for (auto i = _front_chunk->begin; i != _front_chunk->end; ++i) {
231 _front_chunk->items[mask(i)].data.~T();
233 chunk *p = _front_chunk->next;
235 // Delete all the middle chunks (all completely filled)
237 while (p != _back_chunk) {
238 // These are full chunks
239 chunk *nextp = p->next;
240 for (auto i = 0; i != items_per_chunk; ++i) {
241 // Note we delete out of order (we don't start with p->begin).
242 // That should be fine..
243 p->items[i].data.~T();
248 // Finally delete back chunk (partially filled)
249 for (auto i = _back_chunk->begin; i != _back_chunk->end; ++i) {
250 _back_chunk->items[mask(i)].data.~T();
254 _front_chunk = nullptr;
255 _back_chunk = nullptr;
260 template <typename T, size_t items_per_chunk> void
261 chunked_fifo<T, items_per_chunk>::shrink_to_fit() {
262 while (_free_chunks) {
263 auto next = _free_chunks->next;
270 template <typename T, size_t items_per_chunk>
271 chunked_fifo<T, items_per_chunk>::~chunked_fifo() {
276 template <typename T, size_t items_per_chunk>
278 chunked_fifo<T, items_per_chunk>::back_chunk_new() {
279 chunk *old = _back_chunk;
281 _back_chunk = _free_chunks;
282 _free_chunks = _free_chunks->next;
285 _back_chunk = new chunk;
287 _back_chunk->next = nullptr;
288 _back_chunk->begin = 0;
289 _back_chunk->end = 0;
291 old->next = _back_chunk;
293 if (_front_chunk == nullptr) {
294 _front_chunk = _back_chunk;
300 template <typename T, size_t items_per_chunk>
302 chunked_fifo<T, items_per_chunk>::ensure_room_back() {
303 // If we don't have a back chunk or it's full, we need to create a new one
304 if (_back_chunk == nullptr ||
305 (_back_chunk->end - _back_chunk->begin) == items_per_chunk) {
310 template <typename T, size_t items_per_chunk>
312 chunked_fifo<T, items_per_chunk>::undo_room_back() {
313 // If we failed creating a new item after ensure_room_back() created a
314 // new empty chunk, we must remove it, or empty() will be incorrect
315 // (either immediately, if the fifo was empty, or when all the items are
316 // popped, if it already had items).
317 if (_back_chunk->begin == _back_chunk->end) {
321 _back_chunk = nullptr;
322 _front_chunk = nullptr;
324 // Because we don't usually pop from the back, we don't have a "prev"
325 // pointer so we need to find the previous chunk the hard and slow
327 chunk *old = _back_chunk;
328 _back_chunk = _front_chunk;
329 while (_back_chunk->next != old) {
330 _back_chunk = _back_chunk->next;
332 _back_chunk->next = nullptr;
338 template <typename T, size_t items_per_chunk>
339 template <typename... Args>
341 chunked_fifo<T, items_per_chunk>::emplace_back(Args&&... args) {
343 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
345 new(p) T(std::forward<Args>(args)...);
353 template <typename T, size_t items_per_chunk>
355 chunked_fifo<T, items_per_chunk>::push_back(const T& data) {
357 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
367 template <typename T, size_t items_per_chunk>
369 chunked_fifo<T, items_per_chunk>::push_back(T&& data) {
371 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
373 new(p) T(std::move(data));
381 template <typename T, size_t items_per_chunk>
384 chunked_fifo<T, items_per_chunk>::back() {
385 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
388 template <typename T, size_t items_per_chunk>
391 chunked_fifo<T, items_per_chunk>::back() const {
392 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
395 template <typename T, size_t items_per_chunk>
397 chunked_fifo<T, items_per_chunk>::front() const noexcept {
398 return _front_chunk->items[mask(_front_chunk->begin)].data;
401 template <typename T, size_t items_per_chunk>
403 chunked_fifo<T, items_per_chunk>::front_chunk_delete() noexcept {
404 chunk *next = _front_chunk->next;
405 // Certain use cases may need to repeatedly allocate and free a chunk -
406 // an obvious example is an empty queue to which we push, and then pop,
407 // repeatedly. Another example is pushing and popping to a non-empty queue
408 // we push and pop at different chunks so we need to free and allocate a
409 // chunk every items_per_chunk operations.
410 // The solution is to keep a list of freed chunks instead of freeing them
411 // immediately. There is a performance/memory tradeoff of how many freed
412 // chunks to save: If we save them all, the queue can never shrink from
413 // its maximum memory use (this is how circular_buffer behaves).
414 // The ad-hoc choice made here is to limit the number of saved chunks to 1,
415 // but this could easily be made a configuration option.
416 static constexpr int save_free_chunks = 1;
417 if (_nfree_chunks < save_free_chunks) {
418 _front_chunk->next = _free_chunks;
419 _free_chunks = _front_chunk;
424 // If we only had one chunk, _back_chunk is gone too.
425 if (_back_chunk == _front_chunk) {
426 _back_chunk = nullptr;
432 template <typename T, size_t items_per_chunk>
434 chunked_fifo<T, items_per_chunk>::pop_front() noexcept {
436 // If the front chunk has become empty, we need to free remove it and use
438 if (++_front_chunk->begin == _front_chunk->end) {
439 front_chunk_delete();
443 template <typename T, size_t items_per_chunk>
444 void chunked_fifo<T, items_per_chunk>::reserve(size_t n) {
445 // reserve() guarantees that (n - size()) additional push()es will
446 // succeed without reallocation:
447 size_t need = n - size();
448 // If we already have a back chunk, it might have room for some pushes
449 // before filling up, so decrease "need":
451 need -= items_per_chunk - (_back_chunk->end - _back_chunk->begin);
453 size_t needed_chunks = (need + items_per_chunk - 1) / items_per_chunk;
454 // If we already have some freed chunks saved, we need to allocate fewer
455 // additional chunks, or none at all
456 if (needed_chunks <= _nfree_chunks) {
459 needed_chunks -= _nfree_chunks;
460 while (needed_chunks--) {
461 chunk *c = new chunk;
462 c->next = _free_chunks;