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 for exact implementations)

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). 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.

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:

_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:

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);
}