Здравствуйте, Pzz, Вы писали:
Pzz>Buddy allocation system имеет сложность, для операций выделения и Pzz>освобождения памяти, не превышающую O(log2(N)), где N — максимальный Pzz>размер блока, который можно зааллоцировать.
Pzz>Для любых практических целей это то же самое, что O(1), поскольку N - Pzz>константа.
Если бы речь шла не об операциях, которые вызываются миллионы раз, с этим можно было бы согласиться. В данном же случае даже этот небольшой цикл на 8-12 шагов будет весьма существенным в конечном итоге. ИМХО.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
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>>Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
PD>Идея неплохая, но дополнительные операции на каждое добавление / удаление. Впрочем, небольшой расход. Но я не очень пойму, что это даст. Освобождать можно только отдельные страницы. Вероятность того, что страницы окажутся совсем пустыми, невелика ИМХО, да даже если это будет и так, какая от этого нам польза ? Я вообще сомневаюсь, что этим надо заниматься. В конце концов commited size еще не есть working set, ненужные страницы уйдут в своп сами. В конце концов никто со стеком такое не делает, а стеков тоже много, по одному на поток.
1) Я не грил, что есть от этого мегапольза, но иногда может понадобится, так что, в целом, в CQG like allocator можно предоставить такую ОПЦИОНАЛЬНУЮ возможность. Т.е. не используешь- не плати, хочешь использовать- заплати.
2) Вот то, что они будут в свопе — и не нравится, они же ненужные
Здравствуйте, srggal, Вы писали:
S>1) Я не грил, что есть от этого мегапольза, но иногда может понадобится, так что, в целом, в CQG like allocator можно предоставить такую ОПЦИОНАЛЬНУЮ возможность. Т.е. не используешь- не плати, хочешь использовать- заплати.
Эта опциональная возможность потребует некоторой (пустячной, впрочем) переделки алгоритма выделения некоторого 4К блока. А именно, надо сначала просмотреть для всех уже занятых 4Кблоков page_infos[i].use_counter на предмет нуля. Если оно так и есть, можно его брать вместо выделения нового. Логично.
S>2) Вот то, что они будут в свопе — и не нравится, они же ненужные
Да, это не совсем хорошо. Потенциальный рост свопа без необходимости. В ОП ничего плохого не будет, а вот файл будет (возможно) расти. Но учет пустых блоков эту проблему едва ли решит. Не верю я, что они в реальной жизни будут. Чтобы они были, надо не приложение иметь, а роту солдат — по команде все заняли, по команде освободили... А может, иногда такое и будет.
Вообще-то есть еще одна идея. Правда, это уже будет переход на С++. Вернуть какой-нибудь умный указатель, так чтобы в действительности это был указатель на указатель на запись. Тогда можно будет при необходимости компактировать хип.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
PD>Вообще-то есть еще одна идея. Правда, это уже будет переход на С++. Вернуть какой-нибудь умный указатель, так чтобы в действительности это был указатель на указатель на запись. Тогда можно будет при необходимости компактировать хип.
Не нравится.
Хочется С/С++
PD>Разрабатывать идею не буду
Дык, побольшому счету, мой интерес к CQG like allocator АБСОЛЮТНО теоритический.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>1) Я не грил, что есть от этого мегапольза, но иногда может понадобится, так что, в целом, в CQG like allocator можно предоставить такую ОПЦИОНАЛЬНУЮ возможность. Т.е. не используешь- не плати, хочешь использовать- заплати.
PD>Эта опциональная возможность потребует некоторой (пустячной, впрочем) переделки алгоритма выделения некоторого 4К блока. А именно, надо сначала просмотреть для всех уже занятых 4Кблоков page_infos[i].use_counter на предмет нуля. Если оно так и есть, можно его брать вместо выделения нового. Логично.
ГМ, я имел ввиду случай когда фрагмент хипа равен размеру вмртуальной страницы, в противном случае со сбросом неиспользуемых страниц будет гиммор.
Кроме этого, необходимо предусмотреть ограничение на кол-во распределенных, но неиспользуемых фрагментов хипов, дабы небыло такого, что только сбросили страницу, и тутже её необхлдимо опять использовать.
Не нравится мне переделка освобождения, что-то тревожит, пока сформулировать не могу ; подумаю на выходных.
PD>Да, это не совсем хорошо. Потенциальный рост свопа без необходимости. В ОП ничего плохого не будет, а вот файл будет (возможно) расти. Но учет пустых блоков эту проблему едва ли решит. Не верю я, что они в реальной жизни будут. Чтобы они были, надо не приложение иметь, а роту солдат — по команде все заняли, по команде освободили... А может, иногда такое и будет.
Гм, рота солдат — мощно
std::vector< X > — вот она, то ли рота, то ли батальон, а возможно и дивизия
Что именно — зависит от 3х факторов:
1) sizeof(X)
2) vector.size()
3) специфики работы программы.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>ГМ, я имел ввиду случай когда фрагмент хипа равен размеру вмртуальной страницы, в противном случае со сбросом неиспользуемых страниц будет гиммор.
Естественно.
S>Кроме этого, необходимо предусмотреть ограничение на кол-во распределенных, но неиспользуемых фрагментов хипов, дабы небыло такого, что только сбросили страницу, и тутже её необхлдимо опять использовать.
И это возможно.
S> Не нравится мне переделка освобождения, что-то тревожит, пока сформулировать не могу ; подумаю на выходных.
Я тоже подумаю. Но, в конце концов, от этого и отказаться можно.
S>std::vector< X > — вот она, то ли рота, то ли батальон, а возможно и дивизия
Да, согласен. Захватили этот vector, потом чего-то еще, потом его выбросили — и готовы несколько страниц свободных.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>Дык, побольшому счету, мой интерес к CQG like allocator АБСОЛЮТНО теоритический.
PD>А я вот думаю, не дать ли это третьекурснику в качестве курсовой
Здравствуйте, srggal, Вы писали:
S>П что за предемет ?
Курсовая — не по предмету. Это просто некоторая работа, которую студент должен сделать в течение года. Факультет математический, поэтому либо математика (это не мое), либо программирование. Какая именно область программирования — не так уж важно, определяет научный руководитель.
За выходные придумал еще одно небольшое изменение. Если страница была захвачена и потом была полностью освобождена — не делать ей VirtualFree, а просто оставить ее. При выделении новой страницы ее можно выделить.
Т.е была, к примеру, некая страница выделена под элементы длиной 256. Потом все они были удалены, так что use_counter == 0. Теперь нужна новая страница под элементы с размером 128. Если есть хоть одна страница с use_counter == 0, взять ее, иначе коммитировать еще 4К.
Для нахождения страницы с use_counter==0 можно в приниципе и отказаться от О(1), просто искать ее в массиве. Это не так уж часто будет делаться. Но если уж очень хочется О(1), то можно провязать все нули еще одним LRU списком — освобожденных страниц. Т.е. когда у страницы use_counter становится равным 0, номер ее добавляется в LRU (стек) освобожденых страниц, а при запросе новой страницы берем оттуда , если стек не пуст.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>П что за предемет ?
PD>Курсовая — не по предмету. Это просто некоторая работа, которую студент должен сделать в течение года. Факультет математический, поэтому либо математика (это не мое), либо программирование. Какая именно область программирования — не так уж важно, определяет научный руководитель.
Ок
PD>За выходные придумал еще одно небольшое изменение. Если страница была захвачена и потом была полностью освобождена — не делать ей VirtualFree, а просто оставить ее. При выделении новой страницы ее можно выделить. PD>Т.е была, к примеру, некая страница выделена под элементы длиной 256. Потом все они были удалены, так что use_counter == 0. Теперь нужна новая страница под элементы с размером 128. Если есть хоть одна страница с use_counter == 0, взять ее, иначе коммитировать еще 4К.
PD>Для нахождения страницы с use_counter==0 можно в приниципе и отказаться от О(1), просто искать ее в массиве. Это не так уж часто будет делаться. Но если уж очень хочется О(1), то можно провязать все нули еще одним LRU списком — освобожденных страниц. Т.е. когда у страницы use_counter становится равным 0, номер ее добавляется в LRU (стек) освобожденых страниц, а при запросе новой страницы берем оттуда , если стек не пуст.
Да, я жумал именно об этом, но ак-то слишком много списков
Здравствуйте, gear nuke, Вы писали:
GN>Я имел ввиду не управление памятью в целом, а использование объектов, тем или иным образом уже инкапсулирующих управление памяти в себе — будь то GC, RAII или ещё что-то. То есть, где подумать надо один раз, а не для каждого экземпляра.
RAII — это не автоматическое управление памятью. Это костыль в процессе ручного управления ею. Так что средствами RAII нельзя полностью инкапсулировать работу с памятью. Тебе прийдется продумывать политику владения и вручную ее отслеживать. Причем в мало мальски серьезном проекте ты сталкнешся с тем, что есть чужой код который плевать хотел на твою политику владения. И у тебя в программе появится еще одна политика, а потом еще...
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
дравствуйте, gear nuke, Вы писали:
GN>Даже если всё будет распологаться не в стеке, а в куче — не будет фрагментации, и создание + удаление останутся так же почти бесплатны, поскольку порядок этих операций гарантирован.
Не, батенька. Только стэк практически беслатен. А куча всегда платна. Это и вылет за пределы кэша, и синхронизация.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, _Winnie, Вы писали:
_W>А я мечтаю о 64-битах. О резервировании для каждого вектора по гигабайту памяти. И о коммите, только когда надо. То есть, получаем невозможное — отсуствие переаллокаций при переполнении (при переполнении просто коммитим следующую страничку) и одновременно линейный кусок памяти...
Тсссс! Тут рядом Дворкин. Он же поаусает за такие траты ресурсов.
ЗЫ
Если серьезно, то управление виртуальной памятью двольно дорого. Перезаняите памяти в неком ЖЦ и копирование ее в с помощью SSE2 куда быстрее. У МС при разработке ЖЦ стояла задача сделать сборку нулевого и первого поколения быстрее чем обработка Page Fault и они этого добились (даже на P90).
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, srggal, Вы писали:
S>ГМ, я вел речь не о блоке памяти, который распределен на куче, а о самой куче, их должно быть несколько.
Если подумать, то у кучь разное адрессное пространство (ни же не двигаются). Так что берем адрес и смотрим в какой диапазно он входит. Ну, или еще тупее. Кладем в каждый блок ссылку на кучу. Я в QuickHeap
так делал. В статье этого не сказно, но в дальнейшем по совоету одного орла сделал указатель на следующий блок и ссылку на хип одним юнионом. Результат на лицо
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
Только учти в своих размышлениях, что выделение памяти (VirtualAlloc) в ОС довольно дорого.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Gaperton, Вы писали:
G>Это все ерунда. Главное — экономно обойтись с адредным пространством (оно должно отжираться плавно и пропорционально выделенной памяти), а вот как ты при этом собираешься делать деаллокацию объекта за О(1) — очень любопытный вопрос. Плюс — хипов у тебя должно быть много разных в любом случае — во избежание фрагментации для обеспечения хранения объектов разных длин. Соответственно, ты никуда не денешься без определения адреса хипа по указателю на объект. Еще немного, и у тебя появится в этом уверенность. Хотя, если у тебя появится уверенность в обратном — обязательно пиши, это уже будет что-то оригинальное. Баллов дадим — сам понимаешь .
Согласен. Но почему обязательно "экономно обойтись с адредным пространством"? Может у программы важность большая, а памяти она и так не много расходунет (но часто ее перезанимает)? В ООП так часто бывает.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, srggal, Вы писали:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
S>а младште 3 бита будем использовать для кодирования длины выделенного блока.
А теперь подумай. Ты постоянно будешь терять тучу места на каждый обхект. Не проще ли в него запихать ссылку на нужную структуру? Тогда будешь терять фиксированное количество памяти(4 байта) и иметь возможность адресовать все что хочешь.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > Если серьезно, то управление виртуальной памятью двольно дорого.
C чего бы? Управление VM — это по сути просто записи в таблицы.
Обработку страничных ошибок можно тоже значительно ускорить (до
нескольких тысяч тактов — никакому GC такое и не снилось).
.
