Comment by oconnor663 | Hacker News Reader

Comment by oconnor663 | Hacker News Reader

Parent Full thread

I only played with Zig for a weekend, so others will need to chime in, but a few points:

- Zig's comptime is extremely flexible, while Rust's generics are more constrained. It's not clear if Rust will ever get "specialization" for example, but Zig gets that sort of thing for free by making the whole language available at comptime.

- Zig is very explicit about memory allocation, and the standard library doesn't include types like Rust's Vec or String that implicitly talk to a global allocator. If you're writing an application that must not allocate in the render loop / control cycle / etc, that can be a feature.

- Zig doesn't have a borrow checker. If your application plans to use memory management strategies like "a bump allocator that frees everything at the end of a frame" or "a bump allocator that frees everything at the end of a query", it can be painful to express the lifetime restrictions of those allocations in Rust. Zig doesn't get in the way of those strategies, though that also means there's no such thing as "safe code" in the Rust sense.

> Zig doesn't have a borrow checker. If your application plans to use memory management strategies like "a bump allocator that frees everything at the end of a frame" or "a bump allocator that frees everything at the end of a query", it can be painful to express the lifetime restrictions of those allocations in Rust. Zig doesn't get in the way of those strategies, though that also means there's no such thing as "safe code" in the Rust sense.

I don't use Rust often, so I'm admittedly not that knowledgeable on what's already possible, but does seem like something that could benefit Rust is if there were a way to express in some limited context that something like a doubly-linked list is safe because all its nodes are associated with / owned by the same allocator, and their lifetimes all end when the allocator dies. The rule could be that, within the context of an arena allocator, these arena pointers could point to any memory also allocated by the same arena allocator (including mutable aliasing pointers), but the things they point to could never be moved (or else other arena pointers might dangle) and they wouldn't ever be freed until the "allocator context" ends (or else you might get use-after-free mistakes), and it would have to be within the context of one thread (or else there might be data races). The idea being that all the memory in the arena is allocated at once. Then you could do things like e.g. join two doubly-linked lists that were allocated by the same arena allocator. Then multiple doubly-linked lists could be expressed in safe Rust, as long as they were backed by one arena allocator that deallocates all at once.

Arena allocators can be used with lifetimes in the way you describe, but that's just not people's usual definition of linked list, as it misses out on some key properties people use linked lists for.

How can you? (genuine question)

I found this project: https://git.sr.ht/~vlmutolo/chainlink

But they use generational indices into a vector. You can't append two doubly-linked lists because they have their own vectors. I was thinking of two separate doubly-linked lists using real pointers (not indices into a vector), but since they were allocated by the same arena allocator, they can be appended.

Is that already possible (in safe Rust)? If so, I guess I should have done more research, sorry :)

Edit: Oh, do you mean the normal one from the standard library? https://doc.rust-lang.org/std/collections/struct.LinkedList....

My bad. I was thinking of something similar, just not implemented with raw pointers underneath, but it already takes an allocator argument in the type, so there would be no benefit to this. Kind of embarrassed now.

I wasn't thinking "use std::collections::LinkedList with an allocator parameter," just that like:

1. The reason linked lists in Rust are difficult is due to lifetimes.

2. Arenas in Rust are parameterized by a lifetime, and that does the stuff you want here, that is, make sure that they can't go away until the arena does.

3. This means this should Just Work.

I haven't written the code because I don't think it would be that useful. I already wrote one terrible linked list based on generational indices that's not useful for anything, so doing it again doesn't sound that fun, haha. Looking at chainlink, it's roughly the same design, except with a Vec instead of the arena, which isn't much of a difference.

> Kind of embarrassed now.

No need to be embarrassed by asking good-faith questions.

You can put nodes in a Slab or a SlotMap, use keys/indexes for your next pointers, and create multiple interacting (possibly overlapping) lists that way. You have to be careful not to combine nodes from different collections, but that's also sort of true with memory allocators.

Reply on news.ycombinator.com