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

41–50 of 52 posts

Re: Atomics and Concurrency

#41

Post by lmuscat »

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…

Ignoring the ABA problem, given the implementation of `new` and `delete` are blocking, so is the queue.

Re: Atomics and Concurrency

#42

Post by miloudi »

menaerus wrote: post #34
redixhumayun wrote: post #32

Earlier quoted context omitted.

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…

are you talking about this one? https://www.youtube.com/watch?v=AJBmIaUneB0&list=PL5Q2soXY2Z...

Re: Atomics and Concurrency

#43

Post by [deleted] »

infamouscow wrote: post #40
maxbond wrote: post #22

Earlier quoted context omitted.

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…

[deleted]

Re: Atomics and Concurrency

#44

Post by maxbond »

infamouscow wrote: post #40
maxbond wrote: post #22

Earlier quoted context omitted.

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…

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

In safe Rust, if I have a mutable reference to Foo, and Foo contains a shared reference to Bar, then no other thread has a mutable reference to Foo or Bar. So no other thread will make a CAS on my reference to Bar, or drop Bar and then allocate something at the same memory address, etc.

You could have some higher level ABA problem I suppose, where you acquire a lock, read a value, give up the lock, and then make spurious assumptions about what happens while you've let the lock go. But that's obviously not what we're talking about if we're talking about CAS. (ETA: or if these were application level references, eg indices into a list.)

If we're going to implement a lockfree data structure, we're going to need unsafe Rust to hand-roll interior mutability. Because we're going to be sharing mutable state. Which isn't allowed in safe Rust.

Or am I mistaken?

Re: Atomics and Concurrency

#45

Post by CyberDildonics »

lmuscat wrote: post #41
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…

Ignoring the ABA problem, given the implementation of `new` and `delete` are blocking, so is the queue.

This is a great point. Technically you could replace your allocator with jemalloc or something similar, but most people probably don't.

Memory allocation gets forgotten in the "lock free" algorithms all the time, especially in java where allocation is forgotten about and brushed aside.

Re: Atomics and Concurrency

#46

Post by infamouscow »

maxbond wrote: post #44
infamouscow wrote: post #40

Earlier quoted context omitted.

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…

> The ABA problem is a false-positive execution of a CAS speculation on a shared memory location. In safe Rust, if I have a mutable reference to Foo, and Foo contains a shared reference to Bar, then no other thread has a mutable reference to Foo or Bar. So no other thread will make a CAS on my reference to Bar, or drop Bar and then allocate something at the same memory address, etc. You could have some higher level A…

This demonstrates the ABA problem in safe Rust: https://play.rust-lang.org/?version=stable&mode=debug&editio...

Substitute the sleep with a combination of doing computation/work and the OS thread scheduler, and you can see how the bug surfaces.

Re: Atomics and Concurrency

#47

Post by maxbond »

infamouscow wrote: post #46
maxbond wrote: post #44

Earlier quoted context omitted.

> The ABA problem is a false-positive execution of a CAS speculation on a shared memory location. In safe Rust, if I have a mutable reference to Foo, and Foo contains a shared reference to Bar, then no other thread has a mutable reference to Foo or Bar. So no other thread will make a CAS on my reference to Bar, or drop Bar and then allocate something at the same memory address, etc. You could have some higher level A…

This demonstrates the ABA problem in safe Rust: https://play.rust-lang.org/?version=stable&mode=debug&editio... Substitute the sleep with a combination of doing computation/work and the OS thread scheduler, and you can see how the bug surfaces.

I guess? I've only ever heard about the ABA problem in reference to pointers, eg in the context of lockfree queues. Maybe that's my ignorance. (Which is why I addressed shared references in my comment.)

Yes, if you don't hold a lock on a value, or exert some kind of control at the API level (eg making it monotonic so your CAS will work), you can't make assumptions about it. I think you'll find that Rust developers understand that concept about as well as any other community of concurrent developers.

But yes, granted, the semantic information about these integers isn't represented in Rust's type system, and won't be caught by it's static analysis.

Re: Atomics and Concurrency

#48

Post by menaerus »

miloudi wrote: post #42
menaerus wrote: post #34

Earlier quoted context omitted.

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…

are you talking about this one? https://www.youtube.com/watch?v=AJBmIaUneB0&list=PL5Q2soXY2Z...

Yes, that's the one. These lectures seem to repeat yearly so there're also playlists with the updated content from 2021, 2022 and 2023.

There's also an "advanced" playlist and there're plenty of other interesting lectures about the memory.

Re: Atomics and Concurrency

#49

Post by menaerus »

CyberDildonics wrote: post #45
lmuscat wrote: post #41

Earlier quoted context omitted.

Ignoring the ABA problem, given the implementation of `new` and `delete` are blocking, so is the queue.

This is a great point. Technically you could replace your allocator with jemalloc or something similar, but most people probably don't. Memory allocation gets forgotten in the "lock free" algorithms all the time, especially in java where allocation is forgotten about and brushed aside.

I think that the point rather was not to use any allocation in critical sections since allocator implementations are not lock-free or wait-free.

https://github.com/jemalloc/jemalloc/blob/dev/src/mutex.c

Re: Atomics and Concurrency

#50

Post by CyberDildonics »

menaerus wrote: post #49
CyberDildonics wrote: post #45

Earlier quoted context omitted.

This is a great point. Technically you could replace your allocator with jemalloc or something similar, but most people probably don't. Memory allocation gets forgotten in the "lock free" algorithms all the time, especially in java where allocation is forgotten about and brushed aside.

I think that the point rather was not to use any allocation in critical sections since allocator implementations are not lock-free or wait-free. https://github.com/jemalloc/jemalloc/blob/dev/src/mutex.c

That was their point and that was my point.

Just because jemalloc has a mutex.c file, that doesn't mean that common paths aren't meant to be lock free and in the case of lots of little allocations that can go into small bucket sizes in jemalloc they should be.

It is still putting your head in the sand since at some point they have to go to the OS and map in memory which should lock and lots of small allocations are a terrible way to anything for performance, but it is possible to have some paths in an allocator not have locks.

Also if there are thread local heaps, those won't lock either.

Post reply on HN