Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
PD>Память выделяют в куче. Реализация кучи в С++ и в управляемой среде делается по-разному. Обсуждать сейчас не буду, и тот и другой метод имеют свои преимущества и недостатки.
PD>А если реализовать кучу следующим образом ?
Если я ничего не перепутал при беглом прочтении, то ты изобрел менеджер памяти Delphi. См. здесь
Pavel Dvorkin wrote:
> С>Правда, все осожняется многопоточностью, но тут тоже можно много > чего сделать. > Кстати, насче многопоточности, здесь как раз проблем меньше. После > выяснения размера объекта нужно захватить только тот список, к > которому он относится. Выделение памяти в других списках можно вести > параллельно.
Просто если имеется только один глобальный набор списков, то нужны
interlocked-операции или мьютексы. А это нежелательно — поэтому есть
схемы с thread-local аренами, очередями запросов и т.п. За долгие годы
на эту тему ооочень много всего написали.
Дарней wrote:
> объекты, которые разделяются между потоками — это вообще редкость > с помощью статического анализа программы можно выделить для каждого > объекта "точки освобождения" в коде, по достижении одной из которых > объект становится ненужным. > объекты, которые освобождаются в одной и той же "точке освобождения", > можно объединить в группу (такой точкой может стать выход из функции > для всех локальных объектов, например) > таким образом, объекты каждой группы можно выделять из отдельного пула > памяти, а при достижении соответствующей "точки освобождения" убивать > этот пул одной операцией
Поздравляю, ты изобрел region inference
Как обычно, несколько "но": вообще говоря, нельзя определить "точку
освобождения" в общем случае. Даже в чистых функциональных языках это не
делается в полном объеме.
В C++ я делал нечто подобное — была иерархия пулов, причем в каждом
указателе лежала ссылка на свой пул. Можно было создавать объекты в
текущем пуле, в пуле другого указателя, или в именованом пуле. Причем
если какие-то указатели переживали свой пул, то их объекты перемещались
в более старший пул. Использовать было достаточно удобно, покрывалось
99% требований.
Это нужно было для одной сложной системы анализаторов, где важна была
скорость.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Cyberax, Вы писали:
С>>Правда, все осожняется многопоточностью, но тут тоже можно много чего сделать.
PD>Кстати, насче многопоточности, здесь как раз проблем меньше. После выяснения размера объекта нужно захватить только тот список, к которому он относится. Выделение памяти в других списках можно вести параллельно.
Списки — это зло. Это оверхед sizeof(void*)*2 == 8 байт на блок на 32-х битной машине.
Гораздо лучше массивы юзать. Выделяем большие блоки по 64, 128к или больше и главное чтобы начало блока было выровнено по его размеру. Тогда обнулив у указателя младшие биты автоматически получаем адресс массива в котором он сидит. Тогда и работает быстрее и нет оврехеда на prev,next в списке. А процедура удаления (без учета синхронизации) будет выглядеть вот так:
void free_( void *p )
{
block *pb = (block*)p;
// обнуляя младшие биты находим начало массива:
chunk *c = (chunk*)((size_t)p & (size_t)chunk_mask_);
// пополняем список свободных,
// поскольку блок больше не используется то указатель next прямо в нем (без оверхеда)
pb->next = c->free;
c->free = pb;
// уменьшаем счетчик занятых
c->used_n--;
}
Разбираться в деталях сейчас не буду, но вот это смущает
Алгоритм выделения памяти
Пытаемся найти в массиве smallTab блок в точности нужного размера.
Пытаемся выделить память из текущего выделяемого фрагмента.
Пытаемся найти блок подходящего размера в начале списка avail.
Просматриваем все оставшиеся элементы в списке avail, начиная с элемента, на который указывает rover.
Просматриваем массив smallTab, и, если в нем находится блок большего размера, используем его для выделения памяти.
Мне все эти "пытаемся", а особенно "просматриваем" не нравятся. В том, что я писал, выделение выглядит примерно так
size = sizeof(var);
if(size < nMin) // пограничное значение для малых объектов
{
size = (size +7) / 8 * 8; // округлить до 8
if(pList[size/8 - 1])
{
pRet = pList[size/8 - 1]; // размер 1-8 -> список 0, размер 9-16 - список 1 и т.д.
pList = pList->next;
return pRet;
}
else
{
pList = VirtualAlloc(1 page);
// прописать в этой странице, рассматривая ее как массив из элементов размера size, последние 4 байта каждого элемента, адресом след. элемента
}
}
else
HeapAlloc
Алгоритм выделения памяти достаточно прост – в цикле перебираются все списки в порядке приоритета, и если находится нужный фрагмент, то его и возвращают программе.
Алгоритм освобождения памяти уже не является линейным, как алгоритм выделения памяти. Однако он также не представляет большой сложности, поскольку большинство развилок связано с объединением смежных свободных блоков.
Нет, это явно не то . Я предлагаю их оба иметь как O(1). Точечно. Раз — и готово. Никаких развилок, никаких смежных блоков, никакого объединения чего бы то ни было с чем бы то ни было.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пытаемся найти в массиве smallTab блок в точности нужного размера. PD>Пытаемся выделить память из текущего выделяемого фрагмента. PD>Пытаемся найти блок подходящего размера в начале списка avail. PD>Просматриваем все оставшиеся элементы в списке avail, начиная с элемента, на который указывает rover. PD>Просматриваем массив smallTab, и, если в нем находится блок большего размера, используем его для выделения памяти.
PD>Мне все эти "пытаемся", а особенно "просматриваем" не нравятся. В том, что я писал, выделение выглядит примерно так
Как ни крути, а написать "идеальный" менеджер памяти под все случаи не получится. Нужно расставить приоритеты и иметь статистические данные.
По поводу менеджера памяти Delphi. В списке avail расположены блоки размером более cSmallSize (4 Кб), что соответствует твоему определению "среднему" размеру. Таким образом в случае небольших объектов подходящим будет первый попавшийся. smallTab просматривается в самую последнюю очередь и только в том случае, когда мв выделяем блок памяти небольшого (до 4 Кб) размера, но при этом у нас нет ни одного свободного блока более 4 Кб... К недостаткам менеджера памяти Delphi я бы отнес тот факт, что он пытается максимально использовать память, выделенную при помощи VirtualAlloc. Т. е. если в системе есть свободный блок подходящего размера, то обращения к функции VirtualAlloc выполнено не будет. В настоящее время вместо просмотра наверное "дешевше" выделить новую страницу памяти (или для очистки совести просмотреть несколько элементов из массива smallTab). Во всяком случае в Delphi 2006 теперь новый менеджер памяти, который работает несколько быстрее, но я его не смотрел.
Как я уже говорил, в менеджере памяти Delphi впециальные свои списки свободных элементов до размера 4096 байт включительно. Если для каждого такого размера вводить свой стисок, то мы получаем 4096 /8 = 512 страниц памяти. Т. е. у нас потенциально до 2 Мб памяти уходит под эти списки. При этом уровень заполняемости их зависит от особенностей приложения. второй минус в том, что Realloc со 100% вероятностью приводит к операции копирования, хотя копировать надо не так иж много.
Здравствуйте, Nickolay Ch, Вы писали: NC>Здравствуйте, Сергей Губанов, Вы писали: СГ>>P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
NC>ЗЫ. Нажал на ссылку интереса ради, и ужаснулся, аж в глазах посинело. Дизайн жуткий, не жмите эту ссылку!
Мда... Видимо, у тех, кто делает проекты на обероне, нету ни денег, ни мозгов, ни друзей — иначе сделать нормальный дизайн для них проблемы не составило бы...
Здравствуйте, Mystic, Вы писали:
M>второй минус в том, что Realloc со 100% вероятностью приводит к операции копирования, хотя копировать надо не так иж много.
Меня давно интересует вопрос: зачем вобще нужен realloc? Сколько пишу программы мне realloc ни разу не понадобился.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Шахтер, Вы писали:
Ш>Откуда ты знаешь, что именно там используется? Ш>Есть исходные коды WinHeap а?
Ш>Для справки. В старых версиях VC++ CRT строила кучу поверх WinHeap а, с добавлением оптимизации для малых объектов. В новых -- фактически напрямую используется WinHeap. Ш>Я подозреваю, что все возможные усовершенствования были перенесены в реализацию WinHeap.
Более того помнится кто-то вроде даже стебался над Юниксовыми хипами и говорил, что мол они не могут взять хип как в винде?
В хипе мло быстро выделить память в первый раз. Там важно хорошо переживать фрагментацию. Вот когда хип одинаково быстро выделит память как после запуска, так и через неделю работы, тогда и можно будет говорить, что хип быстрый. А так ну, пусть в двое быстрее по первой все будет работать. А дельее? Там ведь даже такие вещи как попадение кэш начинают влиять.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Кстати, насче многопоточности, здесь как раз проблем меньше. После выяснения размера объекта нужно захватить только тот список, к которому он относится. Выделение памяти в других списках можно вести параллельно.
Вот одно вычисление твое будет дороже чем открутка указателя в ЖЦ. А блокировка где бы не ставилась, все равно время занимает.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
. Цифра 70 лет — тоже неспроста.
1.1.4 stable rev. 510
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
ну я на всякий случай расставил точки над 'Ё'.
