10 июня 2013

Одним махом 100 миллионов убивахом. Или lock-free распределитель памяти

ПрограммированиеC++Параллельное программирование

Постановка задачи


Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:
  • Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
  • Объекты представляли собой POD- типы.
    POD
    A 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 бита — это счетчик выделенных блоков памяти. Счетчик объявляется как:
 std::atomic<uint64_t> curAtomicIndex_ 

В каждом блоке памяти распределяется одинаковое количество элементов, например 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 алгоритмы это новая область для меня, потому буду рад выслушать соображения относительно корректности алгоритма и/или предложения по ускорению кода.

Update1


Как показало профилирование, основное время тратится на атомарный инкремент 64 битного счетчика curAtomicIndex_. В x64 это транслируется в одну ассемблерную команду lock xadd QWORD PTR, в режиме x86 транслируется в целую поэму
$again$158:
; 2424 : 	again:
; 2425 : 		mov ecx, edx;
    mov	ecx, edx
; 2426 : 		mov ebx, eax;
    mov	ebx, eax
; 2427 : 		add ebx, dword ptr _Value;
    add	ebx, DWORD PTR $T7[ebp]
; 2428 : 		adc ecx, dword ptr _Value[4];
    adc	ecx, DWORD PTR $T7[ebp+4]
; 2429 : 		lock cmpxchg8b [esi];
    lock	 cmpxchg8b QWORD PTR [esi]
; 2430 : 		jnz again;
    jne	SHORT $again$158

По этому выделение элемнта в 64битном режиме происходит значительно быстрее.
Освобождение памяти происходит быстро и в x64 и в x86.

В качестве альтернативы можно было бы использовать boost::object_pool, который подходит по идеологии, но он не многопоточен и может работать с несколькими потоками.
На замену new-delete можно попробовать boost::fast_pool_allocator, он показывает лучшую скорость чем new-delete, и в 32 битном режиме даже идет наравне в общем зачете (выделение + освобождение) с MassAlloc за счет более быстрого выделения.
По эффективности использования памяти все альтернативы уступают MassAlloc, так в 32 битном режиме ни у new-delete, ни у boost::fast_pool_allocator не хватает адресного пространства для размещения 80 миллионов объектов, тогда как MassAllocator потребляет всего 1570 МБ.
Теги:c++11lock-freeatomicthreads
Хабы: Программирование C++ Параллельное программирование
+30
13,8k 127
Комментарии 42
Лучшие публикации за сутки