Programming Language Memory Models • Hacker News Board

Re: Programming Language Memory Models

#21

Post by jqpabc123 » Tue, Jul 06, 2021, 8:09 PM UTC

dragontamer wrote: post #3

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…

Removing optimizations on "global" variables will leave the bug in Singleton objects (which are very similar to global variables, but the compiler doesn't know that they're global) --------- "Volatile" is close but not good enough semantically to describe what we want. That's why these new Atomic-variables are being declared with seqcst semantics (be it in Java, C++, C, or whatever you program in). That's the thing:…

which are very similar to global variables, but the compiler doesn't know that they're global

Since as you say, they are very similar, wouldn't it be reasonable to assume for access purposes that they are effectively global?

Re: Programming Language Memory Models

#22

Post by dragontamer » Tue, Jul 06, 2021, 8:12 PM UTC

jqpabc123 wrote: post #21

dragontamer wrote: post #3

Earlier quoted context omitted.

Removing optimizations on "global" variables will leave the bug in Singleton objects (which are very similar to global variables, but the compiler doesn't know that they're global) --------- "Volatile" is close but not good enough semantically to describe what we want. That's why these new Atomic-variables are being declared with seqcst semantics (be it in Java, C++, C, or whatever you program in). That's the thing:…

which are very similar to global variables, but the compiler doesn't know that they're global Since as you say, they are very similar, wouldn't it be reasonable to assume for access purposes that they are effectively global?

Lets do this example in Java (but it should be simple enough that C#, Python, Javascript and other programmers would understand it).

    public void myFunction(FooObject o){
        o.doSomething();
    }

How does the compiler know if "FooObject o" is a singleton or not? That's the thing about the "Singleton" pattern, you have an effective "global-ish" variable, but all of your code is written with normal pass-the-object style.

EDIT: If you're not aware, the way this works is that you call myFunction(getTheSingleton());, where "getTheSingleton()" fetches the Singleton object. myFunction() has no way of "knowing" its actually interacting with the singleton. This is a useful pattern, because you can create unit-tests over the "global" variable by simply mocking out the Singleton for a mock object (or maybe an object with preset state for better unit testing). Among other benefits (but also similar downsides to using a global variable: difficult to reason because you have this "shared state" being used all over the place)

Re: Programming Language Memory Models

#23

Post by dragontamer » Tue, Jul 06, 2021, 8:29 PM UTC

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…

GPU-spinlocks are a bad idea, unless the spinlock is applied over the entire Thread-group.

Even then, I'm pretty sure the spinlock is a bad idea, because you probably should be using GPUs as a coprocessor and enforcing "orderings" over CUDA-Streams or OpenCL Task Graphs. The kernel-spawn and kernel-end mechanism provides you your synchronization functionality ("happens-before") when you need it.

---------

From there on out: the GPU-low level synchronization of choice is the thread-barrier (which can extend out beyond a wavefront, but only up to a block).

--------

So that'd be my advice: use a thread-barrier at the lowest level for thread blocks (synchronization between 1024 threads and below). And use kernel-start / kernel-end graphs (aka: CUDA Stream and/or OpenCL Task Graphs) for synchronizing groups of more than 1024 threads together.

Otherwise, I've done some experiments with acquire/release and basic lock/unlock mechanisms. They seem to work as expected. You get deadlocks immediately on older hardware because of the implicit SIMD-execution (so you want only thread#0 or active-thread#0 to perform the lock for the whole wavefront / thread block). You'll still want to use thread-barriers for higher performance synchronization.

Frankly, I'm not exactly sure why you'd want to use a spinlock since thread-barriers are simply higher performance in the GPU world.

Re: Programming Language Memory Models

#24

Post by bullen » Tue, Jul 06, 2021, 8:31 PM UTC

In a 100 years the main languages used will still be C on the client (with a C++ compiler) and Java on the server.

Go has no VM but it has a GC. WASM has a VM but no GC.

Eveything has been tried and Java still kicks everythings ass to the moon on the server.

Fragmentation is bad, lets stop using bad languages and focus on the products we build instead.

"While I'm on the topic of concurrency I should mention my far too brief chat with Doug Lea. He commented that multi-threaded Java these days far outperforms C, due to the memory management and a garbage collector. If I recall correctly he said "only 12 times faster than C means you haven't started optimizing"." - Martin Fowler https://martinfowler.com/bliki/OOPSLA2005.html

"Many lock-free structures offer atomic-free read paths, notably concurrent containers in garbage collected languages, such as ConcurrentHashMap in Java. Languages without garbage collection have fewer straightforward options, mostly because safe memory reclamation is a hard problem..." - Travis Downs https://travisdowns.github.io/blog/2020/07/06/concurrency-co...

Re: Programming Language Memory Models

#25

Post by dragontamer » Tue, Jul 06, 2021, 8:38 PM UTC

electricshampo1 wrote: post #12

"Java and JavaScript have avoided introducing weak (acquire/release) synchronizing atomics, which seem tailored for x86." This is not true for Java; see http://gee.cs.oswego.edu/dl/html/j9mm.html https://docs.oracle.com/en/java/javase/16/docs/api/java.base...

Its not true in general. x86 CANNOT have weak acquire/release semantics. x86 is "too strong", you get total-store ordering by default.

If you want to test out weaker acquire/release semantics, you need to buy an ARM or POWER9 processor.

Re: Programming Language Memory Models

#26

Post by raphlinus » Tue, Jul 06, 2021, 8:38 PM UTC

dragontamer wrote: post #23

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…

GPU-spinlocks are a bad idea, unless the spinlock is applied over the entire Thread-group. Even then, I'm pretty sure the spinlock is a bad idea, because you probably should be using GPUs as a coprocessor and enforcing "orderings" over CUDA-Streams or OpenCL Task Graphs. The kernel-spawn and kernel-end mechanism provides you your synchronization functionality ("happens-before") when you need it. --------- From there…

In general spinlocks are a bad idea, but you do see them in contexts like decoupled look-back. As you say, thread granularity is a problem (unless you're on CUDA on Volta+ hardware, which has independent thread scheduling), so you want threadgroup or workgroup granularity.

In any case, I'm interested in pushing the boundaries of lock-free algorithms. It is of course easy to reason about kernel-{start/end} synchronization, but the granularity may be too coarse for some interesting applications.

Re: Programming Language Memory Models

#27

Post by skohan » Tue, Jul 06, 2021, 8:40 PM UTC

bullen wrote: post #24

In a 100 years the main languages used will still be C on the client (with a C++ compiler) and Java on the server. Go has no VM but it has a GC. WASM has a VM but no GC. Eveything has been tried and Java still kicks everythings ass to the moon on the server. Fragmentation is bad, lets stop using bad languages and focus on the products we build instead. "While I'm on the topic of concurrency I should mention my far to…

I'm sorry is this comment from 1998? I've been working in software for over a decade, and I haven't seen server work being done in Java in ages.

From my perspective, Go in the context of serverless programming seems to currently be the best choice for server-side programming.

In the next 20 years I expect Go will be supplanted by a language which is a lot like go (automatic memory management, simple, easy to learn & write and performant enough) but with the addition of algebraic data types, named parameters, and a slightly higher level of abstraction.

Re: Programming Language Memory Models

#28

Post by bullen » Tue, Jul 06, 2021, 8:47 PM UTC

skohan wrote: post #27

bullen wrote: post #24

In a 100 years the main languages used will still be C on the client (with a C++ compiler) and Java on the server. Go has no VM but it has a GC. WASM has a VM but no GC. Eveything has been tried and Java still kicks everythings ass to the moon on the server. Fragmentation is bad, lets stop using bad languages and focus on the products we build instead. "While I'm on the topic of concurrency I should mention my far to…

I'm sorry is this comment from 1998? I've been working in software for over a decade, and I haven't seen server work being done in Java in ages. From my perspective, Go in the context of serverless programming seems to currently be the best choice for server-side programming. In the next 20 years I expect Go will be supplanted by a language which is a lot like go (automatic memory management, simple, easy to learn &…

Infinite growth does not exist, everything peaks at some point. You have to wonder if a memory model from 2005 still kicks go's ass in 2021 how your your prediction that "there will always be something new and shiny to distract us from the focus we need to leverage the real value of the internet" will play out?

What have you built with go that is interesting?

Re: Programming Language Memory Models

#29

Post by dragontamer » Tue, Jul 06, 2021, 8:55 PM UTC

raphlinus wrote: post #26

dragontamer wrote: post #23

Earlier quoted context omitted.

GPU-spinlocks are a bad idea, unless the spinlock is applied over the entire Thread-group. Even then, I'm pretty sure the spinlock is a bad idea, because you probably should be using GPUs as a coprocessor and enforcing "orderings" over CUDA-Streams or OpenCL Task Graphs. The kernel-spawn and kernel-end mechanism provides you your synchronization functionality ("happens-before") when you need it. --------- From there…

In general spinlocks are a bad idea, but you do see them in contexts like decoupled look-back. As you say, thread granularity is a problem (unless you're on CUDA on Volta+ hardware, which has independent thread scheduling), so you want threadgroup or workgroup granularity. In any case, I'm interested in pushing the boundaries of lock-free algorithms. It is of course easy to reason about kernel-{start/end} synchroniza…

This is the first time I've heard of the term "decoupled look-back". But I see that it refers to CUB's implementation of device-wide scan.

I briefly looked at the code, and came across: https://github.com/NVIDIA/cub/blob/main/cub/agent/agent_scan...

I'm seeing lots of calls to "CTA_SYNC()", which ends up being just a "__syncthreads" (a simple thread-barrier). See: https://github.com/NVIDIA/cub/blob/a8910accebe74ce043a13026f...

I admit that I'm looking rather quickly though, but... I'm not exactly seeing where this mysterious "spinlock" is that you're talking about. I haven't tried very hard yet but maybe you can point out what code exactly in this device_scan / decoupled look-back uses a spinlock? Cause I'm just not seeing it.

----------

And of course: a call to cub's "device scan" is innately ordered to kernel-start / kernel-end. So there's your synchronization mechanism right there and then.

Re: Programming Language Memory Models

#30

Post by skohan » Tue, Jul 06, 2021, 8:56 PM UTC

bullen wrote: post #28

skohan wrote: post #27

Earlier quoted context omitted.

I'm sorry is this comment from 1998? I've been working in software for over a decade, and I haven't seen server work being done in Java in ages. From my perspective, Go in the context of serverless programming seems to currently be the best choice for server-side programming. In the next 20 years I expect Go will be supplanted by a language which is a lot like go (automatic memory management, simple, easy to learn &…

Infinite growth does not exist, everything peaks at some point. You have to wonder if a memory model from 2005 still kicks go's ass in 2021 how your your prediction that "there will always be something new and shiny to distract us from the focus we need to leverage the real value of the internet" will play out? What have you built with go that is interesting?

It's not about new and shiny. Programming is still a relatively new field when compared to other fields. For instance, mathematics and physics took centuries to land on the right way to formalize things.

C is maybe the only good programming language invented so far. Java was a failed attempt at improving C. I think we're rapidly converging on the second good programming language, and it's not going to have null pointer exceptions.