Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Atomics and Concurrency

redixhumayun.github.io

Post reply on HN
Print view View original

31–40 of 52 posts

Re: Atomics and Concurrency

#31

Post by redixhumayun »

el_pollo_diablo wrote: post #18

There are many problems with this concurrent queue. Here are a few I found in a cursory reading. In order to enqueue an element, you have to change two atomic pointers: tail->next and tail. That cannot be done atomically. enqueue() assumes that the queue is not empty. enqueue() happily overwrites current_tail->next even if it is not null (which may happen if some other producer has enqueued something since we read cu…

That concurrent queue is only there to illustrate usage of CAS in a data structure. I think having an actual implementation of a concurrent queue along with handling the ABA problem might be an entirely separate post.

I added in a note about the ABA problem but perhaps you're seeing a cached version of the post.

Re: Atomics and Concurrency

#32

Post by redixhumayun »

ZoomZoomZoom wrote: post #26

> This is going to be a long post Is it really? Sorry, but this is barely an introduction. Some additional links to important documentation: https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/atomic/memory_order https://research.swtch.com/mm Effective Concurrency series by Sutter: https://herbsutter.com/2009/07/15/effective-concurrency/ The Art of Multiprocessor Programming by M…

Honestly, now that I look back at it having written it a couple of weeks ago, it doesn't feel that long. But, writing it felt incredibly wrong because I was encountering memory models for the first time.

I think for someone who has no exposure to it before, its quite dense (perhaps long wasn't the best choice of wording)

Also, I've been meaning to read The Art of Multiprocessor Programming. I've heard great things about it!

Re: Atomics and Concurrency

#33

Post by redixhumayun »

dnedic wrote: post #25

If you're interested about practical uses of atomic operations, I wrote lockfree: https://github.com/DNedic/lockfree , a collection of lock-free data structures meant to be readable and both hosted system and embedded friendly.

This is awesome! Also, I'm pretty sure I've come across your repo before from a SO answer (if I remember correctly)

Re: Atomics and Concurrency

#34

Post by menaerus »

redixhumayun wrote: post #32
ZoomZoomZoom wrote: post #26

> This is going to be a long post Is it really? Sorry, but this is barely an introduction. Some additional links to important documentation: https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/atomic/memory_order https://research.swtch.com/mm Effective Concurrency series by Sutter: https://herbsutter.com/2009/07/15/effective-concurrency/ The Art of Multiprocessor Programming by M…

Honestly, now that I look back at it having written it a couple of weeks ago, it doesn't feel that long. But, writing it felt incredibly wrong because I was encountering memory models for the first time. I think for someone who has no exposure to it before, its quite dense (perhaps long wasn't the best choice of wording) Also, I've been meaning to read The Art of Multiprocessor Programming. I've heard great things ab…

You shouldn't feel bad about it - the blog is going to have its audience, so don't worry about it. That said, the topic is incredibly complex and to understand it fully requires intimate knowledge of the CPU microarchitectural details and design. So, technically speaking even the links from the comment you're replying to are providing a shallow although somewhat longer introduction. Programming languages only provide an abstraction for these very real things happening in the silicon so that's about as far as they can go by providing the sufficient amount of details. The real meat is down the rabbit hole of the CPU and memory subsystem design and if you want to go there I'd suggest the yt lectures from ETH Zurich on the topic of computer architectures and design (can find the link later).

Re: Atomics and Concurrency

#35

Post by saagarjha »

gpderetta wrote: post #17
chc4 wrote: post #9

Earlier quoted context omitted.

Funnily enough, ARM has another difference here on top of just having a non-TSO memory model: LL/SC atomics solve the ABA problem, because the word holding the queue head has been written to and the store-conditional fails, even though the contents of the memory will be the same at the end. Which makes sense once you say it and some docs about LL/SC will mention that, but also reading various lockfree data structure…

the issue with LL/SC is that it is hard to expose to higher level languages than assembler. What you can do within an LL/SC section without causing it to spuriously fail is very much architecture dependent and you need full control of the load and stores within it. Exposing it to compiler optimizations won't work reliably. So in practice LL/SC, in higher level languages, is used to implement CAS, XCHG and other atomi…

It would be nice if compilers can lower this back to LL/SC if that’s what you actually wanted.

Re: Atomics and Concurrency

#36

Post by gpderetta »

zozbot234 wrote: post #27

The best exposition of advanced concurrency I know of is Mara Bos' Rust Atomics and Locks - https://marabos.nl/atomics/ also available as a physical book. Don't let the "Rust" reference put you off, the book is relevant to any low-level programming language. (If you're interested in concurrency in a Linux context as seen from a broader systems point of view, you might like Paul McKeneny's 'Is Parallel Programming Har…

Another great book is "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit.

edit: already mentioned elsethread.

Re: Atomics and Concurrency

#37

Post by loeg »

I appreciate that this was written by someone new to atomics and memory ordering semantics. But it presents itself as authoritative despite having some mistakes. So I am not super keen on that.

Just for example, right off the bat:

> Atomics are simply operations or instructions that cannot be split by the compiler or the CPU or re-ordered in any way.

C++ atomics can in fact be reordered by the compiler or CPU, depending on ordering semantics. Acquire loads cannot be reordered after subsequent program-order loads or stores. But they can be reordered before previous program-order operations. Similarly, release stores cannot be reordered before prior program-order operations, but can be reordered after subsequent program-order operations. Relaxed atomic operations can be reordered arbitrarily (other than with accesses to the same object).

Re: Atomics and Concurrency

#38

Post by loeg »

feverzsj wrote: post #13

C++26 will have safe reclamation [0] https://en.cppreference.com/w/cpp/thread#Safe_Reclamation

I'm super excited for this. Do you know if any of the common C++ add-on libraries implement C++26 Safe Reclamation semantics yet? I'm pretty sure Folly has hazard pointers although I think the API is different from this.

Re: Atomics and Concurrency

#39

Post by T0pH4t »

el_pollo_diablo wrote: post #18

There are many problems with this concurrent queue. Here are a few I found in a cursory reading. In order to enqueue an element, you have to change two atomic pointers: tail->next and tail. That cannot be done atomically. enqueue() assumes that the queue is not empty. enqueue() happily overwrites current_tail->next even if it is not null (which may happen if some other producer has enqueued something since we read cu…

I'm surprised more people are not calling out

"enqueue() happily overwrites current_tail->next even if it is not null (which may happen if some other producer has enqueued something since we read current_tail)."

Its probably one of the bigger problems of this queue, basically negates the whole structure with this bug.

Re: Atomics and Concurrency

#40

Post by infamouscow »

maxbond wrote: post #22
redixhumayun wrote: post #20

Earlier quoted context omitted.

I assumed what the poster above meant was that Rust can take care of more than just data races. Specifically Rust can solve the ABA problem somehow?

Rust won't solve the ABA problem, no. You'd be in unsafe Rust if you were writing something that could encounter the ABA problem. You wondered out loud how it was even possible to do that kind of analysis, and that's where my mind went. Evidently people think it's a bad take. That's as deep as it goes.

The ABA problem is a false-positive execution of a CAS speculation on a shared memory location.

It is very easy to create an ABA problem in safe Rust. Data race free sequential consistency, which Rust has, is almost completely orthogonal to the ABA problem.

This is an area of active PLT research, we haven't come anywhere close to addressing the problem in the general case.

I suspect we'll be seeing all kinds of bugs caused by a generation of programmers thinking everything has guard rails in Rust because "safety", so they can turn their brain off and not think. In reality, those promises of safety largely disappear when threads, files, signals, and networks are involved.

At the end of the day, your programs run on computers which exist in the physical world. The abstractions are mostly isomorphic, but it's at the margins where the abstractions aren't isomorphic that all the interesting things happen.

Post reply on HN