Как известно в крупных программах, которые интенсивно работают с данными, очень часто принято писать самодельное распределение памяти, работающее поверх того что есть в Си. На это есть две причины. Во первых это сильно ускоряет работу программы, во вторых экономит память. По этой причине многие, так сказать, дети не могут обогнать по скорости, такие вещи std::list, с помощью самодельных списков. Здесь не будет речи, о том как писать распределители памяти красиво и хорошо, только беглые сравнительные тесты.

Для справки

Если мы возмём Си и выделим несколько элементов размером в один байт (new char), то реально каждый из них займёт по 16 байт, как в Windows, так и в Linux. Вы можете убедиться в том что адрес любого выделяемого элемента - кратен 16 байтам.

За выделение памяти в программе - целиком отвечает тот код, который даётся компилятором во время сборки программы. В Windows как правило, памяти выделяется большими кусками, через системную функцию HeapAlloc, а далее при каждом вызове new или malloc выделеная область отдаётся программе по кусочкам. Размеры выделямых участков измеряются интервалами по 8 байт. При выделении одного байта, требуется два таких интервала. Одни 8 байт для самого байта, и другие 8 байт, для заголовка со служебной информацией (и того уже знакомые 16 байт). Если запрашивается достаточно большая область памяти, то вызов передаётся непосредственно в HeapAlloc. Если память используется интенсивно, то в ней есть выделенные и свободные участки, точнее говоря дырки. Чтобы выделять память по возможности быстро, эти дырки объединяются в списки. Дырки сортируются по размерам. Распределитель поддерживает 64 списка (за точную цифру не отвечаю), в каждый из которых кладёт свободную область (дырку) соотвествующего размера.

GCC(Linux) - так довольно сложная система, которую одним абзацем не описать. Может быть, как-нибудь позднее я выложу полноценные рассказы про устройство диспечеров памяти.

Тесты

Тесты проводились в следующих условиях.

Linux+GCC


Выделение элементов размером от 1 до 100 байт. А так же тех же элементов, пачками по 16 и 32 элемента. Как видно выделение пачками происходит немного быстрее.


Скорость выделения элементов размером до 2000 байт. Похоже что одинаково легко справляется с элементами любых размеров. График можно продолжить до элементов любого размера, картина будет такой же. Одинаково легко справляется в любыми запросами. (вполне возможно за счёт большего потребления памяти, по сравнению с Windows).

Linux(GCC) против Windows 2000 (Visual C++ 6.0)

Размеры от 1 до 1000 байт. Как видно GCC+Linux немного обгоняют по скорости, даже на элементах малого размера.

Windows 2000 (Visual C++ 6.0)


Выделение элементов. Начиная от элементов размером 1017 байт и выше, Visual C++ 6.0 вместо самостоятельного распределения, начинает напрямую запрашивать функции кучи. В итоге элементы подобных размеров выделяются на порядок дольше (разница в скорости от 10 и выше 100 раз).


Выделение элементов от 1 до 100 байт. А так же тех же элементов, порциями или пачками по 16 и 32 штук сразу. Как видно пачками выделять быстрее, но если размер пачки превышает 1017 байт, но начинаются тормоза.

Способы выделения памяти в Windows

Проверялось под Windows XP (Visual C++ 6.0). Выделялся одинаковый участок памяти размером в два мегабайта, но он дробился на разные интервалы. Сначала по одному байту, потом по два, по четыре, и так далее по степеням двойки. Разумеется что следом шли так же попытки записи в выделеные отрезки памяти. Проверено 4 способа выделения:

malloc (он же new)



Показано время затраченное при разном дроблении (от 1, 2, 2^2, 2^3... и т.д.) Для мелких участков - самый быстрый способ. Как видно, при запросе участков, размером от килобайта (1024 байта) и выше скорость резко падает. Адреса выделяемых участков, кратны 16 байтам. Освобождение памяти для мелких участков примерно в 30 раз быстрее чем выделение.

HeapAlloc

Отдельно созданая куча. Не знаю что сказать про его скорость. Для элементов меньше чем 1024 байта (килобайт), он оказался самым медленным способом, который можно придумать (уступал даже LocalAlloc).


Показано общее время выделения.


Начиная с третего слобца идут элементы, от 1024 байт (килобайт) и выше. Как видно, работать начинает быстрее чем malloc. Освобождение выделяемой памяти происходит примерно в два раза быстрее чем выделение.

LocalAlloc

Насколько я знаю отличается, от HeapAlloc только тем что выделяет память в основной куче программы, но работает почему-то в среднем быстрее. Освобождение памяти, так же в два раза быстрее чем выделение. Хотя в HeapAlloc есть ещё приятная возможность снести всю кучу сразу.


Показано время выделения по сравнению с HeapAlloc. Дробление от 1 до 1024 байтов. Как видно LocalAlloc быстрее.


Показано время выделения по сравнению с HeapAlloc. Дробление от 1024 байтов и выше. Где-то он быстрее, но сравнивать уже трудно, так как есть погрешности в измерениях.

VirtualAlloc

Выделяет память целыми страницами. В моём случае выделял участки кратные, с адресами кратными 64 килобайта (размер соотвествующий). Выделить два метра кусками меньшими чем 128 байт, на машине с гигабайтом памяти не получится, так как памяти этой не хватит. Надо сказать что ещё придётся подстраивать вашу программу под размеры страниц на машине. По скорости, обгоняет другие методы, если мы выделяем участки памяти от 2, до 64 килобайт. Да и то ради этой скорости приходится жертвовать тем, что мы не используем часть страниц (притом большую). В остальном по скорости никакой разницы он не даёт. Только освобождает память быстрее. Освобождения страниц в среднем в 4-4.5 раз быстрее, чем выделение.


Показано общее время выделения, начиная с дробления от 128 байт и выше.


Показано общее время выделения по сравнению в malloc, начиная с дробления от 512 байт (пол килобайта) и выше.

Visual C++ 2003/2005/2008

Начиная с 2003 версии студии и выше, код распределителя был удалён из компилятора. Теперь любой запрос новой памяти сводится к вызову функций кучи. А следовательно элементы любого размера, выделяются одинаково медленно (так же медленно как большие элементы). Время стало непредсказуемым и большим. От версии к версии изменяется только оптимизация кода, на котором написан распределитель, но это не даёт принципиальной разницы.

C#

Visual Studio 2008 (Framefork 3.5). Для интереса запустил эквивалетную программу на шарпе (mem.cs), и посмотрел как она себя ведёт. Сравнивать с обычным языком бесполезно, но посмотреть можно:

Visual C++ 6.0 + Intel compiler

У меня довольно старая версия Intel компилятора. Результат его применения прост. Код генерируется другой, а вот библиотеки, по крайней мере та их часть, что лежит в исходниках, используется те же самые. А следовательно и менеджер памяти будет такой же, только в другом коде.

Немного о самих студиях

[Proteus] lawnmower-man@mail.ru

Hosted by uCoz