Временная сложность выделения неинициализированной памяти в стеке в функции constexpr?

Question

Обычно, если программа на C++ выделяет большой массив в стеке, большая часть которого в конечном итоге не инициализируется, я бы сказал, что получение этого массива по сути бесплатное (вы просто перемещаете указатель стека или еще много чего) и платите только за инициализация, которую вы на самом деле делаете.

Например, предположим, что я хэширую n элементов в n блоков, а n здесь является константой времени компиляции. Потенциально каждое ведро может получить все n предметов. Таким образом, мы выделяем память для n блоков размером n в стеке. Поскольку в контейнеры на самом деле помещается только n элементов, я бы сказал, что время выполнения похоже на O(n) - конечно, мы выделили O(n^2) памяти в стеке, но только n из этих ячеек фактически были инициализированы.

Однако, когда код выполняется во время компиляции как побочный продукт constexpr, он на самом деле не работает со стековыми фреймами и таким способом, которым он фактически будет работать на металле. Это как-то интерпретируется компилятором.

Когда я создаю неинициализированный массив в стеке, интерпретатор садится и выделяет столько памяти точно и "фиксирует" некоторые конкретные неопределенные значения для неинициализированных ячеек? Если это так, это будет означать, что производительность во время компиляции, вероятно, больше похожа на O(n^2), чем на O(n). Или это "эффективно" обрабатывает неинициализированные распределения как-то?

---

Конечно, практический ответ, он может варьироваться, и вы должны измерить, но я спрашиваю конкретно, есть ли какое-либо руководство или объяснение высокого уровня.

---

Код, на который я смотрю, находится в библиотеке здесь: https://github.com/serge-sans-paille/frozen

Более конкретно в этом заголовке: https://github.com/serge-sans-paille/frozen/blob/master/include/frozen/bits/pmh.h

Вот рассматриваемая функция, она пытается сделать идеальное хеширование во время компиляции, используя C++14 constexpr. Линия, о которой я особенно беспокоюсь:

// Step 1: Place all of the keys into buckets
cvector<bucket<M>, M> buckets;

Здесь Cvector является std::array, а также bucket также cvector:

template <size_t N>
using bucket = cvector<std::size_t, N>;

(В basic_types.h:)

template <class T, std::size_t N>
class cvector {
  T data [N] = {}; // zero-initialization for scalar type T, default-initialized otherwise
  std::size_t dsize = 0;

public:
  ...
};

Вот соответствующая функция (в pmh.h):

template <std::size_t M, class Item, std::size_t N, class Hash, class Key>
pmh_tables<M, Hash> constexpr make_pmh_tables(const std::array<Item, N> &
                                                               items,
                                                           Hash const &hash,
                                                           Key const &key) {
  // Step 1: Place all of the keys into buckets
  cvector<bucket<M>, M> buckets;
  cvector<uint64_t, M> values;
  cvector<int64_t, M> G;

  auto *it = &std::get<0>(items);

  for (std::size_t i = 0; i < N; ++i)
    buckets[hash(key(it[i])) % M].push_back(1 + i);

  // Step 2: Sort the buckets and process the ones with the most items first.
  bits::quicksort(buckets.begin(), buckets.begin() + M - 1, bucket_size_compare{});

  std::size_t b = 0;
  for (; b < M; ++b) {
    auto &bucket = buckets[b];
    auto const bsize = bucket.size();
    if (bsize <= 1)
      break;

    // Repeatedly try different values of d until we find a hash function
    // that places all items in the bucket into free slots
    std::size_t d = 1;
    cvector<std::size_t, M> slots;

    while (slots.size() < bsize) {
      auto slot = hash(key(it[bucket[slots.size()] - 1]), d) % M;

      if (values[slot] != 0 || !all_different_from(slots, slot)) {
        slots.clear();
        d++;
        continue;
      }

      slots.push_back(slot);
    }

    G[hash(key(it[bucket[0] - 1])) % M] = d;
    for (std::size_t i = 0; i < bsize; ++i)
      values[slots[i]] = bucket[i];
  }

  // Only buckets with 1 item remain. Process them more quickly by directly
  // placing them into a free slot. Use a negative value of d to indicate
  // this.
  cvector<int64_t, M> freelist;

  for (std::size_t i = 0; i < M; ++i)
    if (values[i] == 0)
      freelist.push_back(i);

  for (std::size_t i = b; i < M; ++i) {
    auto &bucket = buckets[i];
    if (bucket.size() == 0)
      break;
    auto slot = freelist.back();
    freelist.pop_back();
    // We subtract one to ensure it's negative even if the zeroeth slot was
    // used.
    G[hash(key(it[bucket[0] - 1])) % M] = -slot - 1;
    values[slot] = bucket[0];
  }
  for (std::size_t i = 0; i < M; ++i)
    if (values[i])
      values[i]--;

  return {G.to_array(), values.to_array(), hash};
}