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

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

Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:

• Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
• Объекты представляли собой 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 ^[1].

Дополнительные особенности

В моем случае объекты могли ссылаться друг на друга, и для экономии памяти был придуман небольшой хак: вместо указателя сохраняется номер объекта, а сам объект получается запросом к хранилищу. Количество объектов гарантированно меньше четырех миллиардов, поэтому использовался 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

Источник ^[2]