![\"\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2025\/01\/Time26Concurrency.png\")
<\/figure>\n\n\n\nGeneral Considerations<\/h2>\n\n\n\n
From the outside, the caller\u2019s responsibility (application) is to protect the data. From inside, the data structure is responsible for protecting itself. A data structure that protects itself so a data race cannot appear is called thread-safe.<\/p>\n\n\n\n
First, what general considerations must you keep in mind when designing a concurrent data structure?<\/p>\n\n\n\n
- \n
- Locking Strategy<\/strong>: Should the data structure support coarse-grained or fine-grained locking or be lock-free? Coarse-grained locking might be easier to implement but introduces contention. A fine-grained implementation or a lock-free one is much more challenging. First of all, what do I mean by coarse-grained locking? Coarse-grained locking means that only one thread uses the data structure at one point in time.<\/li>\n\n\n\n
- The Granularity of the Interface<\/strong>: The bigger the thread-safe data structure\u2019s interface, the more difficult it becomes to reason about its concurrent usage.<\/li>\n\n\n\n
- Typical Usage Pattern<\/strong>: When readers mainly use your data structure, you should not optimize it for writers.<\/li>\n\n\n\n
- Avoidance of Loopholes:<\/strong> Don\u2019t pass the internals of your data structure to clients.<\/li>\n\n\n\n
- Contention<\/strong>: Do concurrent client requests seldom or often use your data structure?<\/li>\n\n\n\n
- Scalability<\/strong>: How is your data structure\u2019s performance characteristic when the number of
concurrent clients increases, or the data structure is bounded?<\/li>\n\n\n\n- Invariants<\/strong>: Which invariant must hold for your data structure when used?<\/li>\n\n\n\n
- Exceptions<\/strong>: What should happen if an exception occurs?<\/li>\n<\/ul>\n\n\n\n
Of course, these considerations are dependent on each other. For example, using a coarse-grained locking strategy may increase the contention on the data structure and break scalability.<\/p>\n\n\n\n
First of all, what is a stack?<\/p>\n\n\n\n
A Stack<\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2025\/01\/stack.png\")
<\/figure>\n\n\n\nAnd
std::stack<\/code> follows the LIFO principle (Last In – First Out). A stacksta<\/code>, which needs the header<stack><\/code>, has three member functions.
Withsta.push(e)<\/code>, you can insert a new element e at the top of the stack, remove it from the top with sta.pop() , and reference it withsta.top()<\/code>. The stack supports the comparison operators and knows its size.<\/p>\n\n\n\n#include <stack><\/span>\n...\nstd::<\/span>stack<<\/span>int<\/span>><\/span> myStack;\n\nstd::<\/span>cout <<<\/span> myStack.empty() <<<\/span> '\\n'<\/span>; \/\/ true<\/span>\nstd::<\/span>cout <<<\/span> myStack.size() <<<\/span> '\\n'<\/span>; \/\/ 0<\/span>\n\nmyStack.push(1<\/span>);\nmyStack.push(2<\/span>);\nmyStack.push(3<\/span>);\n\nstd::<\/span>cout <<<\/span> myStack.top() <<<\/span> '\\n'<\/span>; \/\/ 3<\/span>\nwhile<\/span> (!<\/span>myStack.empty()){\n std::<\/span>cout <<<\/span> myStack.top() <<<\/span> " "<\/span>;\n myStack.pop();\n} \/\/ 3 2 1<\/span>\n\nstd::<\/span>cout <<<\/span> myStack.empty() <<<\/span> '\\n'<\/span>; \/\/ true<\/span>\nstd::<\/span>cout <<<\/span> myStack.size() <<<\/span> '\\n'<\/span>; \/\/ 0<\/span>\n<\/pre><\/div>\n\n\n\nNow, let me start with the implementation of a lock-free stack.<\/p>\n\n\n\n
A Simplified Implementation<\/h2>\n\n\n\n
In my simplified implementation, I start with the
push <\/code>member function. First, let me visualize how a new node is added to a singly-linked list. head is the pointer to the first node in the singly-linked list.<\/p>\n\n\n\n![\"\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2025\/01\/SinglyLinkedList.png\")
<\/figure>\n\n\n\n
<\/p>\n\n\n\n![\"\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2025\/01\/SinglyLinkedListInsert.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2025\/01\/SinglyLinkedListNewHead-1030x236.png\")
<\/figure>\n\n\n\nEach node in the singly-linked list has two attributes. Its value
T<\/code> and thenext. next<\/code> points to the next element in the singly-linked list. Only the node points to thenullptr<\/code>. Adding a new node to the data is straightforward. Create a new node and letnext <\/code>pointer point to the previous head. So far, the new node is not accessible. Finally, the new node becomes the new head, completing the push operation.<\/p>\n\n\n\n
The following example shows the lock-free implementation of a concurrent stack.<\/p>\n\n\n\n\/\/ lockFreeStackPush.cpp<\/span>\n\n#include <atomic><\/span>\n#include <iostream><\/span>\n\ntemplate<\/span><<\/span>typename<\/span> T><\/span>\nclass<\/span> LockFreeStackPush<\/span> {\n private:<\/span>\n struct<\/span> Node {\n T data;\n Node*<\/span> next;\n Node(T d):<\/span> data(d), next(nullptr) {}\n };\n std::<\/span>atomic<<\/span>Node*><\/span> head;\n public:<\/span>\n LockFreeStackPush() =<\/span> default<\/span>;\n LockFreeStackPush(const<\/span> LockFreeStackPush&<\/span>) =<\/span> delete<\/span>;\n LockFreeStackPush&<\/span> operator<\/span>=<\/span> (const<\/span> LockFreeStackPush&<\/span>) =<\/span> delete<\/span>;\n \n void<\/span> push<\/span>(T val) {\n Node*<\/span> const<\/span> newNode =<\/span> new<\/span> Node(val); \/\/ 1<\/span>\n newNode-><\/span>next =<\/span> head.load(); \/\/ 2<\/span>\n while<\/span>( !<\/span>head.compare_exchange_strong(newNode-><\/span>next, newNode) ); \/\/ 3<\/span>\n }\n};\n \nint<\/span> main<\/span>(){\n\n LockFreeStackPush<<\/span>int<\/span>><\/span> lockFreeStack;\n lockFreeStack.push(5<\/span>);\n \n LockFreeStackPush<<\/span>double<\/span>><\/span> lockFreeStack2;\n lockFreeStack2.push(5.5<\/span>);\n \n LockFreeStackPush<<\/span>std::<\/span>string><\/span> lockFreeStack3;\n lockFreeStack3.push("hello"<\/span>);\n\n}\n<\/pre><\/div>\n\n\n\nLet me analyze the crucial member function
push<\/code>. It creates the new node (line 1), adjusts
its next pointer to the old head, and makes the new node in a so-called CAS operation the new head (line 3). A CAS operation provides, in an atomic step, a compare and swap operation.<\/p>\n\n\n\nThe call
newNode->next = head.load() <\/code>loads the old value of head. If the loaded valuenewNode->next<\/code> is still the same such as head in line 3, the head is updated to thenewNode<\/code>, and the callhead.compare_exchange_strong <\/code>returnstrue<\/code>. If not, the call returnsfalse<\/code>, and the while loop is executed until the call returnstrue<\/code>.head.compare_exchange_strong<\/code> returnsfalse <\/code>if another thread has meanwhile added a new node to the stack.<\/p>\n\n\n\n
Lines 2 and 3 build a kind of atomic transaction. First, you make a snapshot of the data structure (line 2), then try to publish the transaction (line 3). If the snapshot is no longer valid, you roll back and try it again.<\/p>\n\n\n\nWhat’s Next?<\/h2>\n\n\n\n
Todays simplified stack implementation serves me as a baseline for upcoming stacks.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today, I continue my mini story about lock-free data structures. General Considerations From the outside, the caller\u2019s responsibility (application) is to protect the data. From inside, the data structure is responsible for protecting itself. A data structure that protects itself so a data race cannot appear is called thread-safe. First, what general considerations must you […]<\/p>\n","protected":false},"author":21,"featured_media":10580,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[559],"tags":[563],"class_list":["post-10598","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c26-blog","tag-hazard-pointers"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10598","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=10598"}],"version-history":[{"count":11,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10598\/revisions"}],"predecessor-version":[{"id":10613,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/10598\/revisions\/10613"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/10580"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=10598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=10598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=10598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- The Granularity of the Interface<\/strong>: The bigger the thread-safe data structure\u2019s interface, the more difficult it becomes to reason about its concurrent usage.<\/li>\n\n\n\n