Постановка задачи
Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:
- Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
- Объекты представляли собой POD- типы.
PODA Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type.
- Заранее было неизвестно какое количество объектов понадобится, могло так случится, что потребуется сотня, а может и сто миллионов.
- Объекты никогда не удаляются по одному, в какой-то момент они становятся не нужны все сразу.
- Алгоритм хорошо распараллеливается, по этому выделением объектов занимается одновременно несколько потоков, по количеству ядер процессора(ов).
Использование в таких условиях стандартного new – delete приводит к очень большим потерям времени на удаление объектов. Если без отладчика удаление происходило хотя бы за несколько секунд, то в присутствии отладчика освобождение памяти замедляется примерно в 100(!) раз, и отладка проекта становится просто невозможной. Кроме того из-за большого количества выделенных объектов достаточно ощутимым становился перерасход памяти на внутренние данные расперделителя памяти.
Для решения задачи выделения огромного количества объектов одного типа, и их пакетного удаления, был сделан lock-free контейнер MassAllocator. Код компилируется Visual Studio 2012. Полный код проекта выложен на github.
Дополнительные особенности
В моем случае объекты могли ссылаться друг на друга, и для экономии памяти был придуман небольшой хак: вместо указателя сохраняется номер объекта, а сам объект получается запросом к хранилищу. Количество объектов гарантированно меньше четырех миллиардов, поэтому использовался 32 битный индекс вместо 64 битного указателя, что дает экономию 4 байта. Так мне удалось примерно на 12 % снизить потребление памяти.
Приятным бонусом оказалось, что к хранилищу легко можно сделать итераторы, чтобы применять алгоритмы стандартной библиотеки, например std::sort.
Реализация
Идея заключается в последовательном выделении элементов блоками. Стандартным malloc выделяется блок памяти, который логически представляется в виде массива элементов. На каждый запрос пользователя о выделении элемента ему возвращается указатель на следующий элемент массива, и счетчик выделенных элементов инкрементируется. Когда все элементы из массива будут выделены, запрашивается следующий блок памяти, и т.д. Освобождение памяти происходит очень быстро, всего лишь происходит освобождение всех выделенных блоков, без каких-либо вызовов деструкторов для элементов.
Все блоки имеют одинаковый размер, таким образом получается очень легко обратится к элементу по сквозному номеру:
template <typename T>
typename MassAllocator<T>::reference MassAllocator<T>::operator[](size_type index)
{
size_t indexOfBlock = index / elementsInBlockCount_;
size_t indexInBlock = index % elementsInBlockCount_;
return blocks_[indexOfBlock][indexInBlock];
}
Выделение нового элемента
Итак, все элементы последовательно располагаются в блоках. Распределение нового элемента выглядит очень просто: нужно увеличить счетчик выделенных элементов, убедится, что место в текущем блоке, из которого ведется распределение элементов, не кончилось, и если потребуется, то выделить новый блок. Конечно же, счетчик, инкрементируемый из разных потоков, должен быть реализован через атомарную переменную std::atomic, а сам алгоритм должен быть lock-free!
Атомарный счетчик последовательно выдает индексы, и все замечательно до тех пор, пока в блоке есть место. Но вот блок заканчивается, и необходимо выделить новый. Выделять блок должен какой-то один поток, а остальные на это время должны приостановиться и возобновить работу после выделения блока. С помощью одного атомарного счетчика мне удалось реализовать такую логику с одним допущением: время выделения блока памяти должно быть достаточно мало, чтобы оставшиеся потоки не смогли переполнить 32 битный счетчик в холостом цикле ожидания. Для синхронизации доступа использована 64 битная атомарная переменная, которая логически разделена на 2 части: младшие 32 бита — это счетчик элемента внутри блока, а старшие 32 бита — это счетчик выделенных блоков памяти. В каждом блоке памяти распределяется одинаковое количество элементов, например 100000. После инкрементирования счетчика может возникнуть три различных ситуации для счетчика элемента в блоке:
- Было получено число от 1 до 99999. Это ситуация означает, что места в блоке хватает, и мы зарезервировали элемент с полученным номером.
- Был получен индекс, совпадающий с размером блока – 100000. Означает что потоку «повезло», и именно на нем закончился блок. В этом случае требуется выделить новый блок памяти, забрать из него нулевой элемент себе, инкрементировать старший счетчик блоков, установить младший счетчик на первый свободный элемент – 1, и записать новое значение в атомарную переменную.
- Был получен индекс с номером больше чем размер блока. Это означает что, в данный момент какой-то из потоков производит выделение памяти, а мы вынуждены ждать, пока он не выставит младший счетчик в значение 1. В этом случае торопиться не стоит, и можно отдавать процессорное время другим потокам вызовом
std::this_thread::yield();
Сначала я пытался сделать реализацию на двух 32битных счетчиках, но в этом случае возникает эффект гонки. Например, первым делается запрос индекса в блоке, а затем номер блока.
// так делать нельзя!
uint32_t itemIndex = atomicIndex++;
uint32_t blockIndx = atomicBlock.load();
Может случиться так, что поток получил валидный индекс элемента itemIndex, но до момента получения индекса блока blockIndx планировщик потоков усыпил его, а за время сна другим потоком был выделен новый блок, тогда по пробуждении поток получит индекс не того блока, где был зарезервирован элемент. По этому, и индекс элемента, и индекс блока должны получаться атомарно либо в критической секции, либо через одну атомарную переменную.
Код выделения элемента имеет особенность в том, что одновременно с указателем на выделенный элемент может возвращаться индекс этого элемента, а обращение к верхней и нижней части 64 битного целого организуется через union, а не битовую арифметику.
template <typename T>
typename MassAllocator<T>::pointer MassAllocator<T>::createElement(size_type *returningIndex)
{
//Делаем union для доступа к старшим и младшим 32 битам 64 битного целого
union {
uint64_t index;
struct HiLoParts {
uint32_t itemIndex;
uint32_t blockIndx;
} parts;
};
//получаем новый полный индекс
index = curAtomicIndex_++;
//если индекс элемента в блоке входит в допустимые пределы, то мы быстренько возвращаем индекс и указатель выделенного элемента
if(parts.itemIndex < elementsInBlockCount_)
{
if (returningIndex != nullptr)
*returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex;
return &(blocks_[parts.blockIndx][parts.itemIndex]);
}
if (parts.itemIndex == elementsInBlockCount_)
{
//на нас закончился блок и именно нашему потоку нужно выделить еще один блок памяти
auto bufferSize = elementsInBlockCount_ * sizeof(T);
T* buffer = (T*)malloc(bufferSize);
memset(buffer, 0, bufferSize);
blocks_.push_back(buffer);
//мы забираем себе нулевой элемент в блоке
parts.blockIndx = (unsigned int)(blocks_.size() - 1);
parts.itemIndex = 0;
if (returningIndex != nullptr)
*returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex;
//устанавливаем счетчик на первый элемент в блоке
setIndex(parts.blockIndx, 1);
return &(blocks_[parts.blockIndx][parts.itemIndex]);
}
//ждем, пока другой поток производит выделение нового блока
while(true)
{
//получаем новый полный индекс
index = curAtomicIndex_++;
if (parts.itemIndex == 0xffffffff)
//мы крутили цикл ожидания настолько долго, что произошло переполнение
throw std::string("Atomic index overflow");
if (parts.itemIndex >= elementsInBlockCount_)
{
//блок еще не выделен, продолжаем ожидание
std::this_thread::yield();
continue;
}
//блок был выделен другим потоком, мы захватили валидный индекс элемента из нового блока
if (returningIndex != nullptr)
*returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex;
return &(blocks_[parts.blockIndx][parts.itemIndex]);
}
}
Производительность
Под платформу x64 выделение 80 миллионов элементов в 8 потоках с помощью MassAllocator выполняется на i5 2500K примерно за 2000 мс, освобождение за 70 мс. Выделение с помощью new происходит примерно за 1350 мс, а вот удаление через delete выполняется за целых 17400 мс! Под отладчиком, даже если проект собран в релизной конфигурации, я так ни разу и не смог дождаться завершения теста.
Для тестирования на платформе x86 пришлось уменьшить количество выделяемых объектов вдвое, так как new-delete имеет большие накладные расходы и адресного пространства не хватает для 80 миллионов объектов. 40 миллионов объектов выделяются MassAllocator’ом за 2400 мс, освобождаются за 35 мс, тогда как new выполняет свою работу за 750 мс, а delete за 6430 мс.
Как и ожидалось, профилирование показывает узкое место – инкрементирование атомарного счетчика, особенно под x86. Каких-то радикальных идей по ускорению этого фрагмента у меня пока нет.
Заключение
Lock-free алгоритмы это новая область для меня, потому буду рад выслушать соображения относительно корректности алгоритма и/или предложения по ускорению кода.
Автор: drBasic
