Как jemalloc работает? Каковы преимущества?
Я на самом деле думал об этом на днях.
пример, который, вероятно, не прекрасен, но достаточно близок к тому, что я думаю, спрашивают, распечатал бы дерево каталогов
public void printTree(directory) {
for(files in directory) {
print(file);
if(file is directory) {
printTree(file);
}
}
}
этот способ, из которого Вы заканчиваете со стеком для циклов, вложенных друг в друге без стычки выяснения точно, как они должны сочетаться.
3 ответа
jemalloc впервые появился для FreeBSD, детище некоего «Джейсона Эванса», отсюда и «je». Я бы высмеял его за эгоизм, если бы я ни разу не написал операционную систему под названием paxos : -)
См. этот PDF для получения полной информации. Это технический документ, в котором подробно описывается, как работают алгоритмы.
Основным преимуществом является масштабируемость в многопроцессорных и многопоточных системах, достигаемая частично за счет использования нескольких арен (фрагментов необработанной памяти, из которых выполняются выделения) .
В однопоточных ситуациях нет реальной пользы от нескольких арен, поэтому используется одна арена.
Однако в многопоточных ситуациях создается много арен (в четыре раза больше арен, чем процессоров ), и потоки назначаются этим областям циклическим образом.
Это означает, что конкуренция за блокировку может быть уменьшена, поскольку, хотя несколько потоков могут вызывать malloc или free одновременно, они буду бороться, только если они будут на одной арене. Два потока с разными аренами не будут влиять друг на друга.
Кроме того, jemalloc пытается оптимизировать локальность кэша, поскольку процесс выборки данных из ОЗУ происходит намного медленнее, чем использование данных, уже находящихся в кешах ЦП ( по концепции ничем не отличается от разницы между быстрой выборкой из ОЗУ и медленной выборкой с диска). С этой целью он сначала пытается минимизировать использование памяти в целом, поскольку это с большей вероятностью гарантирует, что весь рабочий набор приложения находится в кеше.
И, если это не может быть достигнуто,
Есть один интересный источник: сам C-источник: https://dxr.mozilla.org/mozilla-central/source/memory/build/mozjemalloc.cpp ( старый )
В начале краткое описание описывает, как он работает примерно.
// This allocator implementation is designed to provide scalable performance
// for multi-threaded programs on multi-processor systems. The following
// features are included for this purpose:
//
// + Multiple arenas are used if there are multiple CPUs, which reduces lock
// contention and cache sloshing.
//
// + Cache line sharing between arenas is avoided for internal data
// structures.
//
// + Memory is managed in chunks and runs (chunks can be split into runs),
// rather than as individual pages. This provides a constant-time
// mechanism for associating allocations with particular arenas.
//
// Allocation requests are rounded up to the nearest size class, and no record
// of the original request size is maintained. Allocations are broken into
// categories according to size class. Assuming runtime defaults, 4 kB pages
// and a 16 byte quantum on a 32-bit system, the size classes in each category
// are as follows:
//
// |=====================================|
// | Category | Subcategory | Size |
// |=====================================|
// | Small | Tiny | 4 |
// | | | 8 |
// | |----------------+---------|
// | | Quantum-spaced | 16 |
// | | | 32 |
// | | | 48 |
// | | | ... |
// | | | 480 |
// | | | 496 |
// | | | 512 |
// | |----------------+---------|
// | | Sub-page | 1 kB |
// | | | 2 kB |
// |=====================================|
// | Large | 4 kB |
// | | 8 kB |
// | | 12 kB |
// | | ... |
// | | 1012 kB |
// | | 1016 kB |
// | | 1020 kB |
// |=====================================|
// | Huge | 1 MB |
// | | 2 MB |
// | | 3 MB |
// | | ... |
// |=====================================|
//
// NOTE: Due to Mozilla bug 691003, we cannot reserve less than one word for an
// allocation on Linux or Mac. So on 32-bit *nix, the smallest bucket size is
// 4 bytes, and on 64-bit, the smallest bucket size is 8 bytes.
//
// A different mechanism is used for each category:
//
// Small : Each size class is segregated into its own set of runs. Each run
// maintains a bitmap of which regions are free/allocated.
//
// Large : Each allocation is backed by a dedicated run. Metadata are stored
// in the associated arena chunk header maps.
//
// Huge : Each allocation is backed by a dedicated contiguous set of chunks.
// Metadata are stored in a separate red-black tree.
//
// *****************************************************************************
Хотя более глубокий анализ алгоритма отсутствует.
О том, какие преимущества jemalloc принес в mozilla, см. http://blog.pavlov.net/2008/03/11/firefox-3-memory-usage/ (также первый результат Google для mozilla + jemalloc):
[...] пришел к выводу, что jemalloc дает нам наименьшую степень фрагментации после продолжительной работы. [...] Наши автоматизированные тесты в Windows Vista показали 22% -ное снижение использования памяти , когда мы включили jemalloc.