Programming language-independent memory models

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Programming language-independent memory models

Andrew Haley
Do such things exist?  Java and C++ have their own, which are mostly
compatible but not quite.  Any language implemented in C++ will
necessarily implement the C++ memory model, which (perhaps)
unfortunately implies that if it executes any data races the whole
program becomes undefined.  A programming language interpreter written
in C++ could get around that by using atomic types for everything, but
that's rather unpleasant.  The Java memory model is somewhat more sane
than that, and might provide a better base.

Defining a memory model is a substantial task.  It would be nice, from
a blue sky point of view, to be able to pull a memory model off the
shelf and say "Language X uses the Y memory model" and leave it at
that, pausing only to describe Programming Languages X's mapping from
its own operators to those of the Y memory model.  I'll grant that
this is difficult, because programming language semantics play a large
part in the way a language uses memory.  However, that's surely easier
than starting with nothing.

I'm wondering if, in the wonderful world of polyglot systems and
applications, there has been any work in this area.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Andrew Haley
On 04/08/17 18:32, JF Bastien wrote:
> CPUs each have a memory model, formalized or not. x86, ARM and POWER each
> have formalizations.
> Defined mappings have been written from C++ to them too:
> https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

Yes, thanks.  We implemented HotSpot on AArch64, so I am familiar with
how that processor works, and I used Peter Sewell's mappings for inspiration.

> We're currently in the process of defining a formal memory model for
> JavaScript and WebAssembly:
>
> https://github.com/tc39/ecmascript_sharedmem/issues/88
>
> This is different from other language memory models because it's meant as a
> compilation target, closer to a virtual ISA (compilers target them) than
> something programmers use directly.

That's useful, thanks.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Hans Boehm
In reply to this post by Andrew Haley
The problem is that there are actually semi-rational reasons for the differences between the C++ and Java memory models. And we tried to make the two as similar as possible were such reasons didn't exist.

Java wanted to avoid undefined behavior (for the core language) at pretty much all costs. The costs unfortunately include:

- Fences in object constructors
- New (for C++) optimization constraints, e.g. the inability to rematerialize spilled registers from globals
- Serious definitional problems with out-of-thin-air results for basically every program (as opposed to just memory_order_relaxed accesses in C++)

These were probably reasonable tradeoffs for Java, especially at the time. But I don't think they would fly for C or C++.

I'm not sure that using memory_order_relaxed in a Java interpreter is that much of an issue, given that JIT-compiled code would still benefit from the weaker Java semantics. For the few cases for which this is seriously suboptimal, e.g. long accesses on mips32, you could resort to assembly code.

On Fri, Aug 4, 2017 at 10:18 AM, Andrew Haley <[hidden email]> wrote:
Do such things exist?  Java and C++ have their own, which are mostly
compatible but not quite.  Any language implemented in C++ will
necessarily implement the C++ memory model, which (perhaps)
unfortunately implies that if it executes any data races the whole
program becomes undefined.  A programming language interpreter written
in C++ could get around that by using atomic types for everything, but
that's rather unpleasant.  The Java memory model is somewhat more sane
than that, and might provide a better base.

Defining a memory model is a substantial task.  It would be nice, from
a blue sky point of view, to be able to pull a memory model off the
shelf and say "Language X uses the Y memory model" and leave it at
that, pausing only to describe Programming Languages X's mapping from
its own operators to those of the Y memory model.  I'll grant that
this is difficult, because programming language semantics play a large
part in the way a language uses memory.  However, that's surely easier
than starting with nothing.

I'm wondering if, in the wonderful world of polyglot systems and
applications, there has been any work in this area.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Andrew Haley
On 05/08/17 06:04, Hans Boehm wrote:

> The problem is that there are actually semi-rational reasons for the
> differences between the C++ and Java memory models. And we tried to make
> the two as similar as possible were such reasons didn't exist.
>
> Java wanted to avoid undefined behavior (for the core language) at
> pretty much all costs. The costs unfortunately include:
>
> - Fences in object constructors
> - New (for C++) optimization constraints, e.g. the inability to
> rematerialize spilled registers from globals

Really?  I didn't realize that was a change, and I suspect that
compilers still do it.

> - Serious definitional problems with out-of-thin-air results for
> basically every program (as opposed to just memory_order_relaxed
> accesses in C++)
>
> These were probably reasonable tradeoffs for Java, especially at the time.
> But I don't think they would fly for C or C++.

OK, thanks for that explanation.  But there are many languages around,
and many of them allow multiple threads, and many of those allow
concurrent access to shared state.  There is no way that language
designers are going to be able to put in the amount of work needed to
define a memory model for their language.  If they run on x86 they'll
usually be fine, of course!  Perhaps what they need is some kind of
boilerplate for a language memory model.

> I'm not sure that using memory_order_relaxed in a Java interpreter is that
> much of an issue, given that JIT-compiled code would still benefit from the
> weaker Java semantics. For the few cases for which this is seriously
> suboptimal, e.g. long accesses on mips32, you could resort to assembly code.

That makes sense.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Hans Boehm

On Mon, Aug 7, 2017 at 1:46 AM, Andrew Haley <[hidden email]> wrote:

>
> On 05/08/17 06:04, Hans Boehm wrote:
> > The problem is that there are actually semi-rational reasons for the
> > differences between the C++ and Java memory models. And we tried to make
> > the two as similar as possible were such reasons didn't exist.
> >
> > Java wanted to avoid undefined behavior (for the core language) at
> > pretty much all costs. The costs unfortunately include:
> >
> > - Fences in object constructors
> > - New (for C++) optimization constraints, e.g. the inability to
> > rematerialize spilled registers from globals
>
> Really?  I didn't realize that was a change, and I suspect that
> compilers still do it.
Just to be clear: Java does not allow rematerializing spilled registers from
globals. C++ does. AFAIK compilers generally follow the language-
appropriate rules.

>
> > - Serious definitional problems with out-of-thin-air results for
> > basically every program (as opposed to just memory_order_relaxed
> > accesses in C++)
> >
> > These were probably reasonable tradeoffs for Java, especially at the time.
> > But I don't think they would fly for C or C++.
>
> OK, thanks for that explanation.  But there are many languages around,
> and many of them allow multiple threads, and many of those allow
> concurrent access to shared state.  There is no way that language
> designers are going to be able to put in the amount of work needed to
> define a memory model for their language.  If they run on x86 they'll
> usually be fine, of course!  Perhaps what they need is some kind of
> boilerplate for a language memory model.
IMHO, the closest we have that is actually solid and understandable
is the basic DRF model, with undefined semantics for data races.
This was never actually that expensive on x86, and it seems to be getting
more affordable on ARM as well. But my impression is that it'll never fly
on a GPU.

We know how to correctly add acquire/release atomics, though that
mixed model becomes far more complicated and unintuitive.

But almost everyone seems to feel the need to throw in some kind
of relaxed atomics or defined behavior for data races, at which point
things get flaky, and a universal design seems unlikely to me.

>
> > I'm not sure that using memory_order_relaxed in a Java interpreter is that
> > much of an issue, given that JIT-compiled code would still benefit from the
> > weaker Java semantics. For the few cases for which this is seriously
> > suboptimal, e.g. long accesses on mips32, you could resort to assembly code.
>
> That makes sense.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Andrew Haley
On 08/08/17 20:10, Hans Boehm wrote:

> IMHO, the closest we have that is actually solid and understandable
> is the basic DRF model, with undefined semantics for data races.
> e.g. sections 2+3 from http://dl.acm.org/citation.cfm?id=1375581.1375591 .
> This was never actually that expensive on x86, and it seems to be getting
> more affordable on ARM as well. But my impression is that it'll never fly
> on a GPU.
>
> We know how to correctly add acquire/release atomics, though that
> mixed model becomes far more complicated and unintuitive.
>
> But almost everyone seems to feel the need to throw in some kind
> of relaxed atomics or defined behavior for data races, at which point
> things get flaky, and a universal design seems unlikely to me.

Mmm, okay.  I was guessing that might be the situation, and it's very
useful to have it confirmed.  I'm sure that undefined behaviour (in
the unconstrained sense) for data races isn't going to be acceptable
for most programming languages.  The problem is, I suppose, that
specifying exactly what may occur in the presence of data races is
necessarily dependent on the semantics of each programming language.

There are some opportunities for research here.

Thanks.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Andrew Haley
On 09/08/17 10:54, Andrew Haley wrote:
> On 08/08/17 20:10, Hans Boehm wrote:
>> IMHO, the closest we have that is actually solid and understandable
>> is the basic DRF model, with undefined semantics for data races.
>> e.g. sections 2+3 from http://dl.acm.org/citation.cfm?id=1375581.1375591 .

Also at www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Stuart Monteith
Hello,
  We sort of already have a programming language independent memory
model, which is the Java memory model applied on to the other
languages the JVM can host. Furthermore, with Graal, is there more
scope now for there to be issues with ported languages?

BR,
  Stuart


On 9 August 2017 at 10:56, Andrew Haley <[hidden email]> wrote:

> On 09/08/17 10:54, Andrew Haley wrote:
>> On 08/08/17 20:10, Hans Boehm wrote:
>>> IMHO, the closest we have that is actually solid and understandable
>>> is the basic DRF model, with undefined semantics for data races.
>>> e.g. sections 2+3 from http://dl.acm.org/citation.cfm?id=1375581.1375591 .
>
> Also at www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Andrew Haley
On 10/08/17 09:42, Stuart Monteith wrote:
> Hello,
>   We sort of already have a programming language independent memory
> model, which is the Java memory model applied on to the other
> languages the JVM can host.

Sort of, I suppose, but it depends on how the language is mapped on
to bytecode.  It's a start.

> Furthermore, with Graal, is there more
> scope now for there to be issues with ported languages?

That's up to the people using Graal to run other languages.  Graal
follows the JMM in its middle end (or at least doesn't transform
conforming code into non-conforming code) but front ends don't have to
do so.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Programming language-independent memory models

Martin Buchholz-3
In reply to this post by Andrew Haley


On Fri, Aug 4, 2017 at 10:18 AM, Andrew Haley <[hidden email]> wrote:
Any language implemented in C++ will
necessarily implement the C++ memory model, which (perhaps)
unfortunately implies that if it executes any data races the whole
program becomes undefined.  A programming language interpreter written
in C++ could get around that by using atomic types for everything, but
that's rather unpleasant.

I continue to have a mental model where every ordinary java field maps to a relaxed atomic in C++ (disregarding the weird non-atomicity of long and double), so a C++ interpreter for Java that used C++ atomics pervasively seems very natural to me.  No C++ undefined behavior!  Java race detectors can still detect concurrent accesses without happens-before, but there is never a data race in the C++ sense.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest