Что происходит с тем, что происходит с памятью с памятью std:: deque?

Я работаю над внешним алгоритмом сортировки, который использует std::queue и должен тщательно сдерживать использование памяти. Я заметил, что во время фазы слияния (которая использует несколько std::queue фиксированной длины), использование моей памяти увеличивается примерно до 2,5X, что я ожидал. Поскольку std::queue по умолчанию использует std::deque в качестве своего основного контейнера, я провел несколько тестов на std::deque, чтобы определить его служебные данные памяти. Вот результаты, запущенные на VС++ 9, в режиме деблокирования с 64-битным процессом:

При добавлении 100 000 000 char в std::deque, использование памяти увеличивается до 252,216K. Обратите внимание, что 100M char (1 байт) должно занимать 97,656K, поэтому это накладные расходы 154,560K.

Я повторил тест с double (8 байт) и увидел, что память выросла до 1,976,676K, а 100M double должна занимать 781 250K для накладных расходов в 1,195,426K!!

Теперь я понимаю, что std::deque обычно реализуется как связанный список "кусков". Если это так, то почему накладные расходы пропорциональны размеру элемента (из-за того, что размер указателя должен быть зафиксирован на 8 байтов)? И почему это так сильно удалено?

Может ли кто-нибудь пролить свет на то, почему std::deque использует так сильно замедленную память? Я думаю, что я должен переключить базовые контейнеры std::queue на std::vector, так как нет накладных расходов (учитывая, что соответствующий размер reserve ed). Я думаю, что преимущества std::deque в значительной степени отрицаются из-за того, что у него такие огромные накладные расходы (что приводит к промахам в кэше, ошибкам страниц и т.д.), И что стоимость копирования элементов std::vector может быть меньше, учитывая, что общее использование памяти значительно ниже. Это просто плохая реализация std::deque от Microsoft?

Ответ 1

Посмотрите на код для _DEQUESIZ (количество элементов на блок):

#define _DEQUESIZ   (sizeof (_Ty) <= 1 ? 16 \
    : sizeof (_Ty) <= 2 ? 8 \
    : sizeof (_Ty) <= 4 ? 4 \
    : sizeof (_Ty) <= 8 ? 2 : 1)    /* elements per block (a power of 2) */

Он становится меньше, если элемент больше. Только для элементов размером более 8 байт вы получите ожидаемое поведение (процентное снижение накладных расходов с увеличением размера элемента).

Ответ 2

Возможно ли, что вы используете двоичные файлы Debug? 252MB для 100M символов кажется очень много...

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

EDIT: FYI. Когда я запускаю это вне отладчика на VS2010, я получаю 181 МБ с char s.

deque<char> mydequeue;
for (size_t i = 0; i < 100 * 1024 * 1024; ++i)
{
  mydequeue.push_back(char(i));
}

EDIT: поддерживая другой ответ от @Dialecticus, это дает мне такой же след, как double:

struct twoInt64s
{
public:
    twoInt64s(__int64 _a, __int64 _b) : a(_a), b(_b) {}

    __int64 a;
    __int64 b;
};

EDIT: при изменении _DEQUESIZ, как показано (128 символов на блок), 100M символов теперь принимает 113M памяти.

Мой вывод состоит в том, что оставшиеся накладные расходы, которые вы видели, связаны с структурами управления для блоков deque, которые содержат 16 символов данных, а также управляющую информацию для deque плюс дополнительную информацию управления для кучного менеджера.

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 128 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

Мораль - если вы действительно хотите оптимизировать это для своей специальной цели, будьте готовы играть с <deque>. Его поведение в решающей степени зависит от размера ваших элементов, а также от ожидаемого шаблона использования.

EDIT: в зависимости от ваших знаний о размерах очереди вы можете отказаться от boost:: circle_buffer в качестве замены для std:: контейнер очереди. Бьюсь об заклад, это будет работать больше, как вы хотите (и ожидалось).

Ответ 3

Не глядя на фактическую реализацию std:: queue, которую вы используете, я предполагаю, что распределение памяти выглядит примерно так:

if (new element won't fit) {
    double the size of the backing storage
    realloc the buffer (which will probably copy all elements)
}

Причина удвоения, а не более консервативная, заключается в том, что вы хотите, чтобы операция queue.push_pack имела среднее время O (1). Поскольку перераспределение может скопировать существующие элементы, версия, которая только увеличивала массив по мере необходимости (по одному элементу за раз), была бы O (n ^ 2), поскольку вы изначально вставляете все свои значения в очередь. Я оставлю это как упражнение для читателя, как версия удвоения дает постоянное среднее время.

Поскольку вы указываете размер всего процесса, ваша оценка около 2х накладных расходов, когда вы нажимаете чуть больше, чем количество элементов 2 (2 ^ 26 и 100 МЛ), представляется разумным. Попробуйте остановиться на 2 ^ (n-1), измерив, затем надавив несколько элементов и снова измерив.