- (2 стр)

Вий
>Ну и в этом аллокаторе главное - именно скорость, а не качественная дефрагментация
Если проблем в количестве памяти нет,
То выделяешь на каждый Трид свой блок памяти и никаких блокировок,
для больших аллокаций можно юзать общий пул с мутексами )

>А проблема фрагментации при мелких аллокациях решается...
Вот в этом проблема решений много, а какие хорошие без понятия,
так как определяются по факту)

exchg
>SLAB allocator.
обычный обжект мемори пул одного типа,
к сожалению никак не решает проблем фрагментации при ограниченном объеме памяти
и большом количестве разных алокацый.
Хотя штука неплохая)

WindreamIce
> обычный обжект мемори пул одного типа,
да ну нет, не совсем так.

WindreamIce
> к сожалению никак не решает проблем фрагментации
как не решает если весь смысл слаба какраз избавится от фрагментации и оверхэда?

kvakvs
> Придумали всякое.
Например?

Вий
> Это если аллокация и освобождение из одного потока вызывались, а если из разных
> - то можно придумать много всякого гораздо лучше пула на односвязном списке
Неа. Просто делается небольшая модификация и всё.

x
> Что там с борьбой с фрагментацией?
+1. Именно это и есть главная проблема хипов.

kvakvs
> 3. Универсального решения нет.
+100500

Вий
> смотрим на картинку
Вот только выводы их неё немного не те, что ты думаешь.

WindreamIce
> обычный обжект мемори пул одного типа,
> к сожалению никак не решает проблем фрагментации при ограниченном объеме
> памяти
> и большом количестве разных алокацый.
> Хотя штука неплохая)
Ну когда такие проблемы с памятью их борят не только элокатором, но и работой с логикой приложения. Ну чтобы меньше различных размеров блоков было и т.п.

exchg
>как не решает если весь смысл слаба какраз избавится от фрагментации и оверхэда?

>при ограниченном объеме памяти
Ну смотри пример:
есть у тебя два блока памяти
один для обжектов в 8 байт, второй на 32.
оба дырявые - так как обжекты юзаются и удаляются.

А теперь надо в эти два блока впихнут обжект размером 200,
надо теперь фрагментирвать и уменьшат конец N пула,

а если надо обьеденить два пула - нет места под 200,
то ещё фрагментирвать начало одного и конец другого пулов.

короче решаемо но не с коробки)

(и проблемы растут по мере роста: количества и размера пулов)

Bishop
>Ну когда такие проблемы с памятью их борят не только элокатором, но и работой с логикой приложения
Не всегда, - это ж отдельная либа,
мало кто будет под либу переписывать большой проект чтоб не было цельных объектов размером больше 64 байт к примеру.
Но безусловно это решает многое.

(к примеру еслиб сделать тег во время компиляции как цельный обжект можно разбить на куски без вреда,
и если нет претензий к длине мемори пойнтеров то все будет кул, кроме прямого копирования обжектов 1 блоком =))

WindreamIce
> А теперь надо в эти два блока впихнут обжект размером 200
> надо теперь фрагментирвать и уменьшат конец N пула
ну так слаб какраз и не будет никуда впихивать, и 200 байт будут выделены из блока который
отведен для 200 байтных "объектов".

WindreamIce
> а если надо обьеденить два пула - нет места под 200,
> то ещё фрагментирвать начало одного и конец другого пулов.
ненадо ))) смысл в том чтобы заранее отвести пямять под "объекты"
разного размера и по требованию выдавать адреса свободных блоков
заданного размера (это если сильно упростить).

exchg
>и 200 байт будут выделены из блока который отведен для 200 байтных "объектов".

под него нет памяти)
>при ограниченном объеме памяти
в этом и смысл фрагментации
200* - это мифическая цифра
по факту намного чаще будут ситуации есть пул на 100 обжектов, а надо пул на 300,
а через фрейм надо увеличить другой пул и места уже нет,
а в этом что на 300 занято всего 50.

WindreamIce
> по факту намного чаще будут ситуации есть пул на 100 обжектов, а надо пул на
> 300,
> а через фрейм надо увеличить другой пул и места уже нет,
> а в этом что на 300 занято всего 50.
ну в таком случае да, аут оф мемори, все приехали, хотя за частоту такой ситуации я б еще поспорил.
Но тоже самое случится и с кучей.

Bishop
> > Придумали всякое.
> Например?
Группировка по размеру и типу в один пул (кучу).
Выбор вариантов размеров куч для одинаковых блоков по степеням двойки.
Выбор вариантов размеров куч для одинаковых блоков по числам фибоначчи.
Перемещение и упаковка кучи (с прямыми указателями не получится, но если где-то регистрировать адреса всех указателей владеющих этим блоком, то вполне даже получится. Или если разыменовывать блок через индексную таблицу, тогда тоже блок можно двигать).
Вообще книга по GC адская сила )

WindreamIce
> Не всегда, - это ж отдельная либа,
Что именно? Элокатор?

> мало кто будет под либу переписывать большой проект чтоб не было цельных
> объектов размером больше 64 байт к примеру.
> Но безусловно это решает многое.
Ну на консолях извращаются очень и очень сильно.

kvakvs
> Группировка по размеру и типу в один пул (кучу).
Ну пул как бы и подразумевает работу с одинаковыми участками памяти, так что для разных размеров пулы разные. Я думал это само собой...

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

> Выбор вариантов размеров куч для одинаковых блоков по числам фибоначчи.
Хм... а вот такого варианта не знал, спс.

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

Bishop
> А вот это уже медленно будет, т.к. косвенная адресация... а это же зависимое
> чтение из памяти.
Да, двойное разыменование медленно.
А вот если отслеживать все копии указателя и при движении менять -- можно получить профит. Обращение к такой памяти останется обычным прямым по указателю. Да и даже если двойные, то ведь не все указатели в программе должны быть двойными, только те, которые больше всего способствуют фрагментаци, и часто ли приходится их разыменовывать, если это большие блоки нужные в начале рендера, один раз можно и на стек скопировать новый корректный указатель в локальную переменную.

Bishop
>Что именно? Элокатор?
Ну как бы да)
>Ну когда такие проблемы с памятью их борят работой с логикой приложения
Мы ведь рассматривает решение фром бокс, без переписывания всего проекта после смены аллокатора.
(на теже полу блоки для лучшей фрагментации или тип того)

>А вот это уже медленно будет, т.к. косвенная адресация... а это же зависимое чтение из памяти.
если юзать полу джампы
Тупавнул с компиляцией кода и выделением динамической памяти)
kvakvs
> Выбор вариантов размеров куч для одинаковых блоков по числам фибоначчи.
а можно больше деталей, а то что-то не понимаю в чем прикол)

Вий
> Требования:
> ... - быстро ... - быстро .... - быстро
Недавно мне пришлось написать свой аллокатор, но не из-за чистой скорости.
Мне нужна была возможность подкачки памяти с диска, без ручного изменения размера своп-файла в винде.

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

Она может сначала надавать страниц, потом совершенно внезапно в какой-то момент начнёт их свопить.
Причём не только те которые нужны, а вообще все добполнительные 16 GB которые я выделил. И пока все не засвопит, не вернет управление.
То есть программа в совершенно непроизвольные моменты времени может зависнуть на неопределённо-большой интервал вроде нескольких десятков минут !!!
Вот это действительно медленно.

В итоге часть я сделал через этот аллокатора, а часть данных я просто вручную принудительно выгружаю на диск в определённых условиях. Потом загружаю обратно. Не айс.
Мне был бы нужен аллокатор, который выделяет память относительно-большими блоками и как-то по стратегии кольцевого буффера старается свопить то, что было выделено в самом начале, или отмечено специальным флагом.
То есть я бы наверное предпочёл при вызове malloc указывать вес, который говорит можно свопить данный участок памяти - или это крайне нежелательно.
Ну что-то в этом направлении )

Угу. просто физически стоит 8. А объём данных был большой. (20+ GB).
В результате дефолтного размера своп-файла не хватало.
Можно увеличить вручную в винде, но это решение не очень для конечного пользователя.
Да и всё-равно хреново помогает )

Причём в моменты свопа система просто лежит, как XP в далекие 2000-ые или win 3.1 при форматировании дискет )

Вий
> Ну или поддержите, скажите, что вам тоже нужен аллокатор с MIT лицензией и что
> мне стоит писать FAP
Я когда-то написал свой (далеко не эффективный аллокатор) адресного пространства. Не памяти, а именно пространства. Такая штука мне понадобилась, чтобы скаладывать в один большой VertexBuffer кучу разных моделек, биндить его лишь однажды и рисовать из него по смещениями.

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