CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part II"

Подписаться 153 тыс.

Просмотров 50 тыс.

50% 1

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...
*-----*

Опубликовано:

28 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 29

@FanRRice 4 года назад

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 :(

@warrenbuckley3267 3 года назад

Damn, I just tested this with GCC 11 and got a static assert that std::atomic requires a trivially copyable type... That sucks..

@sean7235 Год назад

gcc 12.1 and clang 15 now support this.

@phillipratzloff8923 6 лет назад

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)?

@perekman3570 4 года назад

The atomic shared_ptr specialization is coming in C++20.

@warrenbuckley3267 3 года назад

@@perekman3570 It's been implemented in MSVC but not gcc or clang.

@sanjuuyonsai 9 лет назад

But you don't see that at the calling site, only if you see the called function's signature or documentation.

@sanjuuyonsai 10 лет назад

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.

@Jackmccallumlols 9 лет назад

Shared Pooter

@seditt5146 5 лет назад

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.

@toryvindmoe6794 4 года назад

@@seditt5146 it's a shared_ptr. You may want it to be a pointer, but that doesn't make it one.

@origamibulldoser1618 10 лет назад

Reference counting the entire list? ... So it's lock free, and should scale well, but has a higher baseline from the reference counting?

@Astfresser 2 года назад

- 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.

@dang5402 3 года назад

What about double linked lists ? It is so mch hurder I can't even know where to start from.

@warrenbuckley3267 3 года назад

I'm curious if there would be an issue if we returned an aliased shared_ptr from the pop_front member function.

@jithintc4200 3 года назад

@24:24 can reference be null/nullptr ? References aren't pointers right ? Or is it possible for references to be nullptr ?

@sanjuuyonsai 10 лет назад

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!

@NoNameAtAll2 4 года назад

Reference is IN-OUT parameter Const ref is IN parameter

@93Mosfet 2 года назад

At 38:00 I think is Fedor Pikus asking the question

@eiroo5192 2 года назад

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?

@myname356 Год назад

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.

@ekimr90 9 лет назад

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.

@dosomething3 7 лет назад

48:51 "divider = divider->next; " - but in the ctor we initialized: "divider = Node(T())".

@schulmastery 6 лет назад

you forgot the new keyword

@GeorgeTsiros 5 лет назад

but why is head "shared data"? Doesn't each slist instance get its own head?

@foxtrotromeo4876 5 лет назад

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.