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

Question

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

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

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

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

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

Answer 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 байт вы получите ожидаемое поведение (процентное уменьшение служебных данных при увеличении размера элемента).

Answer 2

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

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

РЕДАКТИРОВАТЬ: FYI - Когда я запускаю это вне отладчика на VS2010, я получаю 181 МБ с char с.

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

РЕДАКТИРОВАТЬ: Поддержка другого ответа от @Диалектика, это дает мне ту же площадь, что и double:

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

    __int64 a;
    __int64 b;
};

РЕДАКТИРОВАТЬ: С _DEQUESIZ, измененным, как показано (128 символов на блок), 100 миллионов символов теперь занимают 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>.Его поведение критически зависит от размера ваших элементов, а также от ожидаемого шаблона использования.

РЕДАКТИРОВАТЬ: В зависимости от ваших знаний о размерах очереди, вы можете включить boost :: циркуляр_buffer. в качестве замены контейнера std :: queue.Могу поспорить, что это будет работать так, как вы хотите (и ожидаете).

Answer 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).Поскольку перераспределение может копировать существующие элементы, версия, которая только увеличивала массив по мере необходимости (1 элемент за один раз), была бы O (n ^ 2), поскольку вы изначально помещаете все свои значения в очередь.Я оставлю это в качестве упражнения для читателя, как удвоение версии дает постоянное среднее время.

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