OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 18 Сентябрь, 2019 22:45

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3
Автор Сообщение
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Суббота, 10 Январь, 2009 09:32 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Евгений Темиргалеев писал(а):
Что Вы скажете про подход, указанный у Кнута в разделе про списки. Выделенный у системы блок памяти превращается в односвязный список L свободных Piece. При выделении блоки удаляются из начала L, при освобождении по ref = 0 блоки добавляются в начало L.
Очень интересный подход. При достаточно больших полезных объёмах дополнительный указатель не сильно обременит.

Я думал сделать так: у системы берётся блок памяти P, скажем, на 100 Piece. Если в процессе работы окажется мало, то берутся дополнительные блоки P. Они связываются в кольцевой односвязный список (т.е. оверхед = 1 указатель на 100 Piece). В каждый момент времени менеджер памяти помнит только один указатель - на тот блок P, в котором был выделен последний Piece. При необходимости найти свободный Piece, идёт с начала этого P и по всему кругу в поиске Piece с ref = 0. Если прошёл весь круг и не нашёл, значит пора новый блок P попросить у ОС.

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

В любом случае меня ещё вот какой вопрос интересует: как предусмотреть возврат блока P обратно ОС. Скажем, после завершения некой пиковой нагрузки хочется, чтобы объём выделенной памяти вернулся к близкому к минимуму значению. Или это не актуально в современных ОС? Алгоритм Кнута никак не способствует высвобождению или дефрагментации памяти, а мой подход заставляет хотя бы по максимуму оставаться в пределах одного блока P.

И ещё, наверное, имеет смысл блока P согласовать с каким-то системным размером? Где почитать, какие блоки рекомендуется брать у ОС?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Суббота, 10 Январь, 2009 10:15 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9139
Откуда: Россия, Орёл
По всем вопросам системщины Windows полезно читать Джеффри Рихтера (могу снабдить электронно).

Вообще, размер страницы был всегда в Win32 = 4K. Т.е. это гранулярность, с которой можно запрашивать память через VirtualAlloc у системы (если не создавать Heap).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Суббота, 10 Январь, 2009 18:40 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Выделение памяти хорошо проработано в "заменителе" менеджера памяти для Delphi - FastMM.
Память выделяется там, насколько я помню, блоками разного размера - от 160 байт и более, что-то около 20-25 разных размеров.
Вообще, я смотрел несколько разных менеджеров памяти (в частности, в СУБД), выделение памяти, обычно, идет тремя типами блоков - маленькими, средними, большими. Таким способом пытаются бороться с фрагментацией. Причем, почему-то для маленьких блоков размер кратен 160 байтам (или килобайтам). Объяснения этому феномену я не нашел, принял как данность :)

Что касается списков свободных блоков, то он успешно применяется в СУБД Оракл уже лет ...дцать. Блоки для сегмента (таблицы, индекса и др.) записываются в список свободных блоков и по мере использования оттуда изымаются и наоборот.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Четверг, 15 Январь, 2009 18:48 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Александр Ильин писал(а):
Я решил-таки сделать нормальную библиотеку для работы с динамическими строками.


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

P.S. С менеджером памяти та же фигня.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Четверг, 15 Январь, 2009 20:17 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Vlad писал(а):
Сделать нормальную библиотеку для работы с любыми строками очень сложно и работать она будет все равно хуже, чем оптимизация "по месту".

P.S. С менеджером памяти та же фигня.
А не с любой ли оптимизацией такая фигня? Понятно, что оптимизация увеличивает, э-мм... оптимальность системы. У меня задача - минимально приподняться над сверхоптимизацией, чтобы плюнуть с этой высоты на статические строки и присущие им игры в угадывание размера. Да, будет перерасход памяти и дополнительная нагрузка на GC, но типичные операции будут 1) выполняться быстрее (меняю память на скорость), 2) находиться в библиотеке (независимость от реализации) и 3) абстрагированы (прозрачный Юникод и пр.).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Четверг, 22 Январь, 2009 20:02 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Чем дальше занимаюсь строками, тем больше понимаю, что подсистема Text (BlackBox) и модуль Texts (Oberon System) - это и есть те самые библиотеки для работы с динамическими строками. Что-то более простое реализовать сложно. Единственная к ним претензия - излишек в виде форматирования (rich text). Вот если бы был базовый уровень без форматирования, а потом к нему надстройка для поддержки разукрашивания, тогда было бы совсем замечательно.

С другой стороны, rich text и plain text эффективно реализуются по-разному. Plain text эффективнее реализуется через буферы фиксированного размера, а rich text проще обрабатывать, когда он побит на run'ы (блоки произвольной длины, но с одинаковым форматированием).

А впрочем, "заседание продолжается..." Возможно, что вскоре я ещё передумаю насчёт plain text # rich text.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB