WUFFS [LWN.net]

WUFFS

Posted Aug 16, 2024 10:42 UTC (Fri) by paulj (subscriber, #341)
In reply to: WUFFS by khim
Parent article: Standards for use of unsafe Rust in the kernel

Isn't it the case that more Rust programmes that have to work with more complex data-models and/or deal with long-lived state end-up relying heavily on RC/ARC?

Is runtime reference counted GC better than tracing GC? (I prefer ref counting myself, but I don't think I could claim RC is always better than tracing GC).

to post comments

WUFFS

Posted Aug 16, 2024 12:42 UTC (Fri) by khim (subscriber, #9252) [Link]

> Is runtime reference counted GC better than tracing GC?

You would need to define what do you mean when you are saying “better” if you want to have a meaningful answer to that quesion. So far I know one example of task where tracing GC looks like a better fit: theorem provers. First of all you, usually, have no idea, in advance, if said theorem can even be proven or not (and that means that “spurious rejectings” can be tolerated which immediately makes situation slightly unusual) and you genuinely don't know which data is still useful and which one is garbage.

But over years I only saw that one example where tracing GC is clearly the superior solution. Most of the time tracing GC is not just useless, but it's actively harmful if you goal is the Hoare property.

> Isn't it the case that more Rust programmes that have to work with more complex data-models and/or deal with long-lived state end-up relying heavily on RC/ARC?

Yes, but there's an interesting Rust-specific side to that story: Rust doesn't have fully automatic reference counting! Or, rather, Rust does half of it (it automatically decrements counter when object is no longer needed and deallocates it when counter reaches zero), but it doesn't do automatic increment for you. This works very nicely because Rust passes objects around by moving then, not by copying them, which means that you usually need to do an explicit counter increment (by explicitly calling clone and obtaining copy of you refcounter-pointer) only in places where you need shared ownership.

This, again, leaves breadcrumbs in your code that help you to understand where do you split ownership and, again, helps to achieve the Hoare property.

WUFFS

Posted Aug 16, 2024 12:54 UTC (Fri) by excors (subscriber, #95769) [Link] (4 responses)

> Is runtime reference counted GC better than tracing GC?

Depends what you mean by "better". I think the main differences are that tracing GC typically has better long-term-average performance and can handle cyclic data structures, while refcounting has more predictable performance and can have useful destructors.

The average performance is a bigger deal in languages like Python or Java where almost everything is heap-allocated and GCed, even objects that only ever have a single owner, so a lot of time would be spent needlessly updating refcounts (especially with multithreading where they need to be atomic updates). It should matter less in Rust where the programmer can choose to use Rc only for the relatively rare objects with non-trivial ownership, and the more expensive atomic Arc for the even rarer ones that are shared between threads (and Rust guarantees you'll never accidentally share a non-atomic Rc between threads). That does require some extra thought from the programmer, though.

It also takes some extra thought to avoid cyclic data structures (maybe using weak references etc), or to explicitly break cycles when destroying the container, to avoid memory leaks. (Python solves it by using reference counting plus a tracing GC to find cycles, but then you get most of the downsides of both.)

Tracing GC has much less predictable performance because it might pause all your threads, or at least eat up a lot of CPU time, whenever it arbitrarily feels like it. For batch processing, that doesn't matter. For moderately latency-sensitive tasks (like web services), you might end up spending significant effort tuning the GC heuristics to minimise pauses. For real-time, no.

It's pretty nice having destructors that are guaranteed to run immediately when the last reference to an object is dropped (which tracing GC can't do) - you can use RAII for objects that hold non-memory resources (like file handles) that the GC doesn't know about, without worrying that you'll suffer resource exhaustion while the GC thinks you've still got plenty of memory and there's no need to collect any garbage. Particularly useful for a systems programming language since you're often working with resources provided by the system, outside of the GC's scope.

The tradeoffs chosen by Rust wouldn't work for every language; but for a systems programming language aimed at relatively sophisticated programmers, I think it has made a good choice.

WUFFS

Posted Aug 16, 2024 13:07 UTC (Fri) by mb (subscriber, #50428) [Link] (3 responses)

>I think it has made a good choice.

Yeah, it's ok-ish most of the time.

Except for the case of move-capturing blocks. Passing an Arc clone to multiple async-move blocks is awkward.
It basically means cloning the Arc to a different name and then moving that name into the async block.
Which typically results in names such as foo2 or foo_cloned.
(Name shadowing is also possible in some cases.)

I think this is on the current list of things to be improved. But I'm not sure what an elegant solution would look like.

WUFFS

Posted Aug 16, 2024 19:12 UTC (Fri) by mathstuf (subscriber, #69389) [Link] (2 responses)

I think that Claim[1] looks ok. It makes a different cut to help understand "cheap to Clone" because `Rc::clone` is (almost certainly) cheaper than `[u8; 16536]` despite the latter being `Copy`.

[1] https://smallcultfollowing.com/babysteps/blog/2024/06/21/...

WUFFS

Posted Aug 16, 2024 20:49 UTC (Fri) by khim (subscriber, #9252) [Link] (1 responses)

I actually dislike that proposal. Because it's conceptually wrong. It asserts that the only difference between copy and clone is efficiency. But in reality difference is on another level: Copy types are just chunks of memory without internal structure and their copy is entirely independent from the original while clone means something else.

To me, on the congnitive level, clone of Rc<Vec<u32>> means that we want to split ownership of that [unmodifiable] vector… which maybe is kinda-sorta-Ok (because it's fixed and unmodifiable), but I would definitely not want to see Rc<RefCell<Vec<u32>>> automatically clones and, if understand correctly, this proposal would make it automatically clone'able, too.

The whole thing is solving entirely wrong problem: if the desire is to replace this:

tokio::spawn({
    let io = cx.io.clone():
    let disk = cx.disk.clone():
    let health_check = cx.health_check.clone():
    async move {
        do_something(io, disk, health_check)
    }
})

with this:

tokio::spawn(async move {
    do_something(cx.io, cx.disk, cx.health_check)
})

then it can be fixed with addition of just one keyword (it may even not be a keyword since it always comes after async):

tokio::spawn(async clone {
    do_something(cx.io, cx.disk, cx.health_check)
})

This would make it possible for a people like me to enable a clippy lint which rejects such code (I very much do want to see when I'm sharing ownership with some other task), although I can see why some people would want to add some magic to their programs.

Thankfully this proposal also comes with #![deny(automatic_claims)] which is good enough for me: while complexity of that whole madness is a bit larger than I would like with existence of #![deny(automatic_claims)] I don't care all that much about what other people are doing about Claim.

IOW: IMNSHO this proposal is a net negative, but very mild one, not enough to throw a temper tantrum if it would be accepted.

WUFFS

Posted Aug 16, 2024 21:28 UTC (Fri) by mathstuf (subscriber, #69389) [Link]

> then it can be fixed with addition of just one keyword (it may even not be a keyword since it always comes after async):
>
> tokio::spawn(async clone {
> do_something(cx.io, cx.disk, cx.health_check)
> })

Except I want it for plain closures too, not just `async` blocks.