PD>Насчет грануляронсти — или 8, или 16. Я не думаю, что иные значения имеют смысл — будет просто рост накладных расходов. А вообще в той модели, о которой писал утром сегодня, хипов может быть до 128-256, так что это не проблема.
Т.е. таки два варианта всеже есть
PD>Мне одно пока что не нравится. В результате автору запроса возвращается нечто, из чего он может сделать указатель. При освобождении он дожен передать нам это нечто, а не указатель. Да и вообще возврат этого нечто означает, что будет специализированный код — заменить вызовы malloc вызовом MyAlloc просто так не удастся.
PD>Я хочу, чтобы просто возвращались указатели. Настоящие, чтобы к ним * применить и все! Без игр с младшими/старшими битами
Хочется тогоже.
Пока вижу один вариант
Блок под объект выделяется чуть большего размера и в нем хранится допинфо.
— дополнительный расход памяти.
Каждый хип при необходимости расширения использует использует область памяти расчитанную по след. формуле:
адрес текущего_фрагмента_хипа + N * размер_фрагмента_хипа
Здравствуйте, srggal, Вы писали:
S>Пока вижу один вариант
S>Блок под объект выделяется чуть большего размера и в нем хранится допинфо. S> — дополнительный расход памяти.
Да, я об этом уже думал. Мне не жалко дополнительный расход иметь, но только при малых размерах блока. Все же терять 2^N я не хочу, а поэтому надо резервировать запись, а не 1 байт в 4К. Хотя, между прочим, требование 2^N не обязательно и ни на что не влияет, кроме как на перегрузку кеша. Но и этого достаточно.
Здравствуйте, srggal, Вы писали:
S>Имеем N хипов.
S>Каждый хип при необходимости расширения использует использует область памяти расчитанную по след. формуле: S> адрес текущего_фрагмента_хипа + N * размер_фрагмента_хипа
S>Что думаете по этому поводу Павел ?
Рискованно. Это будет означать жесткое требование — всем хипам одинаковый максимальный размер. Если это не требовать — могут расти те хипы, которым нужно , за счет тех, которым не нужно — при ограничении только суммарного объема. Объектов 1-8 не создавалось, а 9-16 — хоть пруд пруди...
PD>Все же терять 2^N я не хочу, а поэтому надо резервировать запись, а не 1 байт в 4К. Хотя, между прочим, требование 2^N не обязательно и ни на что не влияет, кроме как на перегрузку кеша. Но и этого достаточно.
Этого я не понял N — кол-во блоков а 2 — размер допинфо ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>Имеем N хипов.
S>>Каждый хип при необходимости расширения использует использует область памяти расчитанную по след. формуле: S>> адрес текущего_фрагмента_хипа + N * размер_фрагмента_хипа
S>>Что думаете по этому поводу Павел ?
PD>Рискованно. Это будет означать жесткое требование — всем хипам одинаковый максимальный размер. Если это не требовать — могут расти те хипы, которым нужно , за счет тех, которым не нужно — при ограничении только суммарного объема. Объектов 1-8 не создавалось, а 9-16 — хоть пруд пруди...
ГМ, правда Ваша. Чтож получается для каждого фрагмента хипа первый (0ой) блок — своя информация о размере элемента.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Все же терять 2^N я не хочу, а поэтому надо резервировать запись, а не 1 байт в 4К. Хотя, между прочим, требование 2^N не обязательно и ни на что не влияет, кроме как на перегрузку кеша. Но и этого достаточно.
S>Этого я не понял N — кол-во блоков а 2 — размер допинфо ?
В начале страницы 4К можно бы хранить размер, т.е. номер хипа Получить адрес начала по указателю — p & 0xFFFFF000. Но на это надо отдать байт хотя бы. После чего в 4К останется 4095 байт и оно на размер элемента (8,16,24...) не делится. А целый элемент отдать — при больших размерах элементов слишком неэкономно.
nBlockSize[nPageNumber++] = nElementSize; // размер элемента, хранимого в этой странице.
Пусть освобождаемый адрес lpElement.
Находим
int nIndex = (lpElement — lpHeapBase) >> 12;
где lpHeapBase — адрес начала области, зарезервированной по VirtualAlloc/MEM_RESERVE для всех хипов.
nIndex и есть тот самый номер страницы, а nBlockSize[nIndex] и есть тот самый размер, а, значит, и номер хипа.
Все это ИМХО уложится в 10-15 ассемблерных команд.
Примечания.
1.Выделение именно квантами в 4К необязательно. Вполне возможно выделение 4К*n, где n можно даже изменять по ходу работы, как это делается у VladD2 http://www.rsdn.ru/article/?53
, да и в куче VC++ тоже. Определить, стоит ли это делать, можно ИМХО только экспериментально.
2. И вообще стоит подумать, не заменить ли 4К на 64К. Это и лучше, меньше дергать VirtualAlloc/MEM_COMMIT. Меня только оверхед смущает...
3. Массив nBlockSize можно даже не занулять.Пусть мусор остается в нем. Использование мусора невозможно по определению
4. Мимоходом — получаем информацию о том, какие 4K блоки отведены каким хипам. Непосредственно она нам не нужна, но можно реализовать функцию GetCurrentHeapSize(int nBlockSize).
5. Освобождение всех хипов (уничтожение кучи) делаем очень просто — VirtualFree/MEM_RELEASE при полном игнорировании того, какие блоки заняты, какие нет, и чем заняты, если заняты . Перед этим в отладочной версии можно проверить блоки и найти memory leaks.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>unsigned char nBlockSize[65536];
PD>Вполне достаточно. Будем иметь до 256 хипов
Гм, пока не нашел к чеиу придраться.
Но вот, об освобождении памяти:
Мы выделяем VP — страницу за страницой, но в том случае если вся память в странице освобождена — сброс страницы — непредусмотрен алгоритмом, я конечно понимаю, кеширование ресурсов и все-такое, но не очень нравится мне этот момент.
Здравствуйте, srggal, Вы писали:
S>Но вот, об освобождении памяти:
S>Мы выделяем VP — страницу за страницой, но в том случае если вся память в странице освобождена — сброс страницы — непредусмотрен алгоритмом, я конечно понимаю, кеширование ресурсов и все-такое, но не очень нравится мне этот момент.
Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
Придумать несложно, но О(1) не получится
PD>ИМХО это не страшно.
Когда-как , но спорить небуду.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
S>Придумать несложно, но О(1) не получится
Да нет, хуже. Можно, конечно, попробовать поискать блоки, в которых все элементы пусты и откорректировать списки. Но, во-первых, где гарантия, что хоть один найдется, а во-вторых, это несколько усложнит схему выделения (не очень).
PD>>ИМХО это не страшно. S>Когда-как , но спорить небуду.
S>Вроде как решение портабельное получилось
Вроде да. Возможно, для Win64 придется небольшие коррективы сделать. Какой там, кстати, размер страницы, не знаете ?
S>>Вроде как решение портабельное получилось
PD>Вроде да. Возможно, для Win64 придется небольшие коррективы сделать. Какой там, кстати, размер страницы, не знаете ?
Нет пока под руко 64битной винды Не начем вызвать GetSystemInfo.
PD>>>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
S>>Придумать несложно, но О(1) не получится
PD>Да нет, хуже. Можно, конечно, попробовать поискать блоки, в которых все элементы пусты и откорректировать списки. Но, во-первых, где гарантия, что хоть один найдется, а во-вторых, это несколько усложнит схему выделения (не очень).
Павел — такая мысль
nBlockSize это не массив unsigned char, но массив
struct
{
unsigned char block_size;
unsigned int use_counter; // maybe unsigned long at Win64
} page_infos[65536];
Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>>>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
S>>>Придумать несложно, но О(1) не получится
PD>>Да нет, хуже. Можно, конечно, попробовать поискать блоки, в которых все элементы пусты и откорректировать списки. Но, во-первых, где гарантия, что хоть один найдется, а во-вторых, это несколько усложнит схему выделения (не очень).
S>Павел — такая мысль
S>nBlockSize это не массив unsigned char, но массив S>
S>struct
S>{
S> unsigned char block_size;
S> unsigned short use_counter; // maybe unsigned int/long at Win64
S>} page_infos[65536];
S>
S>Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
S>O(1)
Здравствуйте, Pzz, Вы писали:
Pzz>Pavel Dvorkin wrote: >> >> *unsigned char* nBlockSize[65536]; >> >> Вполне достаточно. Будем иметь до 256 хипов
Pzz>Господа,
Pzz>а вы когда-нибудь слышали про buddy allocation system? Если нет, Pzz>рекомендую услышать
ГМ или я чего-то не понял, но здесь написано следующее:
ypically the buddy memory allocation system is implemented with the use of a binary tree to represent used or unused split memory blocks.
srggal wrote: > > Pzz>Господа, > > Pzz>а вы когда-нибудь слышали про buddy allocation system? Если нет, > Pzz>рекомендую услышать > > ГМ или я чего-то не понял, но здесь > <http://en.wikipedia.org/wiki/Buddy_memory_allocation> написано следующее: > > ypically the buddy memory allocation system is implemented with the use > of a *binary tree* to represent used or unused split memory blocks. > > А речь идет об О(1).
Buddy allocation system имеет сложность, для операций выделения и
освобождения памяти, не превышающую O(log2(N)), где N — максимальный
размер блока, который можно зааллоцировать.
Для любых практических целей это то же самое, что O(1), поскольку N —
константа.
S>Павел — такая мысль
S>nBlockSize это не массив unsigned char, но массив S>
S>struct
S>{
S> unsigned char block_size;
S> unsigned int use_counter; // maybe unsigned long at Win64
S>} page_infos[65536];
S>
S>Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
Идея неплохая, но дополнительные операции на каждое добавление / удаление. Впрочем, небольшой расход. Но я не очень пойму, что это даст. Освобождать можно только отдельные страницы. Вероятность того, что страницы окажутся совсем пустыми, невелика ИМХО, да даже если это будет и так, какая от этого нам польза ? Я вообще сомневаюсь, что этим надо заниматься. В конце концов commited size еще не есть working set, ненужные страницы уйдут в своп сами. В конце концов никто со стеком такое не делает, а стеков тоже много, по одному на поток.
