Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло

Память выделяют в куче. Реализация кучи в С++ и в управляемой среде делается по-разному. Обсуждать сейчас не буду, и тот и другой метод имеют свои преимущества и недостатки.

А если реализовать кучу следующим образом ?

Каждый объект, размещаемый в куче, имеет свой размер 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 кольца ?

Все. я готов к критике