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

Programming Language Memory Models

research.swtch.com

Post reply on HN
Print view View original

11–20 of 101 posts

Re: Programming Language Memory Models

#11

Post by jqpabc123 »

ekiwi wrote: post #4
jqpabc123 wrote: post #2

If thread 2 copies done into a register before thread 1 executes, it may keep using that register for the entire loop, never noticing that thread 1 later modifies done. Alternative solution: Forget all the "atomic" semantics and simply avoid "optimization" of global variables. Access to any global variable should always occur direct from memory. Sure, this will be less than optimal in some cases but such is the price…

> Access to any global variable should always occur direct from memory. What if your function takes a pointer that might be pointing to a global variable? Does that mean that all accesses through a pointer are now excempt from optimization unless the compiler can prove that the pointer will never point to a global variable?

What if your function takes a pointer that might be pointing to an "atomic" variable?

Pointers can be used to circumvent most safety measures. If you obscure the access, you should assume responsibility for the result.

Re: Programming Language Memory Models

#13

Post by dragontamer »

knz42 wrote: post #7

A lot of the complexity comes from the lack of expressivity in languages to relate variables (or data structure fields) semantically to each other. If there was a way to tell the compiler "these variables are always accessed in tandem", the compiler could be smart about ordering and memory fences. The idea to extend programming languages and type systems in that direction is not new: folk who've been using distribute…

That's Java's Object.lock() mechanism.

All variables inside of an object (aka: any class) are assumed to be related to each other. synchronized(foobar_object){ baz(); } ensures that all uses of foobar_object inside the synchronization{} area are sequential (and therefore correct).

--------

The issue is that some people (a minority) are interested in "beating locks" and making something even more efficient.

Re: Programming Language Memory Models

#14

Post by temac »

voidnullnil wrote: post #10

These "memory models" are too complex for languages intended for dilettante developers. It was a disaster in Java/C#. Not even more than a handful of programmers in existence know in depth how it works, as in, can they understand any given trivial program in their language. At best they only know some vague stuff like that locking prevents any non visibility issues. It goes far deeper than that though (which is also…

They are not too complex for "languages intended for dilettante developers": they can (and should) use sequential consistency or locks everywhere.

Re: Programming Language Memory Models

#15

Post by voidnullnil »

dragontamer wrote: post #6
mumblemumble wrote: post #5

Earlier quoted context omitted.

This problem isn't specific to global variables; it happens with all shared mutable state. I would assume that the author only used global variables because that lets them keep the working examples as short as possible, and minimize irrelevant details. And yes, you can put a full memory fence around every access to a variable that is shared across threads. But doing so would just destroy the performance of your progr…

> And yes, you can put a full memory fence around every access to a variable that is shared across threads. But doing so would just destroy the performance of your program. Given that we're talking about concerns that are specific to a relatively low-level approach to parallelism, I think it's safe to assume that performance is the whole point, so that would be an unacceptable tradeoff. Indeed. Just a reminder to eve…

> This "Memory Model" discussion is only for people who want to build faster systems: for people searching for a "better spinlock", or for writing lock-free algorithms / lock-free data structures.

Actually, most practitioner code has bugs from their implicit assumptions that shared variable writes are visible or ordered the way they think they are.

Re: Programming Language Memory Models

#16

Post by voidnullnil »

temac wrote: post #14
voidnullnil wrote: post #10

These "memory models" are too complex for languages intended for dilettante developers. It was a disaster in Java/C#. Not even more than a handful of programmers in existence know in depth how it works, as in, can they understand any given trivial program in their language. At best they only know some vague stuff like that locking prevents any non visibility issues. It goes far deeper than that though (which is also…

They are not too complex for "languages intended for dilettante developers": they can (and should) use sequential consistency or locks everywhere.

How many programmers do you know put locks around polling varibles for seemingly no reason (as they are not cognizant of the memory model)?

Re: Programming Language Memory Models

#17

Post by dragontamer »

voidnullnil wrote: post #15
dragontamer wrote: post #6

Earlier quoted context omitted.

> And yes, you can put a full memory fence around every access to a variable that is shared across threads. But doing so would just destroy the performance of your program. Given that we're talking about concerns that are specific to a relatively low-level approach to parallelism, I think it's safe to assume that performance is the whole point, so that would be an unacceptable tradeoff. Indeed. Just a reminder to eve…

> This "Memory Model" discussion is only for people who want to build faster systems: for people searching for a "better spinlock", or for writing lock-free algorithms / lock-free data structures. Actually, most practitioner code has bugs from their implicit assumptions that shared variable writes are visible or ordered the way they think they are.

But the practitioner doesn't need to know the memory model (aside from "memory models are complicated").

To solve that problem, the practitioner only needs to know that "mutex.lock()" and "mutex.unlock()" orders reads/writes in a clearly defined manner. If the practitioner is wondering about the difference between load-acquire and load-relaxed, they've probably gone too deep.

Re: Programming Language Memory Models

#18

Post by raphlinus »

A GPU followup to this article.

While on CPU sequentially consistent semantics are efficient to implement, that seems to be much less true on GPU. Thus, Vulkan completely eliminates sequential consistency and provides only acquire/release semantics[1].

It is extremely difficult to reason about programs using these advanced memory semantics. For example, there is a discussion about whether a spinlock implemented in terms of acquire and release can be reordered in a way to introduce deadlock (see reddit discussion linked from [2]). I was curious enough about this I tried to model it in CDSChecker, but did not get definitive results (the deadlock checker in that tool is enabled for mutexes provided by API, but not for mutexes built out of primitives). I'll also note that using AcqRel semantics is not provided by the Rust version of compare_exchange_weak (perhaps a nit on TFA's assertion that Rust adopts the C++ memory model wholesale), so if acquire to lock the spinlock is not adequate, it's likely it would need to go to SeqCst.

Thus, I find myself quite unsure whether this kind of spinlock would work on Vulkan or would be prone to deadlock. It's also possible it could be fixed by putting a release barrier before the lock loop.

We have some serious experts on HN, so hopefully someone who knows the answer can enlighten us - mixed in of course with all the confidently wrong assertions that inevitably pop up in discussions about memory model semantics.

[1]: https://www.khronos.org/blog/comparing-the-vulkan-spir-v-mem...

[2]: https://rigtorp.se/spinlock/

Re: Programming Language Memory Models

#19

Post by voidnullnil »

dragontamer wrote: post #17
voidnullnil wrote: post #15

Earlier quoted context omitted.

> This "Memory Model" discussion is only for people who want to build faster systems: for people searching for a "better spinlock", or for writing lock-free algorithms / lock-free data structures. Actually, most practitioner code has bugs from their implicit assumptions that shared variable writes are visible or ordered the way they think they are.

But the practitioner doesn't need to know the memory model (aside from "memory models are complicated"). To solve that problem, the practitioner only needs to know that "mutex.lock()" and "mutex.unlock()" orders reads/writes in a clearly defined manner. If the practitioner is wondering about the difference between load-acquire and load-relaxed, they've probably gone too deep.

> To solve that problem, the practitioner only needs to know that "mutex.lock()"

This is true, but they do not know that. If you do not give some kind of substantiation, they will shrug it off and go back to "nah this thing doesn't need a mutex", like with a polling variable (contrived example).

Re: Programming Language Memory Models

#20

Post by raphlinus »

raphlinus wrote: post #18

A GPU followup to this article. While on CPU sequentially consistent semantics are efficient to implement, that seems to be much less true on GPU. Thus, Vulkan completely eliminates sequential consistency and provides only acquire/release semantics[1]. It is extremely difficult to reason about programs using these advanced memory semantics. For example, there is a discussion about whether a spinlock implemented in te…

Also: it remains difficult to fully nail down the semantics of sequential consistency as well, especially when it's mixed with other memory semantics. Very likely next time Russ updates his article he should add a reference to Repairing Sequential Consistency in C/C++11[1].

[1]: https://plv.mpi-sws.org/scfix/full.pdf

Post reply on HN