luislomбоевыеСамтролль? Ядро вам выдаёт только целые страницы.

Да, физическую память помечает как используемую именно страницами,
перемещая указатель на неё в дескрипторы в pgd/pmd/pte, которые
индексируются битами виртуального адреса. Если имеете что против, обоснуйте.
Я ниасилил, при чём тут эта тема.

MasterZiv(3.5) Сейчас не могу сказать... Может не от гугла, а может это - https://code.google.com/p/cpp-btree/, не знаю точно сейчас

А ты там при как?
Нихрена не знаешь, но хочешь все исправить и делаешь глубоко идущие выводы..

(4) Какая именно накладуха?

само дерево.


Фрагментация от удалений-добавлений?
(5) Весь код знать нереально, нужна куча времени на чтение всех исходников проекта. Чтобы прочитать все исходники этого btree и всё уложить у себя в голове только неделя нужна или около того...

Неделя — это немного.[/quot]
Я сказал - "сейчас", т.е. на момент написания поста.
Ну кому много, кому не много...

MasterZivOn 21.04.2014 14:27, боевые wrote:

> Я ниасилил, при чём тут эта тема.

Намекают на то, что с приложением вашим всё в порядке,
память не течёт, вы просто неправильно используете средства диагностики.
А приложение (видимо) просто в таком варианте не влезает в память.

Я не понял аргументов про неправильность использования средств диагностики.

MasterZivOn 21.04.2014 14:32, mayton wrote:

> Еще мысли вслух. Я не знаю как он ищет самые старые записи. Но b-tree
> явно не оптимизирована для выбрасывания
> старых записей. Возможно в этой архитектуре еще много косяков куда можно
> приложить руку.

Что в дереве хранится ?
Какие операции нужны для элементов, хранящихся в дереве ?


Давайте это не будем обсуждать, тут проблем нет.

luislomбоевыеЯ ниасилил, при чём тут эта тема.

авторПриложение на старте засасывает в себя данные из базы, занимая 80 ГБ ОЗУ и работает 3 дня, после которых сжирает все 128 ГБ ОЗУ. По логам (которые, может быть и кривые) и по заявлениям разраба, приложение хранит всегда строго ограниченное число "записей", выкидывая самые старые при необходимости.


Вот эти 128 ГБ в статистике ОС, и не больше 80 ГБ по статистике приложения-это то,
что приложение считает по *malloc/free, а ОС по выделенным для размещения кусков
виртуальной памяти процессу физическим страницам. Если приложение имеет 3 региона, полученные *malloc, по 100B,
то она покажет занятость памяти в 300B. Но, если эти три региона будут распологаться на трёх разных физических
страницах, то ОС покажет занятость в 3*PAGE_SIZE B, 12KB на linux. Одна из причин такой ситуации, в постоянных *malloc
и free кусков памяти разного размера в хаотичном хронологическом порядке. Излишняя увлечённость std::string, std::hash_map и пр.
Как следствие-пишите свою B-tree. Если изначально планируется, что оно будет занимать определённый объём памяти,
то можно запросить этот объём один раз при создании, разбить на блоки одинакового размера и вести некий стек
свободных блоков для выделения/освобождения. Узлы B-tree будут представлять собой списки этих блоков.
Перемещениё ключей будет реализовано как обмен указателями между блоками. Выделение/освобождение
блоков-пихаем указатели на них в стек свободных блоков. Таким образом, дерево будет всегда занимать определённую область
виртуальной памяти и фиксированный набор физ. страниц для размещения.
Это всё понятно. Я только не понимаю, при чём тут всё это?

luislomбоевыеЯ ниасилил, при чём тут эта тема.

авторПриложение на старте засасывает в себя данные из базы, занимая 80 ГБ ОЗУ и работает 3 дня, после которых сжирает все 128 ГБ ОЗУ. По логам (которые, может быть и кривые) и по заявлениям разраба, приложение хранит всегда строго ограниченное число "записей", выкидывая самые старые при необходимости.


Вот эти 128 ГБ в статистике ОС, и не больше 80 ГБ по статистике приложения-это то,
что приложение считает по *malloc/free, а ОС по выделенным для размещения кусков
виртуальной памяти процессу физическим страницам. Если приложение имеет 3 региона, полученные *malloc, по 100B,
то она покажет занятость памяти в 300B. Но, если эти три региона будут распологаться на трёх разных физических
страницах, то ОС покажет занятость в 3*PAGE_SIZE B, 12KB на linux. Одна из причин такой ситуации, в постоянных *malloc
и free кусков памяти разного размера в хаотичном хронологическом порядке. Излишняя увлечённость std::string, std::hash_map и пр.
Как следствие-пишите свою B-tree. Если изначально планируется, что оно будет занимать определённый объём памяти,
то можно запросить этот объём один раз при создании, разбить на блоки одинакового размера и вести некий стек
свободных блоков для выделения/освобождения. Узлы B-tree будут представлять собой списки этих блоков.
Перемещениё ключей будет реализовано как обмен указателями между блоками. Выделение/освобождение
блоков-пихаем указатели на них в стек свободных блоков. Таким образом, дерево будет всегда занимать определённую область
виртуальной памяти и фиксированный набор физ. страниц для размещения.
Когда я вызываю malloc, управление передаётся не в ядро, а на библиотеку. А что там происходит вы как будто забываете. Вы знаете что происходит в этой библиотеке в случае применения там аллокатора jemalloc при выделении множества мелких объектов разной величины в хаотическом хронологическом порядке?

Мы до обсуждения страниц и ОС ещё не дошли, у нас ещё до этого куча всего интересного при выделении памяти происходит.

Dima TПроблемы-то вообще в чем?

Утечек памяти нет, просто алгоритм требует до 100% избытка памяти для работы. http://shpargalum.ru/shpora-gos-povtas/strukturyi-i-algoritmyi-obrabotki-dannyix/b-derevya.-osobennosti-predstavleniya-b-derevev.html Б-дерево порядка m со страничной организацией - это структура данных, удовлетворяющая следующим условиям:

весь набор из n элементов разбивается на отдельные страницы, причем каждая страница может содержать от m до 2m вершин , за исключением корневой страницы, для которой число вершин может изменяться от 1 до 2m
...
т.е. при изменении дерева оно может занять памяти до 2х раз больше при том же количестве элементов (в наихудшем варианте когда каждая страница содержит m вершин) т.к. алгоритм не обещает немедленного освобождения памяти удаленных из дерева вершин. Память высвобождается при удалении страницы, а страница удаляется если на ней осталось <m вершин.

Вывод: на низком уровне нечего оптимизировать. Только перестроение дерева освободит память. Надо ли это в твоем случае - решай сам, это по количеству свопящихся страниц видно.
Это ясно. Просто искусственный эксперимент пока не дал 50% прироста потребления памяти.
Эксперимент:
1. Было построено дерево на 200 млн ключей с нуля. Заняло 11 гигов ОЗУ.
2. Поток добавления продолжал работать (с блокировками всё в порядке), но при превышении лимита кол-ва ключей в дереве, вызывалась процедура удаления случайных 33....1000 ключей последовательно (.erase(iterator_from, iterator_until)).
3. Получилось таким образом отожрать лишних 100 мб памяти, далее всё стабилизировалось.
4. Возможно, надо удалять хитрее и агрессивнее, не диапазонами, а единичными ключами и т.п., незнаю, но в сабжевом приложении ключи удаляются пачками последовательных ключей сотнями штук. Мне кажется, чем больше последовательных ключей в пачке при удалении, тем дереву лучше, меньше разрозненных дырок, поэтому я уменьшал число ключей в пачке, чтобы сильнее спровоцировать "эффект разряжения".

Короче, 100 мегабайт для 11 гигов - это не 50% )

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