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:

    Код шаблона 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 потоков любого типа, напряжение драматически возрастает, на порядки. Такую линию сложно вывести на график к первым трём. Наверное нагляднее будет с логарифмической шкалой.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 44

      0
      Спасибо, это интересно.
      В чём диаграммки делали?
        +2
        Да, это была целая история…
        Одно барахло везде попадалось. В итоге, поставили DataScene
          +2
          Спасибо. Пара замечаний:
          1. Похоже, вы забыли голову (m_stack_head) выровнять.
          2. Если тело функции внутри объявления класса идет, такие функции по умолчанию считаются inline. C++STD 2012, 7.1.2: A function defined within a class definition is an inline function.
            +2
            Спасибо за ваши замечания — исправлено по обоим пунктам.
            0
            А как связано наличие 128bit CAS и Windows 8? В x86_64 всегда вроде инструкция CMPXCHG16B была… Берется да вызывается.
              0
              Наверное, криво написано в статье…
              Связаны эти вещи всего лишь, потому что в WinAPI функция InterlockedCompare64Exchange128 пришла начиная с Windows 8, а так на ассемблере может и всегда можно было.
                +4
                Отвечу отчасти сам себе. В первых 64bit камнях AMD этой инструкции как оказалось небыло. А начиная с Win 8 Windows требует ее поддержку и предоставляет API.
              +1
              Было бы странно, если бы в продуктам M$ не встречалось удачных кусков. У них задача даже проще, чем у разработчиков кроссплатформенных продуктов, которым нужно учитывать особенности всех поддерживаемых систем, т.к. разрабатывают под вполне известное окружение с некоторой долей разнообразия (версии Windows в смысле).
              Кстати, отличный момент для доказательства себе своей крутости :) Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево
                +2
                В проектах с хорошим governance — это довольно просто. Например, в openstack есть чёткая процедура как из «постороннего человека» оказаться в самой мякотке. На всю бюрократию надо минут 15-20, ещё примерно пол-часа час на изучение git review и других фрагментов gerrit'а. После этого можно предлагать блюпринты, писать патчи, фиксить баги и т.д. И оно войдёт в проект правильно, с автоматическим гигантским тестированием, проверкой совместимости с кодом разных вендоров и разных конфигураций, и без каких-либо «ну я тут покодил вот мой патч как он там у вас будет я не знаю, но примите пожалуйста».
                  0
                  Речь же не о бюрократической сложности, а о сложности по разработке решения работающего одинавого хорошо под всеми возможными платформами.
                    +1
                    Я отвечал на тезис «Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево „
                  0
                  Не могу не заметить, что «продукты MS» и «кроссплатформенные продукты» — это несколько пересекающиеся множества. Особенно в последнее время.
                    0
                    Часто проблемы с переносом на Windows бывают, например, c pthread. Хотя есть пару реализаций под WinAPI, но выглядят они как-то не очень.
                    А так, некоторые вещи из posix поддерживаются в VS SDK, поэтому малая часть проблем с переносом уходит. Вот здесь у них, например, гид по переносу на Win32

                    А вообще, то что называется кросс-платформенным решением часто не является таковым в полной мере, потому что именно Windows и не поддерживается… И не потому что это невозможно портировать. Так что, скорее, это правильно называть кросс-nix-овые продукты.

                    А вот многие вещи от Гугла или тот же SQLite, как раз, в большей степени кросс-платформенные: собираются на чём хочешь.
                  +1
                  Не совсем понятно, зачем дожидаться, пока продьюсеры закончат свою работу? Как раз интересно посмотреть в сценарии, когда молотят одновременно и продьюсеры, и консьюмеры, т.е. когда конкурентность одновременно и на push, и на pop операциях. Именно такие сценарии представляют наибольший интерес, т.к. они встречаются наиболее часто в реальности.
                    +1
                    Нужен критерий остановки для потребителей. Само по себе отсутствие заданий в стеке не означает, что их больше не будет, т.к. вероятно какие-то производители просто запаздывают и положат задания позднее. Поэтому сначала мы ждем пока все производители отработают и до тех пор честно пробуем найти еще задания в стеке, а вот когда они закончили работу, тогда пустой стек можно считать концом.
                      0
                      Критерий очень простой: локальный счетчик количества извлеченных элементов ==iterations (в случае, когда n_producers == n_consumers). Более того, приведенный тест не гарантирует, что все элементы будут извлечены: возможно ситуация, когда евент сработал, и элементов к тому времени уже нет.
                        0
                        Если возникает «ситуация, когда евент сработал, и элементов к тому времени уже нет.», то ничего страшного не будет — это значит, что consumer-ы уже всё разобрали и условие во втором цикле consumer «while (stack.pop(value))» нас тут же выбросит на конец потока. На самом деле, это как раз неплохой сценарий: в том смысле что consumer-ы быстро справились и не надо чистить
                          0
                          Либо другой вариант: консьюмеры отработали не весь список, но он стал пустым, а продьюсеры еще молотят данные. В таком случае консьюмеры закончат работу, а продьюсеры — нет.
                            0
                            А это невозможно, потому что hEvtDone ставится после выхода их блокирующего вызова producer_threads.join_all() в методе run_test. Это гарантирует окончание работы всех производителей до того, как consumer-ы пройдут Wait на событии и приступят к своим вторым циклам по чистке стека.
                          0
                          Кажется, что предложенный вами критерий «локальный счетчик количества извлеченных элементов ==iterations» насильственно закрепощает потоки потребители обрабатывать ровно столько заданий, сколько вбросил побратим-производитель в случае p=c, а если p!=c, то это вообще неверно. Так выходит?

                          И, кроме того, дело-то в том, что исходно обсчитывался квадрат {p X c}, где p почти везде не равно c, так что случай p=c, как бы вырожденный.
                            0
                            Ну вот количество итераций для продьюсера вас не смущают, а вот для консьюмера внезапно стало смущать. Не очень понятно.

                            Ну и проблема в вырожденности легко снимается, когда количество итераций для консьюмера = iterations * n_producers / n_consumers (можно сделать, чтобы всегда делилось нацело без остатка, но это не важно).
                              0
                              Тогда каждый поток должен знать об общем количестве потоков каждого типа, значит ему это нужно давать в аргументе. Это меняет структуру организации worker потоков. Лучше ли это?

                              И главное для чего? Избежать 1 Wait-а на поток? Общее заданий >>>> числа потоков и один wait на поток ничего не стоит, потому что мы можем потерять на нём 1 раз 10 мс, и то без нагрузки на CPU — это же не sleep…
                                0
                                Как я указывал выше, цель — чтобы продьюсеры и консьюмеры работали параллельно. Здесь же в тестах они работают последовательно, сначала отрабатывают продьюсеры, а потом — консьюмеры. Т.е. нет замеров именно конкурентного доступа к данным, когда есть и те и другие. Конечно, частично они будут пересекаться, но непонятно насколько частично и как это сказывается на производительности. Поэтому хотелось бы видеть одновременное действие producers/consumers в разных пропорциях.
                                  0
                                  Это совсем не верно. Посмотрите, пожалуйста, на код функции run_test.

                                  1. Стартуют все производители и начинают накидывать задания
                                  2. Стартуют все потребители и уже начинают потреблять задания
                                  3. Ждем окончания работы производителей
                                  4. Ждем окончания работы работы потребителей

                                  Задержка между (1) и (2) только на время запуска (!) потоков, но никак не их работу. Лучше бы было только стартовать каждый из типов попеременно, но это не даст никакой заметной разницы.
                                    0
                                    Не совсем так. Потребители во втором пункте, конечно, стартуют, но вторая часть этого пункта не совсем корректна. Они начинают потреблять только после того, как пройдет 10 мс, либо после того, как выполнится 3-я часть. При этом мне неочевидно, что пересечение между началом работы потребления и началом реальной работы производителей является существенным вкладом в общее время работы. Возможно, я чего-то упустил.
                                      0
                                      А, вот, насчет 10 мс рассогласования на старте вы совершенно правы, и об этом мы написали чуть выше. Можно было бы избежать этого, например, изменив внешний цикл на do-while, чтобы потребители сразу пробовали брать задания.

                                      Однако, этот фрагмент кода, касается лишь самого теста. Нигде в тексте статьи мы не апеллируем к абсолютным числам по тестам. Проводится лишь сравнение реализаций. А поскольку каждый из 3(4) тестов имеет эти 10 мс, и время работы 1 теста составляет ~10-40 секунд, то они в этом плане абсолютно сравнимы и отмена 10мс не изменит соотношения.
                                        0
                                        Если время составляет 10-40 секунд, то в таком случае, безусловно, этой паузой можно пренебречь.
                      +2
                      Спасибо, интересно.

                      А нельзя ли для масштаба добавить к трём lock-free стэкам ещё и простейший стэк с блокировкой (CriticalSection или mutex)?
                        0
                        Ответ добавили в конец статьи.
                          0
                          Спасибо
                            0
                            Судя по графику, на 2 и 4 потоках mutex обгоняет?
                              0
                              Вроде бы нет… вот результаты в сыром виде (но надо иметь в виду, что было только по 100К заданий и один проход, так что числа грубые):

                              Сырые числа
                              mutex   2       2       937  
                              mutex   2       4       1250 
                              mutex   2       8       43203
                              mutex   2       16      42421
                              mutex   2       32      36796
                              mutex   2       64      42812
                              mutex   4       2       1250 
                              mutex   4       4       1523 
                              mutex   4       8       43046
                              mutex   4       16      24921
                              mutex   4       32      38984
                              mutex   4       64      33789
                              mutex   8       2       41757
                              mutex   8       4       43125
                              mutex   8       8       74589
                              mutex   8       16      84453
                              mutex   8       32      82656
                              mutex   8       64      84746
                              mutex   16      2       42177
                              mutex   16      4       42333
                              mutex   16      8       82900
                              mutex   16      16      84736
                              mutex   16      32      85175
                              mutex   16      64      85458
                              mutex   32      2       43120
                              mutex   32      4       43554
                              mutex   32      8       85083
                              mutex   32      16      84453
                              mutex   32      32      84531
                              mutex   32      64      85634
                              mutex   64      2       43215
                              mutex   64      4       43437
                              mutex   64      8       84768
                              mutex   64      16      85146
                              mutex   64      32      85366
                              mutex   64      64      85651
                              
                              0
                              Мьютекс имеет смысл использовать только в случае небольшого числа потоков. Поэтому было бы интересно увидеть сравнительный график вблизи единицы, скажем 1, 2, 4. Результат может удивить.
                                0
                                Результаты работы теста c mutex при малом числе потоков действительно удивляют: даже на этих грубых числах уже видно, что числа с mutex, как минимум сравнимы, а то и меньше, чем у lock-free.
                            +2
                            Спасибо за хорошую статью и проведенную работу по сравнительному анализу! Независимые данные всегда особо ценны, в том числе и критика. Как автор libcds, постараюсь в одной из следующих статей своего эпического цикла объяснить, как появился интерфейс контейнеров в libcds, — это может быть интересно. Быть может, хабрасообщество подскажет более красивое решение тех проблем, с которыми я столкнулся при разработке библиотеки.
                            По поводу майкрософтовского SList. Я несколько лет назад где-то на просторах сети находил внутреннее устройство, — довольно интересно: если мне не изменяет память, они борются с ABA-проблемой с помощью SEH (structured exception handling). Грубо говоря, если получаем SEGFAULT, аккуратно обрабатываем его на очень низком уовне. К сожалению, пруф я сейчас найти не смог.
                            И по поводу Microsoft вообще, присоединюсь, покидаю на вентилятор: я считаю, что существование Windows — это большая удача для кросс-платформенных разработчиков, ибо ставит нетривиальные задачи по обобщению *nix и Windows подхода при кросс-платформенной разработке. Да, колемся, плачем, но продолжаем решать нестандартные задачи по унификации столь разных API столь разных операционных систем и компиляторов
                              +1
                              Да, чуда не произошло.

                              Я тут вечерком протестировал приведенную реализацию на предмет ABA проблемы, и оказалось, что она таки присутствует. Чтобы в этом убедиться, достаточно переписать тест на использование в качестве T=std::function<void()>, на push операцию добавлять []{}, на pop: вызывать соответствующий функтор. Практически сразу программа падает, что говорит о том, что имеется серьезная проблема, которая как раз и связана с ABA при удалении ресурса. Внутри реализации используется 8-байтовый CAS (на x86 архитектуре), который просто не в состоянии решить проблему корректного удаления объекта. Увы.

                              Не ожидал такого подвоха в библиотечной функции от Microsoft, честно говоря.
                                0
                                Не могли бы вы показать конкретнее?

                                У нас вот в таком случае:
                                UMS::SList<std::function<void()>> stack;
                                ...
                                stack.push([]{}) // producer
                                ...
                                stack.pop(value) // consumer
                                value()          //
                                


                                ничего не падает
                                  0
                                  У меня несколько другой тест. Не падает скорее всего из-за того, что есть небольшая пауза между производителями и потребителями. Поэтому можно просто убрать ожидание на событии, и сделать бесконечный цикл с pop:

                                  while (true)
                                  {
                                      std::function<void()> f;
                                      while (!tasks.pop(f));
                                      f();
                                  }
                                  

                                  И желательно потребителей запускать до производителей.
                                    0
                                    Да, и еще одно замечание. Количество производителей стоит сделать = 1, а потребителей = числу ядер. Тогда вероятность ситуации сильно возрастет.
                                      0
                                      Мы, вот, всё пытаемся воспроизвести ваш сценарий — пока безуспешно… но попутно кое-что заметили плохое ))

                                      После замечаний от lek, из конструктора шаблона, который здесь на странице пропал вызов InitializeSListHead, в архиве с изначальной версией такой проблемы нет. А отсутствие инициализации головы, как раз, приводит к падению на пустом стеке. (Сейчас исправили здесь в статье)

                                      Вы какой версией пользовались?
                                        0
                                        Да, действительно, если добавить эту строчку, то все становится отлично. По крайней мере, сейчас у меня тоже не падает )
                                          0
                                          Извините за этот наш косяк…
                                          Сначала всё было нормально, но потом поспешили исправить то, о чем говорил lek, и насмешили накосячили.
                                          Спасибо за вашу внимательность.
                                            0
                                            Хотелось бы понять, как MS удалось это реализовать. Работает действительно быстро. Проблем сходу не видно.
                                              0
                                              Вот здесь написано отчасти про их внутреннее устройство и про решение ABA проблемы, кстати тоже. Только вот момент насчёт выигранных четырех бит, как-то не до конца понятен…

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое