Neuerungen in C++26: Read-Copy-Update

Read-Copy-Update (RCU) ist besonders in Multithreading-Umgebungen geeignet, in denen eine Datenstruktur fast ausschließlich gelesen, aber nur selten geschrieben wird.

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

Zunächst einmal: Wie funktioniert RCU? Die hervorragende englisch Wikipedia-Seite zu Read-Copy-Update bietet eine gute Einführung:

In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e.g., linked lists, trees, hash tables).

Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g., dereferencing null pointers).

It is used when performance of reads is crucial and is an example of space–time tradeoff, enabling fast operations at the cost of more space. This makes all readers proceed as if there were no synchronization involved, hence they will be fast, but also making updates more difficult

Der Name RCU wurde vom Workflow-Schreiber geprägt. Zuerst werden die aktuellen Daten gelesen, in die neuen Daten kopiert und dann die aktuellen Daten aktualisiert.

Der Proposal P2545R4 stellt drei Anwendungsfälle für RCU vor und vergleicht sie mit Reader-Writer-Locks.

Drei Anwendungsfälle

Die drei Anwendungsfälle vergleichen Reader-Writer-Locks mit intrusiven, nicht-intrusiven und synchronen RCUs.

Der Hauptunterschied zwischen intrusiver und nicht-intrusiver RCU besteht darin, dass im intrusiven Fall Data direkt von der Klasse abgeleitet wird struct Data : std::rcu_obj_base<Data>. Diese Technik, bei der ein Template sich selbst als Parameter hat, ist als Curiously Recurring Template Pattern (CRTP) bekannt. Auf der Leserseite wird std::scoped_lock l(std::rcu_default_domain()) verwendet. Auf der Schreibseite wird entweder retire() oder std::rcu_synchronize() verwendet.

Dies wirft die Frage auf: Wann sollten ähnliche Techniken wie atomare Shared Pointer, Read-Write-Locks, Hazard Pointers und RCU verwendet werden? Der Proposal P2545R4 liefert eine einfache Regel: As a very rough rule of thumb, Hazard Pointers can be considered to be a scalable replacement for reference counters and RCU can be considered to be a scalable replacement for reader-writer locking. A high-level comparison of reference counting, Hazard Pointers, and RCU is displayed in this table:

Schnittstelle von RCU

Die Schnittstelle besteht aus den Klassen, rcu_obj_base und rcu_domain sowie den Funktionen rcu_default_domain, rcu_synchronize, rcu_barrier und rcu_retire.

cppreference bietet eine kurze Beschreibung:

Classes

• rcu_obj_base: allows an object to be protected by RCU
• rcu_domain: provides regions of RCU protection

Functions

• rcu_default_domain: returns a reference to a static-duration object of type std::rcu_domain
• rcu_synchronize: blocks until a protection region unlocks on a RCU domain
• rcu_barrier: may evaluate scheduled operations on a RCU domain and blocks until all preceding evaluations are complete
• rcu_retire: schedules the evaluation of a specified function on a RCU domain, potentially allocating memory, and invoking scheduled evaluations

Wie geht es weiter?

In meinem nächsten Artikel werde ich die Bibliothek für datenparallele Datentypen (SIMD) und deren passende Operationen näher betrachten.

(rme)