Есть map<__int64, __int64>. Вставляю в него 10 млн элементов.

Измеряю сколько это хозяйство занимает в памяти места получается ~650 Мб.
При том, что сами данные грубо занимают ~160 Мб.

Как снизить издержки по памяти? Функциональность мap-а терять не хочется.

MEMORYSTATUSEX mem1 ={0}, mem2 ={0}, mem3 ={0};

mem1.dwLength = sizeof(mem1);
mem2.dwLength = sizeof(mem2);

GlobalMemoryStatusEx(&mem1);

map<__int64, __int64> mm1;

for (__int64 i=0; i<10000000; i++){
    mm1[i] = i;
}

GlobalMemoryStatusEx(&mem2);

смотрю разницу mem1.ullAvailVirtual — mem2.ullAvailVirtual
Платформа Win32, сборка Release.

Здравствуйте, kgrach, Вы писали:

K>Есть map<__int64, __int64>. Вставляю в него 10 млн элементов.

K>Измеряю сколько это хозяйство занимает в памяти места получается ~650 Мб.
K>При том, что сами данные грубо занимают ~160 Мб.

K>Как снизить издержки по памяти? Функциональность мap-а терять не хочется.

Без потерь функциональности не получится.
Возможно что-то можно потерять?
Что именно из функциональности map-а нужно:
время поиска,
время вставки,
сортированность (обход элементов в порядке возрастания),
валидность итераторов после вставок/удаления элементов.

Здравствуйте, kgrach, Вы писали:

K>Как снизить издержки по памяти? Функциональность мap-а терять не хочется.
Использовать свой аллокатор, который будет выделять память большими кусками.

ps/
глюпост написал, да.
помимо данных на ноду надо 3 указателя + цвет. так-что порядка 600 и будет => никак,

Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, kgrach, Вы писали:

C>Без потерь функциональности не получится.
C>Возможно что-то можно потерять?
C>Что именно из функциональности map-а нужно:
C>время поиска,
C>время вставки,
C>сортированность (обход элементов в порядке возрастания),
C>валидность итераторов после вставок/удаления элементов.

готов пожертвовать, только валидностью итераторов

Здравствуйте, kgrach, Вы писали:

K>Как снизить издержки по памяти? Функциональность мap-а терять не хочется.

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

Здравствуйте, kgrach, Вы писали:

K>Есть map<__int64, __int64>. Вставляю в него 10 млн элементов.

K>Измеряю сколько это хозяйство занимает в памяти места получается ~650 Мб.
K>При том, что сами данные грубо занимают ~160 Мб.

K>Как снизить издержки по памяти? Функциональность мap-а терять не хочется.

А если так:

#include <boost/pool/pool_alloc.hpp>

MEMORYSTATUSEX mem1 ={0}, mem2 ={0}, mem3 ={0};

mem1.dwLength = sizeof(mem1);
mem2.dwLength = sizeof(mem2);

GlobalMemoryStatusEx(&mem1);

typedef std::less<__int64> Int64Compare;
typedef std::pair<__int64, __int64> Int64Pair;
typedef boost::pool_allocator<Int64Pair> Int64Pool;
typedef std::map<__int64, __int64, Int64Compare, Int64Pool> Int64Map;
Int64Map mm1;

for (__int64 i=0; i<10000000; i++){
    mm1[i] = i;
}

GlobalMemoryStatusEx(&mem2);

Здравствуйте, TimurSPB, Вы писали:

TSP>Здравствуйте, kgrach, Вы писали:

TSP>А если так:

TSP>

TSP>#include <boost/pool/pool_alloc.hpp>

TSP>MEMORYSTATUSEX mem1 ={0}, mem2 ={0}, mem3 ={0};

TSP>mem1.dwLength = sizeof(mem1);
TSP>mem2.dwLength = sizeof(mem2);

TSP>GlobalMemoryStatusEx(&mem1);

TSP>typedef std::less<__int64> Int64Compare;
TSP>typedef std::pair<__int64, __int64> Int64Pair;
TSP>typedef boost::pool_allocator<Int64Pair> Int64Pool;
TSP>typedef std::map<__int64, __int64, Int64Compare, Int64Pool> Int64Map;
TSP>Int64Map mm1;

TSP>for (__int64 i=0; i<10000000; i++){
TSP>    mm1[i] = i;
TSP>}

TSP>GlobalMemoryStatusEx(&mem2);
TSP>

В проекте буста нет, на досуге попробую

Здравствуйте, kgrach, Вы писали:


K>Как снизить издержки по памяти? Функциональность мap-а терять не хочется.

Какую именно функциональность map ты используешь? Редко кому нужны все свойства, гарантируемые стандартом.
Например, если разрешить инвалидацию итераторов после модификации данных (подобно поведению std::vector), то можно использовать B-дерево, что одновременно как снизит потребление памяти (скажем, до +5Мб на все служебные потери), так и ускорит саму вставку десяти миллионов элементов в дерево (равно как и прочие операции). Попробуй cpp-btree.

K>В проекте буста нет, на досуге попробую
Если уж до boost дело дойдет, то там есть свой набор контейнеров. http://www.boost.org/doc/libs/1_59_0/doc/html/container.html

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, kgrach, Вы писали:


K>>Как снизить издержки по памяти? Функциональность мap-а терять не хочется.

W>Какую именно функциональность map ты используешь? Редко кому нужны все свойства, гарантируемые стандартом.
W>Например, если разрешить инвалидацию итераторов после модификации данных (подобно поведению std::vector), то можно использовать B-дерево, что одновременно как снизит потребление памяти (скажем, до +5Мб на все служебные потери), так и ускорит саму вставку десяти миллионов элементов в дерево (равно как и прочие операции). Попробуй cpp-btree.

Поиск и вставку в основном. Выгляди заманчиво, попробую

Здравствуйте, kgrach, Вы писали:

K>Здравствуйте, Chorkov, Вы писали:

C>>Здравствуйте, kgrach, Вы писали:

C>>Без потерь функциональности не получится.
C>>Возможно что-то можно потерять?
C>>Что именно из функциональности map-а нужно:
C>>время поиска,
C>>время вставки,
C>>сортированность (обход элементов в порядке возрастания),
C>>валидность итераторов после вставок/удаления элементов.

K>готов пожертвовать, только валидностью итераторов

btree уже посоветовали.

Еще можно посмотреть на flat_map.
Он даст падение производительности вставок, но возможно, не такое критическое как кажется.
(Сильно зависит от сценария вставки данных, особенно если вставляешь "пакетами", а не по одному элементу.)

Если ничего готовое не подойдет, то я бы попробовал сделал такой велосипед:

std::set<  std::vector< std::pair< int64, int64 > > >

Где вектор — отсортирован по ключам.
Сравнение в set-е по значению ключа первого элемента вектора.
При вставке, добавляем пару в соответствующий вектор. Если размер вектора привышает заданный — делим элемент на два.

Здравствуйте, kgrach, Вы писали:

Поддерживую идею эксперимента с контейнером на b-tree. Кроме экономии памяти эта структура может обеспечить бОльшую локальность данных в памяти, что обычно положительно влияет на быстродействие. Но здесь, как обычно, нужно смотреть на результаты профайлера.

Я использовал STX B+ Tree C++ Template Classes — интейрфейс почти полностью совместим со стандартными ассоциативными контейнерами. Единственная тонкость — при доступе к элементам map через итератор, для модификации значения нужно использовать функцию iterator::data() из-за этого:

Problem with Separated Key/Data Arrays
The most noteworthy difference to the default red-black tree implementation of std::map is that the B+ tree does not hold key/data pairs together in memory. Instead each B+ tree node has two separate arrays containing keys and data values. This design was chosen to utilize cache-line effects while scanning the key array.

However it also directly generates many problems in implementing the iterators' operators. These return a (writable) reference or pointer to a value_type, which is a std::pair composition. These data/key pairs however are not stored together and thus a temporary copy must be constructed. This copy should not be written to, because it is not stored back into the B+ tree. This effectively prohibits use of many STL algorithms which writing to the B+ tree's iterators. I would be grateful for hints on how to resolve this problem without folding the key and data arrays.

Здравствуйте, kgrach, Вы писали:
K>готов пожертвовать, только валидностью итераторов

Loki::AssocVector смотрели?

Здравствуйте, kgrach, Вы писали:

K>Измеряю сколько это хозяйство занимает в памяти места получается ~650 Мб.
K>При том, что сами данные грубо занимают ~160 Мб.
Для информации: http://info.prelert.com/blog/stl-container-memory-usage, там и табличка есть. К слову, в студии 2013 и позже неплохо оптимизировали контейнеры в этом плане.

Здравствуйте, flаt, Вы писали:

F>Для информации: http://info.prelert.com/blog/stl-container-memory-usage, там и табличка есть. К слову, в студии 2013 и позже неплохо оптимизировали контейнеры в этом плане.

ага. вот кто интересно мог до такого додуматься:

deque uses 40 bytes for the deque object itself, then allocates at least 64 bytes more on the heap for a "node map", and then stores the contained objects in pages that are 16 bytes in size

т.е. таблица сегментов будет всего вдвое меньше самих сегментов и к тому же либо одним непрерывным объектом, либо многоуровневая. в чём смысл такого deque???

Здравствуйте, flаt, Вы писали:

F>Здравствуйте, kgrach, Вы писали:

K>>Измеряю сколько это хозяйство занимает в памяти места получается ~650 Мб.
K>>При том, что сами данные грубо занимают ~160 Мб.
F>Для информации: http://info.prelert.com/blog/stl-container-memory-usage, там и табличка есть. К слову, в студии 2013 и позже неплохо оптимизировали контейнеры в этом плане.

Ерунда или там речь о чем-то другом. Я делал этот же тест на 2013 студии все тоже самое.

Flat, c чем ты не согласен?

Здравствуйте, PPA, Вы писали:

PPA>Здравствуйте, kgrach, Вы писали:
K>>готов пожертвовать, только валидностью итераторов

PPA>Loki::AssocVector смотрели?
нет, но посмотрю, спасибо за наводку

Здравствуйте, kgrach, Вы писали:

K>Ерунда или там речь о чем-то другом. Я делал этот же тест на 2013 студии все тоже самое.
GlobalMemoryStatusEx говорит о системной памяти. Рантайм же использует свой хип, который может быть фрагментирован, отсюда и завышенное потребление. Чтобы точно сказать, сколько памяти расходуют контейнеры, нужно подставить свой аллокатор им и в нём уже считать

Здравствуйте, flаt, Вы писали:

F>Здравствуйте, kgrach, Вы писали:

K>>Ерунда или там речь о чем-то другом. Я делал этот же тест на 2013 студии все тоже самое.
F>GlobalMemoryStatusEx говорит о системной памяти. Рантайм же использует свой хип, который может быть фрагментирован, отсюда и завышенное потребление. Чтобы точно сказать, сколько памяти расходуют контейнеры, нужно подставить свой аллокатор им и в нём уже считать

GlobalMemoryStatusEx так же говорит и о размере доступного виртуального адресного пространства процессу. Фрагментация то тут причем. Фрагментация это когда у меня есть 200 Мб, но я не могу выделить например 1 Мб.
Сколько на выделяли на столько виртуальной памяти стало меньше.

PM>Поддерживую идею эксперимента с контейнером на b-tree. Кроме экономии памяти эта структура может обеспечить бОльшую локальность данных в памяти, что обычно положительно влияет на быстродействие. Но здесь, как обычно, нужно смотреть на результаты профайлера.

PM>Я использовал STX B+ Tree C++ Template Classes

я бы не советовал именно этот проект, нашел там давно багу, ее так и не пофиксили, лучше cpp-btree