Sperrfreier Stack für Windows


    Windows ist üblich, nicht zu lieben. Oft beschreibt der Satz: "Ich habe das Buch des Schriftstellers nicht gelesen, aber ich verurteile" diese Situation sehr gut. Trotz der tief verwurzelten Verachtung für Windows wurden bestimmte Dinge sehr erfolgreich darin implementiert, und wir möchten über eines davon schreiben. Einzelne Fragmente von WinAPI sind, obwohl sie schon lange implementiert sind, aus verschiedenen Gründen und oftmals unverdienterweise für ein breites Publikum außer Sichtweite geraten.
    In diesem Artikel werden wir über die Betriebssystemimplementierung des sperrfreien Stacks sprechen und seine Leistung mit plattformübergreifenden Gegenstücken vergleichen.

    Daher gibt es in WinAPI seit einiger Zeit eine Implementierung eines nicht blockierenden Stacks, der auf einer einfach verknüpften Liste ( Interlocked Singly Linked Lists) basiert), was als SList abgekürzt wird. Initialisierungsoperationen einer solchen Liste und Stapelprimitiven darüber wurden implementiert. Ohne auf die Details der Implementierung ihrer SList einzugehen, gibt Microsoft nur an, dass ein bestimmter nicht blockierender Algorithmus verwendet wird, um die atomare Synchronisation zu implementieren, die Produktivität zu steigern und Probleme zu blockieren.

    Nicht blockierende, einfach verbundene Listen können unabhängig voneinander implementiert werden, und Maxim Khizhinsky ( khizmax ) hat in seiner monumentalen Artikelserie über sperrfreie Algorithmen auf Habré ausführlich darüber geschrieben . Vor Windows 8 gab es jedoch keine 128-Bit-CAS-Operation, was manchmal zu Problemen führte, wenn ähnliche Algorithmen in 64-Bit-Anwendungen implementiert wurden. Slist hilft somit, dieses Problem zu lösen.

    Implementierung


    Zu den Besonderheiten der SList-Implementierung gehört die Anforderung der Speicherausrichtung für Listenelemente entlang der Grenze MEMORY_ALLOCATION_ALIGNMENT. Ähnliche Anforderungen gelten jedoch für andere ineinandergreifende Vorgänge in WinAPI. Für uns bedeutet dies die Notwendigkeit, align_malloc / align_free zu verwenden, wenn mit dem Speicher von Listenelementen gearbeitet wird.

    Ein weiteres Merkmal ist die Anforderung, dass sich der Zeiger auf das nächste Listenelement vom Typ SLIST_ENTRY ganz am Anfang der Struktur befindet: auf unsere eigenen Felder.

    Das Folgende ist eine Implementierung einer C ++ - Vorlage, die die nativen WinAPI-Funktionen für die Arbeit mit SList umschließt:

    C ++ - Vorlagencode
    	template
    	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(p)) T(init);
    		}
    		void free_obj(T* p)
    		{
    			p->~T();
    		}
    	};
    


    Leistungstest


    Um den Algorithmus zu testen, wurde ein Standardtest mit "Produzenten" und "Konsumenten" verwendet. Zusätzlich haben wir bei jedem Testlauf die Anzahl der Threads von Typ Consumer und Typ Producer variiert. Gleichzeitig hat sich auch die Gesamtzahl der Aufgaben geändert, da in diesem Fall jeder „Produzent“ gemäß den Testbedingungen immer die gleiche Anzahl von Aufgaben (Iterationen) erzeugt, die 1 Million entspricht. Bei einer Anzahl von Producer-Threads von N betrug die Gesamtzahl der Jobs also N * 1M.

    SList-Testcode
    class test
    {
    private:
    	static UMS::SList 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;
    		}
    	}
    };
    

    Um zu verhindern, dass Consumer-Workflows inaktiv sind und im garantierten Ruhezustand nicht einfrieren, haben wir Windows-Synchronisationsobjekte vom Typ Event verwendet, damit „Consumer“ den Stapel bereinigen, nachdem die „Hersteller“ ihre Arbeit beendet haben. „Verbraucher“ starten gleichzeitig mit „Produzenten“. Wenn „Produzenten“ aufhören und wir das Ereignis hEvtDone aktivieren, können sie bereits einige der Aufgaben aus dem Stapel analysieren.

    Nachfolgend finden Sie eine Funktion, die unseren Test mit der erforderlichen Anzahl von Threads aufruft:

    Also nennen wir den Test
    template
    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(nanoseconds);
    	auto time_per_item = nanoseconds.count() / producer_count;
    	cout << time_per_item << "\t" << seconds.count() << endl;
    }
    

    Der Test wurde unter folgenden Bedingungen durchgeführt:
    • Betriebssystem: Windows 8 64-Bit
    • CPU: 4x Intel Core i7-3667U bei 2,00 GHz
    • RAM: 8 GB
    • Compiler: Microsoft C / C ++ Optimizing Compiler Version 18.00.21005.1
    • Konfiguration: Release, Statische Laufzeit (/ MT), Geschwindigkeit optimieren (/ Ox), x64-Architektur
    • Boost: Version 1.55
    • libcds: version 1.5.0



    Variationen von Parametern in zwei Dimensionen (Verbraucher, Erzeuger) geben uns die Funktion t (p, c), deren Graph in der Abbildung links gezeigt wird.

    Um die Anzahl der Nullen in den Ergebnissen nicht mit unseren Augen zählen zu müssen, anstatt die Anzahl der Aufgaben pro Sekunde zu zählen, geben wir die Zeit, um eine Aufgabe in Nanosekunden zu erledigen, berechnet als Gesamttestzeit geteilt durch die Gesamtanzahl der Aufgaben. Je niedriger dieser Wert ist, desto schneller arbeitet der Algorithmus.

    Die Anzahl der Threads jedes Typs hat sich in der Reihenfolge geändert:
    int NumThreads[] = { 2, 4, 8, 12, 16, 20, 24, 32, 36, 48, 56, 64, 72 };


    Achten Sie auf diese Oberfläche. Deutlich schwerwiegende Beschleunigung des Algorithmus bei einer geringen Anzahl von Verbrauchern (Grundstücksfläche, grün gestrichen). Eine weitere Erhöhung der Anzahl der Flüsse beider Arten führt zu keiner merklichen Änderung der Arbeitsgeschwindigkeit, obwohl erkennbar ist, dass der Indikator in einem engen Korridor etwas „schwebt“, die Grafik jedoch einen beruhigenden Orangeton beibehält.

    Wenn wir dasselbe Diagramm in einer anderen Version betrachten, ist dieser Rand noch deutlicher sichtbar. Im Bild rechts ist der graziöse grün-blaue Streifen deutlich erkennbar. Er kennzeichnet die gesamte Region mit vier „Verbrauchern“ und einer beliebigen Anzahl von „Produzenten“, die im Übrigen mit der Anzahl der Kerne im Experiment übereinstimmen. Nachfolgend wird gezeigt, dass andere Implementierungen eine ähnliche Dynamik aufweisen. Dies weist auf die Ähnlichkeit des von Microsoft verwendeten Algorithmus mit dem in Bibliotheken von Drittanbietern verwendeten hin.

    Es ist erfreulich zu sehen, dass der schlossfreie Ansatz hier in seiner ganzen Pracht glänzt: Es ist schwer vorstellbar, dass 72 (+72) Threads mit jeweils 1 Million Aufgaben im Schloss hängen. In der Regel beginnen jedoch schlossfreie Artikel damit.

    Vergleich


    Ein identischer Test wurde auf demselben Computer für zwei andere Implementierungen von nicht blockierenden Containern aus bekannten Bibliotheken (boost :: lockfree und libcds) in der folgenden Schleife ausgeführt:

    	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(p, c);
    		run_test(p, c);
    		run_test(p, c);
    	}
    


    Trotz einiger Ähnlichkeiten bei den Implementierungen werden im Folgenden die für diese Bibliotheken durchgeführten Tests und die Ergebnisse der einzelnen Bibliotheken aufgeführt.

    Boost.Lockfree-Bibliothek


    Diese Bibliothek wurde vor relativ kurzer Zeit in Boost aufgenommen. Es besteht aus drei Containern: einer Warteschlange, einem Stapel und einem Ringpuffer. Die Verwendung ihrer Klassen ist immer bequem. Es gibt Dokumentation und sogar Beispiele.

    Unten finden Sie den Code für einen ähnlichen Test mit boost :: stack.
    Boost-Test
    class test
    {
    private:
    	static ::boost::lockfree::stack 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;
    		}
    	}
    };
    


    Wir präsentieren die Ergebnisse dieses Tests in Form von Diagrammen:



    Libcds-Bibliothek


    Auf diese Bibliothek wird in ihren Artikeln häufig von khizmax verwiesen . Ungeachtet seiner Verbraucherqualitäten erschien es uns etwas umständlich und schlecht dokumentiert (die meisten Informationen, die wir hier auf Habré erhalten haben). Außerdem müssen Sie in jedem Thread, in dem die sperrfreien Container verwendet werden, Ihren Thread an die "Engine" anhängen (wahrscheinlich aufgrund von TLS?). Anschließend müssen Sie den Hazard Pointer-Singleton trennen und dennoch irgendwo initialisieren.

    Trotz der unvorstellbaren Menge an verschließbaren Containern, die für jeden Geschmack etwas dabei ist, kann diese Bibliothek kaum als schön bezeichnet werden - man muss sich erst daran gewöhnen.

    Unten ist der Code für einen ähnlichen Test mit cds :: container :: TreiberStack:
    Libcds-Test
    class xxxstack : public cds::container::TreiberStack
    {
    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();
    	}
    };
    


    Wir präsentieren die Ergebnisse dieses Tests in Form von Diagrammen:



    Leistungsvergleich


    Trotz der Tatsache, dass SList eine native Lösung ist und die beiden anderen "fast" plattformübergreifend sind, glauben wir, dass der folgende Vergleich gültig ist, da alle Tests unter denselben Bedingungen durchgeführt wurden und das Verhalten von Bibliotheken unter diesen Bedingungen demonstrieren.

    Aufgrund der linearen Zunahme der Anzahl der Aufgaben im Test mit zunehmender Anzahl der Threads nimmt die vollständige Implementierung aller Optionen eine angemessene Zeit in Anspruch. Es wurden drei Durchgänge durchgeführt, um das Ergebnis zu stabilisieren, sodass die oben dargestellten Ergebnisse den Durchschnitt zwischen den drei Starts bilden.

    Aus den obigen dreidimensionalen Diagrammen geht hervor, dass die Diagonale (die Werte der Argumente {p = c}) fast geradlinig ist. Für einen visuellen Vergleich der drei Bibliotheken haben wir eine Auswahl der Ergebnisse nach diesem Kriterium getroffen.

    Links ist was wir haben.

    Es ist zu erkennen, dass die Boost-Funktion gegenüber den beiden anderen Implementierungen nachlässt, obwohl dies einen größeren Widerstand gegen die Änderung von Eingabeparametern zeigt.

    Die Implementierungen von libcds und SList unterscheiden sich nicht so sehr, sondern im gesamten Eingabeintervall.

    Schlussfolgerungen


    Es muss anerkannt werden, dass Microsoft diesmal eine sehr gute Implementierung (wenn auch nur einen Container) erstellt hat, die erfolgreich mit Algorithmen aus bekannten Bibliotheken konkurrieren kann. Obwohl die beschriebene Implementierung nicht plattformübergreifend ist, kann sie für Windows-Anwendungsentwickler hilfreich sein.

    Laden Sie das Archiv mit dem Original - Visual Studio Projektcode kann hier

    Verwendete Materialien

    Bild am Anfang des
    MSDN- Artikels slist description boost.lockfree
    library libcds
    library Sperrfreie
    Datenstrukturen. Stack-Entwicklung
    Informationen zu Implementierungsdetails von SList

    UPD:
    Auf Anfrage von mickey99 haben wir einen weiteren Test durchgeführt: Diesmal haben wir einen gewöhnlichen std :: stack verwendet, zu dem der Zugriff durch den regulären std :: mutex gesperrt wurde.
    Mutex-Test
    class test
    {
    private:
    	static std::stack 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();
    		}
    	}
    };
    


    Sagen wir gleich: Ich musste lange warten, sehr lange. Dann wurde die Anzahl der Aufgaben pro Stream von 1 Million auf 100.000 reduziert, was natürlich zu nicht so genauen Ergebnissen führte (dies ist bei solchen Zahlen wahrscheinlich nicht erforderlich), und der Satz für die Anzahl der Eingabeströme wurde geändert, sodass weniger Punkte für die Berechnung zur Verfügung standen :
    int NumThreads[] = { 2, 4, 8, 16, 32, 64};


    Hier sind die Ergebnisse: Das Ergebnis ist sehr bezeichnend: Bereits bei mehr als 4 Flüssen jeder Art steigt die Spannung dramatisch um Größenordnungen an. Es ist schwierig, eine solche Linie mit den ersten drei auf der Karte zu zeichnen. Wahrscheinlich deutlicher wird mit einer logarithmischen Skala.





    Jetzt auch beliebt: