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

21–30 of 52 posts

Re: Atomics and Concurrency

#21

Post by gpderetta »

redixhumayun wrote: post #19
gpderetta wrote: post #16

IMHO that the graph in the Memory Barrier section is misleading [1]. It has the barriers spanning across threads, but that's not the right mental model. Something like this is more correct (note the additional barriers after the store and before the load to match seq_cst semantics): Thread 1 Memory Thread 2 --------- ------- --------- | | | | write(data, 100) | | | -----------------------> | | | | | | ====Memory Barr…

Hey, so I'm curious why having memory barriers span across threads is the wrong mental model. Assuming that the memory barrier is syncing across a single variable (in this case ready), why would it be correct to think of it as two separate barriers? If it were correct to think of it as two separate barriers on two separate threads, wouldn't there need to be some form of synchronization or linkage between the two barr…

The linking of barriers in pair is really just a mental model, not (usually) what happens at the hardware level. In fact in the C++ memory model the synchronizes-with relationship is load and stores, not barriers, which indirectly affect the properties of load and stores around them. That's another reason why I don't really like the memory barrier model and I prefer to think in terms of happens-before dependency graphs.

edit: AFAIK, seq_cst ordering (as opposed to acq_rel) is only relevant when you have more than two threads and you care about things like IRIW. In this case acquires and releases are not enough to capture the full set of constraints, although at the hardware level it is still everything local.

edit2: I guess the missing bit is that beyond the hardware fences you have the hardware cache coherency protocol that makes sure that a total order of operations always exist once load and stores reach the coherence fabric.

Re: Atomics and Concurrency

#22

Post by maxbond »

redixhumayun wrote: post #20
kaba0 wrote: post #15

Earlier quoted context omitted.

No data races is just a very tiny subset of semantic invariants, though.

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.

Re: Atomics and Concurrency

#23

Post by bluetomcat »

redixhumayun wrote: post #19
gpderetta wrote: post #16

IMHO that the graph in the Memory Barrier section is misleading [1]. It has the barriers spanning across threads, but that's not the right mental model. Something like this is more correct (note the additional barriers after the store and before the load to match seq_cst semantics): Thread 1 Memory Thread 2 --------- ------- --------- | | | | write(data, 100) | | | -----------------------> | | | | | | ====Memory Barr…

Hey, so I'm curious why having memory barriers span across threads is the wrong mental model. Assuming that the memory barrier is syncing across a single variable (in this case ready), why would it be correct to think of it as two separate barriers? If it were correct to think of it as two separate barriers on two separate threads, wouldn't there need to be some form of synchronization or linkage between the two barr…

Modern processors are out-of-order execution beasts. A barrier within a thread serves to enforce some ordering within that thread - that a store will occur after another store, and that a load will occur before another load. Threads know nothing of each other.

Re: Atomics and Concurrency

#24

Post by [deleted] »

chc4 wrote: post #3

For the concurrent queue at the bottom, the issue is with the ABA problem where you're guaranteed to execute the atomic compare-and-swap correctly, but you aren't guaranteed that the same pointer value means the queue is in the same state: if you have a queue `123` and start a dequeue, you load current head = 1, next = 2, and then can be scheduled out for another thread to execute a series of operations resulting in…

[deleted]

Re: Atomics and Concurrency

#26

Post by ZoomZoomZoom »

> 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 Maurice Herlihy, Nir Shavit et al. ISBN: 978-0124159501

Re: Atomics and Concurrency

#27

Post by zozbot234 »

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 Hard, And If So What Can You Do About It?" https://mirrors.edge.kernel.org/pub/linux/kernel/people/paul... )

Re: Atomics and Concurrency

#28

Post by sneela »

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…

> The Art of Multiprocessor Programming by Maurice Herlihy, Nir Shavit et al. ISBN: 978-0124159501

An excellent book that I used for my Parallel Programming course in my undergrad. While looking up Nir Shavit (back then), I came across a "Summer School on Practice and Theory of Concurrent Computing (2017)" [1] which had notable people give talks about interesting & fundamental topics related to Parallel Computing such as "Wait-free computing 'for dummies'", "Lock-free concurrent data structures", and "Locking, from traditional to modern" (taught by Nir Shavit). [2] is a link to a YouTube playlist containing all the videos from that Summer School. I highly recommend it.

[1] https://neerc.ifmo.ru/sptcc/courses.html

[2] https://www.youtube.com/playlist?list=PLVe-2wcL84b9G9o7KPubp...

Re: Atomics and Concurrency

#29

Post by adastra22 »

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…

> In order to enqueue an element, you have to change two atomic pointers: tail->next and tail. That cannot be done atomically.

With added indirection, there are ways of doing this atomically.

Re: Atomics and Concurrency

#30

Post by redixhumayun »

gpderetta wrote: post #21
redixhumayun wrote: post #19

Earlier quoted context omitted.

Hey, so I'm curious why having memory barriers span across threads is the wrong mental model. Assuming that the memory barrier is syncing across a single variable (in this case ready), why would it be correct to think of it as two separate barriers? If it were correct to think of it as two separate barriers on two separate threads, wouldn't there need to be some form of synchronization or linkage between the two barr…

The linking of barriers in pair is really just a mental model, not (usually) what happens at the hardware level. In fact in the C++ memory model the synchronizes-with relationship is load and stores, not barriers, which indirectly affect the properties of load and stores around them. That's another reason why I don't really like the memory barrier model and I prefer to think in terms of happens-before dependency grap…

Yeah, I see your point about thinking in terms of dependency graphs. I actually got the idea for using a visual memory barrier from the Linux docs(https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...) and the C++ concurrency in action book.

>I guess the missing bit is that beyond the hardware fences you have the hardware cache coherency protocol that makes sure that a total order of operations always exist once load and stores reach the coherence fabric.

Can you explain more about this?

Post reply on HN