Здравствуйте, Gaperton, Вы писали:
G>Это все ерунда. Главное — экономно обойтись с адредным пространством (оно должно отжираться плавно и пропорционально выделенной памяти),
Да. Это одно любопытное место.
>а вот как ты при этом собираешься делать деаллокацию объекта за О(1) — очень любопытный вопрос. Плюс — хипов у тебя должно быть много разных в любом случае — во избежание фрагментации для обеспечения хранения объектов разных длин.
Нет. Только по хипу на каждую длину (с учетом выравнивания) Хип0 : 1-8, Хип1 : 9-16 и т.д. (ну может, квант не 8, а 16). Все хипы фрагментированы квантами по 4К.
>Соответственно, ты никуда не денешься без определения адреса хипа по указателю на объект. Еще немного, и у тебя появится в этом уверенность.
У меня давно в этом уверенность есть и желание от нее избавиться. . Какое мне дело до хипа в целом, если я знаю указатель на буфер, где лежит удаляемый элемент ? Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . Проблема — как по указателю на элемент узнать размер. Пока придумал только в самом буфере. Не нравится.
А сам хип можно вполне на произвол его судьбы бросить. Не нужно мне о нем ничего знать. Как рос — так и рос. Мне даже не надо знать , какие страницы он занял — достаточно его в непрерывном пространствек вирт. адресов разместить.
>Хотя, если у тебя появится уверенность в обратном — обязательно пиши, это уже будет что-то оригинальное. Баллов дадим — сам понимаешь .
PD>У меня давно в этом уверенность есть и желание от нее избавиться. . Какое мне дело до хипа в целом, если я знаю указатель на буфер, где лежит удаляемый элемент ? Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . Проблема — как по указателю на элемент узнать размер. Пока придумал только в самом буфере. Не нравится.
PD>А сам хип можно вполне на произвол его судьбы бросить. Не нужно мне о нем ничего знать. Как рос — так и рос. Мне даже не надо знать , какие страницы он занял — достаточно его в непрерывном пространствек вирт. адресов разместить.
обсуждение Нюансов адресации памяти, делаем вывод, что свободно 4 бита 3 младших + 1 старший:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа — неправильно — имелось ввиду- аллокатора ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
S>а младште 3 бита будем использовать для кодирования длины выделенного блока.
S>Или я чего-то не понял ?
S>ЗЫ S>при помощи 3х младших бит — мы сможем расширить поддерживаемый диапазон, при желании
Здравствуйте, srggal, Вы писали:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
Я не планировал эту идею использовать. Но подумаю.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали: S>[] PD>>Я не планировал эту идею использовать. Но подумаю.
S>Могу я расчитывать на то, что вы поделитесь хотя-бы идеей реализации, отличной от трансляции адресов ?
Я идею выскажу, но хотел бы сам додумать до того, что получится.
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
-- Вчера на улице ко мне подошла старуха и предложила
купить вечную иглу для примуса. Вы знаете, Адам, я не купил.
Мне не нужна вечная игла, я не хочу жить вечно. Я хочу умереть.
У меня налицо все пошлые признаки влюбленности: отсутствие
аппетита, бессонница и маниакальное стремление сочинять стихи.
Слушайте, что я накропал вчера ночью при колеблющемся свете
электрической лампы: "Я помню чудное мгновенье, передо мной
явилась ты, как мимолетное виденье, как гений чистой красоты".
Правда, хорошо? Талантливо? И только на рассвете, когда
дописаны были последние строки, я вспомнил, что этот стих уже
написал А. Пушкин. Такой удар со стороны классика! А?
-- Нет, нет, продолжайте, -- сказал Козлевич сочувственно.
P.S. Если мне не изменяет память, встречал описание подобного алгоритма в первом томе
"Искусства Программирования" и еще в паре других источников.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
S>а младште 3 бита будем использовать для кодирования длины выделенного блока.
S>Или я чего-то не понял ?
S>ЗЫ S>при помощи 3х младших бит — мы сможем расширить поддерживаемый диапазон, при желании
Подумал над этой идеей. Если уж ей следовать, то у нас может быть не 3 младших бита и один старший, а 3(или 4) младших плюс 4-5 старших. Для этого достаточно память выделять в некоторой области , заранее зарезервированной по VirtualAlloc/MEM_RESERVE, а возвращать разницу между указателем на выделенный блок и началом этой зарезервированной области
lpHeapBase = VirtualAlloc(... MEM_RESERVE);
// пусть теперь выделили блок, lpBlock — его адрес
(lpBlock-lpHeapBase) >> 3 (или 4) — разница адресов, сдвинутая вправо. В этой величине левые n бит нулевые
n определяется так
Если размер кратен 8 , то
при макс. размере кучи 128 Мб имеем 3 бита (бывших правых) + 5 бит (бывших левых) — итого аж 8 бит. Один из них (старший есть
признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа, а еще 7 — под размер, что даст 128 разных вариантов — от 8 до 1024 байт.
sch>P.S. Если мне не изменяет память, встречал описание подобного алгоритма в первом томе sch>"Искусства Программирования" и еще в паре других источников.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Подумал над этой идеей. Если уж ей следовать, то у нас может быть не 3 младших бита и один старший, а 3(или 4) младших плюс 4-5 старших. Для этого достаточно память выделять в некоторой области , заранее зарезервированной по VirtualAlloc/MEM_RESERVE, а возвращать разницу между указателем на выделенный блок и началом этой зарезервированной области
PD>lpHeapBase = VirtualAlloc(... MEM_RESERVE);
PD>// пусть теперь выделили блок, lpBlock — его адрес
PD>(lpBlock-lpHeapBase) >> 3 (или 4) — разница адресов, сдвинутая вправо. В этой величине левые n бит нулевые
PD>n определяется так
PD>Если размер кратен 8 , то
PD>при макс. размере кучи 128 Мб имеем 3 бита (бывших правых) + 5 бит (бывших левых) — итого аж 8 бит. Один из них (старший есть PD>признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа, а еще 7 — под размер, что даст 128 разных вариантов — от 8 до 1024 байт.
ГМ, конечно я с Вами согласен, но идея была не в тем чтобы максимально увеличить кол-во хипов, ИМХО 4-8 — достаточно .
Здравствуйте, srggal, Вы писали:
S>ГМ, конечно я с Вами согласен, но идея была не в тем чтобы максимально увеличить кол-во хипов, ИМХО 4-8 — достаточно .
Ну тогда не понял я. Что такое кол-во хипов ? Зачем вообще их нужно иметь несколько ? Я полагаю, что нужен один хип, а нем подхиы — один для 1-8, другой для 9-16 и т.д.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>ГМ, конечно я с Вами согласен, но идея была не в тем чтобы максимально увеличить кол-во хипов, ИМХО 4-8 — достаточно .
PD>Ну тогда не понял я. Что такое кол-во хипов ? Зачем вообще их нужно иметь несколько ? Я полагаю, что нужен один хип, а нем подхиы — один для 1-8, другой для 9-16 и т.д.
ГМ, подхипы — я называю хипами, ибо термина подхип — нет, а хип есть.
ИМХО когда мы грим — хип для объектов размером от 1 до 8 байт — звучит нормально, а когда тоже озвучиваем как подхип для объектов размером от 1 до 8 байт — как-то кривовато.
PD>>Ну тогда не понял я. Что такое кол-во хипов ? Зачем вообще их нужно иметь несколько ? Я полагаю, что нужен один хип, а нем подхиы — один для 1-8, другой для 9-16 и т.д.
S>ГМ, подхипы — я называю хипами, ибо термина подхип — нет, а хип есть.
S>ИМХО когда мы грим — хип для объектов размером от 1 до 8 байт — звучит нормально, а когда тоже озвучиваем как подхип для объектов размером от 1 до 8 байт — как-то кривовато.
S>Просто вопрос терминологии.
Вот ещё Вас процитирую
Нет. Только по хипу на каждую длину (с учетом выравнивания) Хип0 : 1-8, Хип1 : 9-16 и т.д. (ну может, квант не 8, а 16). Все хипы фрагментированы квантами по 4К.
И вопрос по существу:
Павел а в чем проблема освобождения памяти о которой твердили большивики ?
Имея LRU блоков, освобождение будет легким и безболезненным, я правильно понимаю ?
Здравствуйте, srggal, Вы писали:
S>ИМХО когда мы грим — хип для объектов размером от 1 до 8 байт — звучит нормально, а когда тоже озвучиваем как подхип для объектов размером от 1 до 8 байт — как-то кривовато.
Сергей. я не хочу о терминах спорить. Пусть будут хипы, хотя я намерен все эти хипы в одном месте держать. Я другое не понимаю — если есть желание 3 бита на номер хипа, то объекты размером больше чем 8*8 == 64 сюда не полезут.
Здравствуйте, srggal, Вы писали:
S>И вопрос по существу: S> Павел а в чем проблема освобождения памяти о которой твердили большивики ?
Проблема в следующем. Есть указатель, который надо освободить. Адрес его буфера в 4К найти не проблема. Но какой размер у элементов этого буфера ? К какому хипу он принадлежит ?
S> Имея LRU блоков, освобождение будет легким и безболезненным, я правильно понимаю ?
Я как-то о LRU в этом контексте вообще не думал. Что освобождать-то по LRU ? У меня есть указатель, надо его запись считать свободной и добавить к списку свободных записей для этого хипа. Какое отношение к этому имеет LRU ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>И вопрос по существу: S>> Павел а в чем проблема освобождения памяти о которой твердили большивики ?
PD>Проблема в следующем. Есть указатель, который надо освободить. Адрес его буфера в 4К найти не проблема. Но какой размер у элементов этого буфера ? К какому хипу он принадлежит ?
S>> Имея LRU блоков, освобождение будет легким и безболезненным, я правильно понимаю ?
PD>Я как-то о LRU в этом контексте вообще не думал. Что освобождать-то по LRU ? У меня есть указатель, надо его запись считать свободной и добавить к списку свободных записей для этого хипа. Какое отношение к этому имеет LRU ?
PD>Похоже, мы не об одном и том же говорим.
ИМХО об одном и томже, только отрывочно, причем и с Вашей стороны, и с моей
Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента .
ОК, имеем указатель на буфер, в указатели в "свободных" битах закодирован индекс хипа(подхипа) в котором он выделен, это и есть размер, поскольку из каждого хипа/подхипа память выделяется блоками фиксированного размера.
Т.е. это массив элементами которого являются головы списков LRU свободных блоков.
ТОгда освобождение блока это:
1) Проверка на то, что этот блок был выделен CQG like allocator;
2) Получения из адреса индекса хипа/подхипа в котором был распределен этот блок;
3) Освобождаемый блок делаем головой списка pEmptyListStart[ index_of_heap ] ( это и есть LRU )
Здравствуйте, srggal, Вы писали:
S>Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . S>[/q]
S>ОК, имеем указатель на буфер, в указатели в "свободных" битах закодирован индекс хипа(подхипа) в котором он выделен, это и есть размер, поскольку из каждого хипа/подхипа память выделяется блоками фиксированного размера.
S>Т.е. это массив элементами которого являются головы списков LRU свободных блоков.
S>ТОгда освобождение блока это: S> 1) Проверка на то, что этот блок был выделен CQG like allocator; S> 2) Получения из адреса индекса хипа/подхипа в котором был распределен этот блок; S> 3) Освобождаемый блок делаем головой списка pEmptyListStart[ index_of_heap ] ( это и есть LRU )
S>Об этом говорим?
Да. При чем здесь LRU — понял теперь
Но тогда остается вопрос о битах. 3 битов явно не хватит для серьезной работы, так как макс. размер объекта 64 байта при гранулярности 8 байт.
[] PD>Но тогда остается вопрос о битах. 3 битов явно не хватит для серьезной работы, так как макс. размер объекта 64 байта при гранулярности 8 байт.
Нет никакой ложки
Изначально Вы тоже говорили о 3х хипах, я их немного расширил, ведь это пока, с моей стороны, теоретические выкладки, ни строчки кода не написано мной.
ИМХО, реализация несложна, при достаточно детализации теоретических выкладок.
Естетсвенно, что для реальных задач 3х бит недостаточно, но хочется заметить, что для реальной задачи может понадобиться и другая гранулярность.
Если грить о внедрении CQG like allocator в конретный проект, то для достижения максимальной эффективности необходимо воспользоваться memory profiling, в противном случае некоторый процент эффективности может быть утерян из-за универсальности.
Как вывод: хорошобы чтобы CQG like allocator был максимально настраиваемым как с точки зрения интервалов хипов, так и с точки зрения их гранулярности.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>Изначально Вы тоже говорили о 3х хипах, я их немного расширил, ведь это пока, с моей стороны, теоретические выкладки, ни строчки кода не написано мной.
Нет. я имел в виду произвольное (ограниченное, конечно) количество хипов, просто писал Хип0- 1..8, Хип1 — 9..16 и имел в виду, что далее и т.д. Сорри, если тем самым ввел в заблуждение.
S>ИМХО, реализация несложна, при достаточно детализации теоретических выкладок.
S>Естетсвенно, что для реальных задач 3х бит недостаточно, но хочется заметить, что для реальной задачи может понадобиться и другая гранулярность.
Насчет грануляронсти — или 8, или 16. Я не думаю, что иные значения имеют смысл — будет просто рост накладных расходов. А вообще в той модели, о которой писал утром сегодня, хипов может быть до 128-256, так что это не проблема.
S>Если грить о внедрении CQG like allocator в конретный проект, то для достижения максимальной эффективности необходимо воспользоваться memory profiling, в противном случае некоторый процент эффективности может быть утерян из-за универсальности.
Туманное это дело. Возможно, что и да.
S>Как вывод: хорошобы чтобы CQG like allocator был максимально настраиваемым как с точки зрения интервалов хипов, так и с точки зрения их гранулярности.
S>ЗЫ S>Хорошо, что мы наконец друг друга поняли.
Мне одно пока что не нравится. В результате автору запроса возвращается нечто, из чего он может сделать указатель. При освобождении он дожен передать нам это нечто, а не указатель. Да и вообще возврат этого нечто означает, что будет специализированный код — заменить вызовы malloc вызовом MyAlloc просто так не удастся.
Я хочу, чтобы просто возвращались указатели. Настоящие, чтобы к ним * применить и все! Без игр с младшими/старшими битами
. Какое мне дело до хипа в целом, если я знаю указатель на буфер, где лежит удаляемый элемент ? Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . Проблема — как по указателю на элемент узнать размер. Пока придумал только в самом буфере. Не нравится.
.
