Предисловие
Данная статья выросла из проблемы, которую мне относительно недавно пришлось решить: скорость кода, предназначенного для работы одновременно в нескольких потоках, резко упала после очередного расширения функционала, но только на Windows XP/2003. С помощью Process Explorer я выяснил, что в большинство моментов времени исполняется только 1 поток, остальные находятся в ожидании, причём TID активного потока постоянно меняется. На лицо явная конкуренция за ресурс, и этим ресурсом оказалась куча по умолчанию (default heap). Новый код активно использует динамическое выделение/высвобождение памяти (копирование строк, копирование/модификация STL контейнеров большого размера), что собственно и привело к возникновению данной проблемы.
Немного теории
Как известно, аллокатор по умолчанию (default allocator) для STL контейнеров и std::basic_string (std::allocator) выделяет память из кучи по умолчанию, а операции выделения/высвобождения памяти в ней являются блокирующими (косвенное подтверждение). Исходя из этого, при частых вызовах HeapAlloc/HeapFree мы рискуем намертво заблокировать кучу для других потоков. Собственно это и произошло в моём случае.
Простое решение
Первое решение данной проблемы — включение так называемой low fragmentation heap. При переключении кучи в данный режим повышается расход памяти за счёт выделения чаще всего существенно большего фрагмента, чем был запрошен, но повышается общее быстродействие кучи. Данный режим по умолчанию включен в Windows Vista и новее (правдоподобная причина тормозов на XP/2003 и их отсутствия на 2008/7/2008R2). Код переключения кучи по умолчанию в данный режим предельно прост:
#define HEAP_LFH 2
ULONG HeapInformation = HEAP_LFH;
HeapSetInformation(GetProcessHeap(), HeapCompatibilityInformation, &HeapInformation, sizeof(HeapInformation));
Поправленный и собранный с помощью visual studio 2013 код сделал своё дело — CPU теперь загружен на 100%, время прохождения эталонного теста сократилось в N раз! Однако при сборке на нашей (мне больно это говорить...) visual studio 2003 (да, ей ещё пользуются) эффекта от исправления 0… Хьюстон, у нас проблемы…
Универсальное решение
Второе возможное решение проблемы — создать каждому потоку собственную кучу. Приступим.
Для хранения хендлов (handle) разных куч предлагаю использовать TLS слоты. Так как мой код — лишь часть библиотеки, непосредственно не управляющей созданием/завершением потоков, у меня нет информации, когда необходимо удалить кучу (с созданием всё тривиально, с удалением — сложнее). В качестве решения предлагаю использовать пул куч следующего вида:
class HeapPool
{
private:
std::stack<HANDLE> pool;
CRITICAL_SECTION sync;
bool isOlderNt6;
public:
HeapPool()
{
InitializeCriticalSection(&sync);
DWORD dwMajorVersion = (DWORD)(GetVersion() & 0xFF);
isOlderNt6 = (dwMajorVersion < 6);
}
~HeapPool()
{
DeleteCriticalSection(&sync);
while (!pool.empty()) // удаляем все кучи при выгрузке библиотеки
{
HeapDestroy(pool.top());
pool.pop();
}
}
HANDLE GetHeap()
{
EnterCriticalSection(&sync);
HANDLE hHeap = NULL;
if (pool.empty())
{
hHeap = HeapCreate(0, 0x100000, 0);
if (isOlderNt6) // для NT6.0+ данный код не имеет смысла
{
ULONG info = 2 /* HEAP_LFH */;
HeapSetInformation(hHeap, HeapCompatibilityInformation, &info, sizeof(info));
}
}
else
{
hHeap = pool.top();
pool.pop();
}
LeaveCriticalSection(&sync);
return hHeap;
}
void PushHeap(HANDLE hHeap)
{
EnterCriticalSection(&sync);
pool.push(hHeap);
LeaveCriticalSection(&sync);
}
};
HeapPool heapPool; // создаем пул
Теперь создадим глобальную переменную-слот:
class TlsHeapSlot
{
private:
DWORD index;
public:
TlsHeapSlot()
{
index = TlsAlloc();
}
void set(HANDLE hHeap)
{
TlsSetValue(index, hHeap);
}
HANDLE get()
{
return (HANDLE)TlsGetValue(index);
}
};
/*глобальная переменная, однако результат метода get() зависит от потока, в котором он вызван */
TlsHeapSlot heapSlot;
Так как наша цель — оптимизация работы std::basic_string и STL контейнеров, нам понадобится «самопальный» аллокатор:
template <typename T>
class parallel_allocator : public std::allocator<T>
{
public:
typedef size_t size_type;
typedef T* pointer;
typedef const T* const_pointer;
template<typename _Tp1>
struct rebind
{
typedef parallel_allocator<_Tp1> other;
};
pointer allocate(size_type n, const void *hint = 0)
{
return (pointer)HeapAlloc(heapSlot.get(), 0, sizeof(T) * n);
}
void deallocate(pointer p, size_type n)
{
HeapFree(heapSlot.get(), 0, p);
}
parallel_allocator() throw() : std::allocator<T>() {}
parallel_allocator(const parallel_allocator &a) throw() : std::allocator<T>(a) { }
template <class U>
parallel_allocator(const parallel_allocator<U> &a) throw() : std::allocator<T>(a) { }
~parallel_allocator() throw() { }
};
И финальный штрих:
class HeapWatch // вспомогательный класс для возврата кучи в пул при выходе
{
private:
HANDLE hHeap;
public:
HeapWatch(HANDLE heap) : hHeap(heap) {}
~HeapWatch()
{
heapPool.PushHeap(hHeap);
}
};
extern "C" int my_api(const char * arg) // предположим, что интерфейс такой
{
HANDLE hHeap = heapPool.GetHeap();
HeapWatch watch(hHeap);
heapSlot.set(hHeap);
/* Здесь располагается или отсюда вызывается код, интенсивно выделяющий/высвобождающий память.
Теперь мы можем использовать код вроде
std::basic_string<char, std::char_traits<char>, parallel_allocator<char> > str и
std::list<int, parallel_allocator<int> > lst,
которые будут работать быстрее, чем аналоги со стандартным аллокатором (при параллельном исполнении)
*/
}
Результаты:
Главное — задача решена, и притом не костыльно. Второе решение сложнее, но даёт прирост производительности на всех протестированных платформах (win xp — windows 10) при сборке решения и в VS2013, и в VS2003 (максимальный эффект достигается в XP/2003 при использовании VS 2003 — время выполнения эталонного теста сократилось почти в N раз (где N — число ядер CPU), на более новых платформах — от 3 до 10 процентов). Простое решение идеально подойдёт тем, кто использует свежие версии компиляторов. Надеюсь, данная информация окажется полезной не только мне.
Комментарии (33)
encyclopedist
18.09.2015 14:43Будет ли это работать, если выделить память из одного потока, а освободить из другого?
maxdm
18.09.2015 16:25Нет конечно. Самая простая доработка — в первых четырех/восьми байтах хранить хэндл кучи и возвращать сдвинутый указатель.
Ivan_83
18.09.2015 21:45+2С добрым утром :)
Это МС накорябал 20 лет назад:
http://www.verysource.com/code/166704_1/mpheap.c.html
Это я, 11 лет назад:
http://netlab.linkpc.net/download/software/SDK/old/%21Clases/include/MABEX.h
http://netlab.linkpc.net/download/software/SDK/old/%21Clases/include/Old/MAB.h
(по нынешнем временам код блювотный, но вполне работал раньше)
Уже не помню по какой книге это делалось, какая то одна из трёх от МС пресс, скорее всего.
А может по сайтам.
Смысл в том чтобы:
— держать пул куч, желательно по одной для каждого потока в процессе
— каждому потоку стараться выделять память из собственной кучи
— если потоков больше, чем куч то искать свободную кучу
— если поток освобождает память которая выделена не из его кучи, то не пытаться заблочить чужую кучу, а просто ставить в очередь на освобождение, а в след раз перед выделением памяти когда куча будет залочена то освободить всю память из односвязного списка на освобождение.
— ещё можно держать пулы кусков памяти, чтобы в кучу не лазать
— ещё можно перед выделением из кучи во время освобождения искать куски подходящего размера
А ещё важно правильное выравнивание.
Заодно я отключил сериализацию куч, тк использую критические секции для этого и память руками обнуляю.
Deamhan
18.09.2015 23:21+1Согласен, идея один поток <-> одна куча не нова (это справедливо не только для MS), вопрос лишь в том, когда это действительно необходимо. В моём случае это оказалось именно так. Насчёт пулов фрагментов памяти — Вам не кажется, что Вы изобретаете велосипед (куча, по сути, как раз и является таким пулом)? Насчёт поисков кусков подходящего размера — LFH куча и так справится с этим на ура. Неоспоримый факт, что усложнение кода такими «оптимизациями» приведёт к дополнительным багам, а вырастет ли быстродействие — вопрос. Насчёт несериализуемой кучи — полезное замечание. Ещё один нюанс — в сумме небольшой и хорошо читаемый исходник моего решения, который реально работает.
Ivan_83
19.09.2015 21:59Понятно что для гуй проги обычно это всё не нужно, и можно вообще обойтись статическими буферами.
Насчёт пулов — уже не кажется :)
Под виндой пишу теперь оч редко, а на остальных ОС с аллокаторами проще, и выбора больше.
Те рекомендации были во время ХР, и вероятно относились к ещё более старым реализациям куч в винде, где, скорее всего, можно было легко на этом ощутимо выиграть.
От VEG с интересом узнал что в NFS3 была своя реализация аллокатора, видимо для ускорения.
На уровне ОС аллокаторы обычно выделяют большой кусок памяти через mmap а в винде скорее всего VirtualAlloc и дальше продают его в розницу.
Это, кстати, ещё один вектор оптимизации. Читал что большие куски лучше всего выделять через VirtualAlloc / mmap а не тягать из кучи.
Не знаю что считать большим, но явно не меньше одной страницы памяти, те 4к как правило на современных системах. Учитывая что для выделения 4к нужно ещё 4к под служебку (сама то она маленькая, но хранить её нужно до начала отдаваемого и отдавать желательно выровненное) то с 32-64кб я бы точно начинал выделять уже не из кучи.
С другой стороны часто дёргать VirtualAlloc / mmap тоже накладно.
Опять же, для своих страниц памяти можно сделать lock и это может дать профит, потому что ОС не будет больше дёргать страницы памяти.
Возможно сейчас LFH и будет лучше самостоятельной реализации, нужно пробовать.
Можно долго пилить идеальный аллокатор, но в итоге оптимизация кода чтобы он меньше выделял/освобождал всегда даст больше.encyclopedist
19.09.2015 22:53В Линукс все растпространённые аллокаторы так и делают — выделяют большие куски прямо с помощью mmap (GNUшный ptmalloc например начиная со 128кБ)
Deamhan
20.09.2015 12:08На Windows при выделении фрагмента размером около allocation granularity HeapAlloc почти напрямую переходит в VirtualAlloc (оверхед небольшой). Аllocation granularity обычно равен 64КБ.
vpolin
22.09.2015 18:18кстати, а как живет parallel_allocator с множеством маленьких аллокаций типа 8-32 байта
phprus
19.09.2015 11:14А у вас контейнеры, использующие аллокатор parallel_allocator, используются строго в одном потоке?
В смысле, что все модифицирующие (не const) методы вызываются исключительно в одном потоке?
Если нет, то у Вас проблемы. Например, resize или какой-нибудь push_* может вызвать перераспределение памяти и если он будет вызван из другого потока, то heapSlot.get() вернет не ту кучу, которую Вы ожидаете.
Если такая проблема возможна, то, как вариант, можно посмотреть в сторону stateful аллокаторов (С++11), но я не уверен, поддерживает ли их STL из VisualStudio (но они работают в boost::container).
В дополнение могу посоветовать посмотреть на tbbmalloc из Intel Threading Building Blocks. Их opensource лицензия позволяет применять библиотеку даже в ПО с закрытым кодом, сейчас у них появились Community лицензии, а на моих задачах (многопоточных с высокой интенсивность перераспределения памяти) использование этого аллокатора сократило нагрузку на CPU на 5-7% по сравнению с tcmalloc (который сейчас живет по адресу: https://github.com/gperftools/gperftools).Deamhan
19.09.2015 12:22Разумеется. Все модификации контейнеров с данным аллокатором проводятся только в потоке, их создавшем. А за советы спасибо.
vpolin
22.09.2015 09:59Отмечу одностроковое решение для автоматической подмены системного аллокатора:
www.threadingbuildingblocks.org/docs/help/index.htm#tbb_userguide/Windows_C_Dynamic_Memory_Interface_Replacement.htmDeamhan
22.09.2015 14:16Я не ставил целью глобальное переопределение new / malloc / delete /free, а в Вашем случае происходит именно это (Ваше «одностроковое решение» в общем случае потребует модификации других библиотек, что не всегда возможно). В случае Intel Threading Building Blocks мне бы идеально подошёл вариант phprus-а.
vpolin
22.09.2015 14:25модификации каких других библиотек? эту строчку нужно добавить _в один_ из модулей, которые будут подгружаться во время загрузки приложения.
Deamhan
22.09.2015 14:43Объясняю: Вы переопределяете malloc только в своём модуле (например library.dll) и выделяете память с её помощью. Затем в другом модуле (например, test.exe, в котором она не переопределена) её освобождаете с помощью free (плохой стиль, но тем не менее это возможно). Что произойдёт?
vpolin
22.09.2015 15:01мы переопределяем маллос и в всех студийных рантаймах, приложения (msvcrt*.dll), которые подняты при старте подмены аллокатора. Т.е library.dll и test.exe будут использовать один и тот же аллокатор.
Более того, если используется «плохой стиль» + library.dll и test.exe собраны разными студиями («не повторяйте этого дома»:)), тогда всё равно будет использоваться один подмененный аллокатор.Deamhan
22.09.2015 15:20Хм, интересно. Каким образом достигается такой эффект? Мне приходят на ум приходят 2 варианта: патч msvcrt и патчи IAT в других библиотеках. Вы писали, что
мы переопределяем маллос и в всех студийных рантаймах, приложения (msvcrt*.dll), которые подняты при старте подмены аллокатора
, из чего я склоняюсь ко второму варианту. Что насчёт библиотек, загруженных после старта (LoadLibrary и аналоги)?vpolin
22.09.2015 15:41Первый вариант («патч msvcrt»). Поскольку у каждой студии свой рантайм (msvcrt70.dll,msvcrt71.dll...,msvcrt120.dll,ucrtbase.dll), я указал «рантаймы» во множественном числе. Они все меняются одновременно. Соответственно, если какая-то новая библиотека, которая загружена позже через LoadLibrary(), использует тот же рантайм, что был уже перегружен при запуске программы, то эта новая библиотека будет использовать перегруженный аллокатор. Если же используется какой-то новый рантайм, в котором аллокатор не перегружен, то при определенных обстоятельствах неправильного использования можно столкнуться со знаменитым «cross module boundaries hell».
Deamhan
22.09.2015 15:43Тогда такой вопрос: что происходит в случае статической CRT (ключ /MT в VS)?
vpolin
22.09.2015 15:51этот модуль будет использовать CRT аллокатор с выделенным пулом памяти. Это всё равно, что построить обе library.dll и test.exe со статическим рантаймом и пробовать выделять/освобождать память в разных модулях. Классический «cross module boundaries hell».
Deamhan
22.09.2015 16:00Понятно. Лично я обошёл бы подобную технику стороной (к чему злить антималварный софт).
vpolin
22.09.2015 16:36OK, для плюсовых программистов у нас есть scalable_allocator вот тут можно посмотреть дискуссию. stackoverflow.com/questions/657783/how-does-intel-tbbs-scalable-allocator-work.
Я так понял, что это тоже самое, что было реализовано в этой статье.vpolin
22.09.2015 16:38Ссылка на статью «The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks» протухла вот новая ссылка
www.intel.com/content/dam/www/public/us/en/documents/research/2007-vol11-iss-4-intel-technology-journal.pdfDeamhan
22.09.2015 17:40Дискуссия — громко сказано. Назначение scalable_allocator, пожалуй, сходное, хотя вдумчиво прочитать док пока нет возможности. Но есть одна большая разница — код, приведенном в данной статье, может использовать любой желающий совершенно задаром, можно ли то же самое сказать про Intel-овский? В нём нет никаких акцентов на аппаратную платформу, что насчёт Intel-овского (просто предположение)? Ещё такой вопрос: scalable_allocator тоже использует приватные кучи?
vpolin
22.09.2015 17:591. scalable_allocator идет под лицензией GPLv2 with runtime exception + Commercial. Лицензии использования алгоритма, представленного в топике не указаны.
2. scalable_allocator использует всю мощь tbbmalloc, который работает в бэкэнде, и соответственно работает на всех платформах, куда запортирован tbbmalloc.Deamhan
22.09.2015 19:00Насчёт 1: в пред. комментарии я указал, что мой код может использовать кто угодно, в том числе в комм. приложениях с закрытым исходным кодом (хотя могу указать BSD или MIT лицензию, шутки ради). Насчёт 2:
может быть, «мощь» tbbmalloc и впрямь велика, но насколько часто она действительно нужна? Стоит ли она того, чтобы за неё платить в описанной ситуации (прим: использовал прив. код в комм. софте)? Приведенный код прекрасно себя чувствует при работе в 8 потоков, но это, как мне кажется, не предел. Плюс его легко портировать на другие платформы, поддерживающие работу с приватными кучами и аналогами TLS (хотя передо мной такая задача не стояла). И ещё: вы пропустили вопрос насчёт аппаратных акцентов (хотя про такое обычно и не говорят).vpolin
22.09.2015 19:10+1Насчет п.2 спорить бесполезно, ибо холивар. Если есть какие-то конкретные вопросы, можно обсудить.
Но в целом, мой совет про аллокаторы (не ТС, а всем): необходимо попробовать различные аллокаторы (tbbmalloc, TCMalloc, jemalloc, parallel_allocator, hoard, etc.) и использовать тот, который больше всего устраивает устраивает для этого конкретного приложения или ворклода.
phprus
24.09.2015 18:21> Насчёт 2: может быть, «мощь» tbbmalloc и впрямь велика, но насколько часто она действительно нужна? Стоит ли она того, чтобы за неё платить в описанной ситуации (прим: использовал прив. код в комм. софте)?
За TBB нужно платить только если нужна поддержка.
Наличие runtime exception позволяет использовать opensource версию TBB даже в коммерческих проектах с закрытым кодом.
RPG18
Отмечу Thread-Caching Malloc, jemalloc.
encyclopedist
А они под Windows работают?
RPG18
tcmalloc из коробки поддерживает Windows, для jemalloc jemalloc-win32
Googolplex
+1 к jemalloc. Например, он вполне успешно используется в качестве дефолтного аллокатора в языке Rust, на всех платформах вплоть до Windows XP.