For these cases you could always use Zig instead of C
Already setting the proper defaults on a Makefile would get many people half way there, without changing to language yet to be 1.0, and no use-after-free story.
And thats why Zig don’t offer much. Devs will just ignore it.
I know, a linked list is not exactly super complex and rust makes that a bit tough. But the realisation one must have is this: building a linked list will break some key assumptions about memory safety, so trying to force that into rust is just not gonna make it.
Problem is I guess that for several of us, we have forgotten about memory safety and it's a bit painful to have that remembered to us by a compiler :-)
This makes me wonder: what performance cost Rust code pay due to inability represent cyclic structures efficiently? It seems people tend to design their data in way to please Rust and not in way that would be otherwise more performance efficient.
> what performance cost Rust code pay due to inability represent cyclic structures efficiently?
You can still write the code you'd write in C with unsafe. There's no inherent loss left on the table.
Furthermore, a lot of C folks reach for intrusive lists because it's easy in C, but that doesn't mean that it's always the most performant. See https://bcantrill.dtrace.org/2018/09/28/the-relative-perform... as an example of this phenomenon.
Lots of things C chose to use intrusive pointers and custom data structures for, you would program very differently in a different language.
I'm an old C neckbeard and I find Rust a great experience. Some of the arguments against it sound like people are complaining about how hard it is to run pushing a bicycle.
https://doc.rust-lang.org/src/alloc/collections/linked_list....
It also trusts your neighbor, your kid, your LLM, you, your dog, another linked list...
If you’re having trouble designing a safe interface for your collection then that should be a signal that maybe what you are doing will result in UB when looked at the wrong way.
That is how all standard library collections in Rust works. They’ve just gone to the length of formally verifying parts of the code to ensure performance and safety.
Rust is great, but there are some things that are safe (and you could prove them safe in the abstract), but that you can't easily express in Rust's type system.
More specifically, there are some some things and usage pattern of these things that are safe when taken together. But the library can't force the safe usage pattern on the client, with the tools that Rust provides.
Take a look at the unsafe functions for the standard library Vec type to see examples of this:
https://doc.rust-lang.org/std/vec/struct.Vec.html#method.fro...
Yes, that's what you do in practice. But it's no different--in principle--from the approach C programmers have to use.
Yeah and that's what not going to work for high performance data structures because you need to embed hooks into the objects - not just put objects into a bigger collection object. Once you think in terms of a collection that contains things you have already lost that specific battle.
Another thing that doesn't work very well in Rust (from my understanding, I tried it very briefly) is using multiple memory allocators which is also needed in high performance code. Zig takes care to make it easy and explicit.
Like a linked list that forces you to add a next pointer to the record you want to store in it.
And generally I'd imagine it's quite a weird form for data structures for which being in a linked list isn't a core aspect (no clue what specifically the kernel uses, but I could imagine situations where where objects aren't in any linked list for 99% of time, but must be able to be chained in even if there are 0 bytes of free RAM ("Error: cannot free memory because memory is full" is probably not a thing you'd ever want to see)).
That is why kernel mostly (always?) uses intrusive linked lists. They have no such problem.
That's a great point! A language almost like C plus a smart enough compiler could do the unboxing, but this technique doesn't work for multiple structures.
> And generally I'd imagine it's quite a weird form for data structures for which being in a linked list isn't a core aspect (no clue what specifically the kernel uses, but I could imagine situations where where objects aren't in any linked list for 99% of time, but must be able to be chained in even if there are 0 bytes of free RAM ("Error: cannot free memory because memory is full" is probably not a thing you'd ever want to see)).
I think you are right in practice, though in principle you could pre-allocate the necessary memory when you create the items? When you have the intrusive links, you pay for their allocation already anyway, too. In terms of total storage space, you wouldn't pay for more.
(And you don't have to formally alloc them via a call to kmalloc or so. In the sense that you don't need to find a space for them: you just need to make sure that the system keeps a big enough buffer of contiguous-enough space somewhere. Similar to how many filesystems allow you to reserve space for root, but that doesn't mean any particular block is reserved for root up-front.)
But as I thought, that's about in-principle memory usage. A language like C makes the alternative of intrusive data structures much simpler.
Said file system reserving can fill up (I've experienced that :) ). Could perhaps engineer some super-equation for a global reserved memory size that can actually guarantee being sufficient; but, unless you mark allocations as needing reserved space vs not and compute based on that (which is back to overhead), that'll necessarily waste a good amount of memory.
And such a global equation of course can result in global failure if just one subsystem miscalculates its required reserved amount, or the calculations improperly account for worst-case non-contiguousness or interleaved different-size-linked-list-alloc-requests or whatever. (never mind that you now need to alloc when adding elements to linked lists, an action that would otherwise be 1-4 inlined stores)
Probably (?) possible to handle, but way way way more easy to break or get wrong (with very-difficult-to-debug consequences) than just some pointer fields.
Oh and also of course, if you store list data in a separate allocation from the main object, you lose the ability to do O(1) (and extremely-cheap at that) "remove self from linked list just given my own pointer", which is probably quite common (and you can't even O(1) with an arraylist instead of a linkedlist).
Is there known compilers that can do that?
The above is about the optimiser figuring out whether to box or unbox by itself.
If you are willing to give the compiler a hand: Rust can do it just fine and it's the default when you define data structures. If you need boxing, you need to explicitly ask for it, eg via https://doc.rust-lang.org/std/boxed/struct.Box.html
Same story for games where it can be in the list of all objects and in the list of objects that might be attacked. Once it's killed you can remove it from all lists without searching for it in every single one.