## Sidetrack↵
↵
It has been two years since I wrote an educational blog. I've been inactive in the CP community recently as I've shifted my focus to internships. Recently, I observed some interesting behaviour with `std::queue` while profiling an application during my internship, which led me to writing this blog.↵
↵
Most of the images below are taken from the C++ standard https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4950.pdf↵
↵
## Queues and stacks↵
↵
Queues and stacks do not actually provide any new implementations... They are just wrappers around a container (which is `std::deque`) by default.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
This means that if you use the default `Container` template of `std::stack` and `std::queue`, it will be as slow as a `std::deque`. Now, let us see why `std::deque` is slow.↵
↵
## Deque↵
↵
Below is a brief implementation of deque. (You may refer to the section [below](#gcc-analysis) for exact implementations)↵
↵
```c++↵
template<typename T>↵
struct SimpleDeque {↵
static constexpr size_t BLOCK_BYTES = 512;↵
static constexpr size_t BLOCK_SIZE = BLOCK_BYTES / sizeof(T);↵
↵
T** map = nullptr;↵
size_t map_size = 0;↵
size_t n = 0;↵
↵
void grow_map() {↵
size_t new_size = map_size ? map_size * 2 : 2;↵
↵
T** new_map = new T*[new_size]{};↵
↵
for (size_t i = 0; i < map_size; i++)↵
new_map[i] = map[i];↵
↵
delete[] map;↵
map = new_map;↵
map_size = new_size;↵
}↵
↵
SimpleDeque() : map(new T*[2]{}), map_size(2), n(0) {}↵
↵
void push_back(const T& value) {↵
size_t block = n / BLOCK_SIZE;↵
size_t offset = n % BLOCK_SIZE;↵
↵
if (block >= map_size)↵
grow_map();↵
↵
if (offset == 0)↵
map[block] = new T[BLOCK_SIZE];↵
↵
map[block][offset] = value;↵
++n;↵
}↵
↵
T& operator[](size_t i) {↵
return map[i / BLOCK_SIZE]↵
[i % BLOCK_SIZE];↵
}↵
};↵
```↵
↵
Essentially, the deque stores an array of tiny blocks. In GCC, each tiny block is $512$ bytes, but it can be different in other compilers (see https://codeforces.me/blog/entry/135332?#comment-1210774).↵
↵
[cut]↵
↵
So, if you are storing a deque of `int32`, each tiny block will store $\frac{512}{4} = 128$ `int32`. If you push $500$ `int32` into a deque, `map` will be an array consisting of $\left\lceil \frac{500}{128} \right\rceil = 4$ tiny arrays each capable of storing $128$ `int32`.↵
↵
When we `push_back`, we will add the element to the tiny block. However, when we reach the end of a tiny block, we will need to create a new tiny block (which allocates on the heap!!).↵
↵
This means that every time you push $512$ bytes into the deque, it will result in a `malloc` call!↵
↵
This does not sound very efficient. Why is deque implemented this way? Let's look at the standard.↵
↵
↵
↵
The most important part is "An insertion at either end of the deque ... has no effect on the validity of references to elements of the deque". If we implement deque the same way as a vector, where we create a new array that has double the size of the original capacity, this would cause the references to elements of the deque to be invalidated since the new array will be a contiguous chunk of memory at a different location from the original array.↵
↵
By using this array of tiny blocks structure, the tiny blocks are always the same after the first time its created, so references to elements in the tiny blocks will always remain valid.↵
↵
## Consequences↵
↵
1. Deque causes a lot of allocation and deallocation. For performance sensitive code, you should probably implement your own deque that uses vector's doubling behavior.↵
2. Deque allocates a chunk of memory (the tiny block) even if the deque only contains one element. So if you have many deques each with very few elements, you will probably be surprised by the amount of wasted memory (especially clang which will use $4096$ bytes even if there is only one element).↵
3. The tiny blocks are not contiguous in memory. Not sure whether this has any performance impact since each tiny block itself is contiguous and larger than a single cache line.↵
↵
## <a name="gcc-analysis"></a> Detailed GCC Analysis↵
↵
Let us look at GCC's implementation of deque. The implementations jump around the below two files, so you will need to refer to both.↵
↵
- https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a02018.html↵
- https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-api-4.6/a00861_source.html↵
↵
`_Tp** _M_node` is the array of tiny arrays. Let's look at the `+=` operator of the `_Deque_iterator`:↵
↵
```c++↵
_Self& operator+=(difference_type __n)↵
{↵
const difference_type __offset = __n + (_M_cur - _M_first);↵
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))↵
_M_cur += __n;↵
else↵
{↵
const difference_type __node_offset =↵
__offset > 0 ? __offset / difference_type(_S_buffer_size())↵
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;↵
_M_set_node(_M_node + __node_offset);↵
_M_cur = _M_first + (__offset - __node_offset↵
* difference_type(_S_buffer_size()));↵
}↵
return *this;↵
}↵
```↵
↵
See how we need to jump by `__node_offset` which is just the number of $512$ byte blocks that we need to shift by.↵
↵
Then, when we `push_front` or `push_back`, if the front / back tiny array still has space, we just add it there. However, once we reach the end of the tiny array, we would need to make a new tiny array block. We can see this in the `push_back` function:↵
↵
```c++↵
void push_back(const value_type& __x) {↵
if (this->_M_impl._M_finish._M_cur↵
!= this->_M_impl._M_finish._M_last - 1) {↵
this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);↵
++this->_M_impl._M_finish._M_cur;↵
} else↵
_M_push_back_aux(__x);↵
}↵
↵
void deque<_Tp, _Alloc>::_M_push_back_aux(const value_type& __t) {↵
_M_reserve_map_at_back();↵
...↵
}↵
↵
void _M_reserve_map_at_back(size_type __nodes_to_add = 1) {↵
if (__nodes_to_add + 1 > this->_M_impl._M_map_size↵
- (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))↵
_M_reallocate_map(__nodes_to_add, false);↵
}↵
↵
template <typename _Tp, typename _Alloc>↵
void deque<_Tp, _Alloc>::_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) {↵
const size_type __old_num_nodes↵
= this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;↵
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;↵
↵
_Map_pointer __new_nstart;↵
if (this->_M_impl._M_map_size > 2 * __new_num_nodes) {↵
...↵
} else {↵
size_type __new_map_size = this->_M_impl._M_map_size↵
+ std::max(this->_M_impl._M_map_size,↵
__nodes_to_add) + 2;↵
↵
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);↵
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2↵
+ (__add_at_front ? __nodes_to_add : 0);↵
std::copy(this->_M_impl._M_start._M_node,↵
this->_M_impl._M_finish._M_node + 1,↵
__new_nstart);↵
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);↵
↵
this->_M_impl._M_map = __new_map;↵
this->_M_impl._M_map_size = __new_map_size;↵
}↵
↵
this->_M_impl._M_start._M_set_node(__new_nstart);↵
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);↵
}↵
```
↵
It has been two years since I wrote an educational blog. I've been inactive in the CP community recently as I've shifted my focus to internships. Recently, I observed some interesting behaviour with `std::queue` while profiling an application during my internship, which led me to writing this blog.↵
↵
Most of the images below are taken from the C++ standard https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4950.pdf↵
↵
## Queues and stacks↵
↵
Queues and stacks do not actually provide any new implementations... They are just wrappers around a container (which is `std::deque`) by default.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
This means that if you use the default `Container` template of `std::stack` and `std::queue`, it will be as slow as a `std::deque`. Now, let us see why `std::deque` is slow.↵
↵
## Deque↵
↵
Below is a brief implementation of deque. (You may refer to the section [below](#gcc-analysis) for exact implementations)↵
↵
```c++↵
template<typename T>↵
struct SimpleDeque {↵
static constexpr size_t BLOCK_BYTES = 512;↵
static constexpr size_t BLOCK_SIZE = BLOCK_BYTES / sizeof(T);↵
↵
T** map = nullptr;↵
size_t map_size = 0;↵
size_t n = 0;↵
↵
void grow_map() {↵
size_t new_size = map_size ? map_size * 2 : 2;↵
↵
T** new_map = new T*[new_size]{};↵
↵
for (size_t i = 0; i < map_size; i++)↵
new_map[i] = map[i];↵
↵
delete[] map;↵
map = new_map;↵
map_size = new_size;↵
}↵
↵
SimpleDeque() : map(new T*[2]{}), map_size(2), n(0) {}↵
↵
void push_back(const T& value) {↵
size_t block = n / BLOCK_SIZE;↵
size_t offset = n % BLOCK_SIZE;↵
↵
if (block >= map_size)↵
grow_map();↵
↵
if (offset == 0)↵
map[block] = new T[BLOCK_SIZE];↵
↵
map[block][offset] = value;↵
++n;↵
}↵
↵
T& operator[](size_t i) {↵
return map[i / BLOCK_SIZE]↵
[i % BLOCK_SIZE];↵
}↵
};↵
```↵
↵
Essentially, the deque stores an array of tiny blocks. In GCC, each tiny block is $512$ bytes, but it can be different in other compilers (see https://codeforces.me/blog/entry/135332?#comment-1210774).↵
↵
[cut]↵
↵
So, if you are storing a deque of `int32`, each tiny block will store $\frac{512}{4} = 128$ `int32`. If you push $500$ `int32` into a deque, `map` will be an array consisting of $\left\lceil \frac{500}{128} \right\rceil = 4$ tiny arrays each capable of storing $128$ `int32`.↵
↵
When we `push_back`, we will add the element to the tiny block. However, when we reach the end of a tiny block, we will need to create a new tiny block (which allocates on the heap!!).↵
↵
This means that every time you push $512$ bytes into the deque, it will result in a `malloc` call!↵
↵
This does not sound very efficient. Why is deque implemented this way? Let's look at the standard.↵
↵
↵
↵
The most important part is "An insertion at either end of the deque ... has no effect on the validity of references to elements of the deque". If we implement deque the same way as a vector, where we create a new array that has double the size of the original capacity, this would cause the references to elements of the deque to be invalidated since the new array will be a contiguous chunk of memory at a different location from the original array.↵
↵
By using this array of tiny blocks structure, the tiny blocks are always the same after the first time its created, so references to elements in the tiny blocks will always remain valid.↵
↵
## Consequences↵
↵
1. Deque causes a lot of allocation and deallocation. For performance sensitive code, you should probably implement your own deque that uses vector's doubling behavior.↵
2. Deque allocates a chunk of memory (the tiny block) even if the deque only contains one element. So if you have many deques each with very few elements, you will probably be surprised by the amount of wasted memory (especially clang which will use $4096$ bytes even if there is only one element).↵
3. The tiny blocks are not contiguous in memory. Not sure whether this has any performance impact since each tiny block itself is contiguous and larger than a single cache line.↵
↵
## <a name="gcc-analysis"></a> Detailed GCC Analysis↵
↵
Let us look at GCC's implementation of deque. The implementations jump around the below two files, so you will need to refer to both.↵
↵
- https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a02018.html↵
- https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-api-4.6/a00861_source.html↵
↵
`_Tp** _M_node` is the array of tiny arrays. Let's look at the `+=` operator of the `_Deque_iterator`:↵
↵
```c++↵
_Self& operator+=(difference_type __n)↵
{↵
const difference_type __offset = __n + (_M_cur - _M_first);↵
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))↵
_M_cur += __n;↵
else↵
{↵
const difference_type __node_offset =↵
__offset > 0 ? __offset / difference_type(_S_buffer_size())↵
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;↵
_M_set_node(_M_node + __node_offset);↵
_M_cur = _M_first + (__offset - __node_offset↵
* difference_type(_S_buffer_size()));↵
}↵
return *this;↵
}↵
```↵
↵
See how we need to jump by `__node_offset` which is just the number of $512$ byte blocks that we need to shift by.↵
↵
Then, when we `push_front` or `push_back`, if the front / back tiny array still has space, we just add it there. However, once we reach the end of the tiny array, we would need to make a new tiny array block. We can see this in the `push_back` function:↵
↵
```c++↵
void push_back(const value_type& __x) {↵
if (this->_M_impl._M_finish._M_cur↵
!= this->_M_impl._M_finish._M_last - 1) {↵
this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);↵
++this->_M_impl._M_finish._M_cur;↵
} else↵
_M_push_back_aux(__x);↵
}↵
↵
void deque<_Tp, _Alloc>::_M_push_back_aux(const value_type& __t) {↵
_M_reserve_map_at_back();↵
...↵
}↵
↵
void _M_reserve_map_at_back(size_type __nodes_to_add = 1) {↵
if (__nodes_to_add + 1 > this->_M_impl._M_map_size↵
- (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))↵
_M_reallocate_map(__nodes_to_add, false);↵
}↵
↵
template <typename _Tp, typename _Alloc>↵
void deque<_Tp, _Alloc>::_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) {↵
const size_type __old_num_nodes↵
= this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;↵
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;↵
↵
_Map_pointer __new_nstart;↵
if (this->_M_impl._M_map_size > 2 * __new_num_nodes) {↵
...↵
} else {↵
size_type __new_map_size = this->_M_impl._M_map_size↵
+ std::max(this->_M_impl._M_map_size,↵
__nodes_to_add) + 2;↵
↵
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);↵
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2↵
+ (__add_at_front ? __nodes_to_add : 0);↵
std::copy(this->_M_impl._M_start._M_node,↵
this->_M_impl._M_finish._M_node + 1,↵
__new_nstart);↵
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);↵
↵
this->_M_impl._M_map = __new_map;↵
this->_M_impl._M_map_size = __new_map_size;↵
}↵
↵
this->_M_impl._M_start._M_set_node(__new_nstart);↵
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);↵
}↵
```
