Hacker News Reader

Comment by Animats | Hacker News Reader

Rust has an interesting, and somewhat difficult, memory model.

First, there's the single ownership tree. Single ownership is checked by the borrow checker. You can have only one mutable reference to a data object at a time, and that's also checked by the borrow checker. If you can stay within that model, if the program compiles, it will probably work at the data access level.

But then there are all the escape hatches.

There's "Rc", which is reference counting for read-only use. This works fine for immutable objects, but not for mutable ones.

There's "Cell" and "RefCell". These allow multiple ownership, and only one mutable access at a time. Request mutable access via two routes and you get a panic, or an error if you use try_borrow(); The static analysis of the borrow checker is not able to figure out when you're headed for trouble via this route.

There's "Arc" and "Mutex", which allows access across thread boundaries. Request access via two routes in the same thread, and you deadlock.

Designing the data structures for something tightly coupled with concurrency, like a window manager or a game, is difficult.

View on HN

"Memory model" is a term with a lot of different, but partially overlapping, meanings. The one being used in the article only concerns the logical arrangement of data, not rules about ownership and life span.

For the purposes of this article, Rust's memory model is no different from that of Haskell or C++: mostly what the article dubs the "lisp memory model", with some excursions into things like the magnetic tape memory model.

It's worth being pedantic here because, if you don't recognize what TFA means by "memory model", you're maybe not well positioned to recognize the deeper insight about computing that it's trying to present.

Right. This is not what most people these days mean by "memory model" and indeed what I expected based on the date was an article about Consistency Models, maybe talking about the C++ model, the Java model, how they relate to hardware.

I think the article doesn't end up offering a deep insight because at a theoretical level all of these are equivalent (which it acknowledges) and at a practical level what matters is performance. And the practical implications depend on the physical manifestation of the computer. That's an electronics thing not a programming thing.

Pointer chasing was a plausible strategy when your physical computer takes a very similar amount of time to read the next sixty-four bytes from RAM versus chasing pointers to eight sets of eight bytes randomly sprayed around the machine. But today that's not just "a bit slower" it can be literally thousands of times slower.

Because today the next sixty-four bytes are probably in your nearby cache, whereas hopping around madly will cause loads from all the way over in the DRAM, and that takes forever. Worse, with pointer chasing you are waiting for one load, to get the address for the next load. So you don't even get to schedule all the waiting up front and get on with something else in parallel, it's just a series of stalls.

On one level, yes, that's true. On another level, I think you may have left out the human factor. To me, the most important thing about these sorts of models is that they're mental models - they don't govern how the computer language works so much as they govern how the computer programmer works.

For my part, I think about very data (and, by extension, memory) differently depending on whether I'm working in Java or Forth (admittedly it's been a while) or SQL or APL (admittedly not much experience here, unless you're willing to charitably allow me to count numpy). Apache Spark is perhaps yet another model; I'm not sure how to reconcile it with the six in the article. And the different ways of thinking lead to fundamentally different approaches to domain modeling when I'm working in each language.

Reading the article actually helped me understand another angle to my disdain for object-relational modeling: By trying to hack the relational database into being just an object store, you end up sacrificing the unique data modeling possibilities that the relational model offers, and replace it with a rather poor implementation of object graphs. It's difficult for me to see that sort of thing as a clear win. If you want Gemstone, just use Gemstone.

Right but you're talking about an abstraction and the abstraction will leak at least somewhat.

A modern language can present you with what appears to be a doubly linked list, but is actually just a veneer over a data structure that actually performs well on the hardware. But of course you'll write programs that treat it like a linked list, so they'll have markedly worse performance than was necessary and worse, you may try to "improve" this based on your erroneous mental model and make things even worse.

I think that's where you got to with ORM too. The object store is an abstraction, but it somewhat leaks the fact that there's actually a relational database underneath. If you really just wanted an object store, this will be slower and clunkier than it should be, and if you really wanted a relational database you shouldn't have ORM.

So this is the problem, exposing the right abstractions. Making easy things easy, and yet not making difficult things impossible. Trying to discourage the programmer from using a huge fixed size array and a counter when what they actually needed was a growable vector, but not preventing them from using that fixed size array with a counter if that genuinely is the correct way to solve their problem...

These are very deep insights; thank you.

SPARK is weird; to the extent that I understand it, it's sort of more like make than like any conventional programming language.

I think the lifetime stuff is a bit fuzzy: count it in, count it out? I mean, what I'm calling the "Lisp memory model" has the crucial advantage that you can run a garbage collector, or you can do C++-style or Rust-style ownership to manage deallocation, which is not really a thing that makes sense with parallel arrays or nested records.

I don't know about nested records, but you most certainly can garbage collect data that's structured using the parallel arrays model. Look at numpy.

What I mean is that, though you can garbage collect a whole array, if you have an index array X such that Y[X[i]] contains the Y of entity i, the runtime can't automatically compact Y to remove the indices to which X does not point, because you could generate indices into Y in some other way, for example by counting up from 0. Automatically compacting Y in such a way would be the parallel-arrays equivalent of garbage collection in the Lisp memory model.

It's not like the lisp runtime is going to notice that you won't be using specific values anymore and start chopping them out of the middle of your lists, or the Java runtime is going to do that with specific fields in a live object.

Exactly!

So how is that different from Fortran arrays, then?

In the Lisp memory model, we map a conceptual entity to a memory address where we allocated a block to hold data about the entity. With parallel (Fortran) arrays, we map a conceptual entity to an index at which data is stored about the entity in various arrays.

In the first case, forgetting about an entity so we can reuse the memory is just deallocating a block. This is relatively straightforward, to the point that we can automate it with a garbage collector—though it's not so straightforward that Valgrind never finds bugs when we do it by hand.

In the second case, forgetting about an entity is not impossible, but is generally considerably more involved. Even in the relational model, which one could reasonably claim is a sort of systematization or rationalization of parallel arrays, lifetime management with foreign keys is sometimes tricky.

With a pure parallel-arrays model, you don't have any pointers/references, so you can't really run a garbage collector at all. (However, for example, Microsoft BASIC-80 had a kind of garbage collector for strings, despite its semantic model at the user level being devoid of any kind of referencing.) With something like Numpy, you can run a garbage collector, but your use of parallel arrays prevents it from reclaiming space dedicated to data about forgotten entities. Instead, it can reclaim space dedicated to forgotten attributes.

Yes I have found that Rust's ownership system works really well for single-threaded cases, especially when you can get away with a functional-ish programming style, but when you have large amounts of data which has to be shared between different parts of the program it starts to get tricky.

As you mentioned game programming, one common approach there is to have large arenas of structured memory which you use thread-pools to dispatch work over. I know there are some libraries which do this in Rust, but it seems like there's room for some language innovation here to figure out a memory model which would make this style of programming simple and ergonomic while maintaining safety

Is it really different from C though? (But with some runtime intervention instead of UB)

Rc and Arc are maintaining the “be sure that you'll only free this once” invariant automatically. In C you have the same invariant, you just have have to maintain it by yourself (or use an ad hoc reference counting mechanism) and if you don't it's a double free (UB). And in both cases you are responsible ensure the memory is freed at least once.

Mutex ensure you don't perform one read and one write at the same time. This is also forbidden by the C memory model and you'll probably end up using a mutex too (or other concurrency primitives) with the exact same risk of deadlock.

C allows much more flexibility wrt lifetimes than does rust.

For example: a common pattern in video games is the frame-local allocation. You (cheaply) allocate some object at the beginning of a frame. Share references to it all over the place. At the end of the frame, you (cheaply) free all the objects that were allocated in this manner. This cannot really be expressed in terms of rust's ownership system.

More generally, rust enforces local correctness, while c allows for global correctness (a weaker condition). Consider, as a simpler example, this c function which I write frequently:

  char *tmpstr(void) {
   static char buf[16][1024];
   static int i = 0;
   char *ret = buf[i];
   i = (i+1) % 16;
   return ret;
  }

This function is not locally correct; in a vacuum, it is impossible to say whether this function violates invariants. (Ignoring the problem of overflowing the 1024-byte buffer.) There are many programs using this function which are correct; then, there are some programs which call this function more than 16 times in a row and end up with undesirable behaviour as a result.

Rust requires that every function be locally correct. Papering over some details: for any sound function f and hole-containing program P[_], if P[f] is well-typed then P[f] is sound; that means that it's always meaningful to consider f without considering the context in which it will be called. There is no such guarantee in c.

As a sound language, this is a very useful attribute for rust to have, because it means that libraries can be meaningfully type-checked (not to mention it significantly simplifies the type system), but it would be naive to say that rust simply formalizes the ownership model you would have used anyway in c.

You can use your own allocator in Rust, with your own rules, OR you can use static arrays and then just reset aray length to zero at the end of frame.

Your function is easy to write in (unsafe!) Rust:

https://play.rust-lang.org/?version=stable&mode=debug&editio...

  use lazy_static::lazy_static; // 1.4.0
  use std::mem;

  lazy_static! {
    static ref BUF: [String; 16] = [
      String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024),
      String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024),
      String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024),
      String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024), String::with_capacity(1024)
    ];
    static ref BUF_INDEX: usize = 0;
  }

  fn tmpstr() -> &'static mut String { 
   let index_ptr: * const usize = &*BUF_INDEX;
   let index: &'static mut usize = unsafe { mem::transmute(index_ptr) };

   let buf_ptr: * const String = &BUF[*index];
   let ret: &'static mut String = unsafe { mem::transmute(buf_ptr) };

   ret.truncate(0);

   *index = (*index + 1usize) % BUF.len();
   
   return ret;
  }

  fn main(){
    let s1 = tmpstr();
    s1.push_str("Hello, world!");

    let s2 = tmpstr();
    s2.push_str("And hello world again!");

    dbg!(s1, s2);
  }

BTW: It's very good idea for embedded systems.

Yes, of course you can express this in rust. The topic at hand is whether it can be expressed in terms of rust's ownership policies. Your example shows that it cannot; it returns an object of static lifetime, avoiding the issue completely.

The topic at hand was about the comparison between C and Rust in terms of memory model. Ownership policies are one restriction safe Rust uses to ensure that the user is adhering to its memory model, but Rust is not limited to safe Rust and you can op-out ownership policies if you use raw pointers.

The difference between Rust and C in terms of memory model isn't ownership, it's “mutable xor shared”.

I cannot understand your question about "ownership policies". Rust have only one ownership policy: one owner per object.

It's possible to use pointers to circumvent the restriction and then control when object is destructed using ManuallyDrop[0], so burden of memory bookkeeping will be shifted from Rust compiler to the programmer.

[0]: https://doc.rust-lang.org/core/mem/struct.ManuallyDrop.html

But String is heap allocated, right?

Can you just declare a static array and return a pointer pointing to any part of it? Like in the C example?

BUF is also visible to other parts of the program, correct? If so, it's not quite similar to the C example.

> Can you just declare a static array and return a pointer pointing to any part of it? Like in the C example?

Indeed:

    lazy_static! {
      static ref BUF: [[u8;1024]; 16] = [
        [0;1024], [0;1024], [0;1024], [0;1024],
        [0;1024], [0;1024], [0;1024], [0;1024],
        [0;1024], [0;1024], [0;1024], [0;1024],
        [0;1024], [0;1024], [0;1024], [0;1024]];
      static ref BUF_INDEX: usize = 0;
    }

(You'll need to re-implement a `push_str` method on arrays yourself though)

> BUF is also visible to other parts of the program, correct? If so, it's not quite similar to the C example.

No, because it's not marked as `pub`, nobody outside the current module can access it.

String is heap allocated by default, but String can be made from raw pointer to buffer and buffer length: https://doc.rust-lang.org/std/string/struct.String.html#meth... .

Yes, of course. BTW: You can use a c2rust converter to convert a C code to it exact equivalent in Rust.

No, buf is not exported, so it's "static" in C terminology.

> No, buf is not exported, so it's "static" in C terminology.

Yes, I know that is not exported. What I wanted to say is that in the C example, no one outside tmpstr(void) can access static char buf[16][1024].

In the Rust example I can access static ref BUF from fn main() function, for example.

> In the Rust example I can access static ref BUF from fn main() function, for example.

Only because in that simple example, BUF was defined directly in the main module.

In a more realistic exemple, BUF and tmpstr would belong to their own module, with only tmpstr being exported (and then accessible). See: https://play.rust-lang.org/?version=stable&mode=debug&editio...

> C allows much more flexibility wrt lifetimes than does rust.

Because C does not have lifetimes at all, or ownership as a formal langage concept, and thus does not run head first into the completeness problem.

Which is one of unsafe’s use cases: when the compiler can’t prove the code is correct (because there will always be correct programs the compiler can’t prove, and there are currently a fair bit of them), and you can, and there are no suitable safe alternatives, you use unsafe.

> For example: a common pattern in video games is the frame-local allocation. You (cheaply) allocate some object at the beginning of a frame. Share references to it all over the place. At the end of the frame, you (cheaply) free all the objects that were allocated in this manner. This cannot really be expressed in terms of rust's ownership system.

Of course it can, though it requires APIs which are not there (in the stdlib, yet): a frame local allocator and custom per-object allocator. All frame-local objects use that and thus keep a reference to the allocator.

And it avoids storing frame-local objects in locations which outlive the frame.

> This function is not locally correct; in a vacuum, it is impossible to say whether this function violates invariants.

That is also a use-case for unsafe: an unsafe function is one for which the caller is responsible for checking invariants.

This is unsafe anyway because modifying globals is unsafe to start with.

>> cannot really be expressed in terms of rust's ownership system

> Of course it can

You cannot share objects using rust's ownership system.

Interior mutability involves an unacceptable performance hit (and doesn't actually allow you to share anything). And if you use shared indices into a centralized array, then you have blinded the ownership system, creating pointers that it cannot make sense of.

>> This function is not locally correct; in a vacuum, it is impossible to say whether this function violates invariants.

> That is also a use-case for unsafe: an unsafe function is one for which the caller is responsible for checking invariants.

That's exactly right, and was my thesis; rust's type system does not allow you to prove the correctness of such a function, because it is neither correct nor incorrect without context. 'Unsafe', as a subversion of the type system which allows unsound behaviour, is completely uninteresting wrt the topic at hand; the comparison is a purely theoretical one between non-'unsafe' rust—that is, rust's ownership model—and c.

Interior mutability does not have uniform performance characteristics, Cell has a very different cost (that is, none) over RefCell (which involves checking a flag when accessing). Etc etc.

Unsafe does not allow unsound behavior, or rather, it lets you write unsound behavior but that is a bug. You still have to uphold various invariants in unsafe code. It’s there for when you know you can, but the compiler cannot, which is an inherent property of any sound system.

> Unsafe does not allow unsound behavior, or rather, it lets you write unsound behavior but that is a bug. You still have to uphold various invariants in unsafe code. It’s there for when you know you can, but the compiler cannot, which is an inherent property of any sound system.

I don't understand what you're saying here.

Rust-without-'unsafe' is a sound language; i.e. any program which types will be unable to violate runtime invariants.

Rust-with-'unsafe' is an unsound language; i.e. there are programs which type but yet violate runtime invariants.

That is a bug in those programs—sure, yes, of course. It is not a bug in rust; it is the language functioning as intended. However the topic at hand is the relationship between rust's type system and c's; hence unsafe is completely uninteresting, because it is a tool for subverting rust's type system.

(It occurs to me now that I might have gotten a less generally defensive response had I made the original comparison between rust and a hypothetical rust without unsafe. Oh well)

> However the topic at hand is the relationship between rust's type system and c's; hence unsafe is completely uninteresting,

Gotcha, I was just trying to clarify the semantics of unsafe, lots of people think it suddenly lets you do whatever you want, and while it will let you, that doesn't mean that you can, which is an important distinction. You're right that this puts it in the same general category of C in a theoretical perspective, I think practice will bear out that it's not a binary proposition, but time will tell :)

If manually managing memory is like wielding a gun, the borrow checker is an automatic safety that prevents you from pulling the trigger when you're roughly pointing it at yourself. But it's coarse-grained and errs on the side of caution; it simulates your foot as as the rectangular box that would contain it, not as a detailed 3D mesh. If you really think you can aim it between your toes and avoid hitting yourself (for example, "the value returned by this function must remain alive for no more than 15 successive invocations of this function"), unsafe will let you try, but the borrow checker's built-in rules isn't granular enough to help you, though it will still stop you if you accidentally put your hand in front without declaring it.

C is like a laser gun in a room full of oddly-shaped mirrors with no safety at all. Good luck.

> it's coarse-grained and errs on the side of caution

That's what type systems in general do. There is no type system for a turing-complete language that is both sound and complete. (Trivial proof: if (undecidable) halt; unsound.)

> That's exactly right, and was my thesis; rust's type system does not allow you to prove the correctness of such a function, because it is neither correct nor incorrect without context. 'Unsafe', as a subversion of the type system which allows unsound behavior, is completely uninteresting wrt the topic at hand;

For the record, the “topic at hand” was the memory model not the type-system, nor the theorem proving capabilities of the borrow checker.

Your arguments are not wrong per se, but they are completely missing the topic.

Upon further reflection, I don't think 'local/global correctness' distinction this was expressed very well or very usefully. The 'hole' example papers over so many details as to be misleading.

So here's another, hopefully better expression:

Rust's type system wrt lifetimes is not very expressive, compared with 'dynamically-typed' c. It can't represent things like 'the value returned by this function must remain alive for no more than 15 successive invocations of this function'.

A lot of useful C programs can be written without dynamic memory allocation or multithreading though, while Rust seems to assume a sort of "base complexity" even for very simple programs as soon as memory access is involved.

300 byte Blink for Arduino: https://github.com/vlisivka/rust-arduino-blink

Primitive pin tester for Arduino in 1kb: https://github.com/vlisivka/rapt

Not at all. (And that's actually the big reason why Rust is making its way to the Linux Kernel)

Rust doesn't assume an allocator. The Rust standard library (to have things like growable strings) requires an allocator but the language and its core do not.

And Rust doesn't assume threading either. The default stuff isn't even thread safe, it's just that in Rust when you introduce threading and still try to use stuff that isn't thread safe the compiler will tell you that can't work.

You can deliberately write stuff that won't do what you meant of course, but they're trying to make it harder to do that by accident. I have a set of Rust types which defy logical behaviour (for example type whose members always compare as equal yet hash differently) and as intended if you use those in otherwise safe code your program might not work but it doesn't cause random craziness. For example maybe your attempt to binary search an ordered list of my data types that claim they form a total order and yet always reply "I'm smaller" when asked how they compare to anything, even themselves - will become an infinite loop, but it won't suddenly execute environment variables as code or anything like that whereas in C all bets are off.

> And Rust doesn't assume threading either. The default stuff isn't even thread safe

Right, and Rust doesn't even know what a thread is actually. It's all implemented in the standard library. The only thing Rust know, is that there exist some special Traits (Send and Sync) which are automatically implemented if a struct field implements it itself. And that's it.

> The static analysis of the borrow checker is not able to figure out when you're headed for trouble via this route.

This route exists purely because you can't statically prove some programs correct. Without it, the compiler would have to reject some correct programs and the language would be more limited.

This is unfair to complain about it when the GC-based alternatives push all of memory management to runtime, so the surface for getting panics is a lot larger. Rust's solution is not perfect but still the best you can get.

> Designing the data structures for something tightly coupled with concurrency, like a window manager or a game, is difficult.

It is difficult in any language. The difference is that in Rust you face that difficulty when trying to design/compile your program, and in other more permissive languages you face it when your customer reports a bug. The cost of fixing problems is lowest when they are detected early, so Rust has a clear edge here.

I'm not sure someone (including OP) would be "complaining" about it, considering that "this enforces borrow checker rules at runtime" is like the first or second thing in the documentation for RefCell and friends.

The frustrating bit about it is not that you get panics or deadlocks at runtime, that is to be expected when you can't get them at compile time, after all. The nasty bit is that this memory model makes it very difficult to work with tightly-coupled, concurrent state, and you have to go through all the RefCell<Rc<Whatever>> escape hatches, at which point you're not that far from C++ hell (edit: i.e. you "pay extra", in the form of the awkward escape hatches, to get not that far from where you were before).

In theory (or, if we're being realistic, in introductory tutorials) it's possible to avoid the escape hatches if you are careful to structure access to your data juuuuust right. That works out fine if you're the only person working on an infrequently-changing program with a small model that you understand very well. If everyone needs to hook into the first two or three function call levels of the main loop, and if your model is anything but small, that doesn't work out anymore. Six weeks into the whole thing and people spend more time un-breaking builds than writing code.

Also, seriously, not every comment that says "I wish Rust did X better" is a wanton attack upon the technological excellence and purity of the one perfect language to rule them all...

I have written a few parallel, non-trivial Rust programs (actually one of them, fclones seems to be one of the best in class performance-wise, despite many competitors), yet I've never had to use Refcell and runtime-checked borrowing.

Yes there were a few Arc here and there, but 99% of time the simpliest move / clone / compile-time-borrow are enough. Definitely very far from the place I'd be if I coded that in C++.

Oh, I knew I'd recognized your username from somewhere :-D. fclones is actually my favourite dupe finding tool!

In my experience the underlying model is what determines these things. That's not always under one's control. Sometimes you can't meaningfully trace ownership, or the development model (short iterations by a large team) make it hard to keep it in sync. I know of non-trivial programs that rarely (if ever) use runtime-checked borrowing but runtime-checked borrowing is, nonetheless, a thing. Some developers need it.

Oh yeah, definitely. It is good to have these all escape hatches at hand. But it is not good to default to them - I guess you could program Rust like Java by throwing everything into Arc<RefCell<..>>, but that's not they way to go IMHO.

In your experience, what would be a better approach to dealing with “tightly-coupled concurrent state”? I mean, one that a “sufficiently smart compiler” can verify, not just hoping it works at runtime (as in C)?

One obvious approach is to de-parallelise the state (i.e. actor model) but that’s almost cheating (“we solved the problem by removing the problem”) and probably not appropriate for some applications that truly require concurrent state.

Also, are you aware of any codebase that I could take a look at, that is an example of concurrent state?

I'm gonna go with the unpopular opinion here: the "better approach", as in, the one that allows you to have arbitrary state coupling and take the human factor of the equation, is garbage collection.

Rust's trade-off (you get compile-time guarantees in exchange for requiring you to structure data accesses in a particular way) is perfectly valid, but it's still a trade-off. As with any trade-off, you run into the part that's traded for something else sooner or later :-).

Non-deterministic garbage collection applies to a tiny fraction of the state problem though - the memory part. It does not apply to other types of resources: file descriptors, sockets, database sessions, connections, threads, etc. - generally anything that needs proper disposal and is not (only) memory.

It is also worth noting you can perfectly have garbage collection in Rust - reference counted pointers or epoch GC. Refcounted pointers have the advantage of being deterministic.

The ownership is part of the type-checker and disappears at runtime. At runtime (and in memory) you are left with C's memory model (pointers but also can nest records) and with the other things you mention.

I don't immediately see why something like a window manager might need a data structure which requires multiple concurrent writers. Or, while at it, why can't events coming to each window be perfectly serialized and not require any concurrent mutation. Could you share an example?

Serialization does not eliminate concurrency, it is a strategy for dealing with it. That is, when your abstract model requires concurrent writes, you can instead add the operations to an event queue and process them serially. The event queue itself is still concurrently written to. You also still face complex problems with dependent writes - e.g. when two writers want to increment the same place (even worse when they need to apply a more complex function than incrementing, and worse of all when they want to apply a non-pure function to the current value).

I agree, but I still can't see where a WM might need to concurrently write to a per-window event queue. Also, I can't see why pushing onto a queue can't be blocking (with a timeout) and use a mutex, if multiple threads need to write to it.

With game engines, all bets are off, of course.

GPGPU programming with multiple rendering threads for example.

This is all very informative - is there a single page that documents all this?

Reply on news.ycombinator.com