CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part II"
ฝัง
- เผยแพร่เมื่อ 3 ต.ค. 2024
- www.cppcon.org
-
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/Cpp...
--
Example-driven talk on how to design and write lock-free algorithms and data structures using C++ atomic -- something that can look deceptively simple, but contains very deep topics. (Important note: This is not the same as my "atomic Weapons" talk; that talk was about the "what they are and why" of the C++ memory model and atomics, and did not cover how to actually use atomics to implement highly concurrent algorithms and data structures.)
--
Herb Sutter: Author, chair of the ISO C++ committee, software architect at Microsoft.
--
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/reg...
*-----*
For those who wondering why although in c++20 std::atomic already became a standard, your code can't be compile if you write as such:
gcc & clang don't implement it except msvc :(
Damn, I just tested this with GCC 11 and got a static assert that std::atomic requires a trivially copyable type... That sucks..
gcc 12.1 and clang 15 now support this.
I was about to write a few lines about how there's a problem with the singly linked list's "push front" and "pop front" not updating p next and p between CAS iterations. But luckily, before posting I checked the docs for "compare exchange weak" and discovered that the first parameter is actually a reference that returns an updated snapshot of "head" in it! :( That's one example where references hide the fact that they may be out-parameters.
Anyway, a very good and interesting talk!
Reference is IN-OUT parameter
Const ref is IN parameter
- What is the progress on the question regarding stack overflow 23:22? It might very well be an actual issue in embedded systems. Also it introduces a failure condition
- I would like to know an adequate solution for list remove(item). It seems to be far more complex than the other operations even with shared_ptrs
- I also believe that herbs push_front is flawed and races with other push_fronts. The problem is that when two tasks queue up before the CAS and pick up head, both p->next will point to the same node previously stored in head (two atomic_loads will happen beside each other). p->next should be updated within the CAS-loop to consider the other node (who won the race) or this node will lose its pointer right away after the next CAS and get deleted.
Reference counting the entire list? ... So it's lock free, and should scale well, but has a higher baseline from the reference counting?
If a reference being passed into a function isn't const, it's usually safe to assume that it's an output parameter. At least that's my thought on it.
Shared Pooter
Dude, I came to the comments only because I knew I could not be the only person that drove nuts as he kept saying it. Is it suppose to be called a putter or something? Is he just calling it 'p' 't' 'r' and sounding it out phonically? What gives because that shit drives me crazy.
@@seditt5146 it's a shared_ptr. You may want it to be a pointer, but that doesn't make it one.
48:51 "divider = divider->next; " - but in the ctor we initialized: "divider = Node(T())".
you forgot the new keyword
At 38:00 I think is Fedor Pikus asking the question
I'm curious if there would be an issue if we returned an aliased shared_ptr from the pop_front member function.
@24:24 can reference be null/nullptr ? References aren't pointers right ? Or is it possible for references to be nullptr ?
But you don't see that at the calling site, only if you see the called function's signature or documentation.
In the bonus slides (e.g. 49:02) : the consumer releases its "lock" potentially twice. Isn't that inherently unsafe? Isn't it possible that _this_ consumer does it's second release while the lock is effectively already held by the next consumer (that isn't ready for a release yet)? What is it that I don't understand here?
Unless I'm missing something, in the line below the first release the function returns already. So you would never release twice in this code.
What about double linked lists ? It is so mch hurder I can't even know where to start from.
Herb, if you’re monitoring this I’d like to know how a couple of statements you made turned out.
36:18 "It is an open question, including at the standards meeting on Thursday, whether atomic shared_ptr can be written to be lock-free." Can it be atomic?
36:45 I was given an action item on Thursday, between now and November, to try to go put together a benchmark that actually shows it can be competitive or better ….” Is it competitive (faster)?
The atomic shared_ptr specialization is coming in C++20.
@@perekman3570 It's been implemented in MSVC but not gcc or clang.
but why is head "shared data"? Doesn't each slist instance get its own head?
sure, but one slist instance is used in multiple threads. if two threads call pop or push simultaneous, they both access head through that one instance and hence head is shared between the two threads. here, "shared" is defined as multiple threads using it, not multipe objects or datastructures use it.
Interesting. I tried posting something but only got "Error, try again"
Constructing shared_ptr for each push... the performance would be worse then the lock-based implementation
There you go. After making it look less like sourcecode, the error changed to "too long", and I had to shorten it a bit. Censorship sucks. Especially if it's done automatically with obscure rules.
test