News for hackers. Stuff that matters.
Re:The memory models that underlie programming languages (2016) by gumby on Wednesday June 09, 2021 @09:53PM (#27455851)
Wow, I'm surprised I never ran across this excellent essay before.

I also liked the use of the term "memory model" in this case to mean conceptual model, because the metaphors and affordances of a language are what give (or restrict) its expressive power and the level of abstraction you can bring to bear. A mixed blessing.

Re:The memory models that underlie programming languages (2016) by kragen on Wednesday June 09, 2021 @10:00PM (#27455895)
Thanks, that means a lot! I think it kind of falls short of some of its initial promises, and clearly needs revision, but there are some good nuggets in there. As one example of what needs revision, I drew the diagrams after I wrote the text, and I realized that what I was describing in the text was far more complicated than what I really wanted to draw... but then never went back and revised the text.

If this is the kind of thing you like, you might find more things to your taste in http://canonical.org/~kragen/dercuano, which touches on, among other things, the bizarre memory model of the Zork Z-machine.

Re:The memory models that underlie programming languages (2016) by fjfaase on Thursday June 10, 2021 @03:29AM (#27457923)
Hi Kragen,

for a long time, I have been pondenring about a high-level 'programming' languages about structured data. It is by far finished, but I am attempting to deal with the problem of different memory models from the other end: starting with an ideal model trying to abstract from implementations.

I have not address the problem of transactions and cooperation yet. Often the problem with implementation of data models start becoming 'interesting' when several actors at the same time are querying and changing it, especially when the dimension of distribution is added.

https://github.com/FransFaase/DataLang

Re:The memory models that underlie programming languages (2016) by kragen on Thursday June 10, 2021 @10:51AM (#27461416)
This is fascinating! It looks like it's inspired by linear (or affine?) typing, but isn't quite the same thing?

It's definitely true that concurrency is a common source of such complications. Serialization is another one.

Re:The memory models that underlie programming languages (2016) by zestyping on Wednesday June 09, 2021 @10:32PM (#27456069)
Hi, Kragen!

Is Dercuano available as individual HTML pages that can be clicked around (and indexed by search engines)? So far I've only found it as a giant blob (PDF or tar) and I'm wondering why that seems to be its primary presentation.

Re:The memory models that underlie programming languages (2016) by kragen on Wednesday June 09, 2021 @10:40PM (#27456108)
Hi Ping! I miss you a lot! The primary representation of Dercuano is a giant blob both to improve the chances that copies of it will survive after I'm dead and to more clearly establish a publication date for purposes of patent prior art. The PDF isn't very good (I hacked together a PDF-rendering script with reportlab in five days before the deadline, and even the CSS for the HTML version is pretty amateurish) but there are a variety of places that can view or archive PDFs but not tarballs of HTML.

There's also an online mirror at https://dercuano.github.io/, which allows linking to pages like https://dercuano.github.io/topics/memory-models.html, but of course that depends on Microsoft's pleasure.

See also http://canonical.org/~kragen/derctuo/ for the sequel.

Re:The memory models that underlie programming languages (2016) by Cybotron5000 on Thursday June 10, 2021 @07:51AM (#27459575)
I’m only about half way through, but I’m finding it extremely helpful, clear and well-written (some of the terminology/ideas I’m not familiar with/are over my head, but I plan on going back over it again later and looking stuff up :) - Thanks so much!
Re:The memory models that underlie programming languages (2016) by kragen on Thursday June 10, 2021 @10:52AM (#27461424)
Maybe the stuff that seems over your head is just stuff I wrote poorly!
Re:The memory models that underlie programming languages (2016) by Cybotron5000 on Friday June 11, 2021 @07:41AM (#27471952)
Not at all! I’m obviously not qualified to say, but it seems to me to be a great overview of a very complicated topic - clear, concise, comprehensive and not patronising. Stuff I don’t understand off the bat I can always look up, but it gives me a framework to begin to hang stuff on/explore from. Even if you had written several tome-like textbooks you couldn’t have compensated for my ignorance of the basic principles of computer science/informatics/programming etc.! :)
Re:The memory models that underlie programming languages (2016) by tekknolagi on Thursday June 10, 2021 @11:57AM (#27462189)
This is a great teaching attitude. Thank you.
Re:The memory models that underlie programming languages (2016) by kragen on Thursday June 10, 2021 @12:03PM (#27462271)
Maybe if I keep trying I'll get good at teaching some day! So far my results have not been inspiring.
Re:The memory models that underlie programming languages (2016) by silentsea90 on Thursday June 10, 2021 @12:37AM (#27456703)
No offense but I do agree that the text is hard to read and understand and simpler sentences would be nicer.
Re:The memory models that underlie programming languages (2016) by kragen on Thursday June 10, 2021 @01:14AM (#27456905)
I have that problem a lot.
Re:The memory models that underlie programming languages (2016) by danielmarkbruce on Thursday June 10, 2021 @01:22AM (#27456960)
This book is (imo) hilariously good and explains thing well for engineering type folks: https://www.amazon.com/Sense-Style-Thinking-Persons-Writing-...
Re:The memory models that underlie programming languages (2016) by jcranmer on Thursday June 10, 2021 @12:02AM (#27456535)
As a compiler writer, when I hear the term "memory model", I immediately assume it's referring to a multithreaded memory model, and is going to discuss when writes are guaranteed to be made visible to other threads.

A better term for what's discussed here would be the "object model"--you're effectively describing how you would represent a conceptual object in different memory organization schemes.

Re:The memory models that underlie programming languages (2016) by Animats on Thursday June 10, 2021 @12:24AM (#27456628)
Yes. But we mostly have one memory model today - one big flat memory space, because C.

There are other approaches, but most of the clever ones died off. x86-32 has lots of interesting things you can do with segments. Nobody used that stuff, so amd64 has flat memory.

Burroughs once had a memory system that worked like pathnames. Think of an address as being "job/program/module/function/variable[n]", not a number. User programs could not see the physical memory address. This allowed the OS to do swapping and compaction underneath the program. The hardware would catch subscripting out of range. Worked fine, never caught on. Today we do that with collection classes, rather than at the OS/hardware level.

Memory models are making a comeback, as we hit the limits of caches. Machines with some memory shared, some memory unshared, and some slower if shared have appeared.

Re:The memory models that underlie programming languages (2016) by tomp on Thursday June 10, 2021 @05:45AM (#27458820)
> But we mostly have one memory model today - one big flat memory space, because C.

Not really. C (or C++) memory model isn’t really well-defined yet, there’s still fights going on regarding e.g. values out of thin air (or maybe they’ve been resolved recently, I haven’t checked).

In contrast, Java has a well-defined memory model without any undefined behaviour, that can get quite tricky at times (e.g. what happens if you write to a final field (!!) (you first need to make it non-final using runtime reflection operations or use the Unsafe module)).

Re:The memory models that underlie programming languages (2016) by moonchild on Thursday June 10, 2021 @06:06AM (#27458943)
Hans Boehm (author of the c memory model) criticizes the java memory model https://www.usenix.org/legacy/event/hotpar11/tech/final_file...
Re:The memory models that underlie programming languages (2016) by tomp on Thursday June 10, 2021 @06:57AM (#27459238)
Interesting, thanks! I'll read the paper in its entirety later, but suffice to say, me and Hans disagree about the fact that all data races are errors, or what a reasonable compiler is.

For example, take this code:

    // thread 1:                    // thread 2:
    with lock(counter_lock):        with lock(counter_lock):
      print(counter)                  atomic { counter += 1 }
There's one of two possible linear executions of this code: either you print the old value of the counter (n), or the new value (n+1). That's it.

I argue that this code is correct, and should remain legal, even if locks are elided (provided that the write to counter is actually atomic, i.e. doesn't result in a torn write / read). In fact, if the lock is implemented as a spin lock, that's exactly what happens even with locks! I also think that no compiler is "reasonable" if it breaks this code, or invalidates the whole program ("undefined behaviour means anything can happen").

Edit: He actually mentions a similar problem in the paper, and argues that it's valid for the compiler to "optimize" the code and break it. I think the original problem here is that C++ compilers implicitly assume the right to perform global optimisations. I would argue that it's better to move to a local optimisations model, because it's easy to modify the code to make it locally optimisable (just read all variables and make local copies of them, and adopt Rust-like ownership data model for structs/arrays etc. so the programmer can communicate to the compiler the fact that the block of memory is local).

Re:The memory models that underlie programming languages (2016) by tialaramex on Thursday June 10, 2021 @12:00PM (#27462232)
The pseudo-code you listed does not contain a data race by the author's definition since there is no simultaneous read/write assuming words have their usual meanings. As a result I believe it would not be UB in C++ today.

The protest that languages like C or C++ should just leave Undefined Behaviour alone so it will Do What You Mean is probably almost as old as I am and even more futile. You don't actually want that, the languages go as fast as they do because optimising compilers assume undefined behaviour can't happen.

The Java model tries to deliver what you wanted here and it fails. You still get surprising behaviour sometimes (defeating the objective of ensuring that the behaviour with data races is something you can reason about) but now you can't do certain optimisations that seem otherwise reasonable because they defy the promises the model made.

There are people in this space, who believe if they tighten the model even further they can get rid of the surprising behaviour while retaining most performance. That's where OCaml seems to be going. Maybe it will work.

The Rust model is the opposite, Rust evades the problem with its rule about modification XOR multi-reference. Either one thread can write this data, or one or more threads might read the data, but never both and thus no data races. Instead of ensuring you're able to understand the residual data races (and maybe conclude they're "benign") Rust ensures your program doesn't have any.

Re:The memory models that underlie programming languages (2016) by tomp on Thursday June 10, 2021 @01:15PM (#27463075)
The pseudocode isn't UB because of the locks, but my argument is that it shouldn't be UB even if the locks were gone. In that case, there is a simultaneous read/increment, but it's still obviously linearizable exactly the same way as with locks, so it still shouldn't be UB. (Or, if the memory fence caused by atomic increment instruction makes it non-UB, then just imagine overwriting a flag without any fences instead.) In Rust it's not even possible to write such code.

Another example is Figure 5 in this paper [1] (referenced from Bohem's paper above):

    x = y = 0
    
    // thread 1:         // thread 2:
    a = x;               c = y;
    b = x;               x = c;
    if (a == b)
      y = 1;
My point is that the assumption that a == b is invalid if x is a global variable. That's not a valid assumption for the compiler to make, ever, unless it can prove that x isn't accessed from different threads (as a human would have to, to manually perform the optimisation).

I haven't been tracking OCaml's progress too closely (multicore is just taking too long), but hopefully it's going in this direction... if you've any relevant references / descriptions of their memory model, let me know!

https://www.ccs.neu.edu/home/wahl/Teaching/Software-Model-Ch...

Re:The memory models that underlie programming languages (2016) by tialaramex on Thursday June 10, 2021 @02:21PM (#27463760)
> In Rust it's not even possible to write such code.

What does "such code" mean though? Rust won't let you say that your mutable variables are just shared between threads, because that's unsafe. But if you say OK, I want atomic data types (and so they lack tearing and other things you were bothered about) then you can clone an Arc of them, and write code to manipulate the atomics whose consequences are just as under specified. It's just that now you have to spell out that this is what you wanted, writing e.g. std::sync::atomic::Ordering::Relaxed

If you later complain to me that this code surprised you because the memory ordering wasn't what you expected, I will point at that symbol. If you wanted some specific ordering then "Relaxed" was wrong.

> My point is that the assumption that a == b is invalid if x is a global variable.

No it isn't? This is an important optimisation, which you would prefer to sacrifice rather than just writing what you mean in the first place.

> if you've any relevant references / descriptions of their memory model, let me know!

https://kcsrk.info/papers/pldi18-memory.pdf

Re:The memory models that underlie programming languages (2016) by steveklabnik on Thursday June 10, 2021 @03:19PM (#27464478)
Re:The memory models that underlie programming languages (2016) by tialaramex on Thursday June 10, 2021 @08:32PM (#27467877)
Sure, however now your atomic has 'static lifetime so it lives forever and that's sort of cheating. The reference counter means nobody in particular needs to be in charge of cleaning up, whoever has it last will drop it. Call it personal preference.

Also, is the broken kinda of look of your blog an aesthetic choice or a bug? Is "![Today%20is%20my%20first" really what that ought to display under the title ? I feel like it probably isn't.

Re:The memory models that underlie programming languages (2016) by steveklabnik on Thursday June 10, 2021 @09:06PM (#27468130)
I don't see how 'static is cheating, that's the semantic you want: to be able to live as long as the various threads. If you used scoped threads you wouldn't need 'static, but those are less general, so I didn't get into it.

No, it's just buggy. :( Thanks for mentioning though, that bug is not one I had seen just yet.

Re:The memory models that underlie programming languages (2016) by tialaramex on Thursday June 10, 2021 @11:33AM (#27461895)
> C (or C++) memory model isn’t really well-defined yet

To the limited extent this is true, it's about pragmatism.

In Java if the situation is that correct Java now has to be 5% slower then a new JRE is shipped that's 5% slower and some people are unhappy but life goes on.

In C++ if the situation is that correct C++ now has to be 5% slower then C++ programmers will mostly demand an "Incorrect-but-faster" setting on their compiler, and they continue to use the faster code.

So, in practice the fine details of the memory model must reflect the practical reality of the physical computers or else they're useless.

Re:The memory models that underlie programming languages (2016) by secondcoming on Thursday June 10, 2021 @03:52AM (#27458098)
> But we mostly have one memory model today - one big flat memory space, because C.

This is not what is meant by 'memory model'. What is really specifies is how memory operations can ordered and when a write made by one thread is seen by another, acquire, release, relaxed etc.

For example: https://en.cppreference.com/w/cpp/atomic/memory_order

Re:The memory models that underlie programming languages (2016) by secondcoming on Thursday June 10, 2021 @06:00AM (#27458922)
Downvoted. Unbelievable. Here's the Java Memory Model: https://en.wikipedia.org/wiki/Java_memory_model
Re:The memory models that underlie programming languages (2016) by masklinn on Thursday June 10, 2021 @06:21AM (#27459033)
That’s not what Gp is talking about. « Memory model » in a multithreaded context is the guarantees about memory-level interaction of concurrent threads.
Re:The memory models that underlie programming languages (2016) by tsimionescu on Thursday June 10, 2021 @06:18AM (#27459017)
I think the flat memory model predates C significantly. Didn't the earliest LISP (195x) already have a flat, garbage collected memory? In fact, C is one of the few languages which actually exposes the possibility of a segmented memory model to programs.
Re:The memory models that underlie programming languages (2016) by kaba0 on Thursday June 10, 2021 @03:49AM (#27458073)
This topic is outside the realm of my knowledge, but at the language level, we do have that (compacting GCs), and I think we do have it at the OS level as well due to virtual memory (but hardware accelerated TLB).
Re:The memory models that underlie programming languages (2016) by kragen on Thursday June 10, 2021 @12:14AM (#27456584)
Yeah, "memory model" is a terribly overloaded term (myself, I think small, compact, medium, large, huge), and "object model" has the same problem. Maybe I should just generate a random neologism.
Re:The memory models that underlie programming languages (2016) by gumby on Thursday June 10, 2021 @06:01AM (#27458924)
In this case I liked this particular overloading of the term because it caused me to reset certain assumptions.