Lock-free стек для Windows

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:

	template<typename T>
	class SList
	{
	public:
		inline SList()
		{
			// Let Windows initialize an SList head
			InitializeSListHead(&m_stack_head);
		}
		inline ~SList()
		{
			clear();
		}
		inline 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;
		}
		inline 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;
		}
		inline 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:
		SLIST_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;
		};
		inline node* alloc_node()
		{
			return (node*)_aligned_malloc(sizeof(node), MEMORY_ALLOCATION_ALIGNMENT);
		}
		inline void free_node(node* pNode)
		{
			_aligned_free(pNode);
		}
		inline T* init_obj(T* p, const T& init)
		{
			return new (static_cast<void*>(p)) T(init);
		}
		inline void free_obj(T* p)
		{
			p->~T();
		}
	};

Тест производительности

Для проверки алгоритма использовался стандартный тест с «производителями» и «потребителями». Однако дополнительно на каждом прогоне теста мы варьировали число потоков типа consumer и типа producer. При этом менялось и общее количество заданий, так как каждый «производитель» по условиям теста всегда производит одно и то же число заданий (iterations) равное 1 миллиону, в данном случае. Таким образом, при числе потоков типа producer равному N, общее количество заданий составляло N*1M.

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.

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:

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 структуры данных. Эволюция стека

Автор: Vengo

Источник