LINUX.ORG.RU

[c]Вопрос про большую память

 


0

0

Здравствуй, ЛОР

Есть дерево struct tree {void data; tree *left; tree *right}; Пусть тысячи таких структур в памяти: всяко-разно друг с другом связанны, постоянно создаются новые, удаляются старые.

Если на каждую такую структуру делать malloc, а в конце free, то, получаются неприятные тормоза (особенно при запуске\завершении), жуткая фрагментация памяти

Как рационально выделять память под тысячи маленьких структур, чтобы ничего не фрагментировалось и не тормозило (догадываюсь, что выделять надо блоками, но может есть готовая теория\готовое решение)?7

★★★★★

> постоянно создаются новые, удаляются старые

Сделай пул свободных элементов в виде массива и не аллочь ничего пока свободные есть. При освобождении элемента - вместо free просто помещай указатель на тот элемент в конец массива свободных для повторного использования.

anonymous
()

люди, которые написали сборщики мусора, всяко поумнее тебя - пользуйся результатами их труда

anonymous
()
Ответ на: комментарий от anonymous

> люди, которые написали сборщики мусора, всяко поумнее тебя

И поумнее тебя явно. Если ручной free работает медленно, автоматическая сборка мусора ещё больше замедлит процесс.

anonymous
()

хоть я и не программер..

можно взять что-нибудь навроде freelist, в сети можно найти описание

суть состоит в выделении памяти большими блоками, построении связных списков свободных элементов в блоках и связных списков самих больших блоков

twosev ★★
()
Ответ на: комментарий от anonymous

ты наверное до сих пор веришь, что ручное кодописательство лучше только потому, что оно ручное?

anonymous
()
Ответ на: комментарий от anonymous

> ты наверное до сих пор веришь, что ручное кодописательство лучше только потому, что оно ручное?

Хватит троллить. Автоматическая сборка мусора ищет неиспользуемые блоки и вызывает тот же free. Каким макаром поиск + free может быть быстрее free?

anonymous
()
Ответ на: комментарий от anonymous

Тем, что free будет отложенным. В результате будет использовано больше памяти, но возможно пользователь и не заметит тормозов. Сборщик мусора очистит память, когда пользователь забъет на работу и пойдет покурить.

А по делу можно действительно попробовать организовать Пул. Но пул всеже чаще делают, если data большого размера, т. е. выделять/очищать долго. Тем не менее попробуй - делать просто, на результаты интересно посмотреть.

Ian ★★
()

>но может есть готовая теория\готовое решение

Есть готовое решение. JVM называется

Karapuz ★★★★★
()
Ответ на: комментарий от anonymous

Автоматическая сборка мусора ничего не ищет. Она просто копирует живующие объекты в новую область, а в старую тупо пишет новые объекты, дебил

Karapuz ★★★★★
()

>Есть дерево struct tree {void data; tree *left; tree *right}; Пусть тысячи таких структур в памяти: всяко-разно друг с другом связанны, постоянно создаются новые, удаляются старые.

У Александреску в книге приведен оптимизированный аллокатор на блоки данных размером в 8-128 байт. Можешь с С++ на Си спортировать - главное тут прицип. Либо взять из учебника по алгоритмам B* дерево которое хранится на диске и подгружается блоками по несколько килобайт по мере надобности.

Absurd ★★★
()
Ответ на: комментарий от Karapuz

> копирует живующие объекты

Ага, а живет объект или нет определяется за нулевое время? Возвращайся в школу, умник.

anonymous
()

Известный факт, что если надо выделять структуры данных фиксированной заранее определенной длины (как в этом случае), то выделение и освобождение делаются за O(1). Делается очень просто. Имеется односвязный список свободных элементов. Вначале этот список содержит все элементы пула. При требовании выделить память мы берем голову списка и возвращаем ее, в качестве новой головы списка записываем второй элемент. Если свободных элементов нет, то либо запрашиваем очередной большой блок памяти, либо вываливаемся с ошибкой. При освобождении элемента он становится головой списка.

dmitry_vk ★★★
()
Ответ на: комментарий от Ian

>Тем, что free будет отложенным. В результате будет использовано больше памяти, но возможно пользователь и не заметит тормозов. Сборщик мусора очистит память, когда пользователь забъет на работу и пойдет покурить.

Не только этим. Если имеем сборщик мусора, то могут быть более интересные вещи. Например, если сборщик сжимающий (compacting gc), то выделение элемента любого размера требует O(1) времени — имеем указатель на начало свободного блока (а он только один, начинается от последнего выделенного объекта до конца памяти), достаточно взять этот указатель и сдвинуть начало свободной области. Когда настанет сборка мусора, сжимающий сборщик сдвинет все объекты в начало одним непрерывным куском. А сборщик мусора с поколениями, к тому же, обычно мусор подбирает быстро.

dmitry_vk ★★★
()
Ответ на: комментарий от Karapuz

>Автоматическая сборка мусора ничего не ищет. Она просто копирует живующие объекты в новую область, а в старую тупо пишет новые объекты

Так работают только копирующие сборщики (copying gc). Как правило, такие сборщики стараются не использовать — время сборки мусора пропорционально O(size of live objects), да и нужно держать свободной половину памяти.

А сборщик в любом случае должен искать живые (в случае копирующего gc) или неживые (в случае некопирующего gc) объекты.

dmitry_vk ★★★
()
Ответ на: комментарий от dmitry_vk

>Если свободных элементов нет, то либо запрашиваем очередной большой блок памяти, либо вываливаемся с ошибкой. При освобождении элемента он становится головой списка.

Есть еще ньюанс - если блок находится в пуле свободных элементов, то он может содержать данные связанного списка, то есть указатель на следующий узел, а если занят - то данные пользователя. Уменно так устроен Loki::FixedAllocator.

Absurd ★★★
()
Ответ на: комментарий от Absurd

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

Логично. Экономия 4 (8 для 64-битных систем) байта на объект.

dmitry_vk ★★★
()
Ответ на: комментарий от balodja

>>В каких пределах объем data колеблется?

Примерно 512 byte. Ссылка на ресурс и ее описание

makoven ★★★★★
() автор топика
Ответ на: комментарий от anonymous

>>Имеется односвязный список свободных элементов. Вначале этот список содержит все элементы пула. При требовании выделить память мы берем голову списка и возвращаем ее, в качестве новой головы списка записываем второй элемент ...

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

Благодарю, очень интересная идея. Сам думал это массивами делать, но эта идея намного элегантнее

makoven ★★★★★
() автор топика

Если есть понятие сессии (например запрос юзера, обработка, ответ, освобождение использованных данных), то можно все объекты сессии выделять из некого пула, а освобождать потом одним махом весь пул, т.е. заменить множество free одним.

Legioner ★★★★★
()
Ответ на: комментарий от Legioner

>>Если есть понятие сессии (например запрос юзера, обработка, ответ, освобождение использованных данных), то можно все объекты сессии выделять из некого пула, а освобождать потом одним махом весь пул, т.е. заменить множество free одним.

Для каздого запроса поднимать тысячи связей, а потом убивать? Нет уж, пусть лучше постоянно висят

makoven ★★★★★
() автор топика
Ответ на: комментарий от makoven

> Сам думал это массивами делать, но эта идея намного элегантнее

Разумеется, список надо хранить в массиве (и не использовать std::list)

dmitry_vk ★★★
()
Ответ на: комментарий от makoven

Есть довольно много реализаций таких пулов. Поищи по словам memory pool или как-нибудь так.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.