Использование памяти std :: deque - Visual C ++ и сравнение с другими - PullRequest
Новая
       4

Использование памяти std :: deque - Visual C ++ и сравнение с другими

17 голосов
/ 04 ноября 2010

Следуйте до Что за хек происходит с накладными расходами памяти в std :: deque?

Visual C ++ управляет deque блоками в соответствии с типом элемента контейнера, используя это: 

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

Это приводит к очень большой занимаемой памяти для мелких элементов. Изменив значение 16 в первой строке на 128, я смог резко уменьшить объем, необходимый для большого deque<char>. Частные байты Process Explorer уменьшены с 181 МБ до 113 МБ после вызовов 100 м push_back(const char& mychar).

  • Может кто-нибудь обосновать значения в что #define?
  • Как делают другие ручка компилятора deque блок проклейки?
  • Каким будет их след (32-битная операция) для простого тест 100м push_back звонки на deque<char>?
  • Позволяет ли STL переопределение этого размера блока в время компиляции, без изменения <deque> код?

Ответы [ 3 ]

5 голосов
/ 04 ноября 2010

gcc имеет 

return __size < 512 ? size_t(512 / __size) : size_t(1);

с комментарием 

/*  The '512' is
 *  tunable (and no other code needs to change), but no investigation has
 *  been done since inheriting the SGI code.
 */
3 голосов
/ 04 ноября 2010

Реализация Dinkumware (MS) хочет увеличивать deque на 16 байтов за раз. Может ли быть так, что это просто очень старая реализация (как первая в истории?), Которая была настроена для платформ с очень небольшим объемом памяти (по современным стандартам) для предотвращения перераспределения и исчерпания памяти (как это сделает std::vector)? 1002 *

Мне пришлось реализовать собственную очередь в приложении, над которым я работаю, поскольку объем памяти в 2,5 раза std::queue (который использует std::deque) был неприемлемым.

Кажется, что на межплетениях очень мало доказательств того, что люди столкнулись с этой неэффективностью, что удивляет меня. Я бы подумал, что такая фундаментальная структура данных, как очередь (стандартная библиотека, не менее), будет вездесущей в дикой природе и будет использоваться в приложениях, критичных к производительности / времени / пространству. Но мы здесь.

Чтобы ответить на последний вопрос, стандарт C ++ не определяет интерфейс для изменения размера блока. Я почти уверен, что он не требует какой-либо реализации, только требования к сложности для вставки / удаления на обоих концах.

2 голосов
/ 24 ноября 2011

STLPort

... кажется до использовать : 

::: <stl/_alloc.h>
...
enum { _MAX_BYTES = 32 * sizeof(void*) };
...
::: <deque>
...
static size_t _S_buffer_size()
{
  const size_t blocksize = _MAX_BYTES;
  return (sizeof(_Tp) < blocksize ? (blocksize / sizeof(_Tp)) : 1);
}

Таким образом, это будет означать, что размер блока 32 x 4 = 128 байт в 32-разрядном, а размер блока 32 x 8 = 256 байт в 64-разрядном

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

Что касается вопроса

Допускает ли STL переопределение этого размера блока во время компиляции без изменения кода?

Здесь тоже невозможно.

Apache

(похоже, версия Rogue Wave STL), по-видимому, использует: 

static size_type _C_bufsize () {
    // deque only uses __rw_new_capacity to retrieve the minimum
    // allocation amount; this may be specialized to provide a
    // customized minimum amount
    typedef deque<_TypeT, _Allocator> _RWDeque;
    return _RWSTD_NEW_CAPACITY (_RWDeque, (const _RWDeque*)0, 0);
}

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

// returns a suggested new capacity for a container needing more space
template <class _Container>
inline _RWSTD_CONTAINER_SIZE_TYPE
__rw_new_capacity (_RWSTD_CONTAINER_SIZE_TYPE __size, const _Container*)
{
    typedef _RWSTD_CONTAINER_SIZE_TYPE _RWSizeT;

    const _RWSizeT __ratio = _RWSizeT (  (_RWSTD_NEW_CAPACITY_RATIO << 10)
                                       / _RWSTD_RATIO_DIVIDER);

    const _RWSizeT __cap =   (__size >> 10) * __ratio
                           + (((__size & 0x3ff) * __ratio) >> 10);

    return (__size += _RWSTD_MINIMUM_NEW_CAPACITY) > __cap ? __size : __cap;
}

Так что я бы сказал, ах, сложно.

(Если кому-то захочется выяснить это дальше, смело редактируйте мой ответ напрямую или просто оставьте комментарий.)

...