Управление памятью

Thu Mar 24 2005 02:04, Alexander Derazhne wrote to All:

AD> Столкнулся с проблемой - фрагментация :-(.

Hеуж-то нельзя аллокировать статически или в виде какой-то связной структуры типа списка или FAT?

AD> При наличии 100к свободных AD> блок в 3.5к выделить не получается. Текущая реализация менеджера хватает AD> первый свободный блок, превосходящий размером требуемый объём, по AD> возможности расщепляет его на два и т.д. Мне кажется, что подбор блока AD> минимального подходящего размера может помочь

Будет ХУЖЕ. Потому, что быстро образуется большое количество мелких дырок в памяти, в которые уже ничего не влазит и которые плохо консолидируются. Обычно стратегия аллокировать наоборот из самого большого блока работает лучше.

AD> Hо это только мои домыслы. Hе ткнёт ли кто-нибудь в ссылку на теорию AD> %subj'а?

А придется тебе делать сборку мусора.

VLV

"Быть честным - лучший способ оставаться бедным" (c) Hаполеон Бонапарт

Hi !

[...]

AD> P.S. Самое смешное, что где-то я про это читал - но это было давно и AD> неправда...

Тогда иделогически похоже на MCB в DOS с сопутствующими удовольствиями ... ;)

Bye, Aleks

Hello Alexander.

24 Mar 05 02:04, Alexander Derazhne wrote to All:

AD> множество возможных AD> запрашиваемых объёмов очень ограничено,

Если так, то может сделать статически?

Или сделать несколько пyлов таким обpазом, чтобы из одного пyла бpались только близкие по объемy кyски.

Alexey

Thu Mar 24 2005 02:04, Alexander Derazhne wrote to All:

AD> возможности расщепляет его на два и т.д. Мне кажется, что подбор блока AD> минимального подходящего размера может помочь (множество возможных AD> запрашиваемых объёмов очень ограничено, часть блоков будет использована AD> повторно, что "спасёт" бОльшие блоки, оказавшиеся в списке первыми).

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

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

AD> Hо это только мои домыслы. Hе ткнёт ли кто-нибудь в ссылку на теорию AD> %subj'а?

Кнут, Ахо и Сети, возможно.

bzz

Hello, Vladimir! You wrote to Alexander Derazhne on Thu, 24 Mar 2005 02:54:53 +0300:

AD>> Столкнулся с проблемой - фрагментация :-(.

VV> Hеуж-то нельзя аллокировать статически или в виде какой-то связной VV> структуры типа списка или FAT?

Увы, нельзя. Там DMA и DSP пасутся, они этого не поймут :-).

AD>> При наличии 100к свободных блок в 3.5к выделить не получается. AD>> Текущая реализация менеджера хватает первый свободный блок, AD>> превосходящий размером требуемый объём, по возможности расщепляет AD>> его на два и т.д. Мне кажется, что подбор блока минимального AD>> подходящего размера может помочь

VV> Будет ХУЖЕ. Потому, что быстро образуется большое количество мелких VV> дырок в памяти, в которые уже ничего не влазит и которые плохо VV> консолидируются. VV> Обычно стратегия аллокировать наоборот из самого большого блока VV> работает лучше.

Мндя... Наилучшим алгоритмом оказалось разбить все запросы на два класса - до 4К включительно и свыше. Для первых размер запроса округляется до этих самых 4к, поиск начинается с начала списка и предпочтение отдаётся

2**N блокам, в первую очередь самым подходящим (best fit). Для вторых - наоборот, с конца и не-2**N и, по прежнему, best fit. В результате "осадок" сократился до около 29к. Но теперь меня начали мучить сомнения: а вдруг это не фрагментация, а всё-таки утечка?! Ой-ой-ой...

AD>> Hо это только мои домыслы. Hе ткнёт ли кто-нибудь в ссылку на AD>> теорию %subj'а?

VV> А придется тебе делать сборку мусора.

Невозможно.

With best regards, Alexander Derazhne

24-Mar-05 02:54 Vladimir Vassilevsky wrote to Alexander Derazhne:

AD>> При наличии 100к свободных AD>> блок в 3.5к выделить не получается. Текущая реализация менеджера хватает AD>> первый свободный блок, превосходящий размером требуемый объём, по AD>> возможности расщепляет его на два и т.д. Мне кажется, что подбор блока AD>> минимального подходящего размера может помочь

VV> Будет ХУЖЕ. Потому, что быстро образуется большое количество мелких VV> дырок VV> в памяти, в которые уже ничего не влазит и которые плохо консолидируются. VV> Обычно стратегия аллокировать наоборот из самого большого блока VV> работает лучше.

Не помню точно, как было в RT-11 с диском (если размер файла известен уже). Очень простой и при этом довольно действенный механизм.

Кажется, если нет ТОЧНО подходящего куска, то ищется МИНИМАЛЬНЫЙ из тех, в котором запрошенное займёт МЕНЬШЕ ПОЛОВИНЫ.

wbr,

23-Mar-05 23:04 Alexander Derazhne wrote to All:

AD> Столкнулся с проблемой - фрагментация :-(. При наличии 100к свободных AD> блок в 3.5к выделить не получается. Текущая реализация менеджера хватает AD> первый свободный блок, превосходящий размером требуемый объём, по Как там в RT-11 дисковое пространство распределялось? :-) На занятой на 3/4 дискете при интенсивной работе с файлами (редкатирование/компиляция) squeez приходилось делать на удивление редко.

AD> возможности расщепляет его на два и т.д. Мне кажется, что подбор блока AD> минимального подходящего размера может помочь (множество возможных AD> запрашиваемых объёмов очень ограничено, часть блоков будет использована AD> повторно, что "спасёт" бОльшие блоки, оказавшиеся в списке первыми). AD> Но это только мои домыслы. Не ткнёт ли кто-нибудь в ссылку на теорию AD> %subj'а? Не ткну. Навскидку вспомню

1) Совсем просто - для блоков больше определённого размера выделять "первый попавшийся" от начала кучи, меньше - от конца. Уже улучшит ситуацию. Естественно, сделать список двусвязным для скорости.

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

Глянь досовский порт gcc, там, кажется, malloc сделан по такому принципу - выделение памяти кратно фиксированным размерам (4K и 128 байт минус заголовок ??) и двухуровневая (многоуровневая?) куча. Это VMK лет 10 назад копался там, я не помню точно.

wbr,

Привет, Alexander !

24 Mar 05 , 02:04 Alexander Derazhne писал к All:

AD> Столкнулся с проблемой - фрагментация :-(. При наличии 100к AD> свободных блок в 3.5к выделить не получается. Текущая реализация AD> менеджера [skip] AD> P.S. Самое смешное, что где-то я про это читал - но это было давно и AD> неправда...

Дональд Кнут. "Искусство программирования". Hомер тома не помню, но про менеджеры памяти там было очень подробно с кучей вариантов алгоритмов, теорией и тестами.

. С уважением, Hикита. icq:240059686, lj-user:nicka_startcev ... People are strange ... (ц) Doors

Hello, Oleksandr! You wrote to "Alexander Derazhne" snipped-for-privacy@i.com.ua> on Thu, 24 Mar 2005

20:24:17 +0000 (UTC):

OR> Навскидку вспомню

OR> 1) Совсем просто - для блоков больше определённого размера выделять OR> "первый попавшийся" от начала кучи, меньше - от конца. Уже улучшит OR> ситуацию. OR> Естественно, сделать список двусвязным для скорости.

Done, но полного похмелья не даёт.

OR> 2) Сделать фиксированный дискрет выделения памяти (увеличит расход OR> памяти, но уменьшит фрагментацию), для запросов на мелкие куски OR> можно ещё и подкучу реализовывать в выделенном крупном блоке. '1)' OR> для блоков верхнего уровня при этом тоже поможет.

На самом деле ситуацию радикально улучшило следующее - как оказалось, добрые мудрые жители Индостана при _любом_ исходе расщепляют найденый блок на два и возвращают лишнее в пул свободной памяти. Даже если эта сдача нулевой длины. Вообще-то это влиять ни на что не должно - при возврате соседнего блока они вновь сольются, а дескрипторы блоков берутся из другого адресного пространства (сразу: при нехватке дескрипторов возбуждается другая ошибка, это не оно). Логики происходящего я пока не понимаю, но факт налицо - после обхода ненужных расщеплений тест проходит "на ура". В другом тесте, правда, по-прежнему нехватка памяти, но разбирать его логи и дампы я буду только в понедельник.

With best regards, Alexander Derazhne

Hello, Nickita! You wrote to Alexander Derazhne on Fri, 25 Mar 2005 21:28:08 +0300:

AD>> P.S. Самое смешное, что где-то я про это читал - но это было давно AD>> и неправда...

NA> Дональд Кнут. "Искусство программирования". Hомер тома не помню, но NA> про менеджеры памяти там было очень подробно с кучей вариантов NA> алгоритмов, теорией и тестами.

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

With best regards, Alexander Derazhne

NA>> Дональд Кнут. "Искусство программирования". Hомер тома не помню, но AD> Похоже, что первый. Своего экземпляра у меня нет, второй и третий тома AD> в AD> инете есть, а вот о первом только упоминания.

Если кому-то интересно -- положу в будку.

Oneday 27 маpта 05 someone Kirill Frolov wrote Alexander Derazhne on subject Re: Упpавление памятью NA>>> Дональд Кнут. "Искусство пpогpаммиpования". Hомеp тома не помню, но AD>> Похоже, что пеpвый. Своего экземпляpа у меня нет, втоpой и AD>> тpетий тома в инете есть, а вот о пеpвом только упоминания. KF> Если кому-то интеpесно -- положу в будку. о, плиззз поделитесь, очень пpошу, если есть все томики :) буду благодаpен пpимного.

With best regards, Kirill Frolov

Hello, Kirill! You wrote to Alexander Derazhne on Sun, 27 Mar 2005 10:25:44 +0400:

NA>>> Дональд Кнут. "Искусство программирования". Hомер тома не помню, NA>>> но AD>> Похоже, что первый. Своего экземпляра у меня нет, второй и AD>> третий тома в инете есть, а вот о первом только упоминания.

KF> Если кому-то интересно -- положу в будку.

Ещё и как интересно!!! Только если к нему не потребуется отдельная статья "Как перегнать ТеХ в XML" :-)).

With best regards, Alexander Derazhne

Привет Andrey.

28 мар 05 01:19, Andrey Rudin -> Kirill Frolov: [...skipped...]

AR> о, плиззз поделитесь, очень пpошу, если есть все томики :) буду AR> благодаpен пpимного.

Все тома в djvu-формате, суммарный вес ~19M:

Kosty K.

Mon Mar 28 2005 03:39, Alexander Derazhne wrote to Kirill Frolov:

NA>>>> Дональд Кнут. "Искусство программирования". Hомер тома не помню, AD>>> Похоже, что первый. Своего экземпляра у меня нет, второй и KF>> Если кому-то интересно -- положу в будку. AD> Ещё и как интересно!!! Только если к нему не потребуется отдельная AD> статья "Как перегнать ТеХ в XML" :-)).

В шестой будке.

bzz

Hello, Kirill! You wrote to Alexander Derazhne on Mon, 28 Mar 2005 10:01:53 +0000 (UTC):

KF> В шестой будке.

Cпасибо! Нет, мир не без добрых людей!

With best regards, Alexander Derazhne

Oneday 28 маpта 05 someone Konstantin Konstantinov wrote Andrey Rudin on subject Упpавление памятью AR>> о, плиззз поделитесь, очень пpошу, если есть все томики :) буду AR>> благодаpен пpимного. KK> Все тома в djvu-фоpмате, суммаpный вес ~19M: KK>

о-о-о, пpиогpомный pешпект :)

With best regards, Konstantin Konstantinov

Пpиветствую, Konstantin!

KK> Все тома в djvu-формате, суммарный вес ~19M: Премного благодарен.

ЗЫЖ Где б ещё поновее взять ? :-/ Как-нибудь надо придавить жабу и купить домой.... Michael Tulupov ...