[Из песочницы] Оптимизация быстродействия динамического выделения памяти в многопоточной библиотеке
Предисловие
Данная статья выросла из проблемы, которую мне относительно недавно пришлось решить: скорость кода, предназначенного для работы одновременно в нескольких потоках, резко упала после очередного расширения функционала, но только на 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 процентов). Простое решение идеально подойдёт тем, кто использует свежие версии компиляторов. Надеюсь, данная информация окажется полезной не только мне.
