Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
Память выделяют в куче. Реализация кучи в С++ и в управляемой среде делается по-разному. Обсуждать сейчас не буду, и тот и другой метод имеют свои преимущества и недостатки.
А если реализовать кучу следующим образом ?
Каждый объект, размещаемый в куче, имеет свой размер s. Разделим их по размеру на 3 категории — малые (s <= n), средние ( n < s < =N) и большие ( s > N). Численные значения надо определить экспериментально.
Для малых объектов создадим массивы
массив0 — для объектов с размером от 1 до 8 байт
массив1 — от 9 до 16
массив2 от 17 до 24
и т.д.
Для каждого малого объекта будем выделять память, кратную 8 байт, т.е. отнесем его к массиву0, или массиву1 и т.д. Это, в сущности, и сейчас делается в куче С++ — паять выделяется в размере, округленном в верхнюю сторону до 8 (или до 16 ?).
На базе этих массивов реализуем линейный список свободных ячеек. Для этого достаточно расписать элементы этих массивов указателем на следующий в массиве элемент. При взятии элемента из списка берется элемент, на который показывает pList и он продвигается, при освобождении — освобожденный элемент добавляется в список.
Кстати, эти массивы — не обязательно массивы в истинном смысле этого слова. Они могут лежать в памяти кусками — несмежными страницами, т.е. при необходимости расти.
Теперь выделение памяти для малых объектов сводится просто к взятию элемента из списка, а освобождение памяти (хоть delete, хоть GC) — к возвращению в список. Для неуправляемой кучи не требуется поиск подходящего блока, разбиение его и т.д. Для управляемой кучи не требуется сжатия кучи.
К малым объектам будут отнесены
большинство одиночных экземпляров классов
небольшие массивы (POINT[3], к примеру)
текстовые строки малого и среднего размера.
Для средних объектов оставляем все как есть сейчас. К ним будут отнесены средних размеров массивы, очень крупные экземпляры классов и большие текстовые строки. Как правило, таких объектов в программе намного меньше, чем "малых" переменных.
Для больших объектов память выделяем/освобождаем с помощью VirtualAlloc/Free, т.е округляем до размера страницы в верхнюю сторону. Оверхед при этом незначителен. Если, к примеру, большими считать объекты с размером более 100 Кб, то оверхед будет не более 4%, а при 1 Мб — вообще 0.4%. Можно пренебречь.
Таким образом, для малых и больших объектов выделение и освобождение памяти будет операцией O(1), и только для средних оно будет включать в себя поиск пустого блока или сжатие памяти.
Подводный камень, который я вижу
При пиковой нагрузке списки могут начать бурно расти, а освобождения их не предусмотрено. Ситуация примерно та же, что и со стеком в Win32 — он может расти, но декоммитирование страниц в стеке и передвижение PAGE_GUARD обратно не делается. Решение может заключаться в том же — ограничить размер списков некоторой величиной. При превышении этой величины память для малых объектов выделяется из средней кучи — до тех пор, пока в соответсвующем списке не появятся свободные места. Ничего от этого не пострадает — просто в среднюю кучу, которая от размеров объектов не зависит, изредка будут попадать и малые объекты.
Насколько я знаю, нечто подобное есть в ядре — ассоциативные списки, с фиксированным размером элементов, наиболее употребительные размеры. Почему бы это не реализовать и в приложениях 3 кольца ?
Здравствуйте, Павел Лазаревич, Вы писали:
PD> Custom allocator?
У Александреску свой аллокатор для маленьких объектов очень эффективен, можно взять его реализацию.
The allocator implemented by Loki has a four-layered architecture. The first layer consists of a
private type Chunk, which deals with organizing memory chunks in equally sized blocks. The
second layer is FixedAllocator, which uses a variable-length vector of chunks to satisfy
memory allocation to the extent of the available memory in the system. In the third layer,
SmallObjAllocator uses multiple FixedAllocator objects to provide allocations of any
object size. Small objects are allocated using a FixedAllocator, and requests for large objects
are forwarded to ::operator new. Finally, the fourth layer consists of SmallObject, a class
template that wraps a SmallObjAllocator object.
Для средних используем штатный new/delete;
А для больших сделать страничные аллокации, как предлагаете вы.
Чисто умозрительно рассуждая, должно получиться очень неплохо.
Pavel Dvorkin wrote:
> Таким образом, для малых и больших объектов выделение и освобождение > памяти будет операцией O(1), и только для средних оно будет включать в > себя поиск пустого блока или сжатие памяти.
Оно примерно так и сделано в современных вариантах (см. Hoard Allocator
или любые другие современные реализации). Правда, все осожняется
многопоточностью, но тут тоже можно много чего сделать.
Здравствуйте, Cyberax, Вы писали:
C>Оно примерно так и сделано в современных вариантах (см. Hoard Allocator C>или любые другие современные реализации). Правда, все осожняется C>многопоточностью, но тут тоже можно много чего сделать.
А что же все эти современные варианты в наиболее популярных средах не используются ? Я имею в виду кучу RTL, естественно, а не собственные переопределения new/delete
Pavel Dvorkin wrote:
> C>Оно примерно так и сделано в современных вариантах (см. Hoard Allocator > C>или любые другие современные реализации). Правда, все осожняется > C>многопоточностью, но тут тоже можно много чего сделать. > А что же все эти современные варианты в наиболее популярных средах не > используются ? Я имею в виду кучу RTL, естественно, а не собственные > переопределения new/delete
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А если реализовать кучу следующим образом ?
Так оно примерно и делается, только чтобы для того, чтобы избежать фрагментацию памяти выполняются дополнительные шаги:
1. Списки циклические двусвязные. Это позволяет удалить элемент из списка зная только указатель на этот элемент.
2. Флаги того, является ли текущий и предыдущий блок свободным. Это позволяет на этапе освобождения объелинть существующие блоки.
3. Текущий аллокатор, из которого выделяется память в случае, если нет блока в точности нужного размера.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
Идея не странная, а очень даже хорошая — говорю это не с точки зрения теории...
Похожая идея посетила меня примерно 5 лет назад, когда столкнулся с проектом для которого выделение/освобождение памяти было довольно существенной задачей. Решить эту задачу полностью в рамках того проекта — просто не было времени, но у меня появилось хобби связанное с "красивой" реализацией такой задачи.
По поводу "пиковой нагрузки" — собственно это самый "тонкий момент".
Это и есть самый большой недостаток. Ибо в такие моменты — куча будет превращаться в "обыкновенную", лишаясь всех достоинств, которые именно и нужны при "пиковой нагрузке". По мимо этого — установив "некоторый предельный размер" для малых списков (как его найти это ещё одна проблема) лишаемся именно "динамичности" т.е. основного достоинства кучи как таковой.
Собственно в устранении этого подводного камня и состоит задача ... помимо многопоточности и пр.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
Это у Вас всё происходит в вирутальной памяти. Будет сильно эффективнее работать не с виртуальной, а с реальной памятью. Соответственно, менеджер памяти (быть может даже с автоматической сборкой мусора) — это будет некий программно-аппаратный комплекс существующий в единственном экземпляре для всей системы, а не во-множественном — в каждом отдельном виртуальном пространстве. Вот, например, прямо сейчас на моём компьютере под виндос запущено 27 процессов, т.е. есть 27 виртуальных пространств, в каждом из них работает свой собственный программный менеджер памяти (некоторые даже со сборкой мусора), плюс системный программно-аппаратный менеджер памяти. Так вот, будь в системе всего один на всех программно-аппаратный менеджер памяти (а не +27 чисто программных), система работала бы быстрее.
P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Глеб Алексеев, Вы писали:
ГА>>Также рекомендую (не Вам, а Павлу) погуглить на тему dlmalloc и mtmalloc.
PD>OK, спасибо, посмотрел. И все же — почему это не используется в реальном мире Windows ?
Откуда ты знаешь, что именно там используется?
Есть исходные коды WinHeap а?
Для справки. В старых версиях VC++ CRT строила кучу поверх WinHeap а, с добавлением оптимизации для малых объектов. В новых -- фактически напрямую используется WinHeap.
Я подозреваю, что все возможные усовершенствования были перенесены в реализацию WinHeap.
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, Pavel Dvorkin, Вы писали:
Ш>А ты уверен, что это уже не реализовано в куче в твоём любимом компиляторе?
Уверен на 100%.
1. Как именно реализована куча в VC (malloc и т.д.) — знаю довольно хорошо, копался в ее исходниках. Ничего подобного там нет.
2. Как реализована сама куча Windows (HeapAlloc и т.д.) — в деталях не знаю, но вот такой код
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
если хорошенько подумать, то подавляющее большинство объектов имеет небольшое время жизни — в одной функции выделили, в другой поюзали и удалили
объекты, которые разделяются между потоками — это вообще редкость
с помощью статического анализа программы можно выделить для каждого объекта "точки освобождения" в коде, по достижении одной из которых объект становится ненужным.
объекты, которые освобождаются в одной и той же "точке освобождения", можно объединить в группу (такой точкой может стать выход из функции для всех локальных объектов, например)
таким образом, объекты каждой группы можно выделять из отдельного пула памяти, а при достижении соответствующей "точки освобождения" убивать этот пул одной операцией
таким образом можно избавиться и от фрагментации кучи, и от необходимости отслеживать ссылки на объекты в рантайме со всеми сопутствующими накладными расходами
есть конечно объекты, для которых эта схема не сработает — например, если их нужно передавать внешнему коду, или для выявления "точек освобождения" для этих объектов нужен слишком изощренный статический анализ. Для этого 0,1% можно оставить обычную сборку мусора или использовать подсчет ссылок — на общую производительность это уже не будет оказывать влияния.
Здравствуйте, bkat, Вы писали:
СГ>>P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
B>[offtop] B>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>[/offtop]
[offtop-продолжение]
Один извесный писатель был заклятым врагом Эйфелевой башни, критиковал ее при первом удобном случае и предлагал разобрать вообще. Но ежедневно ходил обедать в ресторан на Эйфелевой башне. Когда же у него спросили, почему он это делает, раз он так ее ненавидит, он ответил:
-- Это единственное место в Париже, где я не вижу эту чертову башню.
Продолжая в том же духе, можно предположить, что только в Обероне не видно проблем, которые можно успешно разрешить с помощью Оберона
[/offtop-продолжение]
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, bkat, Вы писали:
B>[offtop] B>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>[/offtop]
Есть, но они уже 70 лет успешно решаются на Лиспе и Хаскеле .
Здравствуйте, Cyberax, Вы писали:
С>Правда, все осожняется многопоточностью, но тут тоже можно много чего сделать.
Кстати, насче многопоточности, здесь как раз проблем меньше. После выяснения размера объекта нужно захватить только тот список, к которому он относится. Выделение памяти в других списках можно вести параллельно.
Здравствуйте, Глеб Алексеев, Вы писали:
B>>[offtop] B>>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>>[/offtop] ГА>Есть, но они уже 70 лет успешно решаются на Лиспе и Хаскеле .
Это теми решается, кто смог освоить языки Лисп и Хаскель
Остальные (Страуструп, Вирт, Грослинг, ван Россум, Уолл, Матцумото, Хальсенберг и др.) придумывали себе языки попроще
В результате каждый может найти себе язык по вкусу. Или свой придумать
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
