[smj-edison]

This is perhaps a different take, but one reason I love Zig and C is because I've learned how to reason in pointers. I've worked with Rust in the past on a ~12,000 LOC side project, so I was all in with tree ownership and XOR mutability. But it turns out there's all sorts of delightful data structures that you can only express with unsafe in Rust. Intrusive doubly linked lists are the coolest thing ever. The fact that I can have a LRU cache that changes what's at the front by shuffling some pointers, while still keeping stable addresses so the hash map stays stable? That's freaking cool. Atomic operations with pointers for linked lists is really slick for implementing an allocator's free list between threads. Being able to walk a live heap using a breadth first search by just... following pointers, made the elegance of Dijkstra's algorithm come alive.

Now, maybe I'm only running into these algorithms because these are the problems I'm running into, but in the Rust community I consistently got the message that linked lists were a legacy data structure. In some cases they are, but when they do apply they do so brilliantly.

I know working in Zig leaves plenty of room for memory unsafety. Perhaps that's a bad thing. But I'm implementing an interpreter, and these algorithms are essential for it to run fast. I really do need to be aware of where every allocation happens, and what instructions the computer is running. So for now I stick with Zig, even though I know I'm opening myself up to memory exploits.

[tialaramex]

Given you like pointers so much a dislike for Rust would make sense if Rust didn't have pointers, but it does and IMO as somebody who spent years getting paid to write in C, Rust's pointers are better.

I don't know if Zig has made any clear decisions about this (chime in any Zig experts) but in C [and C++] the pointers are crap because they're "zapped" when the thing pointed to is gone. Now of course in reality your compiler won't overwrite your pointer just because the standard says it could, but because the compiler knows it would be allowed to do that, it can optimise pointer tricks in surprising ways. To work around this, C and C++ provide pointer-sized integers and exhort you to do any tricks with those instead because there's no zap.

In Rust that's unnecessary, the pointers are just pointers, if the thing pointed at is invalidated, you mustn't dereference that pointer because it's not pointing at anything now, but you can still for example XOR it against another pointer. Clever pointer tricks are thus your responsibility as programmer, and you can just do them with pointers rather than needing this pointer-sized-integer workaround.

[smj-edison]

Not familiar with the idea of "zapped", and I thought that Rust had a similar provenance model?

Working with pointers in Zig is much nicer, since

1. They're not nullable. If you want a nullable pointer, you would use `?*Object` instead of `*Object`.

2. They distinguish between single item and multi-item pointers. `*u8` is a pointer to a single u8, so I couldn't add to it or index it. `[*]u8` is a multi-item u8, which you can index.

3. Pointers track their alignment. I could make a pointer with `*align(128) Object` if I wanted to tag the bottom bits for example. Zig will require casts when changing alignment, for example casting from `*Object`.

4. Everyone uses slices when possible, pretty much Rust's slices.

5. A smaller detail, but there are sentinel pointers/slices, where you guarantee that the last item is a certain things. For example, a C string would be `[*:0]u8`, because it ends with 0.

[tialaramex]

Today the C and C++ standards do not have a provenance model. The model Rust chose is certainly related to the PNVI-ae-udi model proposed for C, in particular "Provenance Not Via Integers" is a core choice in both schemes. Martin Uecker (who has commented elsewhere in this thread) would I think say they're more similar than I would and he is an expert in this area as he co-authored the C proposal.

Zap isn't much related to provenance, it's more of a difference in philosophy about what pointers are for. With zap they're a very bare bones reference type, they always refer to things which exist and that's all, it's important that they never point anywhere without in fact referencing a thing. Without zap most of the behaviour you associate with hardware addresses works, you can do arithmetic on them, including atomic compare operations, you can use them as parameters to MMIO features and so on. Since C doesn't have any other reference types their role in C makes sense, in Rust and C++ of course actual reference types also exist.

[safercplusplus]

Well, there is another safe option for flexible pointers if you can compile as C++ [1]. In C++ you can have non-owning "smart" pointers with run-time-checked lifetimes [2][3]. Importantly, there is no run-time overhead to dereference them. (That is for the "never-null" versions, otherwise there's a null check.) Assignment has additional run-time cost, but pointer assignments are generally much less prevalent in performance-sensitive inner loops than dereferences, right?

And you can statically verify [4] your raw pointers, so that you only need to use the run-time-checked pointers for the more exotic lifetime relationships.

(That said, for the situations where Fil-C acceptably solves your problem, it's probably the more practical, complete and well-supported solution. And since not many seem to be explicitly mentioning it, the recent Fil-C demonstration of memory-safe linux userspace is rather impressive, right? I've heard that IT security is a $100B industry. I'm guessing an inappropriately low proportion of those resources are being invested in Fil-C. :)

[1] https://github.com/duneroadrunner/SaferCPlusPlus-AutoTransla...

[2] https://github.com/duneroadrunner/SaferCPlusPlus#norad-point...

[3] https://github.com/duneroadrunner/SaferCPlusPlus#tnoradproxy...

[4] https://github.com/duneroadrunner/scpptool

[smj-edison]

Interesting, this is pretty cool! I'm guessing it doesn't work with pointer to int casts though? I'm using NaN packing, so I necessarily have to cast it to an integer.

EDIT: though I'm considering switching to a tag + 64 bit union, because of 54 bit addressing and pointer tagging. It makes it tricky to get my data layout right though, since it makes all of the structures larger.

[nitros]

> But it turns out there's all sorts of delightful data structures that you can only express with unsafe in Rust. Intrusive doubly linked lists are the coolest thing ever.

I don't mean this to be a gotcha, but I think it's important to say that we can have these in rust too! The only difference is that the first thing we have to talk about is you the user can go about using an intrusive collection correctly. I love the cordyceps crate for this. If you want to be able to use your type as a linked list node, you must implement a Linked trait, the documentation of which clearly explains how to use it safely: https://docs.rs/cordyceps/latest/cordyceps/trait.Linked.html

[smj-edison]

I think this crate description encapsulates what's difficult about unsafe rust, which is how unergonomic pointers are. Like why do I need to use `addr_of_mut!`? I'm sure there's a good reason, as Rust tends to think these problems through, but it's very unintuitive compared to returning `&mut`. I feel like I'm juggling way more concepts, which to be fair helps with safety, but it can obscure the algorithm itself.

Does cordyceps have a derive macro? I can imagine that helps a lot with correct implemention, though when it comes to linked lists I can see people wanting to do it themselves.

[aw1621107]

> Like why do I need to use `addr_of_mut!`?

As of Rust 1.82.0 [0] you no longer need to!

> I'm sure there's a good reason, as Rust tends to think these problems through, but it's very unintuitive compared to returning `&mut`.

The addr_of_mut docs [1] give a pretty decent explanation of its reason for existence; in short, it lets you get a pointer to something without needing to create potentially-invalid intermediate references. It (and &raw) probably aren't going to be needed if all you need is a &mut, though.

> Does cordyceps have a derive macro?

Doesn't appear to from a quick glance, and given what's in the safety section of the docs [2] it'd probably need to be marked unsafe [3]. Unsafe attributes are new to Rust 2024, though, so that might be a bit new.

[0]: https://blog.rust-lang.org/2024/10/17/Rust-1.82.0/#native-sy...

[1]: https://doc.rust-lang.org/std/ptr/macro.addr_of_mut.html

[2]: https://docs.rs/cordyceps/latest/cordyceps/trait.Linked.html...

[3]: https://doc.rust-lang.org/edition-guide/rust-2024/unsafe-att...

[afdbcreid]

> > Like why do I need to use `addr_of_mut!`?

> As of Rust 1.82.0 [0] you no longer need to!

That's true but misleading. I'm pretty sure the question was why a normal reference is bad. You don't need `addr_of_mut!()`, but you do need `&raw mut`.

[aw1621107]

> I'm pretty sure the question was why a normal reference is bad.

Oh, completely missed that interpretation. I think in that case it comes down to references being incompatible with the desired semantics for an intrusive list - & doesn't work if you want to modify what you're pointing to, and &mut doesn't work since you may want multiple things to be able to point to and modify whatever you're pointing to.

[pwdisswordfishq]

So how do I take a shared reference to a variable named "raw"?

Complicating the grammar for no good reason. This should have stayed a macro.

[smj-edison]

Rust allows you to use a literal iirc like r#raw, which helps with migration. This isn't too different from Zig's @"var" for example, which I'm glad modern languages have an escape hatch for naming things that don't parse normally.

[ssokolow]

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

[afdbcreid]

`raw` is a contextual keyword.

[smj-edison]

Interesting. I stopped working with Rust about two years ago, so it looks like there's been a lot more polish in these areas.

[NobodyNada]

> what's difficult about unsafe rust, which is how unergonomic pointers are. Like why do I need to use `addr_of_mut!`?

Things are slowly getting better here! '&raw'/'&raw mut' reference operators were stabilized a couple years ago.

Another ergonomic improvement in the pipeline is a better way to access fields behind pointers, something like C's -> operator. This is taking some time to design because there are things other than raw pointers that would benefit from a generalized field projection mechanism, like Pin, NonNull, and (potentially user-defined) smart pointer types.

[kibwen]

> Like why do I need to use `addr_of_mut!`? I'm sure there's a good reason, as Rust tends to think these problems through, but it's very unintuitive compared to returning `&mut`.

That documentation appears to be out of date. The `addr_of_mut` macro was elevated to a first-class language feature, `&raw mut` (there's also a corresponding `&raw` operator). These two operators differ from the usual `&mut` and `&` in that they create raw pointers rather than references; prior to the introduction of this feature (or the aforementioned macros that served as precursors) to create a raw pointer you might need to have done a cast like `&foo as *const` in order to create a raw pointer by casting from a reference, but this could have safety consequences if the temporary reference was to an invalid object. Therefore `&raw` and `&raw mut` were introduced to create raw pointers directly without introducing an intermediate reference, which was arguably the most subtle footgun in unsafe Rust for a few years, and it's nice that it's now addressed.

[afdbcreid]

I absolutely agree learning C is a good thing! In fact, there are two camps of Rust people: one that argue that you should not learn C before learning Rust, and one that argues that you should.

Also, while such data structures/algorithms are rare, and more importantly, they can be written once and used many times, someone still needs to write them!

Here is some online content on this side of Rust:

- Learn Rust the Dangerous Way - https://cliffle.com/p/dangerust/

- Learn Rust With Entirely Too Many Linked Lists - https://rust-unofficial.github.io/too-many-lists/

- The Rustonomicon - https://doc.rust-lang.org/nomicon/

[smj-edison]

Thank you! I've seen the latter two mentioned in the past, but I never got very far into the books before getting confused with all the moving pieces. I think now that I've worked a lot in languages that put structs and pointers in the forefront, I'd understand it a lot better. Perhaps I'll have to go back and give them a proper read this time...

[rcxdude]

Linked lists are cool but they are terrible for cache performance, so their apparently elegant performance characteristics are often illusory. And hybrid data structures which get you the best of both worlds are quite complicated to implement. I think that's why there's a general pressure against using them unless you have a very specific reason (and ideally some measurements) to demonstrate that they are a good option.

(part of this I think is some C teaching which tended to overemphasize linked lists because they are useful for teaching the concept of pointers, which gave a lot of people learning C the impression that it should be the default way to represent a list of objects, when it's far more the exception than the rule)

[tialaramex]

Yeah, I'd blame mainly 2 factors for the continued undue influence of linked lists

1. CS professors teach them. The Programme Lead for our CS course still teaches linked lists as the first data structure in the DSA course. Does this type exist? Sure. Is it a good idea? Almost never. But you wouldn't think so from its prominence in the course materials.

2. The Linux kernel uses a LOT of linked lists. Multi-core atomic operations on mutable data, a nightmare you will probably avoid in your software is necessary for the OS kernel and so it has linked lists. Linux is very famous, but your software is almost certainly not an operating system kernel.

[smj-edison]

> but your software is almost certainly not an operating system kernel.

In general yes, but right now I'm contributing to folk.computer, which is a multithreaded task scheduler/central DB (among other things not relevant to the topic at hand). The biggest use of atomics is during statement insertion and removal, by using RCU operations in the central trie.

One of our current performance drags is the interpreter we use is not threadsafe, so we have to serialize and deserialize objects as they move between threads. This contributes to about 30% of Folk's CPU usage. So I'm currently working on making a threadsafe interpreter by porting the Tcl interpreter we use (Jimtcl), and I'm learning all the fun things around atomic ordering and threaded data structures. So I'm definitely the audience for these data structures.

[inigyou]

A linked list is the simplest possible linked structure and should definitely continue to be taught, but you could add another lesson and exercise to compare its performance with dynamic arrays.

[kevincox]

Traversing a linked list is terrible for performance. But in cases like the cache you are only poping from the front, appending to the back or removing which are all quite fast and require little pointer chashing.

Cache cost of individual allocations can be an issue but that can also be mitigated with a good allocator and even without special care can be quite performant in many applications.

I agree the linked lists shouldn't be the first structure you reach to. But there are situations where they can perform very well.

[pjmlp]

Even Lisp got all major data structures relativity early on, building only on lists is mostly used for prototyping.

[jagged-chisel]

> The fact that I can have a LRU cache that changes what's at the front by shuffling some pointers, while still keeping stable addresses so the hash map stays stable? That's freaking cool. Atomic operations with pointers for linked lists is really slick for implementing an allocator's free list between threads. Being able to walk a live heap using a breadth first search by just... following pointers, made the elegance of Dijkstra's algorithm come alive.

I feel like these kinds of things should be transformations that the compiler can use to turn Provably Safe code into performant code, i.e. you write the safe code and, once the borrow checker is happy, the compiler does its magic. I have no idea how to codify any of it into a compiler pass, or whether it's actually possible...

[smj-edison]

There's some interesting work going on with this with Metamath Zero[0], where he's working on verifying everything down to the compiler, to make sure the compiler always emits correct code. His language, Metamath C, also allows for refinement types, which means you can prove certain properties. It's still in its infancy, but I've been watching it from the sidelines for a bit now.

Though in terms of practicality, Graydon Hoare has mentioned in the past that he isn't a big fan of complex systems, and so it's better to have a simple type system that covers 95% of the cases, and an escape hatch when it doesn't. I think that's still a fair assessment, but I've fallen down the proof rabbit hole so I am curious to see how far it could be pushed.

[0] https://github.com/digama0/mm0

[inigyou]

Sadly due to cache friendliness, current conventional wisdom is that linked lists are so slow that a dynamic array of pointers is almost always faster even in cases when you'd think linked lists would be faster, such as frequent insertions in the middle.

[conradludgate]

Given your performance concerns, I'm imagining you're unlikely to run Zig-Fil in practice, due to the GC overhead?

[smj-edison]

Yeah, probably not. I wouldn't mind fuzzing it with Zig-Fil, but the interpreter (Zicl) is embedded in a larger C project that uses a lot of dynamic linking, so chances of using it in production is pretty much zero. I do have a lot of asserts that only have a small overhead, so I'll probably use ReleaseSafe most of the time, since it does catch a lot of the issues.

[qsera]

You are right on the money! I have been saying this for a while.

Apart from the utility, it is also a lot of fun. So it would be a pity if people are told that these things are legacy and they should not try to use/implement them..

[benj111]

See now this is why I don't quite get everyone jumping on the rust bandwagon.

This is a limitation of the rust model. You could have a language where intrusive linked lists are provably safe.

That's not to say rust doesn't work, but it's the first language I'm aware of that's attempted compile time memory safety, and no body seems to be talking about how to do it better.