Windows принято не любить. Однако, зачастую, фраза: «Книгу писателя не читал, но осуждаю» очень хорошо описывает эту ситуацию. Несмотря на укоренившееся презрение к «Винде», отдельные вещи в ней реализованы весьма удачно, и именно об одной из них мы хотели бы написать. Отдельные фрагменты WinAPI, хотя и были реализованы достаточно давно, по разным причинам, и часто незаслуженно, выпали из поля зрения широкой аудитории.
В этой статье речь пойдёт о встроенной в ОС реализации lock-free стека и сравнении его производительности с кросс-платформенными аналогами.
Итак, уже довольно давно в WinAPI есть реализация неблокирующего стека на основе односвязного списка (Interlocked Singly Linked Lists), который сокращенно называют SList. Реализованы операции инициализации такого списка и стековые примитивы над ним. Не вдаваясь в подробности реализации своих SList, Майкрософт лишь указывает, что использует некий неблокирующий алгоритм для реализации атомарной синхронизации, увеличения производительности и проблем с блокировками.
Неблокирующие односвязные списки можно реализовать самостоятельно, и об этом, в частности, уже много и подробно писал Максим Хижинский ( khizmax) в своем монументальном цикле статей о lock-free алгоритмах на Хабре. Однако до Windows 8 не существовало 128-битной операции CAS, что иногда создавало проблемы при реализации подобных алгоритмов в 64-битных приложениях. Slist, таким образом, помогает решать эту задачу.
Реализация
К особенностям реализации SList стоит отнести требование выравнивания памяти для элементов списка по границе MEMORY_ALLOCATION_ALIGNMENT. Впрочем, схожие требования предъявляются и при прочих interlocked операциях в WinAPI. Для нас это означает необходимость использовать aligned_malloc/aligned_free при работе с памятью элементов списка.
Другой особенностью является требование, чтобы указатель на следующий элемент списка типа SLIST_ENTRY располагался в самом начале структуры: до наших собственных полей.
Ниже приводится реализация шаблона на C++, оборачивающего нативные функции WinAPI для работы с SList:
Код шаблона C++
template<typename T>
class SList
{
public:
SList()
{
// Let Windows initialize an SList head
m_stack_head = (PSLIST_HEADER)_aligned_malloc(sizeof(SLIST_HEADER),
MEMORY_ALLOCATION_ALIGNMENT);
InitializeSListHead(m_stack_head); //UPD: 22.05.2014, thx to @gridem
}
~SList()
{
clear();
_aligned_free(m_stack_head);
}
bool push(const T& obj)
{
// Allocate an SList node
node* pNode = alloc_node();
if (!pNode)
return false;
// Call the object's copy constructor
init_obj(&pNode->m_obj, obj);
// Push the node into the stack
InterlockedPushEntrySList(m_stack_head, &pNode->m_slist_entry);
return true;
}
bool pop(T& obj)
{
// Pop an SList node from the stack
node* pNode = (node*)InterlockedPopEntrySList(m_stack_head);
if (!pNode)
return false;
// Retrieve the node's data
obj = pNode->m_obj;
// Call the destructor
free_obj(&pNode->m_obj);
// Free the node's memory
free_node(pNode);
return true;
}
void clear()
{
for (;;)
{
// Pop every SList node from the stack
node* pNode = (node*)InterlockedPopEntrySList(m_stack_head);
if (!pNode)
break;
// Call the destructor
free_obj(&pNode->m_obj);
// Free the node's memory
free_node(pNode);
}
}
private:
PSLIST_HEADER m_stack_head;
struct node
{
// The SList entry must be the first field
SLIST_ENTRY m_slist_entry;
// User type follows
T m_obj;
};
node* alloc_node()
{
return (node*)_aligned_malloc(sizeof(node), MEMORY_ALLOCATION_ALIGNMENT);
}
void free_node(node* pNode)
{
_aligned_free(pNode);
}
T* init_obj(T* p, const T& init)
{
return new (static_cast<void*>(p)) T(init);
}
void free_obj(T* p)
{
p->~T();
}
};
Тест производительности
Для проверки алгоритма использовался стандартный тест с «производителями» и «потребителями». Однако дополнительно на каждом прогоне теста мы варьировали число потоков типа consumer и типа producer. При этом менялось и общее количество заданий, так как каждый «производитель» по условиям теста всегда производит одно и то же число заданий (iterations) равное 1 миллиону, в данном случае. Таким образом, при числе потоков типа producer равному N, общее количество заданий составляло N*1M.
Код теста SList
class test
{
private:
static UMS::SList<int64_t> stack;
public:
static const char* get_name() { return "MS SList"; }
static void producer(void)
{
for (int i = 0; i != iterations; ++i)
{
if (!stack.push(++producer_count))
return;
}
}
static void consumer(void)
{
int64_t value;
while (WaitForSingleObject(hEvtDone, 10) != WAIT_OBJECT_0)
{
while (stack.pop(value))
{
++consumer_count;
}
}
while (stack.pop(value))
{
++consumer_count;
}
}
};
Для того, чтобы рабочие потоки consumer не «молотили» в холостую и не замирали в гарантированном sleep-е, мы использовали объекты синхронизации Windows типа Event, чтобы «потребители» подчищали стек уже после того, как «производители» закончили свою работу. «Потребители» стартуют одновременно с «производителями», и к тому моменту, когда «производители» останавливаются и мы активируем событие hEvtDone, они уже успевают разобрать часть заданий из стека.
Ниже показана функция, которая вызывает наш тест с необходимым числом потоков:
Так вызываем тест
template<typename T>
void run_test(int producers, // Number of producer threads
int consumers // Number of consumer threads
)
{
using namespace std;
boost::thread_group producer_threads, consumer_threads;
// Initiate a timer to measure performance
boost::timer::cpu_timer timer;
cout << T::get_name() << "\t" << producers << "\t" << consumers << "\t";
// Reset the counters after the previous test
producer_count = consumer_count = 0;
done = false;
ResetEvent(hEvtDone);
// Start all the producer threads with a given thread proc
for (int i = 0; i != producers; ++i)
producer_threads.create_thread(T::producer);
// Start all the consumer threads with a given thread proc
for (int i = 0; i != consumers; ++i)
consumer_threads.create_thread(T::consumer);
// Waiting for the producers to complete
producer_threads.join_all();
done = true;
SetEvent(hEvtDone);
// Waiting for the consumers to complete
consumer_threads.join_all();
// Report the time of execution
auto nanoseconds = boost::chrono::nanoseconds(timer.elapsed().user + timer.elapsed().system);
auto seconds = boost::chrono::duration_cast<boost::chrono::milliseconds>(nanoseconds);
auto time_per_item = nanoseconds.count() / producer_count;
cout << time_per_item << "\t" << seconds.count() << endl;
}
Тест запускался в следующих условиях:
- OS: Windows 8 64-bit
- CPU: 4x Intel Core i7-3667U @ 2.00GHz
- RAM: 8GB
- Компилятор: Microsoft C/C++ Optimizing Compiler Version 18.00.21005.1
- Конфигурация: Release, Static Runtime(/MT), Optimize Speed (/Ox), x64 Architecture
- boost: версия 1.55
- libcds: версия 1.5.0
Вариации параметров по двум измерениям (consumers, producers) дают нам функцию t(p, c), чей график приведен на изображении слева.
Для того, чтобы не пришлось глазами считать число нулей в результатах, вместо подсчёта числа заданий в секунду, мы приводим время на выполнение одного задания в наносекундах, посчитанное как общее время теста, деленное на общее число заданий. Чем ниже эта величина, тем быстрее работает алгоритм.
Число потоков каждого типа менялось по последовательности:
int NumThreads[] = { 2, 4, 8, 12, 16, 20, 24, 32, 36, 48, 56, 64, 72 };Обратим внимание на эту поверхность. Заметно серьезное ускорение алгоритма при малом числе потребителей (область графика, окрашенная зеленым цветом). Дальнейшее наращивание числа потоков обоих типов не приводит к заметному изменению скорости работы, хотя видно, что показатель несколько «плавает» в узком коридоре, но график сохраняет успокаивающий оранжевый тон.
Если рассмотреть тот же график в другом исполнении, эта граница видна еще отчетливее. На изображении справа весьма чётко различима благодатная зелено-голубая полоса, отмечающая весь регион с четырьмя «потребителями» и произвольным числом «производителей», что, кстати, совпадает с числом ядер в эксперименте. Далее будет показано, что остальные реализации демонстрируют схожую динамику. Это наталкивает на мысль о схожести алгоритма, использованного Майкрософт, с тем, что применяется в сторонних библиотеках.
Отрадно видеть, что lock-free подход блистает здесь во всей красе: сложно представить 72(+72) потока, с 1млн заданий каждый, висящие в lock-е. Впрочем, с этого обычно начинаются статьи о lock-free
Сравнение
Идентичный тест запускался на том же компьютере и для двух других реализаций неблокирующих контейнеров, взятых из известных библиотек (boost::lockfree и libcds) в следующем цикле:
int NumThreads[] = { 2, 4, 8, 12, 16, 20, 24, 32, 36, 48, 56, 64, 72 };
for (int p : NumThreads)
for (int c : NumThreads)
{
run_test<lf::boost::test>(p, c);
run_test<lf::slist::test>(p, c);
run_test<lf::libcds::test>(p, c);
}
Несмотря на некоторую схожесть реализаций, ниже приводятся тесты, исполненные для этих библиотек и результаты работы каждой из них.
Библиотека Boost.Lockfree
Эта библиотека вошла в состав boost сравнительно недавно. В её составе реализованы три контейнера: очередь, стек и кольцевой буфер. Пользоваться их классами, как всегда удобно. Есть документация и, даже, примеры.
Ниже приводится код для аналогичного теста, использующего boost::stack.
Тест boost
class test
{
private:
static ::boost::lockfree::stack<int64_t> stack;
public:
static const char* get_name() { return "boost::lockfree"; }
static void producer(void)
{
for (int i = 0; i != iterations; ++i)
{
while (!stack.push(++producer_count));
}
}
static void consumer(void)
{
int64_t value;
while (WaitForSingleObject(hEvtDone, 10)!=WAIT_OBJECT_0)
{
while (stack.pop(value))
{
++consumer_count;
}
}
while (stack.pop(value))
{
++consumer_count;
}
}
};
Приводим результаты данного теста в виде графиков:
Библиотека libcds
На эту библиотеку часто ссылается khizmax в своих статьях. Вне зависимости от своих потребительских качеств, она показалось нам несколько громоздкой и плохо документированной (больше всего информации удалось почерпнуть здесь, на Хабре). Кроме того, в каждом потоке, где используются их lock-free контейнеры, требуется выполнять attach своего потока к их «движку» (вероятно, из-за TLS?), потом делать его detach и еще необходимо где-то инициализировать Hazard Pointer синглтон.
Несмотря на немыслимое количество реализованных lock-free контейнеров, на любой вкус, эту библиотеку сложно назвать красивой — к ней нужно привыкать.
Ниже приводится код для аналогичного теста, использующего cds::container::TreiberStack:
Тест libcds
class xxxstack : public cds::container::TreiberStack<cds::gc::HP, int64_t>
{
public:
cds::gc::HP hzpGC;
xxxstack()
{
cds::Initialize(0);
}
};
class test
{
private:
static xxxstack stack;
public:
static const char* get_name() { return "libcds tb"; }
static void producer(void)
{
// Attach the thread to libcds infrastructure
cds::threading::Manager::attachThread();
for (int i = 0; i != iterations; ++i)
{
//int value = ++producer_count;
while (!stack.push(++producer_count));
}
// Detach thread when terminating
cds::threading::Manager::detachThread();
}
static void consumer(void)
{
// Attach the thread to libcds infrastructure
cds::threading::Manager::attachThread();
int64_t value;
while (WaitForSingleObject(hEvtDone, 10) != WAIT_OBJECT_0)
{
while (stack.pop(value))
{
++consumer_count;
}
}
while (stack.pop(value))
{
++consumer_count;
}
// Detach thread when terminating
cds::threading::Manager::detachThread();
}
};
Приводим результаты данного теста в виде графиков:
Сравнение производительности
Несмотря на то, что SList — нативное решение, а два остальных — «почти» кросс платформенные, мы считаем, что приводимое нами ниже сравнение правомочно, так как все тесты были проведены в одинаковых условиях и демонстрируют поведение библиотек в этих условиях.
В связи с линейным ростом числа заданий в тесте по мере роста числа потоков, полное выполнение всех вариантов занимает приличное время. Для стабилизации результата было выполнено три прохода, так что представленные вам выше результаты есть усреднение между тремя запусками.
По приведённым выше трехмерным графикам заметно, что диагональ (значения аргументов {p=c}) выглядит почти прямой линией, поэтому для наглядного сравнения трех библиотек мы сделали выборку результатов именно по этому критерию.
Слева показано то, что у нас получилось.
Видно, что boost проигрывает двум остальным реализациям, хотя и демонстрирует большую устойчивость к изменению входных параметров.
Реализации на libcds и SList отличаются не так значительно, но на всем протяжении входного интервала.
Выводы
Необходимо признать, что в этот раз Майкрософт создала весьма неплохую реализацию (хотя и всего одного контейнера), которая может с успехом соревноваться с алгоритмами из известных библиотек. Несмотря на то, что описанная реализация не является кросс-платформенной, она может оказаться полезной разработчикам Windows приложений.
Скачать архив с исходным кодом проекта Visual Studio можно здесь
Использованные материалы
Картинка в начале статьи
MSDN описание slist
Библиотека boost.lockfree
Библиотека libcds
Lock-free структуры данных. Эволюция стека
Информация о деталях реализации SList
UPD:
По просьбе mickey99 мы провели еще один тест: на этот раз был взять обыкновенный std::stack, доступ к которому закрывал грудью обычный std::mutex.
Тест mutex
class test
{
private:
static std::stack<int64_t> stack;
static std::mutex lock;
public:
static const char* get_name() { return "mutex"; }
static void producer(void)
{
for (int i = 0; i != iterations; ++i)
{
lock.lock();
stack.push(++producer_count);
lock.unlock();
}
}
static void consumer(void)
{
int64_t value;
while (WaitForSingleObject(hEvtDone, 10) != WAIT_OBJECT_0)
{
lock.lock();
if (!stack.empty())
{
value = stack.top();
stack.pop();
++consumer_count;
}
lock.unlock();
}
bool isEmpty = false;
while (!isEmpty)
{
lock.lock();
if (!(isEmpty = stack.empty()))
{
value = stack.top();
stack.pop();
++consumer_count;
}
lock.unlock();
}
}
};
Скажем сразу: ждать пришлось долго, очень долго. Тогда было снижено число заданий на поток с 1 млн до 100К, что, конечно, привело к не таким точным результатам (это наверное и не требуется с такими числами), а также был изменен набор для числа входных потоков, чтобы было меньше точек для расчета:
int NumThreads[] = { 2, 4, 8, 16, 32, 64};Вот результаты:
Результат весьма показателен: уже при наличии свыше 4 потоков любого типа, напряжение драматически возрастает, на порядки. Такую линию сложно вывести на график к первым трём. Наверное нагляднее будет с логарифмической шкалой.
